现代处理器分支预测介绍
发布时间:2022-08-29 07:00
摘要
处理器(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.
上一个: 让照片开口说话:AI驱动的人脸重演
近期文章
通用AI模型的未来:深度强化学习(deep reinforcement learning)
2023-05-08
2023-04-24