changeset 00fd5dce5e7e in /z/repo/gem5
details: http://repo.gem5.org/gem5?cmd=changeset;node=00fd5dce5e7e
description:
cpu: implement an L-TAGE branch predictor
This patch implements an L-TAGE predictor, based on André Seznec's code
available from CBP-2
(http://hpca23.cse.tamu.edu/taco/camino/cbp2/cbp-src/realistic-seznec.h).
Signed-off-by Jason Lowe-Power <[email protected]>
diffstat:
src/cpu/pred/BranchPredictor.py | 16 +
src/cpu/pred/SConscript | 1 +
src/cpu/pred/ltage.cc | 746 ++++++++++++++++++++++++++++++++++++++++
src/cpu/pred/ltage.hh | 408 +++++++++++++++++++++
4 files changed, 1171 insertions(+), 0 deletions(-)
diffs (truncated from 1196 to 300 lines):
diff -r f94c14fd6561 -r 00fd5dce5e7e src/cpu/pred/BranchPredictor.py
--- a/src/cpu/pred/BranchPredictor.py Wed Dec 21 15:07:16 2016 -0600
+++ b/src/cpu/pred/BranchPredictor.py Wed Dec 21 15:25:13 2016 -0600
@@ -86,3 +86,19 @@
choicePredictorSize = Param.Unsigned(8192, "Size of choice predictor")
choiceCtrBits = Param.Unsigned(2, "Bits of choice counters")
+class LTAGE(BranchPredictor):
+ type = 'LTAGE'
+ cxx_class = 'LTAGE'
+ cxx_header = "cpu/pred/ltage.hh"
+
+ logSizeBiMP = Param.Unsigned(14, "Log size of Bimodal predictor in bits")
+ logSizeTagTables = Param.Unsigned(11, "Log size of tag table in LTAGE")
+ logSizeLoopPred = Param.Unsigned(8, "Log size of the loop predictor")
+ nHistoryTables = Param.Unsigned(12, "Number of history tables")
+ tagTableCounterBits = Param.Unsigned(3, "Number of tag table counter bits")
+ histBufferSize = Param.Unsigned(2097152,
+ "A large number to track all branch histories(2MEntries default)")
+ minHist = Param.Unsigned(4, "Minimum history size of LTAGE")
+ maxHist = Param.Unsigned(640, "Maximum history size of LTAGE")
+ minTagWidth = Param.Unsigned(7, "Minimum tag size in tag tables")
+
diff -r f94c14fd6561 -r 00fd5dce5e7e src/cpu/pred/SConscript
--- a/src/cpu/pred/SConscript Wed Dec 21 15:07:16 2016 -0600
+++ b/src/cpu/pred/SConscript Wed Dec 21 15:25:13 2016 -0600
@@ -43,6 +43,7 @@
Source('ras.cc')
Source('tournament.cc')
Source ('bi_mode.cc')
+Source('ltage.cc')
DebugFlag('FreeList')
DebugFlag('Branch')
DebugFlag('LTage')
diff -r f94c14fd6561 -r 00fd5dce5e7e src/cpu/pred/ltage.cc
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/cpu/pred/ltage.cc Wed Dec 21 15:25:13 2016 -0600
@@ -0,0 +1,746 @@
+/*
+ * Copyright (c) 2014 The University of Wisconsin
+ *
+ * Copyright (c) 2006 INRIA (Institut National de Recherche en
+ * Informatique et en Automatique / French National Research Institute
+ * for Computer Science and Applied Mathematics)
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Vignyan Reddy, Dibakar Gope and Arthur Perais,
+ * from André Seznec's code.
+ */
+
+/* @file
+ * Implementation of a L-TAGE branch predictor
+ */
+
+#include "cpu/pred/ltage.hh"
+
+#include "base/intmath.hh"
+#include "base/misc.hh"
+#include "base/random.hh"
+#include "base/trace.hh"
+#include "debug/Fetch.hh"
+#include "debug/LTage.hh"
+
+LTAGE::LTAGE(const LTAGEParams *params)
+ : BPredUnit(params),
+ logSizeBiMP(params->logSizeBiMP),
+ logSizeTagTables(params->logSizeTagTables),
+ logSizeLoopPred(params->logSizeLoopPred),
+ nHistoryTables(params->nHistoryTables),
+ tagTableCounterBits(params->tagTableCounterBits),
+ histBufferSize(params->histBufferSize),
+ minHist(params->minHist),
+ maxHist(params->maxHist),
+ minTagWidth(params->minTagWidth),
+ threadHistory(params->numThreads)
+{
+ assert(params->histBufferSize > params->maxHist * 2);
+ useAltPredForNewlyAllocated = 0;
+ logTick = 19;
+ tCounter = ULL(1) << (logTick - 1);
+
+ for (auto& history : threadHistory) {
+ history.pathHist = 0;
+ history.globalHistory = new uint8_t[histBufferSize];
+ history.gHist = history.globalHistory;
+ memset(history.gHist, 0, histBufferSize);
+ history.ptGhist = 0;
+ }
+
+ histLengths = new int [nHistoryTables+1];
+ histLengths[1] = minHist;
+ histLengths[nHistoryTables] = maxHist;
+
+ for (int i = 2; i <= nHistoryTables; i++) {
+ histLengths[i] = (int) (((double) minHist *
+ pow ((double) (maxHist) / (double) minHist,
+ (double) (i - 1) / (double) ((nHistoryTables- 1))))
+ + 0.5);
+ }
+
+ tagWidths[1] = minTagWidth;
+ tagWidths[2] = minTagWidth;
+ tagWidths[3] = minTagWidth + 1;
+ tagWidths[4] = minTagWidth + 1;
+ tagWidths[5] = minTagWidth + 2;
+ tagWidths[6] = minTagWidth + 3;
+ tagWidths[7] = minTagWidth + 4;
+ tagWidths[8] = minTagWidth + 5;
+ tagWidths[9] = minTagWidth + 5;
+ tagWidths[10] = minTagWidth + 6;
+ tagWidths[11] = minTagWidth + 7;
+ tagWidths[12] = minTagWidth + 8;
+
+ for (int i = 1; i <= 2; i++)
+ tagTableSizes[i] = logSizeTagTables - 1;
+ for (int i = 3; i <= 6; i++)
+ tagTableSizes[i] = logSizeTagTables;
+ for (int i = 7; i <= 10; i++)
+ tagTableSizes[i] = logSizeTagTables - 1;
+ for (int i = 11; i <= 12; i++)
+ tagTableSizes[i] = logSizeTagTables - 2;
+
+ for (auto& history : threadHistory) {
+ history.computeIndices = new FoldedHistory[nHistoryTables+1];
+ history.computeTags[0] = new FoldedHistory[nHistoryTables+1];
+ history.computeTags[1] = new FoldedHistory[nHistoryTables+1];
+
+ for (int i = 1; i <= nHistoryTables; i++) {
+ history.computeIndices[i].init(histLengths[i], (tagTableSizes[i]));
+ history.computeTags[0][i].init(
+ history.computeIndices[i].origLength, tagWidths[i]);
+ history.computeTags[1][i].init(
+ history.computeIndices[i].origLength, tagWidths[i] - 1);
+ DPRINTF(LTage, "HistLength:%d, TTSize:%d, TTTWidth:%d\n",
+ histLengths[i], tagTableSizes[i], tagWidths[i]);
+ }
+ }
+
+ btable = new BimodalEntry[ULL(1) << logSizeBiMP];
+ ltable = new LoopEntry[ULL(1) << logSizeLoopPred];
+ gtable = new TageEntry*[nHistoryTables + 1];
+ for (int i = 1; i <= nHistoryTables; i++) {
+ gtable[i] = new TageEntry[1<<(tagTableSizes[i])];
+ }
+
+ tableIndices = new int [nHistoryTables+1];
+ tableTags = new int [nHistoryTables+1];
+
+ loopUseCounter = 0;
+}
+
+int
+LTAGE::bindex(Addr pc_in) const
+{
+ return ((pc_in) & ((ULL(1) << (logSizeBiMP)) - 1));
+}
+
+int
+LTAGE::lindex(Addr pc_in) const
+{
+ return (((pc_in) & ((ULL(1) << (logSizeLoopPred - 2)) - 1)) << 2);
+}
+
+int
+LTAGE::F(int A, int size, int bank) const
+{
+ int A1, A2;
+
+ A = A & ((ULL(1) << size) - 1);
+ A1 = (A & ((ULL(1) << tagTableSizes[bank]) - 1));
+ A2 = (A >> tagTableSizes[bank]);
+ A2 = ((A2 << bank) & ((ULL(1) << tagTableSizes[bank]) - 1))
+ + (A2 >> (tagTableSizes[bank] - bank));
+ A = A1 ^ A2;
+ A = ((A << bank) & ((ULL(1) << tagTableSizes[bank]) - 1))
+ + (A >> (tagTableSizes[bank] - bank));
+ return (A);
+}
+
+
+// gindex computes a full hash of pc, ghist and pathHist
+int
+LTAGE::gindex(ThreadID tid, Addr pc, int bank) const
+{
+ int index;
+ int hlen = (histLengths[bank] > 16) ? 16 : histLengths[bank];
+ index =
+ (pc) ^ ((pc) >> ((int) abs(tagTableSizes[bank] - bank) + 1)) ^
+ threadHistory[tid].computeIndices[bank].comp ^
+ F(threadHistory[tid].pathHist, hlen, bank);
+
+ return (index & ((ULL(1) << (tagTableSizes[bank])) - 1));
+}
+
+
+// Tag computation
+uint16_t
+LTAGE::gtag(ThreadID tid, Addr pc, int bank) const
+{
+ int tag = (pc) ^ threadHistory[tid].computeTags[0][bank].comp
+ ^ (threadHistory[tid].computeTags[1][bank].comp << 1);
+
+ return (tag & ((ULL(1) << tagWidths[bank]) - 1));
+}
+
+
+// Up-down saturating counter
+void
+LTAGE::ctrUpdate(int8_t & ctr, bool taken, int nbits)
+{
+ assert(nbits <= sizeof(int8_t) << 3);
+ if (taken) {
+ if (ctr < ((1 << (nbits - 1)) - 1))
+ ctr++;
+ } else {
+ if (ctr > -(1 << (nbits - 1)))
+ ctr--;
+ }
+}
+
+// Bimodal prediction
+bool
+LTAGE::getBimodePred(Addr pc, BranchInfo* bi) const
+{
+ return (btable[bi->bimodalIndex].pred > 0);
+}
+
+
+// Update the bimodal predictor: a hysteresis bit is shared among 4 prediction
+// bits
+void
+LTAGE::baseUpdate(Addr pc, bool taken, BranchInfo* bi)
+{
+ int inter = (btable[bi->bimodalIndex].pred << 1)
+ + btable[bi->bimodalIndex ].hyst;
+ if (taken) {
+ if (inter < 3)
+ inter++;
+ } else if (inter > 0) {
+ inter--;
+ }
+ btable[bi->bimodalIndex].pred = inter >> 1;
+ btable[bi->bimodalIndex].hyst = (inter & 1);
+ DPRINTF(LTage, "Updating branch %lx, pred:%d, hyst:%d\n",
+ pc, btable[bi->bimodalIndex].pred,btable[bi->bimodalIndex].hyst);
+}
+
+
+//loop prediction: only used if high confidence
+bool
+LTAGE::getLoop(Addr pc, BranchInfo* bi) const
+{
+ bi->loopHit = -1;
+ bi->loopPredValid = false;
+ bi->loopIndex = lindex(pc);
+ bi->loopTag = ((pc) >> (logSizeLoopPred - 2));
+
+ for (int i = 0; i < 4; i++) {
+ if (ltable[bi->loopIndex + i].tag == bi->loopTag) {
+ bi->loopHit = i;
+ bi->loopPredValid = (ltable[bi->loopIndex + i].confidence >= 3);
+ bi->currentIter = ltable[bi->loopIndex + i].currentIterSpec;
+ if (ltable[bi->loopIndex + i].currentIterSpec + 1 ==
+ ltable[bi->loopIndex + i].numIter) {
+ return !(ltable[bi->loopIndex + i].dir);
+ }else {
+ return (ltable[bi->loopIndex + i].dir);
+ }
+ }
+ }
+ return false;
+}
+
+void
+LTAGE::specLoopUpdate(Addr pc, bool taken, BranchInfo* bi)
+{
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
