summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorAnthony Gutierrez <atgutier@umich.edu>2014-06-30 13:50:03 -0400
committerAnthony Gutierrez <atgutier@umich.edu>2014-06-30 13:50:03 -0400
commitf34a8f0d6163fe82849d494bf78c0f5ec175861c (patch)
treeb3133ce45f089479408e25b73347a14ead3c620f /src
parentdb267da8221ce4905e08e84967096d7a9fa23ca6 (diff)
downloadgem5-f34a8f0d6163fe82849d494bf78c0f5ec175861c.tar.xz
cpu: implement a bi-mode branch predictor
Diffstat (limited to 'src')
-rw-r--r--src/cpu/o3/fetch_impl.hh4
-rw-r--r--src/cpu/pred/BranchPredictor.py2
-rw-r--r--src/cpu/pred/SConscript1
-rw-r--r--src/cpu/pred/bi_mode.cc245
-rw-r--r--src/cpu/pred/bi_mode.hh114
-rw-r--r--src/cpu/pred/bpred_unit.cc3
-rw-r--r--src/cpu/pred/bpred_unit.hh4
7 files changed, 368 insertions, 5 deletions
diff --git a/src/cpu/o3/fetch_impl.hh b/src/cpu/o3/fetch_impl.hh
index 93dc2e250..98c1b6998 100644
--- a/src/cpu/o3/fetch_impl.hh
+++ b/src/cpu/o3/fetch_impl.hh
@@ -1332,8 +1332,8 @@ DefaultFetch<Impl>::fetch(bool &status_change)
nextPC = thisPC;
- // If we're branching after this instruction, quite fetching
- // from the same block then.
+ // If we're branching after this instruction, quit fetching
+ // from the same block.
predictedBranch |= thisPC.branching();
predictedBranch |=
lookupAndUpdateNextPC(instruction, nextPC);
diff --git a/src/cpu/pred/BranchPredictor.py b/src/cpu/pred/BranchPredictor.py
index 07fc840b8..1bdc71d4d 100644
--- a/src/cpu/pred/BranchPredictor.py
+++ b/src/cpu/pred/BranchPredictor.py
@@ -36,7 +36,7 @@ class BranchPredictor(SimObject):
numThreads = Param.Unsigned(1, "Number of threads")
predType = Param.String("tournament",
- "Branch predictor type ('local', 'tournament')")
+ "Branch predictor type ('local', 'tournament', 'bi-mode')")
localPredictorSize = Param.Unsigned(2048, "Size of local predictor")
localCtrBits = Param.Unsigned(2, "Bits per counter")
localHistoryTableSize = Param.Unsigned(2048, "Size of local history table")
diff --git a/src/cpu/pred/SConscript b/src/cpu/pred/SConscript
index d30a7a04d..5b2ecceef 100644
--- a/src/cpu/pred/SConscript
+++ b/src/cpu/pred/SConscript
@@ -38,5 +38,6 @@ if 'InOrderCPU' in env['CPU_MODELS'] or 'O3CPU' in env['CPU_MODELS']:
Source('btb.cc')
Source('ras.cc')
Source('tournament.cc')
+ Source ('bi_mode.cc')
DebugFlag('FreeList')
DebugFlag('Branch')
diff --git a/src/cpu/pred/bi_mode.cc b/src/cpu/pred/bi_mode.cc
new file mode 100644
index 000000000..cb4365ed5
--- /dev/null
+++ b/src/cpu/pred/bi_mode.cc
@@ -0,0 +1,245 @@
+/*
+ * Copyright (c) 2014 The Regents of The University of Michigan
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Anthony Gutierrez
+ */
+
+/* @file
+ * Implementation of a bi-mode branch predictor
+ */
+
+#include "base/bitfield.hh"
+#include "base/intmath.hh"
+#include "cpu/pred/bi_mode.hh"
+
+BiModeBP::BiModeBP(const Params *params)
+ : BPredUnit(params), instShiftAmt(params->instShiftAmt),
+ globalHistoryReg(0),
+ globalHistoryBits(ceilLog2(params->globalPredictorSize)),
+ choicePredictorSize(params->choicePredictorSize),
+ choiceCtrBits(params->choiceCtrBits),
+ globalPredictorSize(params->globalPredictorSize),
+ globalCtrBits(params->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;
+
+ choiceThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
+ takenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
+ notTakenThreshold = (ULL(1) << (choiceCtrBits - 1)) - 1;
+}
+
+/*
+ * For an unconditional branch we set its history such that
+ * everything is set to taken. I.e., its choice predictor
+ * chooses the taken array and the taken array predicts taken.
+ */
+void
+BiModeBP::uncondBranch(void * &bpHistory)
+{
+ BPHistory *history = new BPHistory;
+ history->globalHistoryReg = globalHistoryReg;
+ history->takenUsed = true;
+ history->takenPred = true;
+ history->notTakenPred = true;
+ history->finalPred = true;
+ bpHistory = static_cast<void*>(history);
+ updateGlobalHistReg(true);
+}
+
+void
+BiModeBP::squash(void *bpHistory)
+{
+ BPHistory *history = static_cast<BPHistory*>(bpHistory);
+ globalHistoryReg = history->globalHistoryReg;
+
+ delete history;
+}
+
+/*
+ * Here we lookup the actual branch prediction. We use the PC to
+ * identify the bias of a particular branch, which is based on the
+ * prediction in the choice array. A hash of the global history
+ * register and a branch's PC is used to index into both the taken
+ * and not-taken predictors, which both present a prediction. The
+ * choice array's prediction is used to select between the two
+ * direction predictors for the final branch prediction.
+ */
+bool
+BiModeBP::lookup(Addr branchAddr, void * &bpHistory)
+{
+ unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
+ & choiceHistoryMask);
+ unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
+ ^ globalHistoryReg)
+ & globalHistoryMask);
+
+ assert(choiceHistoryIdx < choicePredictorSize);
+ assert(globalHistoryIdx < globalPredictorSize);
+
+ bool choicePrediction = choiceCounters[choiceHistoryIdx].read()
+ > choiceThreshold;
+ bool takenGHBPrediction = takenCounters[globalHistoryIdx].read()
+ > takenThreshold;
+ bool notTakenGHBPrediction = notTakenCounters[globalHistoryIdx].read()
+ > notTakenThreshold;
+ bool finalPrediction;
+
+ BPHistory *history = new BPHistory;
+ history->globalHistoryReg = globalHistoryReg;
+ history->takenUsed = choicePrediction;
+ history->takenPred = takenGHBPrediction;
+ history->notTakenPred = notTakenGHBPrediction;
+
+ if (choicePrediction) {
+ finalPrediction = takenGHBPrediction;
+ } else {
+ finalPrediction = notTakenGHBPrediction;
+ }
+
+ history->finalPred = finalPrediction;
+ bpHistory = static_cast<void*>(history);
+ updateGlobalHistReg(finalPrediction);
+
+ return finalPrediction;
+}
+
+void
+BiModeBP::btbUpdate(Addr branchAddr, void * &bpHistory)
+{
+ globalHistoryReg &= (historyRegisterMask & ~ULL(1));
+}
+
+/* Only the selected direction predictor will be updated with the final
+ * outcome; the status of the unselected one will not be altered. The choice
+ * predictor is always updated with the branch outcome, except when the
+ * choice is opposite to the branch outcome but the selected counter of
+ * the direction predictors makes a correct final prediction.
+ */
+void
+BiModeBP::update(Addr branchAddr, bool taken, void *bpHistory, bool squashed)
+{
+ if (bpHistory) {
+ BPHistory *history = static_cast<BPHistory*>(bpHistory);
+
+ unsigned choiceHistoryIdx = ((branchAddr >> instShiftAmt)
+ & choiceHistoryMask);
+ unsigned globalHistoryIdx = (((branchAddr >> instShiftAmt)
+ ^ globalHistoryReg)
+ & globalHistoryMask);
+
+ assert(choiceHistoryIdx < choicePredictorSize);
+ assert(globalHistoryIdx < globalPredictorSize);
+
+ if (history->takenUsed) {
+ // if the taken array's prediction was used, update it
+ if (taken) {
+ takenCounters[globalHistoryIdx].increment();
+ } else {
+ takenCounters[globalHistoryIdx].decrement();
+ }
+ } else {
+ // if the not-taken array's prediction was used, update it
+ if (taken) {
+ notTakenCounters[globalHistoryIdx].increment();
+ } else {
+ notTakenCounters[globalHistoryIdx].decrement();
+ }
+ }
+
+ if (history->finalPred == taken) {
+ /* If the final prediction matches the actual branch's
+ * outcome and the choice predictor matches the final
+ * outcome, we update the choice predictor, otherwise it
+ * is not updated. While the designers of the bi-mode
+ * predictor don't explicity say why this is done, one
+ * can infer that it is to preserve the choice predictor's
+ * bias with respect to the branch being predicted; afterall,
+ * the whole point of the bi-mode predictor is to identify the
+ * atypical case when a branch deviates from its bias.
+ */
+ if (history->finalPred == history->takenUsed) {
+ if (taken) {
+ choiceCounters[choiceHistoryIdx].increment();
+ } else {
+ choiceCounters[choiceHistoryIdx].decrement();
+ }
+ }
+ } else {
+ // always update the choice predictor on an incorrect prediction
+ if (taken) {
+ choiceCounters[choiceHistoryIdx].increment();
+ } else {
+ choiceCounters[choiceHistoryIdx].decrement();
+ }
+ }
+
+ if (squashed) {
+ if (taken) {
+ globalHistoryReg = (history->globalHistoryReg << 1) | 1;
+ } else {
+ globalHistoryReg = (history->globalHistoryReg << 1);
+ }
+ globalHistoryReg &= historyRegisterMask;
+ } else {
+ delete history;
+ }
+ }
+}
+
+void
+BiModeBP::retireSquashed(void *bp_history)
+{
+ BPHistory *history = static_cast<BPHistory*>(bp_history);
+ delete history;
+}
+
+void
+BiModeBP::updateGlobalHistReg(bool taken)
+{
+ globalHistoryReg = taken ? (globalHistoryReg << 1) | 1 :
+ (globalHistoryReg << 1);
+ globalHistoryReg &= historyRegisterMask;
+}
diff --git a/src/cpu/pred/bi_mode.hh b/src/cpu/pred/bi_mode.hh
new file mode 100644
index 000000000..a412d63cf
--- /dev/null
+++ b/src/cpu/pred/bi_mode.hh
@@ -0,0 +1,114 @@
+/*
+ * Copyright (c) 2014 The Regents of The University of Michigan
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Anthony Gutierrez
+ */
+
+/* @file
+ * Implementation of a bi-mode branch predictor
+ */
+
+#ifndef __CPU_PRED_BI_MODE_PRED_HH__
+#define __CPU_PRED_BI_MODE_PRED_HH__
+
+#include "cpu/pred/bpred_unit.hh"
+#include "cpu/pred/sat_counter.hh"
+
+/**
+ * Implements a bi-mode branch predictor. The bi-mode predictor is a two-level
+ * branch predictor that has three seprate history arrays: a taken array, a
+ * not-taken array, and a choice array. The taken/not-taken arrays are indexed
+ * by a hash of the PC and the global history. The choice array is indexed by
+ * the PC only. Because the taken/not-taken arrays use the same index, they must
+ * be the same size.
+ *
+ * The bi-mode branch predictor aims to eliminate the destructive aliasing that
+ * occurs when two branches of opposite biases share the same global history
+ * pattern. By separating the predictors into taken/not-taken arrays, and using
+ * the branch's PC to choose between the two, destructive aliasing is reduced.
+ */
+
+class BiModeBP : public BPredUnit
+{
+ public:
+ BiModeBP(const Params *params);
+ void uncondBranch(void * &bp_history);
+ void squash(void *bp_history);
+ bool lookup(Addr branch_addr, void * &bp_history);
+ void btbUpdate(Addr branch_addr, void * &bp_history);
+ void update(Addr branch_addr, bool taken, void *bp_history, bool squashed);
+ void retireSquashed(void *bp_history);
+
+ private:
+ void updateGlobalHistReg(bool taken);
+
+ struct BPHistory {
+ unsigned globalHistoryReg;
+ // was the taken array's prediction used?
+ // true: takenPred used
+ // false: notPred used
+ bool takenUsed;
+ // prediction of the taken array
+ // true: predict taken
+ // false: predict not-taken
+ bool takenPred;
+ // prediction of the not-taken array
+ // true: predict taken
+ // false: predict not-taken
+ bool notTakenPred;
+ // the final taken/not-taken prediction
+ // true: predict taken
+ // false: predict not-taken
+ bool finalPred;
+ };
+
+ // choice predictors
+ std::vector<SatCounter> choiceCounters;
+ // taken direction predictors
+ std::vector<SatCounter> takenCounters;
+ // not-taken direction predictors
+ std::vector<SatCounter> notTakenCounters;
+
+ unsigned instShiftAmt;
+
+ unsigned globalHistoryReg;
+ unsigned globalHistoryBits;
+ unsigned historyRegisterMask;
+
+ unsigned choicePredictorSize;
+ unsigned choiceCtrBits;
+ unsigned choiceHistoryMask;
+ unsigned globalPredictorSize;
+ unsigned globalCtrBits;
+ unsigned globalHistoryMask;
+
+ unsigned choiceThreshold;
+ unsigned takenThreshold;
+ unsigned notTakenThreshold;
+};
+
+#endif // __CPU_PRED_BI_MODE_PRED_HH__
diff --git a/src/cpu/pred/bpred_unit.cc b/src/cpu/pred/bpred_unit.cc
index 52a77119c..585f7c2d8 100644
--- a/src/cpu/pred/bpred_unit.cc
+++ b/src/cpu/pred/bpred_unit.cc
@@ -32,6 +32,7 @@
*/
#include "cpu/pred/2bit_local.hh"
+#include "cpu/pred/bi_mode.hh"
#include "cpu/pred/bpred_unit_impl.hh"
#include "cpu/pred/tournament.hh"
@@ -43,6 +44,8 @@ BranchPredictorParams::create()
return new LocalBP(this);
} else if (predType == "tournament") {
return new TournamentBP(this);
+ } else if (predType == "bi-mode") {
+ return new BiModeBP(this);
} else {
fatal("Invalid BP selected!");
}
diff --git a/src/cpu/pred/bpred_unit.hh b/src/cpu/pred/bpred_unit.hh
index 95f9a3573..0bc0d1569 100644
--- a/src/cpu/pred/bpred_unit.hh
+++ b/src/cpu/pred/bpred_unit.hh
@@ -90,8 +90,8 @@ class BPredUnit : public SimObject
bool predict(StaticInstPtr &inst, const InstSeqNum &seqNum,
TheISA::PCState &pc, ThreadID tid);
bool predictInOrder(StaticInstPtr &inst, const InstSeqNum &seqNum,
- int asid, TheISA::PCState &instPC, TheISA::PCState &predPC,
- ThreadID tid);
+ int asid, TheISA::PCState &instPC,
+ TheISA::PCState &predPC, ThreadID tid);
// @todo: Rename this function.
virtual void uncondBranch(void * &bp_history) = 0;