From d39573a9bebc15e5cc48366420ed065d2f8504e8 Mon Sep 17 00:00:00 2001 From: Javier Bueno Date: Wed, 30 Jan 2019 01:01:50 +0100 Subject: [PATCH] cpu: Added 8KB and 64KB TAGE-SC-L branch predictor The original paper of the branch predictor can be found here: http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf Change-Id: I684863752407685adaacedebb699205c3559c528 Reviewed-on: https://gem5-review.googlesource.com/c/14855 Reviewed-by: Sudhanshu Jha Reviewed-by: Andreas Sandberg Maintainer: Andreas Sandberg --- src/cpu/pred/BranchPredictor.py | 265 +++++++++++++- src/cpu/pred/SConscript | 5 + src/cpu/pred/loop_predictor.cc | 24 +- src/cpu/pred/loop_predictor.hh | 17 +- src/cpu/pred/ltage.cc | 16 +- src/cpu/pred/ltage.hh | 2 + src/cpu/pred/statistical_corrector.cc | 393 +++++++++++++++++++++ src/cpu/pred/statistical_corrector.hh | 265 ++++++++++++++ src/cpu/pred/tage.cc | 17 +- src/cpu/pred/tage.hh | 3 +- src/cpu/pred/tage_base.cc | 13 +- src/cpu/pred/tage_base.hh | 12 +- src/cpu/pred/tage_sc_l.cc | 479 ++++++++++++++++++++++++++ src/cpu/pred/tage_sc_l.hh | 188 ++++++++++ src/cpu/pred/tage_sc_l_64KB.cc | 322 +++++++++++++++++ src/cpu/pred/tage_sc_l_64KB.hh | 135 ++++++++ src/cpu/pred/tage_sc_l_8KB.cc | 325 +++++++++++++++++ src/cpu/pred/tage_sc_l_8KB.hh | 116 +++++++ 18 files changed, 2541 insertions(+), 56 deletions(-) create mode 100644 src/cpu/pred/statistical_corrector.cc create mode 100644 src/cpu/pred/statistical_corrector.hh create mode 100644 src/cpu/pred/tage_sc_l.cc create mode 100644 src/cpu/pred/tage_sc_l.hh create mode 100644 src/cpu/pred/tage_sc_l_64KB.cc create mode 100644 src/cpu/pred/tage_sc_l_64KB.hh create mode 100644 src/cpu/pred/tage_sc_l_8KB.cc create mode 100644 src/cpu/pred/tage_sc_l_8KB.hh diff --git a/src/cpu/pred/BranchPredictor.py b/src/cpu/pred/BranchPredictor.py index 1d5fd5eec..85b225c3b 100644 --- a/src/cpu/pred/BranchPredictor.py +++ b/src/cpu/pred/BranchPredictor.py @@ -118,7 +118,7 @@ class TAGEBase(SimObject): logUResetPeriod = Param.Unsigned(18, "Log period in number of branches to reset TAGE useful counters") numUseAltOnNa = Param.Unsigned(1, "Number of USE_ALT_ON_NA counters") - useAltOnNaBits = Param.Unsigned(4, "Size of the USE_ALT_ON_NA counter") + useAltOnNaBits = Param.Unsigned(4, "Size of the USE_ALT_ON_NA counter(s)") maxNumAlloc = Param.Unsigned(1, "Max number of TAGE entries allocted on mispredict") @@ -185,6 +185,96 @@ class LoopPredictor(SimObject): optionalAgeReset = Param.Bool(True, "Reset age bits optionally in some cases") +class TAGE_SC_L_TAGE(TAGEBase): + type = 'TAGE_SC_L_TAGE' + cxx_class = 'TAGE_SC_L_TAGE' + cxx_header = "cpu/pred/tage_sc_l.hh" + abstract = True + tagTableTagWidths = [0] + numUseAltOnNa = 16 + pathHistBits = 27 + maxNumAlloc = 2 + logUResetPeriod = 10 + useAltOnNaBits = 5 + # TODO No speculation implemented as of now + speculativeHistUpdate = False + + # This size does not set the final sizes of the tables (it is just used + # for some calculations) + # Instead, the number of TAGE entries comes from shortTagsTageEntries and + # longTagsTageEntries + logTagTableSize = Param.Unsigned("Log size of each tag table") + + shortTagsTageFactor = Param.Unsigned( + "Factor for calculating the total number of short tags TAGE entries") + + longTagsTageFactor = Param.Unsigned( + "Factor for calculating the total number of long tags TAGE entries") + + shortTagsSize = Param.Unsigned(8, "Size of the short tags") + + longTagsSize = Param.Unsigned("Size of the long tags") + + firstLongTagTable = Param.Unsigned("First table with long tags") + + truncatePathHist = Param.Bool(True, + "Truncate the path history to its configured size") + + +class TAGE_SC_L_TAGE_64KB(TAGE_SC_L_TAGE): + type = 'TAGE_SC_L_TAGE_64KB' + cxx_class = 'TAGE_SC_L_TAGE_64KB' + cxx_header = "cpu/pred/tage_sc_l_64KB.hh" + nHistoryTables = 36 + + minHist = 6 + maxHist = 3000 + + tagTableUBits = 1 + + logTagTableSizes = [13] + + # This is used to handle the 2-way associativity + # (all odd entries are set to one, and if the corresponding even entry + # is set to one, then there is a 2-way associativity for this pair) + # Entry 0 is for the bimodal and it is ignored + # Note: For this implementation, some odd entries are also set to 0 to save + # some bits + noSkip = [0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1,1, + 1,1,1,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1] + + logTagTableSize = 10 + shortTagsTageFactor = 10 + longTagsTageFactor = 20 + + longTagsSize = 12 + + firstLongTagTable = 13 + +class TAGE_SC_L_TAGE_8KB(TAGE_SC_L_TAGE): + type = 'TAGE_SC_L_TAGE_8KB' + cxx_class = 'TAGE_SC_L_TAGE_8KB' + cxx_header = "cpu/pred/tage_sc_l_8KB.hh" + + nHistoryTables = 30 + + minHist = 4 + maxHist = 1000 + + logTagTableSize = 7 + shortTagsTageFactor = 9 + longTagsTageFactor = 17 + longTagsSize = 12 + + logTagTableSizes = [12] + + firstLongTagTable = 11 + + truncatePathHist = False + + noSkip = [0,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,0,1] + + tagTableUBits = 2 # LTAGE branch predictor as described in # https://www.irisa.fr/caps/people/seznec/L-TAGE.pdf @@ -196,4 +286,177 @@ class LTAGE(TAGE): cxx_header = "cpu/pred/ltage.hh" tage = LTAGE_TAGE() + loop_predictor = Param.LoopPredictor(LoopPredictor(), "Loop predictor") + +class TAGE_SC_L_LoopPredictor(LoopPredictor): + type = 'TAGE_SC_L_LoopPredictor' + cxx_class = 'TAGE_SC_L_LoopPredictor' + cxx_header = "cpu/pred/tage_sc_l.hh" + loopTableAgeBits = 4 + loopTableConfidenceBits = 4 + loopTableTagBits = 10 + loopTableIterBits = 10 + useSpeculation = False + useHashing = True + useDirectionBit = True + restrictAllocation = True + initialLoopIter = 0 + initialLoopAge = 7 + optionalAgeReset = False + +class StatisticalCorrector(SimObject): + type = 'StatisticalCorrector' + cxx_class = 'StatisticalCorrector' + cxx_header = "cpu/pred/statistical_corrector.hh" + abstract = True + + # Statistical corrector parameters + + numEntriesFirstLocalHistories = Param.Unsigned( + "Number of entries for first local histories") + + bwnb = Param.Unsigned("Num global backward branch GEHL lengths") + bwm = VectorParam.Int("Global backward branch GEHL lengths") + logBwnb = Param.Unsigned("Log num of global backward branch GEHL entries") + + lnb = Param.Unsigned("Num first local history GEHL lenghts") + lm = VectorParam.Int("First local history GEHL lengths") + logLnb = Param.Unsigned("Log number of first local history GEHL entries") + + inb = Param.Unsigned(1, "Num IMLI GEHL lenghts") + im = VectorParam.Int([8], "IMLI history GEHL lengths") + logInb = Param.Unsigned("Log number of IMLI GEHL entries") + + logBias = Param.Unsigned("Log size of Bias tables") + + logSizeUp = Param.Unsigned(6, + "Log size of update threshold counters tables") + + chooserConfWidth = Param.Unsigned(7, + "Number of bits for the chooser counters") + + updateThresholdWidth = Param.Unsigned(12, + "Number of bits for the update threshold counter") + + pUpdateThresholdWidth = Param.Unsigned(8, + "Number of bits for the pUpdate threshold counters") + + extraWeightsWidth = Param.Unsigned(6, + "Number of bits for the extra weights") + + scCountersWidth = Param.Unsigned(6, "Statistical corrector counters width") + +# TAGE-SC-L branch predictor as desribed in +# https://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf +# It is a modified LTAGE predictor plus a statistical corrector predictor +# The TAGE modifications include bank interleaving and partial associativity +# Two different sizes are proposed in the paper: +# 8KB => See TAGE_SC_L_8KB below +# 64KB => See TAGE_SC_L_64KB below +# The TAGE_SC_L_8KB and TAGE_SC_L_64KB classes differ not only on the values +# of some parameters, but also in some implementation details +# Given this, the TAGE_SC_L class is left abstract +# Note that as it is now, this branch predictor does not handle any type +# of speculation: All the structures/histories are updated at commit time +class TAGE_SC_L(LTAGE): + type = 'TAGE_SC_L' + cxx_class = 'TAGE_SC_L' + cxx_header = "cpu/pred/tage_sc_l.hh" + abstract = True + + statistical_corrector = Param.StatisticalCorrector( + "Statistical Corrector") + +class TAGE_SC_L_64KB_LoopPredictor(TAGE_SC_L_LoopPredictor): + logSizeLoopPred = 5 + +class TAGE_SC_L_8KB_LoopPredictor(TAGE_SC_L_LoopPredictor): + logSizeLoopPred = 3 + +class TAGE_SC_L_64KB_StatisticalCorrector(StatisticalCorrector): + type = 'TAGE_SC_L_64KB_StatisticalCorrector' + cxx_class = 'TAGE_SC_L_64KB_StatisticalCorrector' + cxx_header = "cpu/pred/tage_sc_l_64KB.hh" + + pnb = Param.Unsigned(3, "Num variation global branch GEHL lengths") + pm = VectorParam.Int([25, 16, 9], "Variation global branch GEHL lengths") + logPnb = Param.Unsigned(9, + "Log number of variation global branch GEHL entries") + + snb = Param.Unsigned(3, "Num second local history GEHL lenghts") + sm = VectorParam.Int([16, 11, 6], "Second local history GEHL lengths") + logSnb = Param.Unsigned(9, + "Log number of second local history GEHL entries") + + tnb = Param.Unsigned(2, "Num third local history GEHL lenghts") + tm = VectorParam.Int([9, 4], "Third local history GEHL lengths") + logTnb = Param.Unsigned(10, + "Log number of third local history GEHL entries") + + imnb = Param.Unsigned(2, "Num second IMLI GEHL lenghts") + imm = VectorParam.Int([10, 4], "Second IMLI history GEHL lengths") + logImnb = Param.Unsigned(9, "Log number of second IMLI GEHL entries") + + numEntriesSecondLocalHistories = Param.Unsigned(16, + "Number of entries for second local histories") + numEntriesThirdLocalHistories = Param.Unsigned(16, + "Number of entries for second local histories") + + numEntriesFirstLocalHistories = 256 + + logBias = 8 + + bwnb = 3 + bwm = [40, 24, 10] + logBwnb = 10 + + lnb = 3 + lm = [11, 6, 3] + logLnb = 10 + + logInb = 8 + +class TAGE_SC_L_8KB_StatisticalCorrector(StatisticalCorrector): + type = 'TAGE_SC_L_8KB_StatisticalCorrector' + cxx_class = 'TAGE_SC_L_8KB_StatisticalCorrector' + cxx_header = "cpu/pred/tage_sc_l_8KB.hh" + gnb = Param.Unsigned(2, "Num global branch GEHL lengths") + gm = VectorParam.Int([6, 3], "Global branch GEHL lengths") + logGnb = Param.Unsigned(7, "Log number of global branch GEHL entries") + + numEntriesFirstLocalHistories = 64 + + logBias = 7 + + bwnb = 2 + logBwnb = 7 + bwm = [16, 8] + + lnb = 2 + logLnb = 7 + lm = [6, 3] + + logInb = 7 + +# 64KB TAGE-SC-L branch predictor as described in +# http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf +class TAGE_SC_L_64KB(TAGE_SC_L): + type = 'TAGE_SC_L_64KB' + cxx_class = 'TAGE_SC_L_64KB' + cxx_header = "cpu/pred/tage_sc_l_64KB.hh" + + tage = TAGE_SC_L_TAGE_64KB() + loop_predictor = TAGE_SC_L_64KB_LoopPredictor() + statistical_corrector = TAGE_SC_L_64KB_StatisticalCorrector() + +# 8KB TAGE-SC-L branch predictor as described in +# http://www.jilp.org/cbp2016/paper/AndreSeznecLimited.pdf +class TAGE_SC_L_8KB(TAGE_SC_L): + type = 'TAGE_SC_L_8KB' + cxx_class = 'TAGE_SC_L_8KB' + cxx_header = "cpu/pred/tage_sc_l_8KB.hh" + + tage = TAGE_SC_L_TAGE_8KB() + loop_predictor = TAGE_SC_L_8KB_LoopPredictor() + statistical_corrector = TAGE_SC_L_8KB_StatisticalCorrector() diff --git a/src/cpu/pred/SConscript b/src/cpu/pred/SConscript index 9e7e166ea..e3a521983 100644 --- a/src/cpu/pred/SConscript +++ b/src/cpu/pred/SConscript @@ -47,7 +47,12 @@ Source('tage_base.cc') Source('tage.cc') Source('loop_predictor.cc') Source('ltage.cc') +Source('statistical_corrector.cc') +Source('tage_sc_l.cc') +Source('tage_sc_l_8KB.cc') +Source('tage_sc_l_64KB.cc') DebugFlag('FreeList') DebugFlag('Branch') DebugFlag('Tage') DebugFlag('LTage') +DebugFlag('TageSCL') diff --git a/src/cpu/pred/loop_predictor.cc b/src/cpu/pred/loop_predictor.cc index 2e709f392..bd32e41c8 100644 --- a/src/cpu/pred/loop_predictor.cc +++ b/src/cpu/pred/loop_predictor.cc @@ -36,6 +36,8 @@ #include "cpu/pred/loop_predictor.hh" +#include "base/random.hh" +#include "debug/LTage.hh" #include "params/LoopPredictor.hh" LoopPredictor::LoopPredictor(LoopPredictorParams *p) @@ -166,14 +168,13 @@ LoopPredictor::specLoopUpdate(bool taken, BranchInfo* bi) } bool -LoopPredictor::optionalAgeInc(int nrand) const +LoopPredictor::optionalAgeInc() const { return false; } void -LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, - int random0, int random1, int random2) +LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred) { int idx = finallindex(bi->loopIndex, bi->loopIndexB, bi->loopHit); if (bi->loopHit >= 0) { @@ -186,7 +187,8 @@ LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, ltable[idx].confidence = 0; ltable[idx].currentIter = 0; return; - } else if (bi->loopPred != tage_pred || optionalAgeInc(random0)) { + } else if (bi->loopPred != tage_pred || optionalAgeInc()) { + DPRINTF(LTage, "Loop Prediction success:%lx\n",pc); unsignedCtrUpdate(ltable[idx].age, true, loopTableAgeBits); } } @@ -206,6 +208,7 @@ LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, if (taken != (useDirectionBit ? ltable[idx].dir : true)) { if (ltable[idx].currentIter == ltable[idx].numIter) { + DPRINTF(LTage, "Loop End predicted successfully:%lx\n", pc); unsignedCtrUpdate(ltable[idx].confidence, true, loopTableConfidenceBits); //just do not predict when the loop count is 1 or 2 @@ -217,6 +220,7 @@ LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, ltable[idx].confidence = 0; } } else { + DPRINTF(LTage, "Loop End predicted incorrectly:%lx\n", pc); if (ltable[idx].numIter == 0) { // first complete nest; ltable[idx].confidence = 0; @@ -235,13 +239,16 @@ LoopPredictor::loopUpdate(Addr pc, bool taken, BranchInfo* bi, bool tage_pred, } } else if (useDirectionBit ? (bi->predTaken != taken) : taken) { - if ((random2 & 3) == 0 || !restrictAllocation) { + if ((random_mt.random() & 3) == 0 || !restrictAllocation) { //try to allocate an entry on taken branch - int nrand = random1; + int nrand = random_mt.random(); for (int i = 0; i < (1 << logLoopTableAssoc); i++) { int loop_hit = (nrand + i) & ((1 << logLoopTableAssoc) - 1); idx = finallindex(bi->loopIndex, bi->loopIndexB, loop_hit); if (ltable[idx].age == 0) { + DPRINTF(LTage, + "Allocating loop pred entry for branch %lx\n", + pc); ltable[idx].dir = !taken; // ignored if no useDirectionBit ltable[idx].tag = bi->loopTag; ltable[idx].numIter = 0; @@ -318,8 +325,7 @@ LoopPredictor::updateStats(bool taken, BranchInfo* bi) void LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, bool tage_pred, BranchInfo* bi, - unsigned instShiftAmt, int rand0, int rand1, - int rand2) + unsigned instShiftAmt) { if (useSpeculation) { // recalculate loop prediction without speculation @@ -337,7 +343,7 @@ LoopPredictor::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, } } - loopUpdate(branch_pc, taken, bi, tage_pred, rand0, rand1, rand2); + loopUpdate(branch_pc, taken, bi, tage_pred); } void diff --git a/src/cpu/pred/loop_predictor.hh b/src/cpu/pred/loop_predictor.hh index 3579c5763..bc626980c 100644 --- a/src/cpu/pred/loop_predictor.hh +++ b/src/cpu/pred/loop_predictor.hh @@ -180,12 +180,8 @@ class LoopPredictor : public SimObject * @param bi Pointer to information on the * prediction recorded at prediction time. * @param tage_pred tage prediction of the branch - * @param random0 random value - * @param random1 random value - * @param random2 random value */ - void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred, - int random0, int random1, int random2); + void loopUpdate(Addr pc, bool Taken, BranchInfo* bi, bool tage_pred); /** * Speculatively updates the loop predictor @@ -204,14 +200,9 @@ class LoopPredictor : public SimObject * @param bi Pointer to information on the prediction * recorded at prediction time. * @param instShiftAmt Number of bits to shift instructions - * @param rand0 Random integer value - * @param rand1 Random integer value - * @param rand2 Random integer value */ - void condBranchUpdate( - ThreadID tid, Addr branch_pc, bool taken, bool tage_pred, - BranchInfo* bi, unsigned instShiftAmt, int rand0, int rand1, - int rand2); + void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, + bool tage_pred, BranchInfo* bi, unsigned instShiftAmt); /** * Get the loop prediction @@ -244,7 +235,7 @@ class LoopPredictor : public SimObject virtual bool calcConf(int index) const; - virtual bool optionalAgeInc(int nrand) const; + virtual bool optionalAgeInc() const; virtual BranchInfo *makeBranchInfo(); diff --git a/src/cpu/pred/ltage.cc b/src/cpu/pred/ltage.cc index cab86e459..44fce4303 100644 --- a/src/cpu/pred/ltage.cc +++ b/src/cpu/pred/ltage.cc @@ -42,6 +42,7 @@ #include "base/intmath.hh" #include "base/logging.hh" +#include "base/random.hh" #include "base/trace.hh" #include "debug/Fetch.hh" #include "debug/LTage.hh" @@ -51,6 +52,12 @@ LTAGE::LTAGE(const LTAGEParams *params) { } +void +LTAGE::init() +{ + TAGE::init(); +} + //prediction bool LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) @@ -82,6 +89,7 @@ LTAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) return pred_taken; } +// PREDICTOR UPDATE void LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, bool squashed, const StaticInstPtr & inst, Addr corrTarget) @@ -105,7 +113,7 @@ LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, return; } - int nrand = TAGEBase::getRandom() & 3; + int nrand = random_mt.random() & 3; if (bi->tageBranchInfo->condBranch) { DPRINTF(LTage, "Updating tables for branch:%lx; taken?:%d\n", branch_pc, taken); @@ -114,12 +122,10 @@ LTAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, loopPredictor->updateStats(taken, bi->lpBranchInfo); loopPredictor->condBranchUpdate(tid, branch_pc, taken, - bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt, - TAGEBase::getRandom(), TAGEBase::getRandom(), - TAGEBase::getRandom()); + bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt); tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo, - nrand, corrTarget); + nrand, corrTarget, bi->lpBranchInfo->predTaken); } tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false, diff --git a/src/cpu/pred/ltage.hh b/src/cpu/pred/ltage.hh index caddbc6a6..13ee5e94c 100644 --- a/src/cpu/pred/ltage.hh +++ b/src/cpu/pred/ltage.hh @@ -70,6 +70,8 @@ class LTAGE : public TAGE void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, bool squashed, const StaticInstPtr & inst, Addr corrTarget = MaxAddr) override; + + void init() override; virtual void regStats() override; protected: diff --git a/src/cpu/pred/statistical_corrector.cc b/src/cpu/pred/statistical_corrector.cc new file mode 100644 index 000000000..ebacd4dad --- /dev/null +++ b/src/cpu/pred/statistical_corrector.cc @@ -0,0 +1,393 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * Statistical corrector base class + */ + + #include "cpu/pred/statistical_corrector.hh" + + #include "params/StatisticalCorrector.hh" + + StatisticalCorrector::StatisticalCorrector( + const StatisticalCorrectorParams *p) + : SimObject(p), + logBias(p->logBias), + logSizeUp(p->logSizeUp), + logSizeUps(logSizeUp / 2), + numEntriesFirstLocalHistories(p->numEntriesFirstLocalHistories), + bwnb(p->bwnb), + logBwnb(p->logBwnb), + bwm(p->bwm), + lnb(p->lnb), + logLnb(p->logLnb), + lm(p->lm), + inb(p->inb), + logInb(p->logInb), + im(p->im), + chooserConfWidth(p->chooserConfWidth), + updateThresholdWidth(p->updateThresholdWidth), + pUpdateThresholdWidth(p->pUpdateThresholdWidth), + extraWeightsWidth(p->extraWeightsWidth), + scCountersWidth(p->scCountersWidth), + firstH(0), + secondH(0) +{ + wb.resize(1 << logSizeUps, 4); + + initGEHLTable(lnb, lm, lgehl, logLnb, wl, 7); + initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, 7); + initGEHLTable(inb, im, igehl, logInb, wi, 7); + + updateThreshold = 35 << 3; + + pUpdateThreshold.resize(1 << logSizeUp, 0); + + bias.resize(1 << logBias); + biasSK.resize(1 << logBias); + biasBank.resize(1 << logBias); + for (int j = 0; j < (1 << logBias); j++) { + switch (j & 3) { + case 0: + bias[j] = -32; + biasSK[j] = -8; + biasBank[j] = -32; + break; + case 1: + bias[j] = 31; + biasSK[j] = 7; + biasBank[j] = 31; + break; + case 2: + bias[j] = -1; + biasSK[j] = -32; + biasBank[j] = -1; + break; + case 3: + bias[j] = 0; + biasSK[j] = 31; + biasBank[j] = 0; + break; + } + } +} + +StatisticalCorrector::BranchInfo* +StatisticalCorrector::makeBranchInfo() +{ + return new BranchInfo(); +} + +StatisticalCorrector::SCThreadHistory* +StatisticalCorrector::makeThreadHistory() +{ + return new SCThreadHistory(); +} + +void +StatisticalCorrector::initGEHLTable(unsigned numLenghts, + std::vector lengths, std::vector * & table, + unsigned logNumEntries, std::vector & w, int8_t wInitValue) +{ + assert(lengths.size() == numLenghts); + if (numLenghts == 0) { + return; + } + table = new std::vector [numLenghts]; + for (int i = 0; i < numLenghts; ++i) { + table[i].resize(1 << logNumEntries, 0); + for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) { + if (! (j & 1)) { + table[i][j] = -1; + } + } + } + + w.resize(1 << logSizeUps, wInitValue); +} + +unsigned +StatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi, + bool bias) const +{ + return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1) + + bi->predBeforeSC) & ((1<> (logBias-2)))<<1) ^ + (bi->highConf))<<1) + bi->predBeforeSC) & ((1<>2)) & ((1 << (logSizeUp)) - 1)); +} + +unsigned +StatisticalCorrector::getIndUpds(Addr branch_pc) const +{ + return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1)); +} + +int64_t +StatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, + int i) +{ + return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^ + (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^ + (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) & + ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1); +} + +int +StatisticalCorrector::gPredict(Addr branch_pc, int64_t hist, + std::vector & length, std::vector * tab, int nbr, + int logs, std::vector & w) +{ + int percsum = 0; + for (int i = 0; i < nbr; i++) { + int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); + int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); + int8_t ctr = tab[i][index]; + percsum += (2 * ctr + 1); + } + percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum; + return percsum; +} + +void +StatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist, + std::vector & length, std::vector * tab, + int nbr, int logs, std::vector & w, + BranchInfo* bi) +{ + int percsum = 0; + for (int i = 0; i < nbr; i++) { + int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); + int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); + percsum += (2 * tab[i][index] + 1); + ctrUpdate(tab[i][index], taken, scCountersWidth); + } + + int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum; + if ((xsum + percsum >= 0) != (xsum >= 0)) { + ctrUpdate(w[getIndUpds(branch_pc)], ((percsum >= 0) == taken), + extraWeightsWidth); + } +} + +bool +StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc, bool cond_branch, + BranchInfo* bi, bool prev_pred_taken, bool bias_bit, + bool use_conf_ctr, int8_t conf_ctr, unsigned conf_bits, + int hitBank, int altBank, int64_t phist) +{ + bool pred_taken = prev_pred_taken; + if (cond_branch) { + + bi->predBeforeSC = prev_pred_taken; + + // first calc/update the confidences from the TAGE prediction + if (use_conf_ctr) { + bi->lowConf = (abs(2 * conf_ctr + 1) == 1); + bi->medConf = (abs(2 * conf_ctr + 1) == 5); + bi->highConf = (abs(2 * conf_ctr + 1) >= (1<= 0)) * lsum; + + int thres = gPredictions(tid, branch_pc, bi, lsum, phist); + + // These will be needed at update time + bi->lsum = lsum; + bi->thres = thres; + + bool scPred = (lsum >= 0); + + if (pred_taken != scPred) { + bool useScPred = true; + //Choser uses TAGE confidence and |LSUM| + if (bi->highConf) { + if (abs (lsum) < (thres / 4)) { + useScPred = false; + } else if (abs (lsum) < (thres / 2)) { + useScPred = (secondH < 0); + } + } + + if (bi->medConf) { + if (abs (lsum) < (thres / 4)) { + useScPred = (firstH < 0); + } + } + + bi->usedScPred = useScPred; + if (useScPred) { + pred_taken = scPred; + bi->scPred = scPred; + } + } + } + + return pred_taken; +} + +void +StatisticalCorrector::scHistoryUpdate(Addr branch_pc, int brtype, bool taken, + BranchInfo * tage_bi, Addr corrTarget) +{ + // Non speculative SC histories update + if (brtype & 1) { + if (corrTarget < branch_pc) { + //This branch corresponds to a loop + if (!taken) { + //exit of the "loop" + scHistory->imliCount = 0; + } else { + if (scHistory->imliCount < ((1 << im[0]) - 1)) { + scHistory->imliCount++; + } + } + } + + scHistory->bwHist = (scHistory->bwHist << 1) + + (taken & (corrTarget < branch_pc)); + scHistory->updateLocalHistory(1, branch_pc, taken); + } +} + +void +StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc, + bool taken, BranchInfo *bi, Addr corrTarget, bool b, int hitBank, + int altBank, int64_t phist) +{ + bool scPred = (bi->lsum >= 0); + + if (bi->predBeforeSC != scPred) { + if (abs(bi->lsum) < bi->thres) { + if (bi->highConf) { + if ((abs(bi->lsum) < bi->thres / 2)) { + if ((abs(bi->lsum) >= bi->thres / 4)) { + ctrUpdate(secondH, (bi->predBeforeSC == taken), + chooserConfWidth); + } + } + } + } + if (bi->medConf) { + if ((abs(bi->lsum) < bi->thres / 4)) { + ctrUpdate(firstH, (bi->predBeforeSC == taken), + chooserConfWidth); + } + } + } + + if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) { + ctrUpdate(updateThreshold, (scPred != taken), updateThresholdWidth); + ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken), + pUpdateThresholdWidth); + + unsigned indUpds = getIndUpds(branch_pc); + unsigned indBias = getIndBias(branch_pc, bi, b); + unsigned indBiasSK = getIndBiasSK(branch_pc, bi); + unsigned indBiasBank = getIndBiasBank(branch_pc, bi, hitBank, altBank); + + int xsum = bi->lsum - + ((wb[indUpds] >= 0) * ((2 * bias[indBias] + 1) + + (2 * biasSK[indBiasSK] + 1) + + (2 * biasBank[indBiasBank] + 1))); + + if ((xsum + ((2 * bias[indBias] + 1) + (2 * biasSK[indBiasSK] + 1) + + (2 * biasBank[indBiasBank] + 1)) >= 0) != (xsum >= 0)) + { + ctrUpdate(wb[indUpds], + (((2 * bias[indBias] + 1) + + (2 * biasSK[indBiasSK] + 1) + + (2 * biasBank[indBiasBank] + 1) >= 0) == taken), + extraWeightsWidth); + } + + ctrUpdate(bias[indBias], taken, scCountersWidth); + ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth); + ctrUpdate(biasBank[indBiasBank], taken, scCountersWidth); + + gUpdates(tid, branch_pc, taken, bi, phist); + } +} + +void +StatisticalCorrector::updateStats(bool taken, BranchInfo *bi) +{ + if (taken == bi->scPred) { + scPredictorCorrect++; + } else { + scPredictorWrong++; + } +} + +void +StatisticalCorrector::init() +{ + scHistory = makeThreadHistory(); +} + +void +StatisticalCorrector::regStats() +{ + scPredictorCorrect + .name(name() + ".scPredictorCorrect") + .desc("Number of time the SC predictor is the provider and " + "the prediction is correct"); + + scPredictorWrong + .name(name() + ".scPredictorWrong") + .desc("Number of time the SC predictor is the provider and " + "the prediction is wrong"); +} diff --git a/src/cpu/pred/statistical_corrector.hh b/src/cpu/pred/statistical_corrector.hh new file mode 100644 index 000000000..f96684346 --- /dev/null +++ b/src/cpu/pred/statistical_corrector.hh @@ -0,0 +1,265 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * Statistical corrector base class + */ + +#ifndef __CPU_PRED_STATISTICAL_CORRECTOR_HH +#define __CPU_PRED_STATISTICAL_CORRECTOR_HH + +#include "base/statistics.hh" +#include "base/types.hh" +#include "sim/sim_object.hh" + +struct StatisticalCorrectorParams; + +class StatisticalCorrector : public SimObject +{ + template + inline void ctrUpdate(T & ctr, bool taken, int nbits) { + assert(nbits <= sizeof(T) << 3); + if (taken) { + if (ctr < ((1 << (nbits - 1)) - 1)) + ctr++; + } else { + if (ctr > -(1 << (nbits - 1))) + ctr--; + } + } + protected: + // histories used for the statistical corrector + struct SCThreadHistory { + SCThreadHistory() { + bwHist = 0; + numOrdinalHistories = 0; + imliCount = 0; + } + int64_t bwHist; // backward global history + int64_t imliCount; + + void setNumOrdinalHistories(unsigned num) + { + numOrdinalHistories = num; + assert(num > 0); + shifts.resize(num); + localHistories = new std::vector [num]; + } + + void initLocalHistory(int ordinal, int numHistories, int shift) + { + assert((ordinal >= 1) && (ordinal <= numOrdinalHistories)); + shifts[ordinal - 1] = shift; + assert(isPowerOf2(numHistories)); + localHistories[ordinal - 1].resize(numHistories, 0); + } + + int64_t getLocalHistory(int ordinal, Addr pc) + { + assert((ordinal >= 1) && (ordinal <= numOrdinalHistories)); + unsigned idx = ordinal - 1; + return localHistories[idx][getEntry(pc, idx)]; + } + + void updateLocalHistory( + int ordinal, Addr branch_pc, bool taken, Addr extraXor = 0) + { + assert((ordinal >= 1) && (ordinal <= numOrdinalHistories)); + unsigned idx = ordinal - 1; + + unsigned entry = getEntry(branch_pc, idx); + int64_t hist = (localHistories[idx][entry] << 1) + taken; + + if (extraXor) { + hist = hist ^ extraXor; + } + + localHistories[idx][entry] = hist; + } + + private: + std::vector * localHistories; + std::vector shifts; + unsigned numOrdinalHistories; + + unsigned getEntry(Addr pc, unsigned idx) + { + return (pc ^ (pc >> shifts[idx])) & (localHistories[idx].size()-1); + } + }; + + // For SC history we use global (i.e. not per thread) non speculative + // histories, as some of the strucures needed are quite big and it is not + // reasonable to make them per thread and it would be difficult to + // rollback on miss-predictions + SCThreadHistory * scHistory; + + const unsigned logBias; + + const unsigned logSizeUp; + const unsigned logSizeUps; + + const unsigned numEntriesFirstLocalHistories; + + // global backward branch history GEHL + const unsigned bwnb; + const unsigned logBwnb; + std::vector bwm; + std::vector * bwgehl; + std::vector wbw; + + // First local history GEHL + const unsigned lnb; + const unsigned logLnb; + std::vector lm; + std::vector * lgehl; + std::vector wl; + + // IMLI GEHL + const unsigned inb; + const unsigned logInb; + std::vector im; + std::vector * igehl; + std::vector wi; + + std::vector bias; + std::vector biasSK; + std::vector biasBank; + + std::vector wb; + + int updateThreshold; + std::vector pUpdateThreshold; + + // The two counters used to choose between TAGE ang SC on High Conf + // TAGE/Low Conf SC + const unsigned chooserConfWidth; + + const unsigned updateThresholdWidth; + const unsigned pUpdateThresholdWidth; + + const unsigned extraWeightsWidth; + + const unsigned scCountersWidth; + + int8_t firstH; + int8_t secondH; + + // stats + Stats::Scalar scPredictorCorrect; + Stats::Scalar scPredictorWrong; + public: + struct BranchInfo + { + BranchInfo() : lowConf(false), highConf(false), altConf(false), + medConf(false), scPred(false), lsum(0), thres(0), + predBeforeSC(false), usedScPred(false) + {} + + // confidences calculated on tage and used on the statistical + // correction + bool lowConf; + bool highConf; + bool altConf; + bool medConf; + + bool scPred; + int lsum; + int thres; + bool predBeforeSC; + bool usedScPred; + }; + + StatisticalCorrector(const StatisticalCorrectorParams *p); + + virtual BranchInfo *makeBranchInfo(); + virtual SCThreadHistory *makeThreadHistory(); + + bool scPredict( + ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi, + bool prev_pred_taken, bool bias_bit, bool use_conf_ctr, + int8_t conf_ctr, unsigned conf_bits, int hitBank, int altBank, + int64_t phist); + + unsigned getIndBias(Addr branch_pc, BranchInfo* bi, bool b) const; + + unsigned getIndBiasSK(Addr branch_pc, BranchInfo* bi) const; + + virtual unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi, + int hitBank, int altBank) const = 0; + + unsigned getIndUpd(Addr branch_pc) const; + unsigned getIndUpds(Addr branch_pc) const; + + virtual int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi, + int & lsum, int64_t phist) = 0; + + int64_t gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, int i); + + virtual int gIndexLogsSubstr(int nbr, int i) = 0; + + int gPredict( + Addr branch_pc, int64_t hist, std::vector & length, + std::vector * tab, int nbr, int logs, + std::vector & w); + + void gUpdate( + Addr branch_pc, bool taken, int64_t hist, std::vector & length, + std::vector * tab, int nbr, int logs, + std::vector & w, BranchInfo* bi); + + void initGEHLTable( + unsigned numLenghts, std::vector lengths, + std::vector * & table, unsigned logNumEntries, + std::vector & w, int8_t wInitValue); + + virtual void scHistoryUpdate( + Addr branch_pc, int brtype, bool taken, BranchInfo * tage_bi, + Addr corrTarget); + + virtual void gUpdates( ThreadID tid, Addr pc, bool taken, BranchInfo* bi, + int64_t phist) = 0; + + void init() override; + void regStats() override; + void updateStats(bool taken, BranchInfo *bi); + + void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, + BranchInfo *bi, Addr corrTarget, bool bias_bit, + int hitBank, int altBank, int64_t phist); +}; +#endif//__CPU_PRED_STATISTICAL_CORRECTOR_HH diff --git a/src/cpu/pred/tage.cc b/src/cpu/pred/tage.cc index 5702c04b3..9b75e6ac8 100644 --- a/src/cpu/pred/tage.cc +++ b/src/cpu/pred/tage.cc @@ -59,28 +59,29 @@ TAGE::update(ThreadID tid, Addr branch_pc, bool taken, void* bp_history, assert(bp_history); TageBranchInfo *bi = static_cast(bp_history); + TAGEBase::BranchInfo *tage_bi = bi->tageBranchInfo; assert(corrTarget != MaxAddr); if (squashed) { // This restores the global history, then update it // and recomputes the folded histories. - tage->squash(tid, taken, bi->tageBranchInfo, corrTarget); + tage->squash(tid, taken, tage_bi, corrTarget); return; } - int nrand = TAGEBase::getRandom() & 3; + int nrand = random_mt.random() & 3; if (bi->tageBranchInfo->condBranch) { DPRINTF(Tage, "Updating tables for branch:%lx; taken?:%d\n", branch_pc, taken); tage->updateStats(taken, bi->tageBranchInfo); - tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo, - nrand, corrTarget); + tage->condBranchUpdate(tid, branch_pc, taken, tage_bi, nrand, + corrTarget, bi->tageBranchInfo->tagePred); } - tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false, - inst, corrTarget); - + // optional non speculative update of the histories + tage->updateHistories(tid, branch_pc, taken, tage_bi, false, inst, + corrTarget); delete bi; } @@ -95,7 +96,7 @@ TAGE::squash(ThreadID tid, void *bp_history) bool TAGE::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) { - TageBranchInfo *bi = new TageBranchInfo(*tage); + TageBranchInfo *bi = new TageBranchInfo(*tage);//nHistoryTables+1); b = (void*)(bi); return tage->tagePredict(tid, branch_pc, cond_branch, bi->tageBranchInfo); } diff --git a/src/cpu/pred/tage.hh b/src/cpu/pred/tage.hh index 0c5cde295..105999c82 100644 --- a/src/cpu/pred/tage.hh +++ b/src/cpu/pred/tage.hh @@ -77,6 +77,7 @@ class TAGE: public BPredUnit virtual bool predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b); + public: TAGE(const TAGEParams *params); @@ -87,7 +88,7 @@ class TAGE: public BPredUnit void btbUpdate(ThreadID tid, Addr branch_addr, void* &bp_history) override; void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, bool squashed, const StaticInstPtr & inst, - Addr corrTarget) override; + Addr corrTarget = MaxAddr) override; virtual void squash(ThreadID tid, void *bp_history) override; }; diff --git a/src/cpu/pred/tage_base.cc b/src/cpu/pred/tage_base.cc index 95be541d3..2d149ea76 100644 --- a/src/cpu/pred/tage_base.cc +++ b/src/cpu/pred/tage_base.cc @@ -42,7 +42,6 @@ #include "base/intmath.hh" #include "base/logging.hh" -#include "base/random.hh" #include "debug/Fetch.hh" #include "debug/Tage.hh" @@ -425,7 +424,7 @@ TAGEBase::tagePredict(ThreadID tid, Addr branch_pc, } void -TAGEBase::adjustAlloc(bool & alloc, bool taken) +TAGEBase::adjustAlloc(bool & alloc, bool taken, bool pred_taken) { // Nothing for this base class implementation } @@ -502,7 +501,7 @@ TAGEBase::resetUctr(uint8_t & u) void TAGEBase::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, - BranchInfo* bi, int nrand, Addr corrTarget) + BranchInfo* bi, int nrand, Addr corrTarget, bool pred) { // TAGE UPDATE // try to allocate a new entries only if prediction was wrong @@ -526,7 +525,7 @@ TAGEBase::condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, } } - adjustAlloc(alloc, taken); + adjustAlloc(alloc, taken, pred); handleAllocAndUReset(alloc, taken, bi, nrand); @@ -640,12 +639,6 @@ TAGEBase::extraAltCalc(BranchInfo* bi) return; } -int -TAGEBase::getRandom() -{ - return random_mt.random(); -} - void TAGEBase::updateStats(bool taken, BranchInfo* bi) { diff --git a/src/cpu/pred/tage_base.hh b/src/cpu/pred/tage_base.hh index ea1d827cb..48daaf9af 100644 --- a/src/cpu/pred/tage_base.hh +++ b/src/cpu/pred/tage_base.hh @@ -317,10 +317,11 @@ class TAGEBase : public SimObject * recorded at prediction time. * @nrand Random int number from 0 to 3 * @param corrTarget The correct branch target + * @param pred Final prediction for this branch */ virtual void condBranchUpdate( ThreadID tid, Addr branch_pc, bool taken, BranchInfo* bi, - int nrand, Addr corrTarget); + int nrand, Addr corrTarget, bool pred); /** * TAGE prediction called from TAGE::predict @@ -370,7 +371,7 @@ class TAGEBase : public SimObject * on an update * For this base TAGE implementation it does nothing */ - virtual void adjustAlloc(bool & alloc, bool taken); + virtual void adjustAlloc(bool & alloc, bool taken, bool pred_taken); /** * Handles Allocation and U bits reset on an update @@ -400,13 +401,6 @@ class TAGEBase : public SimObject */ virtual void extraAltCalc(BranchInfo* bi); - /** - * Algorithm for returning a random number - * This base TAGE class just uses random_mt, but some derived classes - * may want to use a more realistic implementation or force some values - */ - static int getRandom(); - void btbUpdate(ThreadID tid, Addr branch_addr, BranchInfo* &bi); unsigned getGHR(ThreadID tid, BranchInfo *bi) const; int8_t getCtr(int hitBank, int hitBankIndex) const; diff --git a/src/cpu/pred/tage_sc_l.cc b/src/cpu/pred/tage_sc_l.cc new file mode 100644 index 000000000..5f17b8187 --- /dev/null +++ b/src/cpu/pred/tage_sc_l.cc @@ -0,0 +1,479 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * TAGE-SC-L branch predictor base class (devised by Andre Seznec) + * It consits of a TAGE + a statistical corrector (SC) + a loop predictor (L) + */ + +#include "cpu/pred/tage_sc_l.hh" + +#include "base/random.hh" +#include "debug/TageSCL.hh" + +bool +TAGE_SC_L_LoopPredictor::calcConf(int index) const +{ + return LoopPredictor::calcConf(index) || + (ltable[index].confidence * ltable[index].numIter > 128); +} + +bool +TAGE_SC_L_LoopPredictor::optionalAgeInc() const +{ + return (random_mt.random() & 7) == 0; +} + +TAGE_SC_L_LoopPredictor * +TAGE_SC_L_LoopPredictorParams::create() +{ + return new TAGE_SC_L_LoopPredictor(this); +} + +TAGE_SC_L::TAGE_SC_L(const TAGE_SC_LParams *p) + : LTAGE(p), statisticalCorrector(p->statistical_corrector) +{ +} + +TAGEBase::BranchInfo* +TAGE_SC_L_TAGE::makeBranchInfo() +{ + return new BranchInfo(*this); +} +void +TAGE_SC_L_TAGE::calculateParameters() +{ + unsigned numHistLengths = nHistoryTables/2; + histLengths[1] = minHist; + histLengths[numHistLengths] = maxHist; + + // This calculates the different history lenghts + // there are only numHistLengths different lengths + // They are initially set to the lower half of histLengths + for (int i = 2; i <= numHistLengths; i++) { + histLengths[i] = (int) (((double) minHist * + pow ((double) (maxHist) / (double) minHist, + (double) (i - 1) / (double) ((numHistLengths - 1)))) + + 0.5); + } + + // This copies and duplicates the values from the lower half of the table + // Ex: 4, 6, 9, 13 would get exanded to 4, 4, 6, 6, 9, 9, 13, 13 + for (int i = nHistoryTables; i > 1; i--) + { + histLengths[i] = histLengths[(i + 1) / 2]; + } + + for (int i = 1; i <= nHistoryTables; i++) + { + tagTableTagWidths.push_back( + (i < firstLongTagTable) ? shortTagsSize : longTagsSize); + + logTagTableSizes.push_back(logTagTableSize); + } +} + +void +TAGE_SC_L_TAGE::buildTageTables() +{ + // Trick! We only allocate entries for tables 1 and firstLongTagTable and + // make the other tables point to these allocated entries + + gtable[1] = new TageEntry[shortTagsTageFactor * (1 << logTagTableSize)]; + gtable[firstLongTagTable] = + new TageEntry[longTagsTageFactor * (1 << logTagTableSize)]; + for (int i = 2; i < firstLongTagTable; ++i) { + gtable[i] = gtable[1]; + } + for (int i = firstLongTagTable + 1; i <= nHistoryTables; ++i) { + gtable[i] = gtable[firstLongTagTable]; + } +} + +void +TAGE_SC_L_TAGE::calculateIndicesAndTags( + ThreadID tid, Addr pc, TAGEBase::BranchInfo* bi) +{ + // computes the table addresses and the partial tags + + for (int i = 1; i <= nHistoryTables; i += 2) { + tableIndices[i] = gindex(tid, pc, i); + tableTags[i] = gtag(tid, pc, i); + tableTags[i + 1] = tableTags[i]; + tableIndices[i + 1] = tableIndices[i] ^ + (tableTags[i] & ((1 << logTagTableSizes[i]) - 1)); + + bi->tableTags[i] = tableTags[i]; + bi->tableTags[i+1] = tableTags[i+1]; + } + + Addr t = (pc ^ (threadHistory[tid].pathHist & + ((1 << histLengths[firstLongTagTable]) - 1))) + % longTagsTageFactor; + + for (int i = firstLongTagTable; i <= nHistoryTables; i++) { + if (noSkip[i]) { + tableIndices[i] += (t << logTagTableSizes[i]); + bi->tableIndices[i] = tableIndices[i]; + t++; + t = t % longTagsTageFactor; + } + } + + t = (pc ^ (threadHistory[tid].pathHist & ((1 << histLengths[1]) - 1))) + % shortTagsTageFactor; + + for (int i = 1; i <= firstLongTagTable - 1; i++) { + if (noSkip[i]) { + tableIndices[i] += (t << logTagTableSizes[i]); + bi->tableIndices[i] = tableIndices[i]; + t++; + t = t % shortTagsTageFactor; + } + } +} + +unsigned +TAGE_SC_L_TAGE::getUseAltIdx(TAGEBase::BranchInfo* bi) +{ + BranchInfo *tbi = static_cast(bi); + unsigned idx; + idx = ((((bi->hitBank-1)/8)<<1)+tbi->altConf) % (numUseAltOnNa-1); + return idx; +} + +int +TAGE_SC_L_TAGE::gindex(ThreadID tid, Addr pc, int bank) const +{ + int index; + int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits : + histLengths[bank]; + unsigned int shortPc = pc; + + // pc is not shifted by instShiftAmt in this implementation + index = shortPc ^ + (shortPc >> ((int) abs(logTagTableSizes[bank] - bank) + 1)) ^ + threadHistory[tid].computeIndices[bank].comp ^ + F(threadHistory[tid].pathHist, hlen, bank); + + index = gindex_ext(index, bank); + + return (index & ((ULL(1) << (logTagTableSizes[bank])) - 1)); +} + +int +TAGE_SC_L_TAGE::F(int a, int size, int bank) const +{ + int a1, a2; + + a = a & ((ULL(1) << size) - 1); + a1 = (a & ((ULL(1) << logTagTableSizes[bank]) - 1)); + a2 = (a >> logTagTableSizes[bank]); + + if (bank < logTagTableSizes[bank]) { + a2 = ((a2 << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1)) + + (a2 >> (logTagTableSizes[bank] - bank)); + } + + a = a1 ^ a2; + + if (bank < logTagTableSizes[bank]) { + a = ((a << bank) & ((ULL(1) << logTagTableSizes[bank]) - 1)) + + (a >> (logTagTableSizes[bank] - bank)); + } + + return a; +} + +int +TAGE_SC_L_TAGE::bindex(Addr pc) const +{ + return ((pc ^ (pc >> instShiftAmt)) & + ((ULL(1) << (logTagTableSizes[0])) - 1)); +} + +void +TAGE_SC_L_TAGE::updatePathAndGlobalHistory( + ThreadHistory& tHist, int brtype, bool taken, Addr branch_pc, Addr target) +{ + // TAGE update + int tmp = ((branch_pc ^ (branch_pc >> instShiftAmt))) ^ taken; + int path = branch_pc ^ (branch_pc >> instShiftAmt) + ^ (branch_pc >> (instShiftAmt+2)); + if ((brtype == 3) & taken) { + tmp = (tmp ^ (target >> instShiftAmt)); + path = path ^ (target >> instShiftAmt) ^ (target >> (instShiftAmt+2)); + } + + // some branch types use 3 bits in global history, the others just 2 + int maxt = (brtype == 2) ? 3 : 2; + + for (int t = 0; t < maxt; t++) { + bool dir = (tmp & 1); + tmp >>= 1; + int pathbit = (path & 127); + path >>= 1; + updateGHist(tHist.gHist, dir, tHist.globalHistory, tHist.ptGhist); + tHist.pathHist = (tHist.pathHist << 1) ^ pathbit; + if (truncatePathHist) { + // The 8KB implementation does not do this truncation + tHist.pathHist = (tHist.pathHist & ((ULL(1) << pathHistBits) - 1)); + } + for (int i = 1; i <= nHistoryTables; i++) { + tHist.computeIndices[i].update(tHist.gHist); + tHist.computeTags[0][i].update(tHist.gHist); + tHist.computeTags[1][i].update(tHist.gHist); + } + } +} + +void +TAGE_SC_L_TAGE::updateHistories( + ThreadID tid, Addr branch_pc, bool taken, TAGEBase::BranchInfo* b, + bool speculative, const StaticInstPtr &inst, Addr target) +{ + if (speculative != speculativeHistUpdate) { + return; + } + // speculation is not implemented + assert(! speculative); + + ThreadHistory& tHist = threadHistory[tid]; + + int brtype = inst->isDirectCtrl() ? 0 : 2; + if (! inst->isUncondCtrl()) { + ++brtype; + } + updatePathAndGlobalHistory(tHist, brtype, taken, branch_pc, target); + + DPRINTF(TageSCL, "Updating global histories with branch:%lx; taken?:%d, " + "path Hist: %x; pointer:%d\n", branch_pc, taken, tHist.pathHist, + tHist.ptGhist); +} + +void +TAGE_SC_L_TAGE::squash(ThreadID tid, bool taken, TAGEBase::BranchInfo *bi, + Addr target) +{ + fatal("Speculation is not implemented"); +} + +void +TAGE_SC_L_TAGE::adjustAlloc(bool & alloc, bool taken, bool pred_taken) +{ + // Do not allocate too often if the prediction is ok + if ((taken == pred_taken) && ((random_mt.random() & 31) != 0)) { + alloc = false; + } +} + +int +TAGE_SC_L_TAGE::calcDep(TAGEBase::BranchInfo* bi) +{ + int a = 1; + if ((random_mt.random() & 127) < 32) { + a = 2; + } + return ((((bi->hitBank - 1 + 2 * a) & 0xffe)) ^ + (random_mt.random() & 1)); +} + +void +TAGE_SC_L_TAGE::handleUReset() +{ + //just the best formula for the Championship: + //In practice when one out of two entries are useful + if (tCounter < 0) { + tCounter = 0; + } + + if (tCounter >= ((ULL(1) << logUResetPeriod))) { + // Update the u bits for the short tags table + for (int j = 0; j < (shortTagsTageFactor*(1<(tage_bi); + + int bim = (btablePrediction[bi->bimodalIndex] << 1) + + btableHysteresis[bi->bimodalIndex >> logRatioBiModalHystEntries]; + + bi->highConf = (bim == 0) || (bim == 3); + bi->lowConf = ! bi->highConf; + bi->altConf = bi->highConf; + bi->medConf = false; + return TAGEBase::getBimodePred(pc, tage_bi); +} + +void +TAGE_SC_L_TAGE::extraAltCalc(TAGEBase::BranchInfo* bi) +{ + TAGE_SC_L_TAGE::BranchInfo *tage_scl_bi = + static_cast(bi); + int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; + tage_scl_bi->altConf = (abs(2*ctr + 1) > 1); +} + +bool +TAGE_SC_L::predict(ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) +{ + TageSCLBranchInfo *bi = new TageSCLBranchInfo(*tage, + *statisticalCorrector, + *loopPredictor); + b = (void*)(bi); + + bool pred_taken = tage->tagePredict(tid, branch_pc, cond_branch, + bi->tageBranchInfo); + pred_taken = loopPredictor->loopPredict(tid, branch_pc, cond_branch, + bi->lpBranchInfo, pred_taken, + instShiftAmt); + + if (bi->lpBranchInfo->loopPredUsed) { + bi->tageBranchInfo->provider = LOOP; + } + + TAGE_SC_L_TAGE::BranchInfo* tage_scl_bi = + static_cast(bi->tageBranchInfo); + + // Copy the confidences computed by TAGE + bi->scBranchInfo->lowConf = tage_scl_bi->lowConf; + bi->scBranchInfo->highConf = tage_scl_bi->highConf; + bi->scBranchInfo->altConf = tage_scl_bi->altConf; + bi->scBranchInfo->medConf = tage_scl_bi->medConf; + + bool use_tage_ctr = bi->tageBranchInfo->hitBank > 0; + int8_t tage_ctr = use_tage_ctr ? + tage->getCtr(tage_scl_bi->hitBank, tage_scl_bi->hitBankIndex) : 0; + bool bias = (bi->tageBranchInfo->longestMatchPred != + bi->tageBranchInfo->altTaken); + + pred_taken = statisticalCorrector->scPredict(tid, branch_pc, cond_branch, + bi->scBranchInfo, pred_taken, bias, use_tage_ctr, tage_ctr, + tage->getTageCtrBits(), bi->tageBranchInfo->hitBank, + bi->tageBranchInfo->altBank, tage->getPathHist(tid)); + + if (bi->scBranchInfo->usedScPred) { + bi->tageBranchInfo->provider = SC; + } + + // record final prediction + bi->lpBranchInfo->predTaken = pred_taken; + + return pred_taken; +} + +void +TAGE_SC_L::update(ThreadID tid, Addr branch_pc, bool taken, void *bp_history, + bool squashed, const StaticInstPtr & inst, Addr corrTarget) +{ + assert(bp_history); + + TageSCLBranchInfo* bi = static_cast(bp_history); + TAGE_SC_L_TAGE::BranchInfo* tage_bi = + static_cast(bi->tageBranchInfo); + + assert(corrTarget != MaxAddr); + + if (squashed) { + if (tage->isSpeculativeUpdateEnabled()) { + // This restores the global history, then update it + // and recomputes the folded histories. + tage->squash(tid, taken, tage_bi, corrTarget); + if (bi->tageBranchInfo->condBranch) { + loopPredictor->squashLoop(bi->lpBranchInfo); + } + } + return; + } + + int nrand = random_mt.random() & 3; + if (tage_bi->condBranch) { + DPRINTF(TageSCL, "Updating tables for branch:%lx; taken?:%d\n", + branch_pc, taken); + tage->updateStats(taken, bi->tageBranchInfo); + + loopPredictor->updateStats(taken, bi->lpBranchInfo); + + statisticalCorrector->updateStats(taken, bi->scBranchInfo); + + bool bias = (bi->tageBranchInfo->longestMatchPred != + bi->tageBranchInfo->altTaken); + statisticalCorrector->condBranchUpdate(tid, branch_pc, taken, + bi->scBranchInfo, corrTarget, bias, bi->tageBranchInfo->hitBank, + bi->tageBranchInfo->altBank, tage->getPathHist(tid)); + + loopPredictor->condBranchUpdate(tid, branch_pc, taken, + bi->tageBranchInfo->tagePred, bi->lpBranchInfo, instShiftAmt); + + tage->condBranchUpdate(tid, branch_pc, taken, bi->tageBranchInfo, + nrand, corrTarget, bi->lpBranchInfo->predTaken); + } + + if (!tage->isSpeculativeUpdateEnabled()) { + int brtype = inst->isDirectCtrl() ? 0 : 2; + if (! inst->isUncondCtrl()) { + ++brtype; + } + + statisticalCorrector->scHistoryUpdate(branch_pc, brtype, taken, + bi->scBranchInfo, corrTarget); + + tage->updateHistories(tid, branch_pc, taken, bi->tageBranchInfo, false, + inst, corrTarget); + } + + delete bi; +} + +void +TAGE_SC_L::regStats() +{ + LTAGE::regStats(); +} diff --git a/src/cpu/pred/tage_sc_l.hh b/src/cpu/pred/tage_sc_l.hh new file mode 100644 index 000000000..c96cc8960 --- /dev/null +++ b/src/cpu/pred/tage_sc_l.hh @@ -0,0 +1,188 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * TAGE-SC-L branch predictor base class (devised by Andre Seznec) + * It consits of a TAGE + a statistical corrector (SC) + a loop predictor (L) + */ + +#ifndef __CPU_PRED_TAGE_SC_L +#define __CPU_PRED_TAGE_SC_L + +#include "cpu/pred/ltage.hh" +#include "cpu/pred/statistical_corrector.hh" +#include "params/TAGE_SC_L.hh" +#include "params/TAGE_SC_L_LoopPredictor.hh" +#include "params/TAGE_SC_L_TAGE.hh" + +class TAGE_SC_L_TAGE : public TAGEBase { + const unsigned firstLongTagTable; + const unsigned longTagsSize; + const unsigned shortTagsSize; + + const unsigned logTagTableSize; + + const unsigned shortTagsTageFactor; + const unsigned longTagsTageFactor; + + const bool truncatePathHist; + + public: + struct BranchInfo : public TAGEBase::BranchInfo { + bool lowConf; + bool highConf; + bool altConf; + bool medConf; + BranchInfo(TAGEBase &tage) : TAGEBase::BranchInfo(tage), + lowConf(false), highConf(false), altConf(false), medConf(false) + {} + virtual ~BranchInfo() + {} + }; + + virtual TAGEBase::BranchInfo *makeBranchInfo() override; + + TAGE_SC_L_TAGE(const TAGE_SC_L_TAGEParams *p) + : TAGEBase(p), + firstLongTagTable(p->firstLongTagTable), + longTagsSize(p->longTagsSize), + shortTagsSize(p->shortTagsSize), + logTagTableSize(p->logTagTableSize), + shortTagsTageFactor(p->shortTagsTageFactor), + longTagsTageFactor(p->longTagsTageFactor), + truncatePathHist(p->truncatePathHist) + {} + + void calculateParameters() override; + + void buildTageTables() override; + + void calculateIndicesAndTags( + ThreadID tid, Addr branch_pc, TAGEBase::BranchInfo* bi) override; + + unsigned getUseAltIdx(TAGEBase::BranchInfo* bi) override; + + void updateHistories( + ThreadID tid, Addr branch_pc, bool taken, TAGEBase::BranchInfo* b, + bool speculative, const StaticInstPtr &inst, + Addr target) override; + + int bindex(Addr pc_in) const override; + int gindex(ThreadID tid, Addr pc, int bank) const override; + virtual int gindex_ext(int index, int bank) const = 0; + int F(int phist, int size, int bank) const override; + + virtual uint16_t gtag(ThreadID tid, Addr pc, int bank) const override = 0; + + void squash(ThreadID tid, bool taken, TAGEBase::BranchInfo *bi, + Addr target) override; + + void updatePathAndGlobalHistory( + ThreadHistory & tHist, int brtype, bool taken, + Addr branch_pc, Addr target); + + void adjustAlloc(bool & alloc, bool taken, bool pred_taken) override; + + virtual void handleAllocAndUReset(bool alloc, bool taken, + TAGEBase::BranchInfo* bi, int nrand) override = 0; + + void handleUReset() override; + + virtual void handleTAGEUpdate( + Addr branch_pc, bool taken, TAGEBase::BranchInfo* bi) override = 0; + + int calcDep(TAGEBase::BranchInfo* bi); + + bool getBimodePred(Addr branch_pc, + TAGEBase::BranchInfo* tage_bi) const override; + + void extraAltCalc(TAGEBase::BranchInfo* bi) override; + +}; + +class TAGE_SC_L_LoopPredictor : public LoopPredictor +{ + public: + TAGE_SC_L_LoopPredictor(TAGE_SC_L_LoopPredictorParams *p) + : LoopPredictor(p) + {} + + virtual bool calcConf(int index) const override; + virtual bool optionalAgeInc() const override; +}; + +class TAGE_SC_L: public LTAGE +{ + StatisticalCorrector *statisticalCorrector; + public: + TAGE_SC_L(const TAGE_SC_LParams *params); + + bool predict( + ThreadID tid, Addr branch_pc, bool cond_branch, void* &b) override; + + void regStats() override; + + void update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, + bool squashed, const StaticInstPtr & inst, + Addr corrTarget = MaxAddr) override; + + protected: + + struct TageSCLBranchInfo : public LTageBranchInfo + { + StatisticalCorrector::BranchInfo *scBranchInfo; + + TageSCLBranchInfo(TAGEBase &tage, StatisticalCorrector &sc, + LoopPredictor &lp) + : LTageBranchInfo(tage, lp), scBranchInfo(sc.makeBranchInfo()) + {} + + virtual ~TageSCLBranchInfo() + { + delete scBranchInfo; + } + }; + + // more provider types + enum { + SC = LAST_LTAGE_PROVIDER_TYPE + 1 + }; + +}; + +#endif // __CPU_PRED_TAGE_SC_L + diff --git a/src/cpu/pred/tage_sc_l_64KB.cc b/src/cpu/pred/tage_sc_l_64KB.cc new file mode 100644 index 000000000..164d58768 --- /dev/null +++ b/src/cpu/pred/tage_sc_l_64KB.cc @@ -0,0 +1,322 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * 64KB TAGE-SC-L branch predictor (devised by Andre Seznec) + */ + +#include "cpu/pred/tage_sc_l_64KB.hh" + +TAGE_SC_L_64KB_StatisticalCorrector::TAGE_SC_L_64KB_StatisticalCorrector( + TAGE_SC_L_64KB_StatisticalCorrectorParams *p) + : StatisticalCorrector(p), + numEntriesSecondLocalHistories(p->numEntriesSecondLocalHistories), + numEntriesThirdLocalHistories(p->numEntriesThirdLocalHistories), + pnb(p->pnb), + logPnb(p->logPnb), + pm(p->pm), + snb(p->snb), + logSnb(p->logSnb), + sm(p->sm), + tnb(p->tnb), + logTnb(p->logTnb), + tm(p->tm), + imnb(p->imnb), + logImnb(p->logImnb), + imm(p->imm) +{ + initGEHLTable(pnb, pm, pgehl, logPnb, wp, 7); + initGEHLTable(snb, sm, sgehl, logSnb, ws, 7); + initGEHLTable(tnb, tm, tgehl, logTnb, wt, 7); + initGEHLTable(imnb, imm, imgehl, logImnb, wim, 0); + +} + +TAGE_SC_L_64KB_StatisticalCorrector::SCThreadHistory* +TAGE_SC_L_64KB_StatisticalCorrector::makeThreadHistory() +{ + SC_64KB_ThreadHistory *sh = new SC_64KB_ThreadHistory(); + + sh->setNumOrdinalHistories(3); + sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2); + sh->initLocalHistory(2, numEntriesSecondLocalHistories, 5); + sh->initLocalHistory(3, numEntriesThirdLocalHistories, logTnb); + + sh->imHist.resize(1 << im[0]); + return sh; +} + +unsigned +TAGE_SC_L_64KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc, + BranchInfo* bi, int hitBank, int altBank) const +{ + return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) + + (bi->lowConf <<2) + ((altBank!=0)<<3) + + ((branch_pc^(branch_pc>>2))<<7)) & ((1<(scHistory); + + lsum += gPredict( + (branch_pc << 1) + bi->predBeforeSC, sh->bwHist, bwm, + bwgehl, bwnb, logBwnb, wbw); + + lsum += gPredict( + branch_pc, pathHist, pm, pgehl, pnb, logPnb, wp); + + lsum += gPredict( + branch_pc, sh->getLocalHistory(1, branch_pc), lm, + lgehl, lnb, logLnb, wl); + + lsum += gPredict( + branch_pc, sh->getLocalHistory(2, branch_pc), sm, + sgehl, snb, logSnb, ws); + + lsum += gPredict( + branch_pc, sh->getLocalHistory(3, branch_pc), tm, + tgehl, tnb, logTnb, wt); + + lsum += gPredict( + branch_pc, sh->imHist[scHistory->imliCount], imm, + imgehl, imnb, logImnb, wim); + + lsum += gPredict( + branch_pc, sh->imliCount, im, igehl, inb, logInb, wi); + + int thres = (updateThreshold>>3) + pUpdateThreshold[getIndUpd(branch_pc)] + + 12*((wb[getIndUpds(branch_pc)] >= 0) + (wp[getIndUpds(branch_pc)] >= 0) + + (ws[getIndUpds(branch_pc)] >= 0) + (wt[getIndUpds(branch_pc)] >= 0) + + (wl[getIndUpds(branch_pc)] >= 0) + (wbw[getIndUpds(branch_pc)] >= 0) + + (wi[getIndUpds(branch_pc)] >= 0)); + + return thres; +} + +int +TAGE_SC_L_64KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i) +{ + return (i >= (nbr - 2)) ? 1 : 0; +} + +void +TAGE_SC_L_64KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc, + int brtype, bool taken, BranchInfo* tage_bi, Addr corrTarget) +{ + // Non speculative SC histories update + if (brtype & 1) { + SC_64KB_ThreadHistory *sh = + static_cast(scHistory); + int64_t imliCount = sh->imliCount; + sh->imHist[imliCount] = (sh->imHist[imliCount] << 1) + + taken; + sh->updateLocalHistory(2, branch_pc, taken, branch_pc & 15); + sh->updateLocalHistory(3, branch_pc, taken); + } + + StatisticalCorrector::scHistoryUpdate(branch_pc, brtype, taken, tage_bi, + corrTarget); +} + +void +TAGE_SC_L_64KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, + bool taken, BranchInfo* bi, int64_t phist) +{ + SC_64KB_ThreadHistory *sh = + static_cast(scHistory); + + gUpdate((pc << 1) + bi->predBeforeSC, taken, sh->bwHist, bwm, + bwgehl, bwnb, logBwnb, wbw, bi); + + gUpdate(pc, taken, phist, pm, + pgehl, pnb, logPnb, wp, bi); + + gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, + lgehl, lnb, logLnb, wl, bi); + + gUpdate(pc, taken, sh->getLocalHistory(2, pc), sm, + sgehl, snb, logSnb, ws, bi); + + gUpdate(pc, taken, sh->getLocalHistory(3, pc), tm, + tgehl, tnb, logTnb, wt, bi); + + gUpdate(pc, taken, sh->imHist[scHistory->imliCount], imm, + imgehl, imnb, logImnb, wim, bi); + + gUpdate(pc, taken, sh->imliCount, im, + igehl, inb, logInb, wi, bi); +} + +TAGE_SC_L_64KB_StatisticalCorrector* +TAGE_SC_L_64KB_StatisticalCorrectorParams::create() +{ + return new TAGE_SC_L_64KB_StatisticalCorrector(this); +} + +int +TAGE_SC_L_TAGE_64KB::gindex_ext(int index, int bank) const +{ + return index; +} + +uint16_t +TAGE_SC_L_TAGE_64KB::gtag(ThreadID tid, Addr pc, int bank) const +{ + // very similar to the TAGE implementation, but w/o shifting the pc + int tag = pc ^ threadHistory[tid].computeTags[0][bank].comp ^ + (threadHistory[tid].computeTags[1][bank].comp << 1); + + return (tag & ((ULL(1) << tagTableTagWidths[bank]) - 1)); +} + +void +TAGE_SC_L_TAGE_64KB::handleAllocAndUReset( + bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) +{ + if (! alloc) { + return; + } + + int penalty = 0; + int numAllocated = 0; + bool maxAllocReached = false; + + for (int I = calcDep(bi); I < nHistoryTables; I += 2) { + // Handle the 2-way associativity for allocation + for (int j = 0; j < 2; ++j) { + int i = ((j == 0) ? I : (I ^ 1)) + 1; + if (noSkip[i]) { + if (gtable[i][bi->tableIndices[i]].u == 0) { + int8_t ctr = gtable[i][bi->tableIndices[i]].ctr; + if (abs (2 * ctr + 1) <= 3) { + gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; + gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1; + numAllocated++; + maxAllocReached = (numAllocated == maxNumAlloc); + I += 2; + break; + } else { + if (gtable[i][bi->tableIndices[i]].ctr > 0) { + gtable[i][bi->tableIndices[i]].ctr--; + } else { + gtable[i][bi->tableIndices[i]].ctr++; + } + } + } else { + penalty++; + } + } + } + if (maxAllocReached) { + break; + } + } + + tCounter += (penalty - 2 * numAllocated); + + handleUReset(); +} + +void +TAGE_SC_L_TAGE_64KB::handleTAGEUpdate(Addr branch_pc, bool taken, + TAGEBase::BranchInfo* bi) +{ + if (bi->hitBank > 0) { + if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { + if (bi->longestMatchPred != taken) { + // acts as a protection + if (bi->altBank > 0) { + ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, + tagTableCounterBits); + } + if (bi->altBank == 0){ + baseUpdate(branch_pc, taken, bi); + } + } + } + + ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, + tagTableCounterBits); + + //sign changes: no way it can have been useful + if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { + gtable[bi->hitBank][bi->hitBankIndex].u = 0; + } + + if (bi->altTaken == taken) { + if (bi->altBank > 0) { + int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; + if (abs (2 * ctr + 1) == 7) { + if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) { + if (bi->longestMatchPred == taken) { + gtable[bi->hitBank][bi->hitBankIndex].u = 0; + } + } + } + } + } + } else { + baseUpdate(branch_pc, taken, bi); + } + + if ((bi->longestMatchPred != bi->altTaken) && + (bi->longestMatchPred == taken) && + (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) { + gtable[bi->hitBank][bi->hitBankIndex].u++; + } +} + +TAGE_SC_L_TAGE_64KB* +TAGE_SC_L_TAGE_64KBParams::create() +{ + return new TAGE_SC_L_TAGE_64KB(this); +} + +TAGE_SC_L_64KB::TAGE_SC_L_64KB(const TAGE_SC_L_64KBParams *params) + : TAGE_SC_L(params) +{ +} + +TAGE_SC_L_64KB* +TAGE_SC_L_64KBParams::create() +{ + return new TAGE_SC_L_64KB(this); +} diff --git a/src/cpu/pred/tage_sc_l_64KB.hh b/src/cpu/pred/tage_sc_l_64KB.hh new file mode 100644 index 000000000..21dd1703c --- /dev/null +++ b/src/cpu/pred/tage_sc_l_64KB.hh @@ -0,0 +1,135 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * 64KB TAGE-SC-L branch predictor (devised by Andre Seznec) + * + * Most of the code in this file has been adapted from cbp64KB/predictor.h in + * http://www.jilp.org/cbp2016/code/AndreSeznecLimited.tar.gz + */ + +#ifndef __CPU_PRED_TAGE_SC_L_64KB +#define __CPU_PRED_TAGE_SC_L_64KB + +#include "cpu/pred/tage_sc_l.hh" +#include "params/TAGE_SC_L_64KB.hh" +#include "params/TAGE_SC_L_64KB_StatisticalCorrector.hh" +#include "params/TAGE_SC_L_TAGE_64KB.hh" + +class TAGE_SC_L_TAGE_64KB : public TAGE_SC_L_TAGE { + public: + TAGE_SC_L_TAGE_64KB(const TAGE_SC_L_TAGE_64KBParams *p) : TAGE_SC_L_TAGE(p) + {} + + int gindex_ext(int index, int bank) const override; + + uint16_t gtag(ThreadID tid, Addr pc, int bank) const override; + + void handleAllocAndUReset( + bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) override; + + void handleTAGEUpdate( + Addr branch_pc, bool taken, TAGEBase::BranchInfo* bi) override; +}; + +class TAGE_SC_L_64KB_StatisticalCorrector : public StatisticalCorrector +{ + const unsigned numEntriesSecondLocalHistories; + const unsigned numEntriesThirdLocalHistories; + + // global branch history variation GEHL + const unsigned pnb; + const unsigned logPnb; + std::vector pm; + std::vector * pgehl; + std::vector wp; + + // Second local history GEHL + const unsigned snb; + const unsigned logSnb; + std::vector sm; + std::vector * sgehl; + std::vector ws; + + // Third local history GEHL + const unsigned tnb; + const unsigned logTnb; + std::vector tm; + std::vector * tgehl; + std::vector wt; + + // Second IMLI GEHL + const unsigned imnb; + const unsigned logImnb; + std::vector imm; + std::vector * imgehl; + std::vector wim; + + struct SC_64KB_ThreadHistory : public SCThreadHistory + { + std::vector imHist; + }; + + SCThreadHistory *makeThreadHistory() override; + + public: + TAGE_SC_L_64KB_StatisticalCorrector( + TAGE_SC_L_64KB_StatisticalCorrectorParams *p); + + unsigned getIndBiasBank(Addr branch_pc, BranchInfo* bi, int hitBank, + int altBank) const override; + + int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi, + int & lsum, int64_t phist) override; + + int gIndexLogsSubstr(int nbr, int i) override; + + void scHistoryUpdate(Addr branch_pc, int brtype, bool taken, + BranchInfo * tage_bi, Addr corrTarget) override; + + void gUpdates(ThreadID tid, Addr pc, bool taken, BranchInfo* bi, + int64_t phist) override; +}; + +class TAGE_SC_L_64KB : public TAGE_SC_L +{ + public: + TAGE_SC_L_64KB(const TAGE_SC_L_64KBParams *params); +}; + +#endif // __CPU_PRED_TAGE_SC_L_64KB + diff --git a/src/cpu/pred/tage_sc_l_8KB.cc b/src/cpu/pred/tage_sc_l_8KB.cc new file mode 100644 index 000000000..9af21e1a5 --- /dev/null +++ b/src/cpu/pred/tage_sc_l_8KB.cc @@ -0,0 +1,325 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec) + */ + +#include "cpu/pred/tage_sc_l_8KB.hh" + +#include "base/random.hh" +#include "debug/TageSCL.hh" + +TAGE_SC_L_8KB_StatisticalCorrector::TAGE_SC_L_8KB_StatisticalCorrector( + TAGE_SC_L_8KB_StatisticalCorrectorParams *p) + : StatisticalCorrector(p), + gnb(p->gnb), + logGnb(p->logGnb), + gm(p->gm) +{ + initGEHLTable(gnb, gm, ggehl, logGnb, wg, 7); +} + +TAGE_SC_L_8KB_StatisticalCorrector::SCThreadHistory * +TAGE_SC_L_8KB_StatisticalCorrector::makeThreadHistory() +{ + SC_8KB_ThreadHistory *sh = new SC_8KB_ThreadHistory(); + sh->setNumOrdinalHistories(1); + sh->initLocalHistory(1, numEntriesFirstLocalHistories, 2); + return sh; +} + +unsigned +TAGE_SC_L_8KB_StatisticalCorrector::getIndBiasBank(Addr branch_pc, + BranchInfo* bi, int hitBank, int altBank) const +{ + return (bi->predBeforeSC + (((hitBank+1)/4)<<4) + (bi->highConf<<1) + + (bi->lowConf <<2) +((altBank!=0)<<3)) & ((1<(scHistory); + lsum += gPredict( + branch_pc, sh->globalHist, gm, ggehl, gnb, logGnb, wg); + + lsum += gPredict( + branch_pc, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw); + + // only 1 local history here + lsum += gPredict( + branch_pc, sh->getLocalHistory(1, branch_pc), lm, + lgehl, lnb, logLnb, wl); + + lsum += gPredict( + branch_pc, sh->imliCount, im, igehl, inb, logInb, wi); + + int thres = (updateThreshold>>3)+pUpdateThreshold[getIndUpd(branch_pc)]; + + return thres; +} + +int TAGE_SC_L_8KB_StatisticalCorrector::gIndexLogsSubstr(int nbr, int i) +{ + return 0; +} + +void +TAGE_SC_L_8KB_StatisticalCorrector::scHistoryUpdate(Addr branch_pc, int brtype, + bool taken, BranchInfo * tage_bi, Addr corrTarget) +{ + // Non speculative SC histories update + if (brtype & 1) { + SC_8KB_ThreadHistory *sh = + static_cast(scHistory); + sh->globalHist = (sh->globalHist << 1) + taken; + } + + StatisticalCorrector::scHistoryUpdate(branch_pc, brtype, taken, tage_bi, + corrTarget); +} + +void +TAGE_SC_L_8KB_StatisticalCorrector::gUpdates(ThreadID tid, Addr pc, bool taken, + BranchInfo* bi, int64_t phist) +{ + SC_8KB_ThreadHistory *sh = static_cast(scHistory); + gUpdate(pc, taken, sh->globalHist, gm, ggehl, gnb, logGnb, wg, bi); + gUpdate(pc, taken, sh->bwHist, bwm, bwgehl, bwnb, logBwnb, wbw, bi); + gUpdate(pc, taken, sh->getLocalHistory(1, pc), lm, lgehl, lnb, logLnb, wl, + bi); + gUpdate(pc, taken, sh->imliCount, im, igehl, inb, logInb, wi, bi); +} + +TAGE_SC_L_8KB_StatisticalCorrector* +TAGE_SC_L_8KB_StatisticalCorrectorParams::create() +{ + return new TAGE_SC_L_8KB_StatisticalCorrector(this); +} + +TAGE_SC_L_8KB::TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params) + : TAGE_SC_L(params) +{ +} + +void +TAGE_SC_L_TAGE_8KB::initFoldedHistories(ThreadHistory & history) +{ + // Some hardcoded values are used here + // (they do not seem to depend on any parameter) + for (int i = 1; i <= nHistoryTables; i++) { + history.computeIndices[i].init( + histLengths[i], 17 + (2 * ((i - 1) / 2) % 4)); + history.computeTags[0][i].init( + history.computeIndices[i].origLength, 13); + history.computeTags[1][i].init( + history.computeIndices[i].origLength, 11); + DPRINTF(TageSCL, "HistLength:%d, TTSize:%d, TTTWidth:%d\n", + histLengths[i], logTagTableSizes[i], tagTableTagWidths[i]); + } +} + +int +TAGE_SC_L_TAGE_8KB::gindex_ext(int index, int bank) const +{ + return (index ^ (index >> logTagTableSizes[bank]) + ^ (index >> 2 * logTagTableSizes[bank])); +} + +uint16_t +TAGE_SC_L_TAGE_8KB::gtag(ThreadID tid, Addr pc, int bank) const +{ + int tag = (threadHistory[tid].computeIndices[bank - 1].comp << 2) ^ pc ^ + (pc >> instShiftAmt) ^ + threadHistory[tid].computeIndices[bank].comp; + int hlen = (histLengths[bank] > pathHistBits) ? pathHistBits : + histLengths[bank]; + + tag = (tag >> 1) ^ ((tag & 1) << 10) ^ + F(threadHistory[tid].pathHist, hlen, bank); + tag ^= threadHistory[tid].computeTags[0][bank].comp ^ + (threadHistory[tid].computeTags[1][bank].comp << 1); + + return ((tag ^ (tag >> tagTableTagWidths[bank])) + & ((ULL(1) << tagTableTagWidths[bank]) - 1)); +} + +void +TAGE_SC_L_TAGE_8KB::handleAllocAndUReset( + bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) +{ + if (!alloc) { + return; + } + + int penalty = 0; + int truePen = 0; + int numAllocated = 0; + bool maxAllocReached = false; + + for (int I = calcDep(bi); I < nHistoryTables; I += 2) { + // Handle the 2-way associativity for allocation + for (int j = 0; j < 2; ++j) { + int i = ((j == 0) ? I : (I ^ 1)) + 1; + if (i > nHistoryTables) { + break; + } + if (noSkip[i]) { + if (gtable[i][bi->tableIndices[i]].u == 0) { + gtable[i][bi->tableIndices[i]].u = + ((random_mt.random() & 31) == 0); + // protect randomly from fast replacement + gtable[i][bi->tableIndices[i]].tag = bi->tableTags[i]; + gtable[i][bi->tableIndices[i]].ctr = taken ? 0 : -1; + numAllocated++; + + if (numAllocated == maxNumAlloc) { + maxAllocReached = true; + break; + } + I += 2; + } else { + int8_t ctr = gtable[i][bi->tableIndices[i]].ctr; + if ((gtable[i][bi->tableIndices[i]].u == 1) & + (abs (2 * ctr + 1) == 1)) { + if ((random_mt.random() & 7) == 0) { + gtable[i][bi->tableIndices[i]].u = 0; + } + } else { + truePen++; + } + penalty++; + } + } else { + break; + } + } + if (maxAllocReached) { + break; + } + } + + tCounter += (truePen + penalty - 5 * numAllocated); + + handleUReset(); +} + +void +TAGE_SC_L_TAGE_8KB::resetUctr(uint8_t & u) +{ + // On real HW it should be u >>= 1 instead of if > 0 then u-- + if (u > 0) { + u--; + } +} + +void +TAGE_SC_L_TAGE_8KB::handleTAGEUpdate(Addr branch_pc, bool taken, + TAGEBase::BranchInfo* bi) +{ + if (bi->hitBank > 0) { + if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { + if (bi->longestMatchPred != taken) { // acts as a protection + if (bi->altBank > 0) { + int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; + if (abs (2 * ctr + 1) == 1) { + gtable[bi->altBank][bi->altBankIndex].u = 0; + } + + //just mute from protected to unprotected + ctrUpdate(gtable[bi->altBank][bi->altBankIndex].ctr, taken, + tagTableCounterBits); + ctr = gtable[bi->altBank][bi->altBankIndex].ctr; + if (abs (2 * ctr + 1) == 1) { + gtable[bi->altBank][bi->altBankIndex].u = 0; + } + } + if (bi->altBank == 0) { + baseUpdate(branch_pc, taken, bi); + } + } + } + + //just mute from protected to unprotected + if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { + gtable[bi->hitBank][bi->hitBankIndex].u = 0; + } + + ctrUpdate(gtable[bi->hitBank][bi->hitBankIndex].ctr, taken, + tagTableCounterBits); + + //sign changes: no way it can have been useful + if (abs (2 * gtable[bi->hitBank][bi->hitBankIndex].ctr + 1) == 1) { + gtable[bi->hitBank][bi->hitBankIndex].u = 0; + } + + if (bi->altTaken == taken) { + if (bi->altBank > 0) { + int8_t ctr = gtable[bi->altBank][bi->altBankIndex].ctr; + if (abs (2*ctr + 1) == 7) { + if (gtable[bi->hitBank][bi->hitBankIndex].u == 1) { + if (bi->longestMatchPred == taken) { + gtable[bi->hitBank][bi->hitBankIndex].u = 0; + } + } + } + } + } + } else { + baseUpdate(branch_pc, taken, bi); + } + + if ((bi->longestMatchPred != bi->altTaken) && + (bi->longestMatchPred == taken) && + (gtable[bi->hitBank][bi->hitBankIndex].u < (1 << tagTableUBits) -1)) { + gtable[bi->hitBank][bi->hitBankIndex].u++; + } +} + +TAGE_SC_L_TAGE_8KB* +TAGE_SC_L_TAGE_8KBParams::create() +{ + return new TAGE_SC_L_TAGE_8KB(this); +} + +TAGE_SC_L_8KB* +TAGE_SC_L_8KBParams::create() +{ + return new TAGE_SC_L_8KB(this); +} diff --git a/src/cpu/pred/tage_sc_l_8KB.hh b/src/cpu/pred/tage_sc_l_8KB.hh new file mode 100644 index 000000000..74193b020 --- /dev/null +++ b/src/cpu/pred/tage_sc_l_8KB.hh @@ -0,0 +1,116 @@ +/* + * Copyright (c) 2018 Metempsy Technology Consulting + * All rights reserved. + * + * 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. + * + * Author: André Seznec, Pau Cabre, Javier Bueno + * + */ + +/* + * 8KB TAGE-SC-L branch predictor (devised by Andre Seznec) + */ + +#ifndef __CPU_PRED_TAGE_SC_L_8KB +#define __CPU_PRED_TAGE_SC_L_8KB + +#include "cpu/pred/tage_sc_l.hh" +#include "params/TAGE_SC_L_8KB.hh" +#include "params/TAGE_SC_L_8KB_StatisticalCorrector.hh" +#include "params/TAGE_SC_L_TAGE_8KB.hh" + +class TAGE_SC_L_TAGE_8KB : public TAGE_SC_L_TAGE +{ + public: + TAGE_SC_L_TAGE_8KB(const TAGE_SC_L_TAGE_8KBParams *p) : TAGE_SC_L_TAGE(p) + {} + + void initFoldedHistories(ThreadHistory & history) override; + int gindex_ext(int index, int bank) const override; + + uint16_t gtag(ThreadID tid, Addr pc, int bank) const override; + + void handleAllocAndUReset( + bool alloc, bool taken, TAGEBase::BranchInfo* bi, int nrand) override; + + void handleTAGEUpdate( + Addr branch_pc, bool taken, TAGEBase::BranchInfo* bi) override; + + void resetUctr(uint8_t & u) override; +}; + +class TAGE_SC_L_8KB_StatisticalCorrector : public StatisticalCorrector +{ + // global branch history GEHL + const unsigned gnb; + const unsigned logGnb; + std::vector gm; + std::vector * ggehl; + std::vector wg; + + struct SC_8KB_ThreadHistory : public SCThreadHistory + { + SC_8KB_ThreadHistory() { + globalHist = 0; + } + int64_t globalHist; // global history + }; + + SCThreadHistory *makeThreadHistory() override; + + public: + TAGE_SC_L_8KB_StatisticalCorrector( + TAGE_SC_L_8KB_StatisticalCorrectorParams *p); + + unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi, int hitBank, + int altBank) const override; + + int gPredictions( ThreadID tid, Addr branch_pc, + BranchInfo* bi, int & lsum, int64_t phist) override; + + int gIndexLogsSubstr(int nbr, int i) override; + + void scHistoryUpdate( + Addr branch_pc, int brtype, bool taken, BranchInfo * tage_bi, + Addr corrTarget) override; + + void gUpdates(ThreadID tid, Addr pc, bool taken, BranchInfo* bi, + int64_t phist) override; +}; + +class TAGE_SC_L_8KB : public TAGE_SC_L +{ + public: + TAGE_SC_L_8KB(const TAGE_SC_L_8KBParams *params); +}; + +#endif // __CPU_PRED_TAGE_SC_L_8KB + -- 2.30.2