摘要

处理器（CPU）诞生于上世纪70年代，自诞生以来经历了飞速的发展，从最初的简单计算到如今的通用复杂计算，从最初的4位处理器到如今的64位处理器，从单核到多核工作，CPU架构的更新及工艺提升促使其不断完善。

 

CPU简介

1971年，第一块cpu-4004在Intel公司诞生，具有划时代的意义，作为第一代4位处理器产品，尽管在功能及性能上较今天的cpu还存在很大的差距，但它的出现拉开了cpu发展的序幕。

 

1989年的80846处理器，首次采用RISC（精简指令集），实现了5级标量流水线，标志着cpu逐步发展到成熟阶段。

 

1995年，Intel发布了Pentinum处理器，首次引入了分支预测机制及指令乱序技术，是cpu发展史上的重大突破，使得处理器的性能得到大大的提高，此后的众多处理器，基本都沿用此类技术。

 

现阶段的cpu具备多核处理的能力，功能及性能不断提高。现代处理器具有多核性、并行性、集成度、复杂化等特性，使其能够支持更多的应用场景，不断推动着相关产业的发展。

CPU原理

 

典型cpu的执行过程一般可以认为有五个阶段，取指令，指令译码，执行，访存及写回。

 

• 取指令过程根据程序计数器（pc）的记录，依次取出指令传递给译码单元并更新pc；
• 指令译码主要根据不同的指令集架构进行指令行为区分，识别出指令的操作及操作数等；
• 得到指令的对应的操作类型及操作数后，进行执行操作，实现指令的功能；
• 对于一些需要与memory交互的指令，在这一阶段进行访存操作，从memory中读取或写入memory中；
• 最后阶段是写回，将指令执行的结果写回到寄存器中，用于后续指令。

 

为了提高cpu的性能，引入分支预测及乱序执行技术。乱序执行可以提高指令执行的效率，当前条指令处于等待状态而后续的指令不依赖于前条指令时，可以优先执行后续指令，通过引入乱序执行，有效缩短指令执行时间。

 

分支预测可以避免流水线的空闲等待，在指令流水型执行时，不必等待执行结果，提前进行指令预测并取指令进行后续动作，可以大大减少指令等待时间，接下来对分支预测技术进行详细介绍。

 

分支预测

分支预测主要用来预测下一条指令，当没有分支预测机制时，需要等待指令操作数计算出跳转地址后才能确定下一条执行指令，并由取指令单元取指令，这个过程会导致流水线处于等待状态。对于现代处理器来说，若预测结果错误，需要冲刷流水线，因此分支预测的准确率至关重要。

 

预测任务可以分为两个主要部分，1预测是否跳转，2预测跳转地址。

 

分支预测一般包含两种预测器，静态预测（Static Predictor）和动态预测（Dynamic Predictor）。

 

• 静态预测

 

静态预测采用一种既定的策略进行预测而不依赖于历史预测结果，因此受策略本身的精确度及程序类型影响较大。

 

常见的静态预测策略有always not taken，always taken，BFTN（backward taken，forward not taken），predict with certain operation code等等。我们以典型的BFTN为例，对于向后跳转的分支指令，预测为跳转，向前跳转的分支指令，预测为不跳转。在论文[1]中对该策略预测结果进行统计，可以看到静态预测对不同的程序表现出较大的差异。静态预测过于依赖策略而忽略程序的行为，已难以满足现代处理器的需求。

 

图1  BFTN预测策略对各程序预测精度[1]

 

• 动态预测

 

动态预测相比静态预测，引入了分支历史的结果作为参考，预测准确率得到提高。

 

• 2bit饱和计数器（Two-bit counter based prediction）

 

2bit饱和计数器一共包含四种状态，strongly not taken，weakly no taken，weakly taken，strongly taken，利用2bit来进行计数，根据最新的跳转结果，taken则加1，not taken减1，当数值大于1时，预测为跳转，小于等于1，预测不跳转。这种预测方法可以进行最简单的动态预测，对于分支指令，若当前状态是strongly taken，当连续两次跳转结果与当前预测结果相反，预测其下一次将会改变跳转状态，图2为2bit饱和计数器状态图。

 

图2  2bit饱和计数器状态图

 

最理想的情况，可以为每一个分支都分配一个2bit饱和计数器，但是这样的做法会带来巨大的开销，因此一般情况下使用pc的一部分去寻址pattern history table（PHT），查询表中饱和计数器的数值，做出预测，但会导致不同分支寻址到相同的表项而做出错误的预测（aliasing），我们会在下面提到一些解决方法。

 

• TAGE预测器

 

利用饱和计数器作为预测表表项，衍生出了许多其他类型的预测器，包括基于局部/全局历史的分支预测器，Tournament Branch Predictor以及Perceptrons Predictor等等[2-5]，这些预测器都表现出了不错的预测效率，但仍然存在着缺陷。2006年论文[6]提出的tage预测器（Tagged Geometric history length branch predictor），大大提高了预测精度，此后又出现多种基于tage的变种预测器，基于tage的预测器成为目前处理器的主流预测方式。

 

图3  TAGE预测器基本结构[6]

 

以论文[6]中的tage预测器为例，包含一个base predictor及四个partially tagged predictor。

 

TAGE的预测机制：

 

Base predictor利用pc部分位索引，3bit饱和计数器用于计算预测结果，2bit的userful counter及partial tag作为表项，构成标记预测器。四个标记预测器采用不同长度的全局历史寄存器（GHR），四个标记预测表大小一致，因此需要先将GHR压缩为相同位宽后与PC部分位进行哈希作为索引查询表项（利用哈希解决aliasing问题），查询到tag命中（tag的哈希计算方法不同于索引的哈希计算方法），则取出该标记预测器的预测结果，预测结果由3bit的饱和计数器计算得出。

 

Tage最终的预测结果取GHR最长的标记预测器的预测结果，即若T2、T4同时命中，则取T4的预测结果作为最终预测结果，T2就为alternatate，T4为provider ，若T1~T4均无命中，则取base predictor的预测结果。

 

TAGE的更新机制：

 

每个标记预测表中有一个2bit的userful counter，用来记录是否需要更新，当alternate 表和provider表预测结果不同，而provider表预测正确时，provider表的u加1，反之则减1。

 

根据实际结果更新provider标记预测表中的饱和计数器，若预测结果和实际结果一致，则3bit饱和计数器加1，反之则减1。

 

若所有命中的标记预测表均预测错误，首先更新provider表的饱和计数器减1，若provider表不是历史最长表（图T4）则分配新的表项。表项分配时，在provider表和历史最长表之间进行分配，检查这些标记预测表的u，若只有一个表的u为0，则分配给该标记预测器；若有多个标记预测表的u为0，则按照概率进行分配；若都不为0，则将这些表的u都减1。

 

图4  TAGE预测器与其他类型预测器结果对比[6]

 

鉴于tage强大的预测功能，出现了tage-sc，tage-sc-l[7-8]等多类基于tage的变种预测器，这些预测器可以达到更好的预测精度，且针对不同程序场景表现出更好的兼容性。图5展示了tage-sc-l预测器，引入了statistical corrector predictor和loop predictor，在一些和历史不是强相关或者一些循环分支中，用于对tage的预测结果进行修正。

 

图5  TAGE-SC-L预测器[8]

 

基于tage预测器的探索从未停止，tage预测器的预测精度很大程度上依赖于GHR的长度，需要增加GHR的长度来解析不同分支之间的相关性，从而做出更好的预测，但这样会带来很大的存储开销。最新的研究[9]提出一种sparse branch history的方法，表明分支之间存在稀疏的相关性，不需要完整的记录所有的分支历史，并且可以使用稀疏建模方法有效地计算这种相关性；然后引入了一种稀疏感知分支预测机制，可以有效地编码和存储稀疏模型，具体分析可以参考[9]。

 

图6  稀疏感知分支预测器[9]

 

• BTB（Branch Target Buffer）

 

前面讲到的都是对跳转情况的预测，当做出对跳转的预测时，需要查询跳转的地址，这一部分一般由BTB实现。

 

BTB是类似于cache的结构，主要用来记录目标的跳转地址。BTB表用（partial）pc作为索引，当一个分支指令第一次执行时，记录该分支指令的目标地址并分配一个表项，当前面提到的预测器得到taken/not taken的预测结果后，在BTB中查询跳转地址。

 

表1  BTB表结构

 

总结

现代超标量处理器具有高效的流水线，得益于分支预测和乱序执行技术，可以充分填满流水线的执行空缺，提高cpu的执行效率。在分支预测初期，大多采用静态预测技术，静态预测具有功耗低，速度快的优点，但是局限性较大，预测率低。动态预测引入分支历史做参考，在预测率上有了明显的提升。现代处理器大多采用多种预测器混合预测来提高预测精度，随着处理器的流水线深度不断增加，对分支预测的精度要求越来越高，希望在未来能看到更多精准有效的预测器出现。

 

参考文献

[1] Smith J E. A study of branch prediction strategies[C]//25 years of the international symposia on Computer architecture (selected papers). 1998: 202-215

[2] McFarling S. Combining branch predictors[R]. Technical Report TN-36, Digital Western Research Laboratory, 1993.

[3] Nair R. Dynamic path-based branch correlation[C]//Proceedings of the 28th annual international symposium on Microarchitecture. IEEE, 1995: 15-23.

[4] Kessler R E, McLellan E J, Webb D A. The Alpha 21264 microprocessor architecture[C]//Proceedings International Conference on Computer Design. VLSI in Computers and Processors (Cat. No. 98CB36273). IEEE, 1998: 90-95.

[5] Jiménez D A, Lin C. Dynamic branch prediction with perceptrons[C]//Proceedings HPCA Seventh International Symposium on High-Performance Computer Architecture. IEEE, 2001: 197-206.

[6] Seznec A, Michaud P. A case for (partially) TAgged GEometric history length branch prediction[J]. The Journal of Instruction-Level Parallelism, 2006, 8: 23.

[7] Seznec A. A new case for the tage branch predictor[C]//Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture. 2011: 117-127.

[8] Seznec A. Tage-sc-l branch predictors[C]//JILP-Championship Branch Prediction. 2014.

[9] Zouzias A, Kalaitzidis K, Berestizshevsky K, et al. Identifying and Exploiting Sparse Branch Correlations for Optimizing Branch Prediction[J]. arXiv preprint arXiv:2207.14033, 2022.