src/cpu/pred/statistical_corrector.hh - public/gem5 - Git at Google

 /*
  * 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
  */

 #ifndef __CPU_PRED_STATISTICAL_CORRECTOR_HH
 #define __CPU_PRED_STATISTICAL_CORRECTOR_HH

 #include "base/statistics.hh"
 #include "base/types.hh"
 #include "cpu/static_inst.hh"
 #include "sim/sim_object.hh"

 struct StatisticalCorrectorParams;

 class StatisticalCorrector : public SimObject
 {
   protected:
     template<typename T>
     inline void ctrUpdate(T & ctr, bool taken, int nbits) {
         assert(nbits <= sizeof(T) << 3);
         if (nbits > 0) {
             if (taken) {
                 if (ctr < ((1 << (nbits - 1)) - 1))
                     ctr++;
             } else {
                 if (ctr > -(1 << (nbits - 1)))
                     ctr--;
             }
         }
     }
     // histories used for the statistical corrector
     struct SCThreadHistory {
         SCThreadHistory() {
             bwHist = 0;
             numOrdinalHistories = 0;
             imliCount = 0;
         }
         int64_t bwHist;  // backward global history
         int64_t imliCount;

         void setNumOrdinalHistories(unsigned num)
         {
             numOrdinalHistories = num;
             assert(num > 0);
             shifts.resize(num);
             localHistories = new std::vector<int64_t> [num];
         }

         void initLocalHistory(int ordinal, int numHistories, int shift)
         {
             assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
             shifts[ordinal - 1] = shift;
             assert(isPowerOf2(numHistories));
             localHistories[ordinal - 1].resize(numHistories, 0);
         }

         int64_t getLocalHistory(int ordinal, Addr pc)
         {
             assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
             unsigned idx = ordinal - 1;
             return localHistories[idx][getEntry(pc, idx)];
         }

         void updateLocalHistory(
             int ordinal, Addr branch_pc, bool taken, Addr extraXor = 0)
         {
             assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
             unsigned idx = ordinal - 1;

             unsigned entry = getEntry(branch_pc, idx);
             int64_t hist =  (localHistories[idx][entry] << 1) + taken;

             if (extraXor) {
                 hist = hist ^ extraXor;
             }

             localHistories[idx][entry] = hist;
         }

       private:
         std::vector<int64_t> * localHistories;
         std::vector<int> shifts;
         unsigned numOrdinalHistories;

         unsigned getEntry(Addr pc, unsigned idx)
         {
             return (pc ^ (pc >> shifts[idx])) & (localHistories[idx].size()-1);
         }
     };

     // For SC history we use global (i.e. not per thread) non speculative
     // histories, as some of the strucures needed are quite big and it is not
     // reasonable to make them per thread and it would be difficult to
     // rollback on miss-predictions
     SCThreadHistory * scHistory;

     const unsigned logBias;

     const unsigned logSizeUp;
     const unsigned logSizeUps;

     const unsigned numEntriesFirstLocalHistories;

     // global backward branch history GEHL
     const unsigned bwnb;
     const unsigned logBwnb;
     std::vector<int> bwm;
     std::vector<int8_t> * bwgehl;
     std::vector<int8_t> wbw;

     // First local history GEHL
     const unsigned lnb;
     const unsigned logLnb;
     std::vector<int> lm;
     std::vector<int8_t> * lgehl;
     std::vector<int8_t> wl;

     // IMLI GEHL
     const unsigned inb;
     const unsigned logInb;
     std::vector<int> im;
     std::vector<int8_t> * igehl;
     std::vector<int8_t> wi;

     std::vector<int8_t> bias;
     std::vector<int8_t> biasSK;
     std::vector<int8_t> biasBank;

     std::vector<int8_t> wb;

     int updateThreshold;
     std::vector<int> pUpdateThreshold;

     // The two counters used to choose between TAGE ang SC on High Conf
     // TAGE/Low Conf SC
     const unsigned chooserConfWidth;

     const unsigned updateThresholdWidth;
     const unsigned pUpdateThresholdWidth;

     const unsigned extraWeightsWidth;

     const unsigned scCountersWidth;

     int8_t firstH;
     int8_t secondH;

     // stats
     Stats::Scalar scPredictorCorrect;
     Stats::Scalar scPredictorWrong;
   public:
     struct BranchInfo
     {
         BranchInfo() : lowConf(false), highConf(false), altConf(false),
               medConf(false), scPred(false), lsum(0), thres(0),
               predBeforeSC(false), usedScPred(false)
         {}

         // confidences calculated on tage and used on the statistical
         // correction
         bool lowConf;
         bool highConf;
         bool altConf;
         bool medConf;

         bool scPred;
         int lsum;
         int thres;
         bool predBeforeSC;
         bool usedScPred;
     };

     StatisticalCorrector(const StatisticalCorrectorParams *p);

     virtual BranchInfo *makeBranchInfo();
     virtual SCThreadHistory *makeThreadHistory();

     virtual void initBias();

     virtual bool 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 = 0);

     virtual unsigned getIndBias(Addr branch_pc, BranchInfo* bi, bool b) const;

     virtual unsigned getIndBiasSK(Addr branch_pc, BranchInfo* bi) const;

     virtual unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi,
         int hitBank, int altBank) const = 0;

     virtual unsigned getIndUpd(Addr branch_pc) const;
     unsigned getIndUpds(Addr branch_pc) const;

     virtual int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi,
         int & lsum, int64_t phist) = 0;

     int64_t gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, int i);

     virtual int gIndexLogsSubstr(int nbr, int i) = 0;

     int 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);

     virtual void 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);

     void initGEHLTable(
         unsigned numLenghts, std::vector<int> lengths,
         std::vector<int8_t> * & table, unsigned logNumEntries,
         std::vector<int8_t> & w, int8_t wInitValue);

     virtual void scHistoryUpdate(
         Addr branch_pc, const StaticInstPtr &inst , bool taken,
         BranchInfo * tage_bi, Addr corrTarget);

     virtual void gUpdates( ThreadID tid, Addr pc, bool taken, BranchInfo* bi,
         int64_t phist) = 0;

     void init() override;
     void regStats() override;
     void updateStats(bool taken, BranchInfo *bi);

     virtual void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
                           BranchInfo *bi, Addr corrTarget, bool bias_bit,
                           int hitBank, int altBank, int64_t phist);

     virtual size_t getSizeInBits() const;
 };
 #endif//__CPU_PRED_STATISTICAL_CORRECTOR_HH
	/*
	* 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
	*/

	#ifndef __CPU_PRED_STATISTICAL_CORRECTOR_HH
	#define __CPU_PRED_STATISTICAL_CORRECTOR_HH

	#include "base/statistics.hh"
	#include "base/types.hh"
	#include "cpu/static_inst.hh"
	#include "sim/sim_object.hh"

	struct StatisticalCorrectorParams;

	class StatisticalCorrector : public SimObject
	{
	protected:
	template<typename T>
	inline void ctrUpdate(T & ctr, bool taken, int nbits) {
	assert(nbits <= sizeof(T) << 3);
	if (nbits > 0) {
	if (taken) {
	if (ctr < ((1 << (nbits - 1)) - 1))
	ctr++;
	} else {
	if (ctr > -(1 << (nbits - 1)))
	ctr--;
	}
	}
	}
	// histories used for the statistical corrector
	struct SCThreadHistory {
	SCThreadHistory() {
	bwHist = 0;
	numOrdinalHistories = 0;
	imliCount = 0;
	}
	int64_t bwHist; // backward global history
	int64_t imliCount;

	void setNumOrdinalHistories(unsigned num)
	{
	numOrdinalHistories = num;
	assert(num > 0);
	shifts.resize(num);
	localHistories = new std::vector<int64_t> [num];
	}

	void initLocalHistory(int ordinal, int numHistories, int shift)
	{
	assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
	shifts[ordinal - 1] = shift;
	assert(isPowerOf2(numHistories));
	localHistories[ordinal - 1].resize(numHistories, 0);
	}

	int64_t getLocalHistory(int ordinal, Addr pc)
	{
	assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
	unsigned idx = ordinal - 1;
	return localHistories[idx][getEntry(pc, idx)];
	}

	void updateLocalHistory(
	int ordinal, Addr branch_pc, bool taken, Addr extraXor = 0)
	{
	assert((ordinal >= 1) && (ordinal <= numOrdinalHistories));
	unsigned idx = ordinal - 1;

	unsigned entry = getEntry(branch_pc, idx);
	int64_t hist = (localHistories[idx][entry] << 1) + taken;

	if (extraXor) {
	hist = hist ^ extraXor;
	}

	localHistories[idx][entry] = hist;
	}

	private:
	std::vector<int64_t> * localHistories;
	std::vector<int> shifts;
	unsigned numOrdinalHistories;

	unsigned getEntry(Addr pc, unsigned idx)
	{
	return (pc ^ (pc >> shifts[idx])) & (localHistories[idx].size()-1);
	}
	};

	// For SC history we use global (i.e. not per thread) non speculative
	// histories, as some of the strucures needed are quite big and it is not
	// reasonable to make them per thread and it would be difficult to
	// rollback on miss-predictions
	SCThreadHistory * scHistory;

	const unsigned logBias;

	const unsigned logSizeUp;
	const unsigned logSizeUps;

	const unsigned numEntriesFirstLocalHistories;

	// global backward branch history GEHL
	const unsigned bwnb;
	const unsigned logBwnb;
	std::vector<int> bwm;
	std::vector<int8_t> * bwgehl;
	std::vector<int8_t> wbw;

	// First local history GEHL
	const unsigned lnb;
	const unsigned logLnb;
	std::vector<int> lm;
	std::vector<int8_t> * lgehl;
	std::vector<int8_t> wl;

	// IMLI GEHL
	const unsigned inb;
	const unsigned logInb;
	std::vector<int> im;
	std::vector<int8_t> * igehl;
	std::vector<int8_t> wi;

	std::vector<int8_t> bias;
	std::vector<int8_t> biasSK;
	std::vector<int8_t> biasBank;

	std::vector<int8_t> wb;

	int updateThreshold;
	std::vector<int> pUpdateThreshold;

	// The two counters used to choose between TAGE ang SC on High Conf
	// TAGE/Low Conf SC
	const unsigned chooserConfWidth;

	const unsigned updateThresholdWidth;
	const unsigned pUpdateThresholdWidth;

	const unsigned extraWeightsWidth;

	const unsigned scCountersWidth;

	int8_t firstH;
	int8_t secondH;

	// stats
	Stats::Scalar scPredictorCorrect;
	Stats::Scalar scPredictorWrong;
	public:
	struct BranchInfo
	{
	BranchInfo() : lowConf(false), highConf(false), altConf(false),
	medConf(false), scPred(false), lsum(0), thres(0),
	predBeforeSC(false), usedScPred(false)
	{}

	// confidences calculated on tage and used on the statistical
	// correction
	bool lowConf;
	bool highConf;
	bool altConf;
	bool medConf;

	bool scPred;
	int lsum;
	int thres;
	bool predBeforeSC;
	bool usedScPred;
	};

	StatisticalCorrector(const StatisticalCorrectorParams *p);

	virtual BranchInfo *makeBranchInfo();
	virtual SCThreadHistory *makeThreadHistory();

	virtual void initBias();

	virtual bool 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 = 0);

	virtual unsigned getIndBias(Addr branch_pc, BranchInfo* bi, bool b) const;

	virtual unsigned getIndBiasSK(Addr branch_pc, BranchInfo* bi) const;

	virtual unsigned getIndBiasBank( Addr branch_pc, BranchInfo* bi,
	int hitBank, int altBank) const = 0;

	virtual unsigned getIndUpd(Addr branch_pc) const;
	unsigned getIndUpds(Addr branch_pc) const;

	virtual int gPredictions(ThreadID tid, Addr branch_pc, BranchInfo* bi,
	int & lsum, int64_t phist) = 0;

	int64_t gIndex(Addr branch_pc, int64_t bhist, int logs, int nbr, int i);

	virtual int gIndexLogsSubstr(int nbr, int i) = 0;

	int 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);

	virtual void 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);

	void initGEHLTable(
	unsigned numLenghts, std::vector<int> lengths,
	std::vector<int8_t> * & table, unsigned logNumEntries,
	std::vector<int8_t> & w, int8_t wInitValue);

	virtual void scHistoryUpdate(
	Addr branch_pc, const StaticInstPtr &inst , bool taken,
	BranchInfo * tage_bi, Addr corrTarget);

	virtual void gUpdates( ThreadID tid, Addr pc, bool taken, BranchInfo* bi,
	int64_t phist) = 0;

	void init() override;
	void regStats() override;
	void updateStats(bool taken, BranchInfo *bi);

	virtual void condBranchUpdate(ThreadID tid, Addr branch_pc, bool taken,
	BranchInfo *bi, Addr corrTarget, bool bias_bit,
	int hitBank, int altBank, int64_t phist);

	virtual size_t getSizeInBits() const;
	};
	#endif//__CPU_PRED_STATISTICAL_CORRECTOR_HH