处理器分支预测研究的历史和现状.pdf

《处理器分支预测研究的历史和现状.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、处理器分支预测研究的历史和现状冯子军肖俊华章隆兵摘要在过去十几年中，分支预测技术一直是提高处理器性能的重要方法，工业界和学术界对之进行了大量研究。分支预测的本质是克服指令控制相关，提高指令并行度。随着研究的不断深入，当前学术界认为分支预测是一个指令学习的过程，这就使得对分支预测的研究出现了新的趋势。本文对分支预测技术的历史和研究现状进行了归纳，以便从总体上了解分支预测技术的发展过程。1引言过去的十几年里，分支预测技术一直是提高通用处理器性能的重要方法。分支预测的本质是克服指令控制相关，提高指令并行度，从而使得处理器的性能

2、得到提高。在这方面学术界和工业界都进行了大量的研究和实践，分支预测的重要性体现在以下几个方面：首先，现在的通用处理器大多采用深度流水线和宽发射机制，分支预测是两者的关键支撑技术。虽然前两年英特尔（Intel）的奔腾4（Pentium4）靠深度流水提高主频一直为人所诟病，但是同时应该注意到没有一定深度的流水，处理器频率就不可能太高，也就不会有很高的性能。目前x86处理器一般都有20－30级的流水线。此外展望新世纪体系结构时候，耶鲁.帕特（Yale.Patt）[1]预测宽发射将成为单芯片集成10亿晶体管主要解决方案之一，而且

3、宽发射也是提高单片处理器性能的重要手段之一，最近英特尔的新处理器Conroe就从原先奔腾的三发射提高到四发射，使得[2]处理器性能提高30％也是例证。简单的分析表明：在当前流行的深流水线宽发射体系结构中，分支预测率会严重影响取指带宽的利用率。在5发射10级流水线条件下，预测准确率为90%时，带宽会浪费47%；而如果准确率提高到96%则带宽浪费可降低到26%（一般处理器设计为2到8发射，此处为了计算方便假定5发射）。另外，分支预测技术不仅在高性能通用处理器中采用，而且在嵌入式处理器也广泛采用，所以作为一个处理器设计者，我们

4、应该知道当前存在的分支预测的各种算法及其优缺点，这样才能对功耗和性能进行权衡。事实上，一种分支预测机制可能在某些应用中可以提高运算效率，但在另一些应用可能效果就不明显，因此设计者需要对不同应用采用不同的分支预测解决方案。还应该指出，很好地理解分支指令对微处理器的设计至关重要，分支指令是计算机不同于计算器的最重要区别，使得计算机得以超越简单的数字计算功能转变为可以完成各种复杂任务和运算的信息处理装置。分支指令决定了程序从取指令到执行指令的路径，对分支指令的特性和行为理解深刻就可以帮助处理器设计者来平衡处理器结构。在程序里面

5、分支指令组合起来就形成了程序分支行为，后面的介绍将说明不同分支预测机制的提出就是根据这些程序行为来进行设计和改进的。分支行为是取指单元设计必须考虑的关键因素，而掌握更复杂的分支特性，比如分支相关，就能很好地帮助我们对不同应用选择和改进分支预测。综上所述，可以知道分支预测的重要性，本文就处理器的分支预测技术的过去、现在和将来做一下总结和展望。本文首先介绍分支指令的性质和分支行为的一些属性，其次介绍分支预测的发展历程和主要的分支预测方法，然后介绍分支预测的最新进展，最后预测未来处理器设计分支可能会出现的问题和发展趋势。2分支

6、行为分支预测器设计的本质是在对分支指令行为认识的基础上，提出分支指令的预测机制，从而减少分支惩罚，也就是分支预测误预测导致的流水线等待。一组分支指令组合起来就成为程序的分支行为。程序分支行为非常复杂，国外学术界作了大量的研究。这里只介绍一些基本的特点，以便更好地了解后面重点说明的预测机制。下面我们就分别简单介绍一下分支指令属性和程序分支的行为。2.1分支指令的基本属性分支指令总的来说有三个基本属性：分支指令的类型、分支指令发生的频率和分支指令的成功率。分支指令的类型可以分为条件分支指令和无条件分支指令，由于分支指令目标地

7、址的不同，无条件分支又可以进一步分为立即分支指令，间接分支指令和返回分支指令。立即分支指令就是分支的地址就在分支指令中，一般都是直接跳转，比如跳转（jump）这类指令；间接分支就是分支的目标地址不在分支指令中，而是从其他寄存器中取得；返回型分支的分支目标地址是从链接寄存器（Linkregister）或者堆栈中得到，一般是程序返回使用。图1不同分支类型所占SPEC程序比例如图1所示，统计分析SEPC程序结果表明，分支指令中72%是条件分支，17％是无条件立即跳转指令，10％是返回指令，1％是间接分支指令。其中立即分支跳转可

8、以采用BTB（BranchTarget1[5]Buffer，分支预测缓冲区）这种方式精确预测，返回型跳转可以采用返回地址栈(RAS)精确预测，间接分支跳转的预测一直没什么好的办法，在[6]中进行了讨论。所以分支预测大量的工作是进行条件分支预测。图2分支指令执行的频率分布图2说明了SPEC程序条件分支预测执行的频率分布