statistical_corrector.hh revision 13685
113685Sjavier.bueno@metempsy.com/* 213685Sjavier.bueno@metempsy.com * Copyright (c) 2018 Metempsy Technology Consulting 313685Sjavier.bueno@metempsy.com * All rights reserved. 413685Sjavier.bueno@metempsy.com * 513685Sjavier.bueno@metempsy.com * Copyright (c) 2006 INRIA (Institut National de Recherche en 613685Sjavier.bueno@metempsy.com * Informatique et en Automatique / French National Research Institute 713685Sjavier.bueno@metempsy.com * for Computer Science and Applied Mathematics) 813685Sjavier.bueno@metempsy.com * 913685Sjavier.bueno@metempsy.com * All rights reserved. 1013685Sjavier.bueno@metempsy.com * 1113685Sjavier.bueno@metempsy.com * Redistribution and use in source and binary forms, with or without 1213685Sjavier.bueno@metempsy.com * modification, are permitted provided that the following conditions are 1313685Sjavier.bueno@metempsy.com * met: redistributions of source code must retain the above copyright 1413685Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer; 1513685Sjavier.bueno@metempsy.com * redistributions in binary form must reproduce the above copyright 1613685Sjavier.bueno@metempsy.com * notice, this list of conditions and the following disclaimer in the 1713685Sjavier.bueno@metempsy.com * documentation and/or other materials provided with the distribution; 1813685Sjavier.bueno@metempsy.com * neither the name of the copyright holders nor the names of its 1913685Sjavier.bueno@metempsy.com * contributors may be used to endorse or promote products derived from 2013685Sjavier.bueno@metempsy.com * this software without specific prior written permission. 2113685Sjavier.bueno@metempsy.com * 2213685Sjavier.bueno@metempsy.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2313685Sjavier.bueno@metempsy.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2413685Sjavier.bueno@metempsy.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2513685Sjavier.bueno@metempsy.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2613685Sjavier.bueno@metempsy.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2713685Sjavier.bueno@metempsy.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2813685Sjavier.bueno@metempsy.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2913685Sjavier.bueno@metempsy.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 3013685Sjavier.bueno@metempsy.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 3113685Sjavier.bueno@metempsy.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 3213685Sjavier.bueno@metempsy.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 3313685Sjavier.bueno@metempsy.com * 3413685Sjavier.bueno@metempsy.com * Author: André Seznec, Pau Cabre, Javier Bueno 3513685Sjavier.bueno@metempsy.com * 3613685Sjavier.bueno@metempsy.com */ 3713685Sjavier.bueno@metempsy.com 3813685Sjavier.bueno@metempsy.com/* 3913685Sjavier.bueno@metempsy.com * Statistical corrector base class 4013685Sjavier.bueno@metempsy.com */ 4113685Sjavier.bueno@metempsy.com 4213685Sjavier.bueno@metempsy.com#ifndef __CPU_PRED_STATISTICAL_CORRECTOR_HH 4313685Sjavier.bueno@metempsy.com#define __CPU_PRED_STATISTICAL_CORRECTOR_HH 4413685Sjavier.bueno@metempsy.com 4513685Sjavier.bueno@metempsy.com#include "base/statistics.hh" 4613685Sjavier.bueno@metempsy.com#include "base/types.hh" 4713685Sjavier.bueno@metempsy.com#include "sim/sim_object.hh" 4813685Sjavier.bueno@metempsy.com 4913685Sjavier.bueno@metempsy.comstruct StatisticalCorrectorParams; 5013685Sjavier.bueno@metempsy.com 5113685Sjavier.bueno@metempsy.comclass StatisticalCorrector : public SimObject 5213685Sjavier.bueno@metempsy.com{ 5313685Sjavier.bueno@metempsy.com template<typename T> 5413685Sjavier.bueno@metempsy.com inline void ctrUpdate(T & ctr, bool taken, int nbits) { 5513685Sjavier.bueno@metempsy.com assert(nbits <= sizeof(T) << 3); 5613685Sjavier.bueno@metempsy.com if (taken) { 5713685Sjavier.bueno@metempsy.com if (ctr < ((1 << (nbits - 1)) - 1)) 5813685Sjavier.bueno@metempsy.com ctr++; 5913685Sjavier.bueno@metempsy.com } else { 6013685Sjavier.bueno@metempsy.com if (ctr > -(1 << (nbits - 1))) 6113685Sjavier.bueno@metempsy.com ctr--; 6213685Sjavier.bueno@metempsy.com } 6313685Sjavier.bueno@metempsy.com } 6413685Sjavier.bueno@metempsy.com protected: 6513685Sjavier.bueno@metempsy.com // histories used for the statistical corrector 6613685Sjavier.bueno@metempsy.com struct SCThreadHistory { 6713685Sjavier.bueno@metempsy.com SCThreadHistory() { 6813685Sjavier.bueno@metempsy.com bwHist = 0; 6913685Sjavier.bueno@metempsy.com numOrdinalHistories = 0; 7013685Sjavier.bueno@metempsy.com imliCount = 0; 7113685Sjavier.bueno@metempsy.com } 7213685Sjavier.bueno@metempsy.com int64_t bwHist; // backward global history 7313685Sjavier.bueno@metempsy.com int64_t imliCount; 7413685Sjavier.bueno@metempsy.com 7513685Sjavier.bueno@metempsy.com void setNumOrdinalHistories(unsigned num) 7613685Sjavier.bueno@metempsy.com { 7713685Sjavier.bueno@metempsy.com numOrdinalHistories = num; 7813685Sjavier.bueno@metempsy.com assert(num > 0); 7913685Sjavier.bueno@metempsy.com shifts.resize(num); 8013685Sjavier.bueno@metempsy.com localHistories = new std::vector<int64_t> [num]; 8113685Sjavier.bueno@metempsy.com } 8213685Sjavier.bueno@metempsy.com 8313685Sjavier.bueno@metempsy.com void initLocalHistory(int ordinal, int numHistories, int shift) 8413685Sjavier.bueno@metempsy.com { 8513685Sjavier.bueno@metempsy.com assert((ordinal >= 1) && (ordinal <= numOrdinalHistories)); 8613685Sjavier.bueno@metempsy.com shifts[ordinal - 1] = shift; 8713685Sjavier.bueno@metempsy.com assert(isPowerOf2(numHistories)); 8813685Sjavier.bueno@metempsy.com localHistories[ordinal - 1].resize(numHistories, 0); 8913685Sjavier.bueno@metempsy.com } 9013685Sjavier.bueno@metempsy.com 9113685Sjavier.bueno@metempsy.com int64_t getLocalHistory(int ordinal, Addr pc) 9213685Sjavier.bueno@metempsy.com { 9313685Sjavier.bueno@metempsy.com assert((ordinal >= 1) && (ordinal <= numOrdinalHistories)); 9413685Sjavier.bueno@metempsy.com unsigned idx = ordinal - 1; 9513685Sjavier.bueno@metempsy.com return localHistories[idx][getEntry(pc, idx)]; 9613685Sjavier.bueno@metempsy.com } 9713685Sjavier.bueno@metempsy.com 9813685Sjavier.bueno@metempsy.com void updateLocalHistory( 9913685Sjavier.bueno@metempsy.com int ordinal, Addr branch_pc, bool taken, Addr extraXor = 0) 10013685Sjavier.bueno@metempsy.com { 10113685Sjavier.bueno@metempsy.com assert((ordinal >= 1) && (ordinal <= numOrdinalHistories)); 10213685Sjavier.bueno@metempsy.com unsigned idx = ordinal - 1; 10313685Sjavier.bueno@metempsy.com 10413685Sjavier.bueno@metempsy.com unsigned entry = getEntry(branch_pc, idx); 10513685Sjavier.bueno@metempsy.com int64_t hist = (localHistories[idx][entry] << 1) + taken; 10613685Sjavier.bueno@metempsy.com 10713685Sjavier.bueno@metempsy.com if (extraXor) { 10813685Sjavier.bueno@metempsy.com hist = hist ^ extraXor; 10913685Sjavier.bueno@metempsy.com } 11013685Sjavier.bueno@metempsy.com 11113685Sjavier.bueno@metempsy.com localHistories[idx][entry] = hist; 11213685Sjavier.bueno@metempsy.com } 11313685Sjavier.bueno@metempsy.com 11413685Sjavier.bueno@metempsy.com private: 11513685Sjavier.bueno@metempsy.com std::vector<int64_t> * localHistories; 11613685Sjavier.bueno@metempsy.com std::vector<int> shifts; 11713685Sjavier.bueno@metempsy.com unsigned numOrdinalHistories; 11813685Sjavier.bueno@metempsy.com 11913685Sjavier.bueno@metempsy.com unsigned getEntry(Addr pc, unsigned idx) 12013685Sjavier.bueno@metempsy.com { 12113685Sjavier.bueno@metempsy.com return (pc ^ (pc >> shifts[idx])) & (localHistories[idx].size()-1); 12213685Sjavier.bueno@metempsy.com } 12313685Sjavier.bueno@metempsy.com }; 12413685Sjavier.bueno@metempsy.com 12513685Sjavier.bueno@metempsy.com // For SC history we use global (i.e. not per thread) non speculative 12613685Sjavier.bueno@metempsy.com // histories, as some of the strucures needed are quite big and it is not 12713685Sjavier.bueno@metempsy.com // reasonable to make them per thread and it would be difficult to 12813685Sjavier.bueno@metempsy.com // rollback on miss-predictions 12913685Sjavier.bueno@metempsy.com SCThreadHistory * scHistory; 13013685Sjavier.bueno@metempsy.com 13113685Sjavier.bueno@metempsy.com const unsigned logBias; 13213685Sjavier.bueno@metempsy.com 13313685Sjavier.bueno@metempsy.com const unsigned logSizeUp; 13413685Sjavier.bueno@metempsy.com const unsigned logSizeUps; 13513685Sjavier.bueno@metempsy.com 13613685Sjavier.bueno@metempsy.com const unsigned numEntriesFirstLocalHistories; 13713685Sjavier.bueno@metempsy.com 13813685Sjavier.bueno@metempsy.com // global backward branch history GEHL 13913685Sjavier.bueno@metempsy.com const unsigned bwnb; 14013685Sjavier.bueno@metempsy.com const unsigned logBwnb; 14113685Sjavier.bueno@metempsy.com std::vector<int> bwm; 14213685Sjavier.bueno@metempsy.com std::vector<int8_t> * bwgehl; 14313685Sjavier.bueno@metempsy.com std::vector<int8_t> wbw; 14413685Sjavier.bueno@metempsy.com 14513685Sjavier.bueno@metempsy.com // First local history GEHL 14613685Sjavier.bueno@metempsy.com const unsigned lnb; 14713685Sjavier.bueno@metempsy.com const unsigned logLnb; 14813685Sjavier.bueno@metempsy.com std::vector<int> lm; 14913685Sjavier.bueno@metempsy.com std::vector<int8_t> * lgehl; 15013685Sjavier.bueno@metempsy.com std::vector<int8_t> wl; 15113685Sjavier.bueno@metempsy.com 15213685Sjavier.bueno@metempsy.com // IMLI GEHL 15313685Sjavier.bueno@metempsy.com const unsigned inb; 15413685Sjavier.bueno@metempsy.com const unsigned logInb; 15513685Sjavier.bueno@metempsy.com std::vector<int> im; 15613685Sjavier.bueno@metempsy.com std::vector<int8_t> * igehl; 15713685Sjavier.bueno@metempsy.com std::vector<int8_t> wi; 15813685Sjavier.bueno@metempsy.com 15913685Sjavier.bueno@metempsy.com std::vector<int8_t> bias; 16013685Sjavier.bueno@metempsy.com std::vector<int8_t> biasSK; 16113685Sjavier.bueno@metempsy.com std::vector<int8_t> biasBank; 16213685Sjavier.bueno@metempsy.com 16313685Sjavier.bueno@metempsy.com std::vector<int8_t> wb; 16413685Sjavier.bueno@metempsy.com 16513685Sjavier.bueno@metempsy.com int updateThreshold; 16613685Sjavier.bueno@metempsy.com std::vector<int> pUpdateThreshold; 16713685Sjavier.bueno@metempsy.com 16813685Sjavier.bueno@metempsy.com // The two counters used to choose between TAGE ang SC on High Conf 16913685Sjavier.bueno@metempsy.com // TAGE/Low Conf SC 17013685Sjavier.bueno@metempsy.com const unsigned chooserConfWidth; 17113685Sjavier.bueno@metempsy.com 17213685Sjavier.bueno@metempsy.com const unsigned updateThresholdWidth; 17313685Sjavier.bueno@metempsy.com const unsigned pUpdateThresholdWidth; 17413685Sjavier.bueno@metempsy.com 17513685Sjavier.bueno@metempsy.com const unsigned extraWeightsWidth; 17613685Sjavier.bueno@metempsy.com 17713685Sjavier.bueno@metempsy.com const unsigned scCountersWidth; 17813685Sjavier.bueno@metempsy.com 17913685Sjavier.bueno@metempsy.com int8_t firstH; 18013685Sjavier.bueno@metempsy.com int8_t secondH; 18113685Sjavier.bueno@metempsy.com 18213685Sjavier.bueno@metempsy.com // stats 18313685Sjavier.bueno@metempsy.com Stats::Scalar scPredictorCorrect; 18413685Sjavier.bueno@metempsy.com Stats::Scalar scPredictorWrong; 18513685Sjavier.bueno@metempsy.com public: 18613685Sjavier.bueno@metempsy.com struct BranchInfo 18713685Sjavier.bueno@metempsy.com { 18813685Sjavier.bueno@metempsy.com BranchInfo() : lowConf(false), highConf(false), altConf(false), 18913685Sjavier.bueno@metempsy.com medConf(false), scPred(false), lsum(0), thres(0), 19013685Sjavier.bueno@metempsy.com predBeforeSC(false), usedScPred(false) 19113685Sjavier.bueno@metempsy.com {} 19213685Sjavier.bueno@metempsy.com 19313685Sjavier.bueno@metempsy.com // confidences calculated on tage and used on the statistical 19413685Sjavier.bueno@metempsy.com // correction 19513685Sjavier.bueno@metempsy.com bool lowConf; 19613685Sjavier.bueno@metempsy.com bool highConf; 19713685Sjavier.bueno@metempsy.com bool altConf; 19813685Sjavier.bueno@metempsy.com bool medConf; 19913685Sjavier.bueno@metempsy.com 20013685Sjavier.bueno@metempsy.com bool scPred; 20113685Sjavier.bueno@metempsy.com int lsum; 20213685Sjavier.bueno@metempsy.com int thres; 20313685Sjavier.bueno@metempsy.com bool predBeforeSC; 20413685Sjavier.bueno@metempsy.com bool usedScPred; 20513685Sjavier.bueno@metempsy.com }; 20613685Sjavier.bueno@metempsy.com 20713685Sjavier.bueno@metempsy.com StatisticalCorrector(const StatisticalCorrectorParams *p); 20813685Sjavier.bueno@metempsy.com 20913685Sjavier.bueno@metempsy.com virtual BranchInfo *makeBranchInfo(); 21013685Sjavier.bueno@metempsy.com virtual SCThreadHistory *makeThreadHistory(); 21113685Sjavier.bueno@metempsy.com 21213685Sjavier.bueno@metempsy.com bool scPredict( 21313685Sjavier.bueno@metempsy.com ThreadID tid, Addr branch_pc, bool cond_branch, BranchInfo* bi, 21413685Sjavier.bueno@metempsy.com bool prev_pred_taken, bool bias_bit, bool use_conf_ctr, 21513685Sjavier.bueno@metempsy.com int8_t conf_ctr, unsigned conf_bits, int hitBank, int altBank, 21613685Sjavier.bueno@metempsy.com int64_t phist); 21713685Sjavier.bueno@metempsy.com 21813685Sjavier.bueno@metempsy.com unsigned getIndBias(Addr branch_pc, BranchInfo* bi, bool b) const; 21913685Sjavier.bueno@metempsy.com 22013685Sjavier.bueno@metempsy.com unsigned getIndBiasSK(Addr branch_pc, BranchInfo* bi) const; 22113685Sjavier.bueno@metempsy.com 22213685Sjavier.bueno@metempsy.com virtual unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi, 22313685Sjavier.bueno@metempsy.com int hitBank, int altBank) const = 0; 22413685Sjavier.bueno@metempsy.com 22513685Sjavier.bueno@metempsy.com unsigned getIndUpd(Addr branch_pc) const; 22613685Sjavier.bueno@metempsy.com unsigned getIndUpds(Addr branch_pc) const; 22713685Sjavier.bueno@metempsy.com 22813685Sjavier.bueno@metempsy.com virtual int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi, 22913685Sjavier.bueno@metempsy.com int & lsum, int64_t phist) = 0; 23013685Sjavier.bueno@metempsy.com 23113685Sjavier.bueno@metempsy.com int64_t gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, int i); 23213685Sjavier.bueno@metempsy.com 23313685Sjavier.bueno@metempsy.com virtual int gIndexLogsSubstr(int nbr, int i) = 0; 23413685Sjavier.bueno@metempsy.com 23513685Sjavier.bueno@metempsy.com int gPredict( 23613685Sjavier.bueno@metempsy.com Addr branch_pc, int64_t hist, std::vector<int> & length, 23713685Sjavier.bueno@metempsy.com std::vector<int8_t> * tab, int nbr, int logs, 23813685Sjavier.bueno@metempsy.com std::vector<int8_t> & w); 23913685Sjavier.bueno@metempsy.com 24013685Sjavier.bueno@metempsy.com void gUpdate( 24113685Sjavier.bueno@metempsy.com Addr branch_pc, bool taken, int64_t hist, std::vector<int> & length, 24213685Sjavier.bueno@metempsy.com std::vector<int8_t> * tab, int nbr, int logs, 24313685Sjavier.bueno@metempsy.com std::vector<int8_t> & w, BranchInfo* bi); 24413685Sjavier.bueno@metempsy.com 24513685Sjavier.bueno@metempsy.com void initGEHLTable( 24613685Sjavier.bueno@metempsy.com unsigned numLenghts, std::vector<int> lengths, 24713685Sjavier.bueno@metempsy.com std::vector<int8_t> * & table, unsigned logNumEntries, 24813685Sjavier.bueno@metempsy.com std::vector<int8_t> & w, int8_t wInitValue); 24913685Sjavier.bueno@metempsy.com 25013685Sjavier.bueno@metempsy.com virtual void scHistoryUpdate( 25113685Sjavier.bueno@metempsy.com Addr branch_pc, int brtype, bool taken, BranchInfo * tage_bi, 25213685Sjavier.bueno@metempsy.com Addr corrTarget); 25313685Sjavier.bueno@metempsy.com 25413685Sjavier.bueno@metempsy.com virtual void gUpdates( ThreadID tid, Addr pc, bool taken, BranchInfo* bi, 25513685Sjavier.bueno@metempsy.com int64_t phist) = 0; 25613685Sjavier.bueno@metempsy.com 25713685Sjavier.bueno@metempsy.com void init() override; 25813685Sjavier.bueno@metempsy.com void regStats() override; 25913685Sjavier.bueno@metempsy.com void updateStats(bool taken, BranchInfo *bi); 26013685Sjavier.bueno@metempsy.com 26113685Sjavier.bueno@metempsy.com void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken, 26213685Sjavier.bueno@metempsy.com BranchInfo *bi, Addr corrTarget, bool bias_bit, 26313685Sjavier.bueno@metempsy.com int hitBank, int altBank, int64_t phist); 26413685Sjavier.bueno@metempsy.com}; 26513685Sjavier.bueno@metempsy.com#endif//__CPU_PRED_STATISTICAL_CORRECTOR_HH 266