现代处理器分支预测介绍

发布时间: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 Artist背后的算法原理I:Text-to-Image

近期文章

AI 智能体:应用前景与对算力需求的影响

人工智能技术的迅猛发展,尤其是 AI 智能体这一核心部分。本文讨论了AI智能体的定义、应用前景和其对算力需求的影响。

2023-11-13

查看更多