changeset 515891d9057a in /z/repo/gem5
details: http://repo.gem5.org/gem5?cmd=changeset;node=515891d9057a
description:
TournamentBP: Fix some bugs with table sizes and counters
globalHistoryBits, globalPredictorSize, and choicePredictorSize are
decoupled.
globalHistoryBits controls how much history is kept, global and choice
predictor sizes control how much of that history is used when accessing
predictor tables. This way, global and choice predictors can actually be
different sizes, and it is no longer possible to walk off the predictor
arrays
and cause a seg fault.
There are now individual thresholds for choice, global, and local
saturating
counters, so that taken/not taken decisions are correct even when the
predictors' counters' sizes are different.
The interface for localPredictorSize has been removed from TournamentBP
because
the value can be calculated from localHistoryBits.
Committed by: Nilay Vaish <[email protected]>
diffstat:
configs/common/O3_ARM_v7a.py | 1 -
src/cpu/inorder/resources/bpred_unit.cc | 3 +-
src/cpu/o3/bpred_unit_impl.hh | 3 +-
src/cpu/pred/tournament.cc | 92 ++++++++++++++++++++------------
src/cpu/pred/tournament.hh | 46 +++++++++------
5 files changed, 85 insertions(+), 60 deletions(-)
diffs (truncated from 372 to 300 lines):
diff -r 63bd743e1acb -r 515891d9057a configs/common/O3_ARM_v7a.py
--- a/configs/common/O3_ARM_v7a.py Thu Dec 06 05:25:40 2012 -0600
+++ b/configs/common/O3_ARM_v7a.py Thu Dec 06 09:31:06 2012 -0600
@@ -90,7 +90,6 @@
class O3_ARM_v7a_3(DerivO3CPU):
predType = "tournament"
- localPredictorSize = 64
localCtrBits = 2
localHistoryTableSize = 64
localHistoryBits = 6
diff -r 63bd743e1acb -r 515891d9057a src/cpu/inorder/resources/bpred_unit.cc
--- a/src/cpu/inorder/resources/bpred_unit.cc Thu Dec 06 05:25:40 2012 -0600
+++ b/src/cpu/inorder/resources/bpred_unit.cc Thu Dec 06 09:31:06 2012 -0600
@@ -53,8 +53,7 @@
params->instShiftAmt);
predictor = Local;
} else if (params->predType == "tournament") {
- tournamentBP = new TournamentBP(params->localPredictorSize,
- params->localCtrBits,
+ tournamentBP = new TournamentBP(params->localCtrBits,
params->localHistoryTableSize,
params->localHistoryBits,
params->globalPredictorSize,
diff -r 63bd743e1acb -r 515891d9057a src/cpu/o3/bpred_unit_impl.hh
--- a/src/cpu/o3/bpred_unit_impl.hh Thu Dec 06 05:25:40 2012 -0600
+++ b/src/cpu/o3/bpred_unit_impl.hh Thu Dec 06 09:31:06 2012 -0600
@@ -65,8 +65,7 @@
params->instShiftAmt);
predictor = Local;
} else if (params->predType == "tournament") {
- tournamentBP = new TournamentBP(params->localPredictorSize,
- params->localCtrBits,
+ tournamentBP = new TournamentBP(params->localCtrBits,
params->localHistoryTableSize,
params->localHistoryBits,
params->globalPredictorSize,
diff -r 63bd743e1acb -r 515891d9057a src/cpu/pred/tournament.cc
--- a/src/cpu/pred/tournament.cc Thu Dec 06 05:25:40 2012 -0600
+++ b/src/cpu/pred/tournament.cc Thu Dec 06 09:31:06 2012 -0600
@@ -40,11 +40,11 @@
* Authors: Kevin Lim
*/
+#include "base/bitfield.hh"
#include "base/intmath.hh"
#include "cpu/pred/tournament.hh"
-TournamentBP::TournamentBP(unsigned _localPredictorSize,
- unsigned _localCtrBits,
+TournamentBP::TournamentBP(unsigned _localCtrBits,
unsigned _localHistoryTableSize,
unsigned _localHistoryBits,
unsigned _globalPredictorSize,
@@ -53,28 +53,25 @@
unsigned _choicePredictorSize,
unsigned _choiceCtrBits,
unsigned _instShiftAmt)
- : localPredictorSize(_localPredictorSize),
- localCtrBits(_localCtrBits),
+ : localCtrBits(_localCtrBits),
localHistoryTableSize(_localHistoryTableSize),
localHistoryBits(_localHistoryBits),
globalPredictorSize(_globalPredictorSize),
globalCtrBits(_globalCtrBits),
globalHistoryBits(_globalHistoryBits),
- choicePredictorSize(_globalPredictorSize),
+ choicePredictorSize(_choicePredictorSize),
choiceCtrBits(_choiceCtrBits),
instShiftAmt(_instShiftAmt)
{
- if (!isPowerOf2(localPredictorSize)) {
- fatal("Invalid local predictor size!\n");
- }
+ localPredictorSize = ULL(1) << localHistoryBits;
- //Setup the array of counters for the local predictor
+ //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 = floorPow2(localPredictorSize) - 1;
+ localPredictorMask = mask(localHistoryBits);
if (!isPowerOf2(localHistoryTableSize)) {
fatal("Invalid local history table size!\n");
@@ -86,9 +83,6 @@
for (int i = 0; i < localHistoryTableSize; ++i)
localHistoryTable[i] = 0;
- // Setup the local history mask
- localHistoryMask = (1 << localHistoryBits) - 1;
-
if (!isPowerOf2(globalPredictorSize)) {
fatal("Invalid global predictor size!\n");
}
@@ -101,21 +95,45 @@
//Clear the global history
globalHistory = 0;
- // Setup the global history mask
- globalHistoryMask = (1 << globalHistoryBits) - 1;
+ // Set up the global history mask
+ // this is equivalent to mask(log2(globalPredictorSize)
+ globalHistoryMask = globalPredictorSize - 1;
if (!isPowerOf2(choicePredictorSize)) {
fatal("Invalid choice predictor size!\n");
}
+ // Set up choiceHistoryMask
+ // 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);
- // @todo: Allow for different thresholds between the predictors.
- threshold = (1 << (localCtrBits - 1)) - 1;
+ //Set up historyRegisterMask
+ historyRegisterMask = mask(globalHistoryBits);
+
+ //Check that predictors don't use more bits than they have available
+ if (globalHistoryMask > historyRegisterMask) {
+ fatal("Global predictor too large for global history bits!\n");
+ }
+ if (choiceHistoryMask > historyRegisterMask) {
+ fatal("Choice predictor too large for global history bits!\n");
+ }
+
+ if (globalHistoryMask < historyRegisterMask &&
+ choiceHistoryMask < historyRegisterMask) {
+ inform("More global history bits than required by predictors\n");
+ }
+
+ // Set thresholds for the three predictors' counters
+ // This is equivalent to (2^(Ctr))/2 - 1
+ localThreshold = (ULL(1) << (localCtrBits - 1)) - 1;
+ globalThreshold = (ULL(1) << (globalCtrBits - 1)) - 1;
+ choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
}
inline
@@ -131,7 +149,7 @@
TournamentBP::updateGlobalHistTaken()
{
globalHistory = (globalHistory << 1) | 1;
- globalHistory = globalHistory & globalHistoryMask;
+ globalHistory = globalHistory & historyRegisterMask;
}
inline
@@ -139,7 +157,7 @@
TournamentBP::updateGlobalHistNotTaken()
{
globalHistory = (globalHistory << 1);
- globalHistory = globalHistory & globalHistoryMask;
+ globalHistory = globalHistory & historyRegisterMask;
}
inline
@@ -163,8 +181,8 @@
TournamentBP::BTBUpdate(Addr &branch_addr, void * &bp_history)
{
unsigned local_history_idx = calcLocHistIdx(branch_addr);
- //Update Global History to Not Taken
- globalHistory = globalHistory & (globalHistoryMask - 1);
+ //Update Global History to Not Taken (clear LSB)
+ globalHistory &= (historyRegisterMask & ~ULL(1));
//Update Local History to Not Taken
localHistoryTable[local_history_idx] =
localHistoryTable[local_history_idx] & (localPredictorMask & ~ULL(1));
@@ -184,13 +202,15 @@
local_history_idx = calcLocHistIdx(branch_addr);
local_predictor_idx = localHistoryTable[local_history_idx]
& localPredictorMask;
- local_prediction = localCtrs[local_predictor_idx].read() > threshold;
+ local_prediction = localCtrs[local_predictor_idx].read() > localThreshold;
//Lookup in the global predictor to get its branch prediction
- global_prediction = globalCtrs[globalHistory].read() > threshold;
+ global_prediction =
+ globalCtrs[globalHistory & globalHistoryMask].read() > globalThreshold;
//Lookup in the choice predictor to see which one to use
- choice_prediction = choiceCtrs[globalHistory].read() > threshold;
+ choice_prediction =
+ choiceCtrs[globalHistory & choiceHistoryMask].read() > choiceThreshold;
// Create BPHistory and pass it back to be recorded.
BPHistory *history = new BPHistory;
@@ -201,9 +221,7 @@
history->localHistory = local_predictor_idx;
bp_history = (void *)history;
- assert(globalHistory < globalPredictorSize &&
- local_history_idx < localHistoryTableSize &&
- local_predictor_idx < localPredictorSize);
+ assert(local_history_idx < localHistoryTableSize);
// Commented code is for doing speculative update of counters and
// all histories.
@@ -283,10 +301,12 @@
// If the local prediction matches the actual outcome,
// decerement the counter. Otherwise increment the
// counter.
+ unsigned choice_predictor_idx =
+ history->globalHistory & choiceHistoryMask;
if (history->localPredTaken == taken) {
- choiceCtrs[history->globalHistory].decrement();
+ choiceCtrs[choice_predictor_idx].decrement();
} else if (history->globalPredTaken == taken) {
- choiceCtrs[history->globalHistory].increment();
+ choiceCtrs[choice_predictor_idx].increment();
}
}
@@ -295,13 +315,15 @@
// resolution of the branch. Global history is updated
// speculatively and restored upon squash() calls, so it does not
// need to be updated.
+ unsigned global_predictor_idx =
+ history->globalHistory & globalHistoryMask;
if (taken) {
- globalCtrs[history->globalHistory].increment();
+ globalCtrs[global_predictor_idx].increment();
if (old_local_pred_valid) {
localCtrs[old_local_pred_index].increment();
}
} else {
- globalCtrs[history->globalHistory].decrement();
+ globalCtrs[global_predictor_idx].decrement();
if (old_local_pred_valid) {
localCtrs[old_local_pred_index].decrement();
}
@@ -310,14 +332,14 @@
if (squashed) {
if (taken) {
globalHistory = (history->globalHistory << 1) | 1;
- globalHistory = globalHistory & globalHistoryMask;
+ globalHistory = globalHistory & historyRegisterMask;
if (old_local_pred_valid) {
localHistoryTable[local_history_idx] =
(history->localHistory << 1) | 1;
}
} else {
globalHistory = (history->globalHistory << 1);
- globalHistory = globalHistory & globalHistoryMask;
+ globalHistory = globalHistory & historyRegisterMask;
if (old_local_pred_valid) {
localHistoryTable[local_history_idx] =
history->localHistory << 1;
@@ -330,9 +352,7 @@
}
- assert(globalHistory < globalPredictorSize &&
- local_history_idx < localHistoryTableSize &&
- local_predictor_idx < localPredictorSize);
+ assert(local_history_idx < localHistoryTableSize);
}
diff -r 63bd743e1acb -r 515891d9057a src/cpu/pred/tournament.hh
--- a/src/cpu/pred/tournament.hh Thu Dec 06 05:25:40 2012 -0600
+++ b/src/cpu/pred/tournament.hh Thu Dec 06 09:31:06 2012 -0600
@@ -63,8 +63,7 @@
/**
* Default branch predictor constructor.
*/
- TournamentBP(unsigned localPredictorSize,
- unsigned localCtrBits,
+ TournamentBP(unsigned localCtrBits,
unsigned localHistoryTableSize,
unsigned localHistoryBits,
unsigned globalPredictorSize,
@@ -181,10 +180,10 @@
/** Local counters. */
std::vector<SatCounter> localCtrs;
- /** Size of the local predictor. */
+ /** Number of counters in the local predictor. */
unsigned localPredictorSize;
- /** Mask to get the proper index bits into the predictor. */
+ /** Mask to truncate values stored in the local history table. */
unsigned localPredictorMask;
/** Number of bits of the local predictor's counters. */
@@ -193,42 +192,49 @@
/** Array of local history table entries. */
std::vector<unsigned> localHistoryTable;
- /** Size of the local history table. */
+ /** Number of entries in the local history table. */
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
