From 0def916836a5cfb570e765d2e1e4774419b56ec6 Mon Sep 17 00:00:00 2001 From: Daniel Date: Fri, 5 Apr 2019 11:28:53 +0200 Subject: [PATCH] cpu: Revamp saturating counters Revamp the SatCounter class, improving comments, implementing increment, decrement and read operators to solve an old todo, and adding missing error checking. Change-Id: Ia057c423c90652ebd966b6b91a3471b17800f933 Signed-off-by: Daniel Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/17992 Reviewed-by: Jason Lowe-Power Maintainer: Jason Lowe-Power Tested-by: kokoro --- src/cpu/pred/2bit_local.cc | 35 ++++--------- src/cpu/pred/2bit_local.hh | 18 +++---- src/cpu/pred/bi_mode.cc | 39 ++++++--------- src/cpu/pred/bi_mode.hh | 14 +++--- src/cpu/pred/sat_counter.hh | 99 +++++++++++++++++++++---------------- src/cpu/pred/tournament.cc | 65 ++++++++++-------------- src/cpu/pred/tournament.hh | 18 +++---- 7 files changed, 129 insertions(+), 159 deletions(-) diff --git a/src/cpu/pred/2bit_local.cc b/src/cpu/pred/2bit_local.cc index 47ca6514d..e61c1e3f6 100644 --- a/src/cpu/pred/2bit_local.cc +++ b/src/cpu/pred/2bit_local.cc @@ -38,29 +38,21 @@ LocalBP::LocalBP(const LocalBPParams *params) : BPredUnit(params), localPredictorSize(params->localPredictorSize), - localCtrBits(params->localCtrBits) + localCtrBits(params->localCtrBits), + localPredictorSets(localPredictorSize / localCtrBits), + localCtrs(localPredictorSets, SatCounter(localCtrBits)), + indexMask(localPredictorSets - 1) { if (!isPowerOf2(localPredictorSize)) { fatal("Invalid local predictor size!\n"); } - localPredictorSets = localPredictorSize / localCtrBits; - if (!isPowerOf2(localPredictorSets)) { fatal("Invalid number of local predictor sets! Check localCtrBits.\n"); } - // Setup the index mask. - indexMask = localPredictorSets - 1; - DPRINTF(Fetch, "index mask: %#x\n", indexMask); - // Setup the array of counters for the local predictor. - localCtrs.resize(localPredictorSets); - - for (unsigned i = 0; i < localPredictorSets; ++i) - localCtrs[i].setBits(localCtrBits); - DPRINTF(Fetch, "local predictor size: %i\n", localPredictorSize); @@ -70,14 +62,6 @@ LocalBP::LocalBP(const LocalBPParams *params) instShiftAmt); } -void -LocalBP::reset() -{ - for (unsigned i = 0; i < localPredictorSets; ++i) { - localCtrs[i].reset(); - } -} - void LocalBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history) { @@ -90,13 +74,12 @@ bool LocalBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history) { bool taken; - uint8_t counter_val; unsigned local_predictor_idx = getLocalIndex(branch_addr); DPRINTF(Fetch, "Looking up index %#x\n", local_predictor_idx); - counter_val = localCtrs[local_predictor_idx].read(); + uint8_t counter_val = localCtrs[local_predictor_idx]; DPRINTF(Fetch, "prediction is %i.\n", (int)counter_val); @@ -107,10 +90,10 @@ LocalBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history) // Speculative update. if (taken) { DPRINTF(Fetch, "Branch updated as taken.\n"); - localCtrs[local_predictor_idx].increment(); + localCtrs[local_predictor_idx]++; } else { DPRINTF(Fetch, "Branch updated as not taken.\n"); - localCtrs[local_predictor_idx].decrement(); + localCtrs[local_predictor_idx]--; } #endif @@ -137,10 +120,10 @@ LocalBP::update(ThreadID tid, Addr branch_addr, bool taken, void *bp_history, if (taken) { DPRINTF(Fetch, "Branch updated as taken.\n"); - localCtrs[local_predictor_idx].increment(); + localCtrs[local_predictor_idx]++; } else { DPRINTF(Fetch, "Branch updated as not taken.\n"); - localCtrs[local_predictor_idx].decrement(); + localCtrs[local_predictor_idx]--; } } diff --git a/src/cpu/pred/2bit_local.hh b/src/cpu/pred/2bit_local.hh index 764a66c74..ef52974b7 100644 --- a/src/cpu/pred/2bit_local.hh +++ b/src/cpu/pred/2bit_local.hh @@ -97,8 +97,6 @@ class LocalBP : public BPredUnit void squash(ThreadID tid, void *bp_history) { assert(bp_history == NULL); } - void reset(); - private: /** * Returns the taken/not taken prediction given the value of the @@ -111,20 +109,20 @@ class LocalBP : public BPredUnit /** Calculates the local index based on the PC. */ inline unsigned getLocalIndex(Addr &PC); - /** Array of counters that make up the local predictor. */ - std::vector localCtrs; - /** Size of the local predictor. */ - unsigned localPredictorSize; + const unsigned localPredictorSize; + + /** Number of bits of the local predictor's counters. */ + const unsigned localCtrBits; /** Number of sets. */ - unsigned localPredictorSets; + const unsigned localPredictorSets; - /** Number of bits of the local predictor's counters. */ - unsigned localCtrBits; + /** Array of counters that make up the local predictor. */ + std::vector localCtrs; /** Mask to get index bits. */ - unsigned indexMask; + const unsigned indexMask; }; #endif // __CPU_PRED_2BIT_LOCAL_PRED_HH__ diff --git a/src/cpu/pred/bi_mode.cc b/src/cpu/pred/bi_mode.cc index e3a1e51ae..604e97e19 100644 --- a/src/cpu/pred/bi_mode.cc +++ b/src/cpu/pred/bi_mode.cc @@ -44,25 +44,16 @@ BiModeBP::BiModeBP(const BiModeBPParams *params) choicePredictorSize(params->choicePredictorSize), choiceCtrBits(params->choiceCtrBits), globalPredictorSize(params->globalPredictorSize), - globalCtrBits(params->globalCtrBits) + globalCtrBits(params->globalCtrBits), + choiceCounters(choicePredictorSize, SatCounter(choiceCtrBits)), + takenCounters(globalPredictorSize, SatCounter(globalCtrBits)), + notTakenCounters(globalPredictorSize, SatCounter(globalCtrBits)) { if (!isPowerOf2(choicePredictorSize)) fatal("Invalid choice predictor size.\n"); if (!isPowerOf2(globalPredictorSize)) fatal("Invalid global history predictor size.\n"); - choiceCounters.resize(choicePredictorSize); - takenCounters.resize(globalPredictorSize); - notTakenCounters.resize(globalPredictorSize); - - for (int i = 0; i < choicePredictorSize; ++i) { - choiceCounters[i].setBits(choiceCtrBits); - } - for (int i = 0; i < globalPredictorSize; ++i) { - takenCounters[i].setBits(globalCtrBits); - notTakenCounters[i].setBits(globalCtrBits); - } - historyRegisterMask = mask(globalHistoryBits); choiceHistoryMask = choicePredictorSize - 1; globalHistoryMask = globalPredictorSize - 1; @@ -120,11 +111,11 @@ BiModeBP::lookup(ThreadID tid, Addr branchAddr, void * &bpHistory) assert(choiceHistoryIdx < choicePredictorSize); assert(globalHistoryIdx < globalPredictorSize); - bool choicePrediction = choiceCounters[choiceHistoryIdx].read() + bool choicePrediction = choiceCounters[choiceHistoryIdx] > choiceThreshold; - bool takenGHBPrediction = takenCounters[globalHistoryIdx].read() + bool takenGHBPrediction = takenCounters[globalHistoryIdx] > takenThreshold; - bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read() + bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx] > notTakenThreshold; bool finalPrediction; @@ -186,16 +177,16 @@ BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, if (history->takenUsed) { // if the taken array's prediction was used, update it if (taken) { - takenCounters[globalHistoryIdx].increment(); + takenCounters[globalHistoryIdx]++; } else { - takenCounters[globalHistoryIdx].decrement(); + takenCounters[globalHistoryIdx]--; } } else { // if the not-taken array's prediction was used, update it if (taken) { - notTakenCounters[globalHistoryIdx].increment(); + notTakenCounters[globalHistoryIdx]++; } else { - notTakenCounters[globalHistoryIdx].decrement(); + notTakenCounters[globalHistoryIdx]--; } } @@ -212,17 +203,17 @@ BiModeBP::update(ThreadID tid, Addr branchAddr, bool taken, void *bpHistory, */ if (history->finalPred == history->takenUsed) { if (taken) { - choiceCounters[choiceHistoryIdx].increment(); + choiceCounters[choiceHistoryIdx]++; } else { - choiceCounters[choiceHistoryIdx].decrement(); + choiceCounters[choiceHistoryIdx]--; } } } else { // always update the choice predictor on an incorrect prediction if (taken) { - choiceCounters[choiceHistoryIdx].increment(); + choiceCounters[choiceHistoryIdx]++; } else { - choiceCounters[choiceHistoryIdx].decrement(); + choiceCounters[choiceHistoryIdx]--; } } diff --git a/src/cpu/pred/bi_mode.hh b/src/cpu/pred/bi_mode.hh index e24c5ee5f..f28fdc926 100644 --- a/src/cpu/pred/bi_mode.hh +++ b/src/cpu/pred/bi_mode.hh @@ -87,13 +87,6 @@ class BiModeBP : public BPredUnit bool finalPred; }; - // choice predictors - std::vector choiceCounters; - // taken direction predictors - std::vector takenCounters; - // not-taken direction predictors - std::vector notTakenCounters; - std::vector globalHistoryReg; unsigned globalHistoryBits; unsigned historyRegisterMask; @@ -105,6 +98,13 @@ class BiModeBP : public BPredUnit unsigned globalCtrBits; unsigned globalHistoryMask; + // choice predictors + std::vector choiceCounters; + // taken direction predictors + std::vector takenCounters; + // not-taken direction predictors + std::vector notTakenCounters; + unsigned choiceThreshold; unsigned takenThreshold; unsigned notTakenThreshold; diff --git a/src/cpu/pred/sat_counter.hh b/src/cpu/pred/sat_counter.hh index 92d5d628c..513419a05 100644 --- a/src/cpu/pred/sat_counter.hh +++ b/src/cpu/pred/sat_counter.hh @@ -1,4 +1,16 @@ /* + * Copyright (c) 2019 Inria + * All rights reserved. + * + * The license below extends only to copyright in the software and shall + * not be construed as granting a license to any other intellectual + * property including but not limited to intellectual property relating + * to a hardware implementation of the functionality of the software + * licensed hereunder. You may use the software subject to the license + * terms below provided that you ensure that this notice is replicated + * unmodified and in its entirety in all distributions of the software, + * modified or unmodified, in source code or in binary form. + * * Copyright (c) 2005-2006 The Regents of The University of Michigan * All rights reserved. * @@ -26,87 +38,88 @@ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * * Authors: Kevin Lim + * Daniel Carvalho */ #ifndef __CPU_PRED_SAT_COUNTER_HH__ #define __CPU_PRED_SAT_COUNTER_HH__ +#include + #include "base/logging.hh" #include "base/types.hh" /** - * Private counter class for the internal saturating counters. * Implements an n bit saturating counter and provides methods to * increment, decrement, and read it. - * @todo Consider making this something that more closely mimics a - * built in class so you can use ++ or --. */ class SatCounter { public: /** - * Constructor for the counter. - */ - SatCounter() - : initialVal(0), counter(0) - { } - - /** - * Constructor for the counter. + * Constructor for the counter. The explicit keyword is used to make + * sure the user does not assign a number to the counter thinking it + * will be used as a counter value when it is in fact used as the number + * of bits. + * * @param bits How many bits the counter will have. + * @param initial_val Starting value for the counter. */ - SatCounter(unsigned bits) - : initialVal(0), maxVal((1 << bits) - 1), counter(0) - { } - - /** - * Constructor for the counter. - * @param bits How many bits the counter will have. - * @param initial_val Starting value for each counter. - */ - SatCounter(unsigned bits, uint8_t initial_val) + explicit SatCounter(unsigned bits, uint8_t initial_val = 0) : initialVal(initial_val), maxVal((1 << bits) - 1), counter(initial_val) { - // Check to make sure initial value doesn't exceed the max - // counter value. - if (initial_val > maxVal) { - fatal("BP: Initial counter value exceeds max size."); - } + fatal_if(bits > 8*sizeof(uint8_t), + "Number of bits exceeds counter size"); + fatal_if(initial_val > maxVal, + "Saturating counter's Initial value exceeds max value."); } - /** - * Sets the number of bits. - */ - void setBits(unsigned bits) { maxVal = (1 << bits) - 1; } - - void reset() { counter = initialVal; } - - /** - * Increments the counter's current value. - */ - void increment() + /** Pre-increment operator. */ + SatCounter& + operator++() { if (counter < maxVal) { ++counter; } + return *this; } - /** - * Decrements the counter's current value. - */ - void decrement() + /** Post-increment operator. */ + SatCounter + operator++(int) + { + SatCounter old_counter = *this; + ++*this; + return old_counter; + } + + /** Pre-decrement operator. */ + SatCounter& + operator--() { if (counter > 0) { --counter; } + return *this; + } + + /** Post-decrement operator. */ + SatCounter + operator--(int) + { + SatCounter old_counter = *this; + --*this; + return old_counter; } /** * Read the counter's value. */ - uint8_t read() const - { return counter; } + operator uint8_t() const { return counter; } + + /** Reset the counter to its initial value. */ + void reset() { counter = initialVal; } private: uint8_t initialVal; diff --git a/src/cpu/pred/tournament.cc b/src/cpu/pred/tournament.cc index 67beb09ef..0a145b4d0 100644 --- a/src/cpu/pred/tournament.cc +++ b/src/cpu/pred/tournament.cc @@ -49,10 +49,12 @@ TournamentBP::TournamentBP(const TournamentBPParams *params) : BPredUnit(params), localPredictorSize(params->localPredictorSize), localCtrBits(params->localCtrBits), + localCtrs(localPredictorSize, SatCounter(localCtrBits)), localHistoryTableSize(params->localHistoryTableSize), localHistoryBits(ceilLog2(params->localPredictorSize)), globalPredictorSize(params->globalPredictorSize), globalCtrBits(params->globalCtrBits), + globalCtrs(globalPredictorSize, SatCounter(globalCtrBits)), globalHistory(params->numThreads, 0), globalHistoryBits( ceilLog2(params->globalPredictorSize) > @@ -60,7 +62,8 @@ TournamentBP::TournamentBP(const TournamentBPParams *params) ceilLog2(params->globalPredictorSize) : ceilLog2(params->choicePredictorSize)), choicePredictorSize(params->choicePredictorSize), - choiceCtrBits(params->choiceCtrBits) + choiceCtrBits(params->choiceCtrBits), + choiceCtrs(choicePredictorSize, SatCounter(choiceCtrBits)) { if (!isPowerOf2(localPredictorSize)) { fatal("Invalid local predictor size!\n"); @@ -70,12 +73,6 @@ TournamentBP::TournamentBP(const TournamentBPParams *params) fatal("Invalid global predictor size!\n"); } - //Set up the array of counters for the local predictor - localCtrs.resize(localPredictorSize); - - for (int i = 0; i < localPredictorSize; ++i) - localCtrs[i].setBits(localCtrBits); - localPredictorMask = mask(localHistoryBits); if (!isPowerOf2(localHistoryTableSize)) { @@ -88,12 +85,6 @@ TournamentBP::TournamentBP(const TournamentBPParams *params) for (int i = 0; i < localHistoryTableSize; ++i) localHistoryTable[i] = 0; - //Setup the array of counters for the global predictor - globalCtrs.resize(globalPredictorSize); - - for (int i = 0; i < globalPredictorSize; ++i) - globalCtrs[i].setBits(globalCtrBits); - // Set up the global history mask // this is equivalent to mask(log2(globalPredictorSize) globalHistoryMask = globalPredictorSize - 1; @@ -106,12 +97,6 @@ TournamentBP::TournamentBP(const TournamentBPParams *params) // this is equivalent to mask(log2(choicePredictorSize) choiceHistoryMask = choicePredictorSize - 1; - //Setup the array of counters for the choice predictor - choiceCtrs.resize(choicePredictorSize); - - for (int i = 0; i < choicePredictorSize; ++i) - choiceCtrs[i].setBits(choiceCtrBits); - //Set up historyRegisterMask historyRegisterMask = mask(globalHistoryBits); @@ -201,15 +186,15 @@ TournamentBP::lookup(ThreadID tid, Addr branch_addr, void * &bp_history) local_history_idx = calcLocHistIdx(branch_addr); local_predictor_idx = localHistoryTable[local_history_idx] & localPredictorMask; - local_prediction = localCtrs[local_predictor_idx].read() > localThreshold; + local_prediction = localCtrs[local_predictor_idx] > localThreshold; //Lookup in the global predictor to get its branch prediction global_prediction = globalThreshold < - globalCtrs[globalHistory[tid] & globalHistoryMask].read(); + globalCtrs[globalHistory[tid] & globalHistoryMask]; //Lookup in the choice predictor to see which one to use choice_prediction = choiceThreshold < - choiceCtrs[globalHistory[tid] & choiceHistoryMask].read(); + choiceCtrs[globalHistory[tid] & choiceHistoryMask]; // Create BPHistory and pass it back to be recorded. BPHistory *history = new BPHistory; @@ -308,16 +293,16 @@ TournamentBP::update(ThreadID tid, Addr branch_addr, bool taken, if (history->localPredTaken != history->globalPredTaken && old_local_pred_valid) { - // If the local prediction matches the actual outcome, - // decrement the counter. Otherwise increment the - // counter. - unsigned choice_predictor_idx = - history->globalHistory & choiceHistoryMask; - if (history->localPredTaken == taken) { - choiceCtrs[choice_predictor_idx].decrement(); - } else if (history->globalPredTaken == taken) { - choiceCtrs[choice_predictor_idx].increment(); - } + // If the local prediction matches the actual outcome, + // decrement the counter. Otherwise increment the + // counter. + unsigned choice_predictor_idx = + history->globalHistory & choiceHistoryMask; + if (history->localPredTaken == taken) { + choiceCtrs[choice_predictor_idx]--; + } else if (history->globalPredTaken == taken) { + choiceCtrs[choice_predictor_idx]++; + } } // Update the counters with the proper @@ -328,15 +313,15 @@ TournamentBP::update(ThreadID tid, Addr branch_addr, bool taken, unsigned global_predictor_idx = history->globalHistory & globalHistoryMask; if (taken) { - globalCtrs[global_predictor_idx].increment(); - if (old_local_pred_valid) { - localCtrs[old_local_pred_index].increment(); - } + globalCtrs[global_predictor_idx]++; + if (old_local_pred_valid) { + localCtrs[old_local_pred_index]++; + } } else { - globalCtrs[global_predictor_idx].decrement(); - if (old_local_pred_valid) { - localCtrs[old_local_pred_index].decrement(); - } + globalCtrs[global_predictor_idx]--; + if (old_local_pred_valid) { + localCtrs[old_local_pred_index]--; + } } // We're done with this history, now delete it. diff --git a/src/cpu/pred/tournament.hh b/src/cpu/pred/tournament.hh index 0eb69e12f..7b16e7224 100644 --- a/src/cpu/pred/tournament.hh +++ b/src/cpu/pred/tournament.hh @@ -174,9 +174,6 @@ class TournamentBP : public BPredUnit /** Flag for invalid predictor index */ static const int invalidPredictorIndex = -1; - /** Local counters. */ - std::vector localCtrs; - /** Number of counters in the local predictor. */ unsigned localPredictorSize; @@ -186,6 +183,9 @@ class TournamentBP : public BPredUnit /** Number of bits of the local predictor's counters. */ unsigned localCtrBits; + /** Local counters. */ + std::vector localCtrs; + /** Array of local history table entries. */ std::vector localHistoryTable; @@ -195,15 +195,15 @@ class TournamentBP : public BPredUnit /** Number of bits for each entry of the local history table. */ unsigned localHistoryBits; - /** Array of counters that make up the global predictor. */ - std::vector globalCtrs; - /** Number of entries in the global predictor. */ unsigned globalPredictorSize; /** Number of bits of the global predictor's counters. */ unsigned globalCtrBits; + /** Array of counters that make up the global predictor. */ + std::vector globalCtrs; + /** Global history register. Contains as much history as specified by * globalHistoryBits. Actual number of bits used is determined by * globalHistoryMask and choiceHistoryMask. */ @@ -225,15 +225,15 @@ class TournamentBP : public BPredUnit * used. */ unsigned historyRegisterMask; - /** Array of counters that make up the choice predictor. */ - std::vector choiceCtrs; - /** Number of entries in the choice predictor. */ unsigned choicePredictorSize; /** Number of bits in the choice predictor's counters. */ unsigned choiceCtrBits; + /** Array of counters that make up the choice predictor. */ + std::vector choiceCtrs; + /** Thresholds for the counter value; above the threshold is taken, * equal to or below the threshold is not taken. */ -- 2.30.2