A PPM-like, Tag-based Branch Predictor

0x00 基本思路

TAGE Branch Predictor是目前很多CPU使用的Branch Predictor，比如使用 TAGE Branch Predictor 和 Perceptrons Branch Predcitor的组合。TAGE即TAgged GEometric length predictor。这篇Paper提出的是一个很接近TAGE的Branch Predictor。其基本结构如下图，其核心思路是使用不同的历史长度来index不同的bank，发现branch在不同历史长度上branch之间的相关性，以实现比使用单一历史长度更好的效果。其有1+4个banks，其中bank 0直接使用branch地址最低的12bit来index，这样看作是一个不考虑branchs之间相关性只考虑自身倾向性的一个预测bank。bank 0是一个bimodel predcitor，实用3bit的counter加上1bit的meta bit，m bit被meta predcitor实用。另外的4个实用3-bit的counter和8-bit的组合，另外还有一个u bit，即useful bit。

• 不同的bank实用不同的历史长度，分别是10,20,40 和 80bit的global history。在global history长度超过了index需要的长度的时候，实用折叠的方式而不是直接截断，比如实用40bit历史的时候，index实用 pc[0 : 9]⊕h[0 : 9]⊕h[10 : 19]⊕h[20 : 29]⊕h[30 : 39]这样的方式得到(⊕ 为 xor)。获取预测值的时候，5个banks同时预测，高4个的bank的处理index到一个entry外，还会根据tag和PC+history的hash进行比较，匹配了的才是命中。在命中了的bank的结果中，选择bank实用历史消息最长的那个的结果。
• 更新的时候，3-bit counter的更新只更新提供了最终预测结果的那个。预测正确+1，错误则-1。如果预测错误，设最终实用的bank为X，如果X <= 4，则会尝试在 > X的bank上面分配一个entry。因为这种情况下是因为> X的bank获取预测值的时候miss了。在 > X的banks上选择u bit没有设置的，如果都设置了则随机选择一个，然后填充这个entry。填充tag实用PC和history得来的一个hash值，counter值填充根据bank 0的meta bit信息来填充value 3 (weakly not-taken) 或者是 4 (weakly taken)。u bit也需要设置。
• 更新u bit和m bit根据如下的规则：如果最终的预测结果和bank 0的预测结果不同，即使用 X > 0的预测的时候，如果预测正确，则同时设置bank 0的m bit和bank X的ubit，否则都reset。最终结果和bi-model即bank 0的预测结果不同的时候，bi-model预测错误的情况下，意味着bank X对应entry预测正确，将对应entry的u bit设置来帮助这个entry保留，设置m bit目的是在分配新的entry的时候使用分支实际的结果来进行初始化而不是使用bank 0的预测的值。如果bi-model预测正确则将bank X对应的entry的u bit设置为0用于加速这个entry被替换，reset m bit用于指示初始化3-bit的counter时候使用bi-model预测的值。

0x01 评估

这里的具体内容可以参考[1].

A Case for (partially)-Tagged Geometrics History Length Branch Predictor

0x10 基本思路

这篇Paper即提出了TAGE branch predictor，有前面提出的一些branch predictor进化而来。其核心思路也是利用上不同的history长度，发觉在不同范围内branchs之间的相关性。TAGE 同样分为几个的bank，使用不同的历史长度，称之为geometrics series，不同bank使用的长度表示为$L(i)=a^{i-1}\cdot L(1)$，这里根据长度只能取整数会对这个式子做一些调整，$L(i)=(int)(a^{i-1}\cdot L(1)+0.5)$。比如当a=2，L(1)=2时候，这个series为{0,2,4,8,16,32,64,128}。这篇paper提出的TAGE branch predictor直接从前面的PPM-like, Tag-based Branch Predictor而来，基本设计/改动如下：

• base predictor，即PPM-like中的bank 0，同样适用一个简单的2-bit的bi-model的方式。在其它的banks，使用一个3-bit的counter作为预测，2-bit的counter作为userful bits，另外还有一个几个bit的tag。其获取预测值的方式也是和前面的PPM-like, Tag-based Branch Predictor一样。
• 其更新策略和PPM-like, Tag-based Branch Predictor有些不同，这篇paper中认为PPM-like, Tag-based Branch Predictor的更新策略存在一些问题。这里将最终提供预测值的bank操作为provider component，altpred为在如果provider component不用的情况下会使用到的bank。如果provider 和 altpred预测的结果不同，在provider预测正确的情况下增加计数，否则减少计数。另外userful bit会有一个周期性更新的策略，周期性地先重置其高为的bit，然后在重置器低位的bit。这样是为了避免一些entry一值被置为userfule的状态。
• 预测错误的时候，会更新provider component对应entry的计数。如果provider component不是最长的，则会尝试在更高的banks上面分配entry。这banks若存在useful计数为0的，则选择其中历史长度最短的，如果useful计数都不为0，则减少这些的useful 计数，且不会有新entry被分配初始化entry的时候设置counter为weak correct，useful计数设置为0。

0x11 评估

这里的具体信息可以参看[2].

TAGE-SC-L Branch Predictor

0x20 基本思路

这篇Paper的改进思路是发现TAGE Branch Predcitor处理在history有比较大相关性的branch比较适合，但是在预测biased比较明显的却可能不如简单的branch predcitor。TAGE-SC-L Branch Predictor的思路是在TAGE的基础上加上2个修正的部分，处理TAGE预测不理想的branchs。其基本结构如下，核心还是一个TAGE Predictor，和一般的没有太大的改变。TAGE预测的结果会被statistical corrector predictor使用，根据自身的一些操作来翻转认为TAGE预测不佳的预测结果，loop predictor部分则用来预测循环。TAGE部分的逻辑和前面的内容基本相同，

• Loop predictor用于预测有固定循环次数的循环。在发现一个循环使用相同的循环次数执行7次之后，最终的结果使用loop predictor的结果。其组成是一些组相联的entries，比如一个64个entries，4-way skewed associative的一个结构。每个使用一个人10bit的计数、一个10bit的retire iteration count，一个10bit的partial tag，一个4-bit的 confidence counter，一个4-bit的age counter 以及1bit的direction bit。计数和tag用于统计循环次数和匹配branch。age counter用于替换策略，在其值为null的时候才会被替换。分配一个新entry的时候初始化为7，在可能是替换的目标的时候被减少，在loop predictor预测正确的时候增加，在不认为是循环的时候被设置为0。

• 另外一个是Statistical Corrector Predictor，使用比较小的空间来实现对TAGE一些预测的纠正。比如对一个32Kbits的predictor，其使用一个Corrector Filter，在TAGE预测错误的时候，其地址和预测结构会被记录，刚记录的时候其confidence设置为一个较低的值。如果TAGE预测的branch在corrector fileter中出现，且confidence值较高，则会翻转TAGE的预测结果。其组成的entry是6-bit counter + 7-bit tag，也是使用一个几路 skewed associative的结构。

• 在257Kbits的TAGE-SC-L Branch Predictor中，Statistical Corrector Predictor使用了更加复杂的结构，称之为Multi-GEHL Statistical Corrector, MGSC，应该是在GEHL类型的branch predictor上面改进而来的。这个MGSC有6个不同组件：1. 一个bias模块，通过branch地址和TAGE的预测来询知的两个tables，两个tables使用寻址时使用不同的hash函数；2. 另外的5个是GEHL-like的组件，包括4个通过global conditional branch history寻址的table，4个通过return-stack-associated branch history寻址的tables，通过一个256-entry local history寻址的3个tables，2个16-entry local history寻址的组件(分别为4个和3个tables)。这些都不适用branch地址的信息。return-stack-associated branch history使用的时候，通过在每次调用的时候相关的调整记录下来，在return的时候可以使用。这里使用两种不同的local history，实际上是1个256-entry加上2个1616-entry local history的，

  The use of two distinct local histories was introduced by [7]. The benefit of the 2nd local history is marginal (about 0.5 % misprediction reduction). However adding a 3rd local history table with also 16 history entries, with a different hashing function on the local history table induces an extra accuracy benefit in the same range.
  

  这里各个tables使用counter是5-bit or 6-bit的counter，比一般使用的2-bit or 3-bit要大。最终的结果通过技术这个tables对应counter的和来得到，O-GEHL论文中使用的是S=M/2 + sum(C(i))，其中M为counter的数量，其预测结果根据S的符号来决定。这里使用的时候，会和TAGE的结果加上这里Corrector Predictor各个tables的counters的两倍。这里为什么证明设计paper中没有具体说，感觉是试出来的。另外选择MGSC还是TAGE的结果，会根据MGSC计算得到的S在那个范围进行调整。

0x21 评估

这里的具体信息可以参考[4].

参考

1. A PPM-like, tag-based branch predictor, JILP ‘05.
2. A Case for (partially)-Tagged Geometrics History Length Branch Predictor， JILP ‘06.
3. The L-TAGE Branch Predictor, JILP ‘07.
4. TAGE-SC-L Branch Predictor.
5. Dynamic Branch Prediction with Perceptrons, HPCA ‘01.
6. Revisiting local history for improv- ing fused two-level branch predictor.