Skip to content

A easy TAGE predictor for cbp4. Lab2 for Computer architecture, Tsinghua University.

Notifications You must be signed in to change notification settings

HITSZ-NSCSCC22/TAGE-Predictor

 
 

Repository files navigation

计算机系统结构 选题2 分支预测

实现内容

在本次实验中,我使用了与TAGE_SC_L相似的算法,完成了由TAGE Predictor、Loop Predictor、Corrector Filter等部件组成的分支预测器。在cbp4的、32KB的测试中,MPKI为3.097。

目录说明

GsharePredictor.h/cc:提供的baseline

TagePredictor.h/cc: 基本的TAGE预测器

TagePredictorOpt.h/cc:对新分配entry使用use_alt进行优化的TAGE预测器

TagePredictor8Com.h/cc:TAGE有8个component。然而MPKI并没有降低。

LTagePredictor.h/cc:TAGE with Loop table

TAGE_SC_LPredictor.h/cc:TAGE with loop table and Corrector filter

predictor.h/cc:调参后,并且修正了TAGEOpt中对于use_alt的update的错误

如果想要运行某个预测器,用它替换掉cbp4的sim/predictor.hsim/predictor.cc即可。

算法设计

整个算法部件由TAGE、Loop Predictor、Corrector Filter三个主要部件组成。我完成代码的时候是按照以上顺序依次完成三个部件,且三个部件之间比较独立,因此将分开叙述。

演示文稿1.jpg

TAGE

TAGE是一种ppm-like的分支预测器,该方法的我在实现TAGE时主要参考了参考文献[1]和[2]的实现。其主要思路是通过不同长度的history和PC进行哈希来获得预测结果,对于与不同长度的history有强关联的分支都能取得比较好的效果。

组成

TAGE由一个BaseTable和M个Tagged Table组成。

2.png

BaseTable(图中T0)是一个简单的根据PC索引的二位饱和计数器,每个表项对应一个index的饱和计数器。

Tagged Table(图中T1-T4)则是用PC和不同长度的GHR(Global history register)生成索引和标签以获取表项。Tagged Table的表项如下

struct TageEntry{
  uint16_t tag; // 9 bits
  uint8_t u;    // 2 bits
  uint8_t ctr;  // 3 bits
};

其中tag是将(PC, GHR[0:L])进行哈希后得到的标签,用于判断当前entry是否对应到目前的状态;u是useful位,用于判断当前entry是否能提供有用的信息;ctr是3位饱和计数器。

  • provider component: 在TAGE预测部件中负责提供最终结果的那个

  • alternate prediction (altpred):除了provider component外,hit的那个预测部件的结果(如果没有部件hit,则认为T0是altpred。

预测

  • BaseTable直接根据pc获得对应表项,通过计数器判断结果;
  • Tagged Table将pc与不同len的GHR做hash1,获得表项的index,取出entry。然后判断entry的tag和hash2(PC, GHR[0:L])是否相等,相等则命中。如果命中,entry.ctr就可以给出当前表的预测结果。注意,这里的hash1和hash2不能是同一个hash函数。
  • 选择匹配长度最长的预测结果作为最终结果,其对应的Tagged Table为provider component。匹配长度第二长的作为备选结果,其对应的Table为altpred。

更新

  • 根据实际结果,更新provider component的计数器
  • 如果预测结果正确,不需要分配新的entry。
  • 如果预测结果错误,可能要分配新的entry。
    • 如果provider component Ti,如果i <M,那么分配一个新的entry在Tk(i<k<M)。
    • 两种分配的可能:
      • 如果有uk=0的项,那么Tk就allocate
      • 否则所有的uj,i<j<M,全部-1
    • 如果有两个component都可以被分配,序号小的那个概率是序号大的那个的两倍
    • 刚分配的entry:prediction设为weak correct,u设为0
  • 更新useful位
    • 当altpred和最终预测结果pred不同,如果provider component的预测结果对了,则provider component的u+1,否则-1
    • 每256k个branch后reset一次高位,再256k后reset一次低位

对新分配节点的优化

如果按照PPM-LIKE的逻辑,一个刚分配的entry很可能会被直接投入使用。但是在特定的测例下,新分配的entry有很大概率会出错,我们需要对这种情况做一些优化。

  • 总体思路:用一个4bit的全局计数器,如果provider_component是新分配的entry,且其预测结果出错,但是altpred预测正确,该计数器+1;反过来计数器-1。然后如果这个计数器超过了阈值,在遇到new_entry的时候,我们就使用altpred作为结果。

  • 判断是不是新entry只需要:useful counter == 0 且 weak(taken or not taken)。

  • 优化效果:大约有0.2MPKI的优化(3.27->3.09)

loop predictor

loop predictor是LTage的组成部分,我的实现主要参考了参考文献[3]。该部件主要是为了处理一些以常数次数循环的循环。其能弥补TAGE的GHR长度有限,对于一些非常长的循环并不能有效预测;或者TAGE对于循环的反应可能不够灵敏。

优化效果:大约有0.04MPKI的优化(3.275->3.237)

构成

loop predictor的主要结构是一个LoopTable,其表项如下。

struct LoopTableEntry{
  uint16_t past_iter_count; //14 bits,该循环总共迭代次数
  uint16_t now_iter_count;  // 14 bits,当前已经迭代次数
  uint16_t tag;             // 14 bits,匹配判断
  uint8_t confidenc_count;  // 2 bits,该entry可信度
  uint8_t age_count;        // 8 bits,该entry是否过时
};

预测

  • 如果past_iter_count<now_iter_count,预测为Taken;如果past_iter_count=now_iter_count,预测为Not Taken。

  • 如果confidence_count为MAX,就认为这个预测结果可以采用;否则预测结果不可以采用。

更新

  • 若loop_tag和entry.tag不同,这说明当前的表项不匹配,就减少entry.age,如果entry.age已经是0,就需要分配新的表项。(这样做的理由是:age实际上标记了一个entry希望被替换的次数,如果一直希望被替换,证明原来的loop可能已经失效了)
  • 若loop_tag和entry.tag相同
    • now_iter_count ++
    • 如果loop predictor提供的预测是正确的,并且预测结果是NotTaken(这证明目前循环到了最后一步),那么重置now_iter_count。然后判断tage_pred提供的结果是否正确,如果tage_pred的结果是错误的,证明loop predictor提供的结果比Tage提供的更可信,confidenc_count和age_count就应该增加。
    • 如果loop predictor提供的预测是错误的,那么需要判断这个entry是否是刚分配的。
      • 如果是刚分配的entry的前两次循环,(因为第一次循环可能不是在循环开始就分配entry的,统计次数会出错,所以需要前两次),需要把past_iter设成now_iter,然后清空now_iter。
      • 如果不是刚分配的,证明这个entry已经是错误的了,直接清空整个entry即可。
  • allocate entry:allocate时age设置为255,conf设为0,past_iter设为MAX(这样可以在第一次循环中确定past_iter的值)。

Corrector Filter

corrector filter主要用于纠正一些Tage不能正确预测的场景。比如,一些分支与历史无关,可能就是统计意义上的偏向某个方向,这时候Tage可能不如单纯的基于PC的预测器。Corrector Filter就可以部分纠正这种问题。实现基本参考文献[4]。

优化效果:大约有0.02MPKI的优化(3.24->3.22)

构成

struct CorrectorFilterEntry{
  uint8_t ctr; // 6 bits的饱和计数器
  uint8_t tag; // 7 bits,匹配判断 
}

预测

首先考虑Tage的结果的可信度。如果Tage的可信度是高的(通过ctr来判断,ctr偏离weak足够远就证明可信度高),那么就不需要再使用Corrector filter。如果Tage的可信度低,就使用Corrector filter的结果。直接通过pc和tage 预测结果索引得到表项,然后判断tag是否匹配,而后根据ctr获得结果即可。

更新

  • 如果tage的预测结果是正确的,且tag不匹配,则不需要做任何操作(tage已经能解决问题)
  • 如果tage的预测结果是错的,且tag匹配,则根据分支结果更新饱和计数器(可能需要使用当前的表项)
  • 如果tage的预测结果是错的,且tag不匹配,则根据不同情况,分配表项或者更新饱和计数器。

参数设置与存储需求

  • TAGE参数设置

    • component number:1 base table, 4 tagged table

    • Base Table

      • entry number:$2^{14}$
      • ctr: $2$
    • tagged table(1-4)

      • entry size:14bit(具体的域见上面算法分析部分)
      • entry number: $2^{12}$
  • loop table

    • entry size: 52bit(具体的域见上面算法分析部分)

    • entry number:256

  • Corrector filter

    • entry size:13 bit(具体的域见上面算法分析部分)
    • entry number:236
  • 全局参数/额外budget

    • GHR: 128 bits

    • TAGE重置useful时使用的clock:19 bits

    • use_alt的计数器:4bits

    • use_cf的计数器:4bits

      其余几项只用于在一个分支指令的GetPrediction()和UpdatePrediction()中传递信息,因此实际上不占用空间。(包括provider_component:2bits,altpred_component:2bits,pred:1bit,altpred:1bit,tage_pred:1bit,high_conf:1bit,cf_pred:1bit)

  • 大块使用的空间: $2^{13} * 2 + 4* 2^{12} * 14 + 52 * 256 + 13 * 236 = 262140 &lt; 262144$

  • 零碎使用的空间:$128+19+4+4=155<512$

    可见是符合空间要求的。

实验结果

最终测试结果如图所示,MPKI为3.097。

3.png

参考文献

[1] Michaud, Pierre. "A PPM-like, tag-based branch predictor." The Journal of Instruction-Level Parallelism 7 (2005): 10.

[2] Seznec, André, and Pierre Michaud. "A case for (partially) TAgged GEometric history length branch prediction." The Journal of Instruction-Level Parallelism 8 (2006): 23.

[3]Seznec, André. "A 256 kbits l-tage branch predictor." Journal of Instruction-Level Parallelism (JILP) Special Issue: The Second Championship Branch Prediction Competition (CBP-2) 9 (2007): 1-6.

[4]Seznec, André. "Tage-sc-l branch predictors." JILP-Championship Branch Prediction. 2014.

About

A easy TAGE predictor for cbp4. Lab2 for Computer architecture, Tsinghua University.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C++ 100.0%