在本次实验中，我使用了与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.h和sim/predictor.cc即可。
整个算法部件由TAGE、Loop Predictor、Corrector Filter三个主要部件组成。我完成代码的时候是按照以上顺序依次完成三个部件，且三个部件之间比较独立，因此将分开叙述。
TAGE是一种ppm-like的分支预测器，该方法的我在实现TAGE时主要参考了参考文献[1]和[2]的实现。其主要思路是通过不同长度的history和PC进行哈希来获得预测结果，对于与不同长度的history有强关联的分支都能取得比较好的效果。
TAGE由一个BaseTable和M个Tagged Table组成。
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是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主要用于纠正一些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 < 262144$ -
零碎使用的空间：$128+19+4+4=155<512$
可见是符合空间要求的。
最终测试结果如图所示，MPKI为3.097。
[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.