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 <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/17992
Reviewed-by: Jason Lowe-Power <jason@lowepower.com>
Maintainer: Jason Lowe-Power <jason@lowepower.com>
Tested-by: kokoro <noreply+kokoro@google.com>
diff --git a/src/cpu/pred/2bit_local.cc b/src/cpu/pred/2bit_local.cc
index 47ca651..e61c1e3 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);
@@ -71,14 +63,6 @@
}
void
-LocalBP::reset()
-{
- for (unsigned i = 0; i < localPredictorSets; ++i) {
- localCtrs[i].reset();
- }
-}
-
-void
LocalBP::btbUpdate(ThreadID tid, Addr branch_addr, void * &bp_history)
{
// Place holder for a function that is called to update predictor history when
@@ -90,13 +74,12 @@
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 @@
// 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 @@
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 764a66c..ef52974 100644
--- a/src/cpu/pred/2bit_local.hh
+++ b/src/cpu/pred/2bit_local.hh
@@ -97,8 +97,6 @@
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 @@
/** Calculates the local index based on the PC. */
inline unsigned getLocalIndex(Addr &PC);
+ /** Size of the local predictor. */
+ const unsigned localPredictorSize;
+
+ /** Number of bits of the local predictor's counters. */
+ const unsigned localCtrBits;
+
+ /** Number of sets. */
+ const unsigned localPredictorSets;
+
/** Array of counters that make up the local predictor. */
std::vector<SatCounter> localCtrs;
- /** Size of the local predictor. */
- unsigned localPredictorSize;
-
- /** Number of sets. */
- unsigned localPredictorSets;
-
- /** Number of bits of the local predictor's counters. */
- unsigned localCtrBits;
-
/** 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 e3a1e51..604e97e 100644
--- a/src/cpu/pred/bi_mode.cc
+++ b/src/cpu/pred/bi_mode.cc
@@ -44,25 +44,16 @@
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 @@
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 @@
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 @@
*/
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 e24c5ee..f28fdc9 100644
--- a/src/cpu/pred/bi_mode.hh
+++ b/src/cpu/pred/bi_mode.hh
@@ -87,13 +87,6 @@
bool finalPred;
};
- // choice predictors
- std::vector<SatCounter> choiceCounters;
- // taken direction predictors
- std::vector<SatCounter> takenCounters;
- // not-taken direction predictors
- std::vector<SatCounter> notTakenCounters;
-
std::vector<unsigned> globalHistoryReg;
unsigned globalHistoryBits;
unsigned historyRegisterMask;
@@ -105,6 +98,13 @@
unsigned globalCtrBits;
unsigned globalHistoryMask;
+ // choice predictors
+ std::vector<SatCounter> choiceCounters;
+ // taken direction predictors
+ std::vector<SatCounter> takenCounters;
+ // not-taken direction predictors
+ std::vector<SatCounter> notTakenCounters;
+
unsigned choiceThreshold;
unsigned takenThreshold;
unsigned notTakenThreshold;
diff --git a/src/cpu/pred/sat_counter.hh b/src/cpu/pred/sat_counter.hh
index 92d5d62..513419a 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 <cstdint>
+
#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 67beb09..0a145b4 100644
--- a/src/cpu/pred/tournament.cc
+++ b/src/cpu/pred/tournament.cc
@@ -49,10 +49,12 @@
: 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 @@
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 @@
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 @@
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 @@
// 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 @@
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 @@
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 @@
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 0eb69e1..7b16e72 100644
--- a/src/cpu/pred/tournament.hh
+++ b/src/cpu/pred/tournament.hh
@@ -174,9 +174,6 @@
/** Flag for invalid predictor index */
static const int invalidPredictorIndex = -1;
- /** Local counters. */
- std::vector<SatCounter> localCtrs;
-
/** Number of counters in the local predictor. */
unsigned localPredictorSize;
@@ -186,6 +183,9 @@
/** Number of bits of the local predictor's counters. */
unsigned localCtrBits;
+ /** Local counters. */
+ std::vector<SatCounter> localCtrs;
+
/** Array of local history table entries. */
std::vector<unsigned> localHistoryTable;
@@ -195,15 +195,15 @@
/** Number of bits for each entry of the local history table. */
unsigned localHistoryBits;
- /** Array of counters that make up the global predictor. */
- std::vector<SatCounter> 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<SatCounter> 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 @@
* used. */
unsigned historyRegisterMask;
- /** Array of counters that make up the choice predictor. */
- std::vector<SatCounter> 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<SatCounter> choiceCtrs;
+
/** Thresholds for the counter value; above the threshold is taken,
* equal to or below the threshold is not taken.
*/
