| /* |
| * Copyright (c) 2018 Metempsy Technology Consulting |
| * All rights reserved. |
| * |
| * Copyright (c) 2006 INRIA (Institut National de Recherche en |
| * Informatique et en Automatique / French National Research Institute |
| * for Computer Science and Applied Mathematics) |
| * |
| * 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. |
| * |
| * Author: André Seznec, Pau Cabre, Javier Bueno |
| * |
| */ |
| |
| /* |
| * Statistical corrector base class |
| */ |
| |
| #include "cpu/pred/statistical_corrector.hh" |
| |
| #include "params/StatisticalCorrector.hh" |
| |
| namespace gem5 |
| { |
| |
| namespace branch_prediction |
| { |
| |
| StatisticalCorrector::StatisticalCorrector( |
| const StatisticalCorrectorParams &p) |
| : SimObject(p), |
| logBias(p.logBias), |
| logSizeUp(p.logSizeUp), |
| logSizeUps(logSizeUp / 2), |
| numEntriesFirstLocalHistories(p.numEntriesFirstLocalHistories), |
| bwnb(p.bwnb), |
| logBwnb(p.logBwnb), |
| bwm(p.bwm), |
| lnb(p.lnb), |
| logLnb(p.logLnb), |
| lm(p.lm), |
| inb(p.inb), |
| logInb(p.logInb), |
| im(p.im), |
| chooserConfWidth(p.chooserConfWidth), |
| updateThresholdWidth(p.updateThresholdWidth), |
| pUpdateThresholdWidth(p.pUpdateThresholdWidth), |
| extraWeightsWidth(p.extraWeightsWidth), |
| scCountersWidth(p.scCountersWidth), |
| firstH(0), |
| secondH(0), |
| stats(this) |
| { |
| wb.resize(1 << logSizeUps, 4); |
| |
| initGEHLTable(lnb, lm, lgehl, logLnb, wl, p.lWeightInitValue); |
| initGEHLTable(bwnb, bwm, bwgehl, logBwnb, wbw, p.bwWeightInitValue); |
| initGEHLTable(inb, im, igehl, logInb, wi, p.iWeightInitValue); |
| |
| updateThreshold = 35 << 3; |
| |
| pUpdateThreshold.resize(1 << logSizeUp, p.initialUpdateThresholdValue); |
| |
| bias.resize(1 << logBias); |
| biasSK.resize(1 << logBias); |
| biasBank.resize(1 << logBias); |
| } |
| |
| StatisticalCorrector::BranchInfo* |
| StatisticalCorrector::makeBranchInfo() |
| { |
| return new BranchInfo(); |
| } |
| |
| StatisticalCorrector::SCThreadHistory* |
| StatisticalCorrector::makeThreadHistory() |
| { |
| return new SCThreadHistory(); |
| } |
| |
| void |
| StatisticalCorrector::initBias() |
| { |
| for (int j = 0; j < (1 << logBias); j++) { |
| switch (j & 3) { |
| case 0: |
| bias[j] = -32; |
| biasSK[j] = -8; |
| biasBank[j] = -32; |
| break; |
| case 1: |
| bias[j] = 31; |
| biasSK[j] = 7; |
| biasBank[j] = 31; |
| break; |
| case 2: |
| bias[j] = -1; |
| biasSK[j] = -32; |
| biasBank[j] = -1; |
| break; |
| case 3: |
| bias[j] = 0; |
| biasSK[j] = 31; |
| biasBank[j] = 0; |
| break; |
| } |
| } |
| } |
| |
| void |
| StatisticalCorrector::initGEHLTable(unsigned numLenghts, |
| std::vector<int> lengths, std::vector<int8_t> * & table, |
| unsigned logNumEntries, std::vector<int8_t> & w, int8_t wInitValue) |
| { |
| assert(lengths.size() == numLenghts); |
| if (numLenghts == 0) { |
| return; |
| } |
| table = new std::vector<int8_t> [numLenghts]; |
| for (int i = 0; i < numLenghts; ++i) { |
| table[i].resize(1 << logNumEntries, 0); |
| for (int j = 0; j < ((1 << logNumEntries) - 1); ++j) { |
| if (! (j & 1)) { |
| table[i][j] = -1; |
| } |
| } |
| } |
| |
| w.resize(1 << logSizeUps, wInitValue); |
| } |
| |
| unsigned |
| StatisticalCorrector::getIndBias(Addr branch_pc, BranchInfo* bi, |
| bool bias) const |
| { |
| return (((((branch_pc ^(branch_pc >>2))<<1) ^ (bi->lowConf & bias)) <<1) |
| + bi->predBeforeSC) & ((1<<logBias) -1); |
| } |
| |
| unsigned |
| StatisticalCorrector::getIndBiasSK(Addr branch_pc, BranchInfo* bi) const |
| { |
| return (((((branch_pc ^ (branch_pc >> (logBias-2)))<<1) ^ |
| (bi->highConf))<<1) + bi->predBeforeSC) & ((1<<logBias) -1); |
| } |
| |
| unsigned |
| StatisticalCorrector::getIndUpd(Addr branch_pc) const |
| { |
| return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUp)) - 1)); |
| } |
| |
| unsigned |
| StatisticalCorrector::getIndUpds(Addr branch_pc) const |
| { |
| return ((branch_pc ^ (branch_pc >>2)) & ((1 << (logSizeUps)) - 1)); |
| } |
| |
| int64_t |
| StatisticalCorrector::gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, |
| int i) |
| { |
| return (((int64_t) branch_pc) ^ bhist ^ (bhist >> (8 - i)) ^ |
| (bhist >> (16 - 2 * i)) ^ (bhist >> (24 - 3 * i)) ^ |
| (bhist >> (32 - 3 * i)) ^ (bhist >> (40 - 4 * i))) & |
| ((1 << (logs - gIndexLogsSubstr(nbr, i))) - 1); |
| } |
| |
| int |
| StatisticalCorrector::gPredict(Addr branch_pc, int64_t hist, |
| std::vector<int> & length, std::vector<int8_t> * tab, int nbr, |
| int logs, std::vector<int8_t> & w) |
| { |
| int percsum = 0; |
| for (int i = 0; i < nbr; i++) { |
| int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); |
| int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); |
| int8_t ctr = tab[i][index]; |
| percsum += (2 * ctr + 1); |
| } |
| percsum = (1 + (w[getIndUpds(branch_pc)] >= 0)) * percsum; |
| return percsum; |
| } |
| |
| void |
| StatisticalCorrector::gUpdate(Addr branch_pc, bool taken, int64_t hist, |
| std::vector<int> & length, std::vector<int8_t> * tab, |
| int nbr, int logs, std::vector<int8_t> & w, |
| BranchInfo* bi) |
| { |
| int percsum = 0; |
| for (int i = 0; i < nbr; i++) { |
| int64_t bhist = hist & ((int64_t) ((1 << length[i]) - 1)); |
| int64_t index = gIndex(branch_pc, bhist, logs, nbr, i); |
| percsum += (2 * tab[i][index] + 1); |
| ctrUpdate(tab[i][index], taken, scCountersWidth); |
| } |
| |
| int xsum = bi->lsum - ((w[getIndUpds(branch_pc)] >= 0)) * percsum; |
| if ((xsum + percsum >= 0) != (xsum >= 0)) { |
| ctrUpdate(w[getIndUpds(branch_pc)], ((percsum >= 0) == taken), |
| extraWeightsWidth); |
| } |
| } |
| |
| bool |
| StatisticalCorrector::scPredict(ThreadID tid, Addr branch_pc, bool cond_branch, |
| BranchInfo* bi, bool prev_pred_taken, bool bias_bit, |
| bool use_conf_ctr, int8_t conf_ctr, unsigned conf_bits, |
| int hitBank, int altBank, int64_t phist, int init_lsum) |
| { |
| bool pred_taken = prev_pred_taken; |
| if (cond_branch) { |
| |
| bi->predBeforeSC = prev_pred_taken; |
| |
| // first calc/update the confidences from the TAGE prediction |
| if (use_conf_ctr) { |
| bi->lowConf = (abs(2 * conf_ctr + 1) == 1); |
| bi->medConf = (abs(2 * conf_ctr + 1) == 5); |
| bi->highConf = (abs(2 * conf_ctr + 1) >= (1<<conf_bits) - 1); |
| } |
| |
| int lsum = init_lsum; |
| |
| int8_t ctr = bias[getIndBias(branch_pc, bi, bias_bit)]; |
| lsum += (2 * ctr + 1); |
| ctr = biasSK[getIndBiasSK(branch_pc, bi)]; |
| lsum += (2 * ctr + 1); |
| ctr = biasBank[getIndBiasBank(branch_pc, bi, hitBank, altBank)]; |
| lsum += (2 * ctr + 1); |
| |
| lsum = (1 + (wb[getIndUpds(branch_pc)] >= 0)) * lsum; |
| |
| int thres = gPredictions(tid, branch_pc, bi, lsum, phist); |
| |
| // These will be needed at update time |
| bi->lsum = lsum; |
| bi->thres = thres; |
| |
| bool scPred = (lsum >= 0); |
| |
| if (pred_taken != scPred) { |
| bool useScPred = true; |
| //Choser uses TAGE confidence and |LSUM| |
| if (bi->highConf) { |
| if (abs (lsum) < (thres / 4)) { |
| useScPred = false; |
| } else if (abs (lsum) < (thres / 2)) { |
| useScPred = (secondH < 0); |
| } |
| } |
| |
| if (bi->medConf) { |
| if (abs (lsum) < (thres / 4)) { |
| useScPred = (firstH < 0); |
| } |
| } |
| |
| bi->usedScPred = useScPred; |
| if (useScPred) { |
| pred_taken = scPred; |
| bi->scPred = scPred; |
| } |
| } |
| } |
| |
| return pred_taken; |
| } |
| |
| void |
| StatisticalCorrector::scHistoryUpdate(Addr branch_pc, |
| const StaticInstPtr &inst, bool taken, BranchInfo * tage_bi, |
| Addr corrTarget) |
| { |
| int brtype = inst->isDirectCtrl() ? 0 : 2; |
| if (! inst->isUncondCtrl()) { |
| ++brtype; |
| } |
| // Non speculative SC histories update |
| if (brtype & 1) { |
| if (corrTarget < branch_pc) { |
| //This branch corresponds to a loop |
| if (!taken) { |
| //exit of the "loop" |
| scHistory->imliCount = 0; |
| } else { |
| if (scHistory->imliCount < ((1 << im[0]) - 1)) { |
| scHistory->imliCount++; |
| } |
| } |
| } |
| |
| scHistory->bwHist = (scHistory->bwHist << 1) + |
| (taken & (corrTarget < branch_pc)); |
| scHistory->updateLocalHistory(1, branch_pc, taken); |
| } |
| } |
| |
| void |
| StatisticalCorrector::condBranchUpdate(ThreadID tid, Addr branch_pc, |
| bool taken, BranchInfo *bi, Addr corrTarget, bool b, int hitBank, |
| int altBank, int64_t phist) |
| { |
| bool scPred = (bi->lsum >= 0); |
| |
| if (bi->predBeforeSC != scPred) { |
| if (abs(bi->lsum) < bi->thres) { |
| if (bi->highConf) { |
| if ((abs(bi->lsum) < bi->thres / 2)) { |
| if ((abs(bi->lsum) >= bi->thres / 4)) { |
| ctrUpdate(secondH, (bi->predBeforeSC == taken), |
| chooserConfWidth); |
| } |
| } |
| } |
| } |
| if (bi->medConf) { |
| if ((abs(bi->lsum) < bi->thres / 4)) { |
| ctrUpdate(firstH, (bi->predBeforeSC == taken), |
| chooserConfWidth); |
| } |
| } |
| } |
| |
| if ((scPred != taken) || ((abs(bi->lsum) < bi->thres))) { |
| ctrUpdate(updateThreshold, (scPred != taken), updateThresholdWidth); |
| ctrUpdate(pUpdateThreshold[getIndUpd(branch_pc)], (scPred != taken), |
| pUpdateThresholdWidth); |
| |
| unsigned indUpds = getIndUpds(branch_pc); |
| unsigned indBias = getIndBias(branch_pc, bi, b); |
| unsigned indBiasSK = getIndBiasSK(branch_pc, bi); |
| unsigned indBiasBank = getIndBiasBank(branch_pc, bi, hitBank, altBank); |
| |
| int xsum = bi->lsum - |
| ((wb[indUpds] >= 0) * ((2 * bias[indBias] + 1) + |
| (2 * biasSK[indBiasSK] + 1) + |
| (2 * biasBank[indBiasBank] + 1))); |
| |
| if ((xsum + ((2 * bias[indBias] + 1) + (2 * biasSK[indBiasSK] + 1) + |
| (2 * biasBank[indBiasBank] + 1)) >= 0) != (xsum >= 0)) |
| { |
| ctrUpdate(wb[indUpds], |
| (((2 * bias[indBias] + 1) + |
| (2 * biasSK[indBiasSK] + 1) + |
| (2 * biasBank[indBiasBank] + 1) >= 0) == taken), |
| extraWeightsWidth); |
| } |
| |
| ctrUpdate(bias[indBias], taken, scCountersWidth); |
| ctrUpdate(biasSK[indBiasSK], taken, scCountersWidth); |
| ctrUpdate(biasBank[indBiasBank], taken, scCountersWidth); |
| |
| gUpdates(tid, branch_pc, taken, bi, phist); |
| } |
| } |
| |
| void |
| StatisticalCorrector::updateStats(bool taken, BranchInfo *bi) |
| { |
| if (taken == bi->scPred) { |
| stats.correct++; |
| } else { |
| stats.wrong++; |
| } |
| } |
| |
| void |
| StatisticalCorrector::init() |
| { |
| scHistory = makeThreadHistory(); |
| initBias(); |
| } |
| |
| size_t |
| StatisticalCorrector::getSizeInBits() const |
| { |
| // Not implemented |
| return 0; |
| } |
| |
| StatisticalCorrector::StatisticalCorrectorStats::StatisticalCorrectorStats( |
| statistics::Group *parent) |
| : statistics::Group(parent), |
| ADD_STAT(correct, statistics::units::Count::get(), |
| "Number of time the SC predictor is the provider and the " |
| "prediction is correct"), |
| ADD_STAT(wrong, statistics::units::Count::get(), |
| "Number of time the SC predictor is the provider and the " |
| "prediction is wrong") |
| { |
| } |
| |
| } // namespace branch_prediction |
| } // namespace gem5 |
