diff options
| -rw-r--r-- | src/cpu/o3/fetch_impl.hh | 4 | ||||
| -rw-r--r-- | src/cpu/pred/BranchPredictor.py | 2 | ||||
| -rw-r--r-- | src/cpu/pred/SConscript | 1 | ||||
| -rw-r--r-- | src/cpu/pred/bi_mode.cc | 245 | ||||
| -rw-r--r-- | src/cpu/pred/bi_mode.hh | 114 | ||||
| -rw-r--r-- | src/cpu/pred/bpred_unit.cc | 3 | ||||
| -rw-r--r-- | src/cpu/pred/bpred_unit.hh | 4 |
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; |