处理器分支预测

处理器分支预测研究的历史和现状 冯子军 肖俊华 章隆兵 摘要 在过去十几年中，分支预测技术一直是提高处理器性能的重要方法，工业界和学术界对之进行了大量研究。 分支预测的本质是克服指令控制相关，提高指令并行度。随着研究的不断深入，当前学术界认为分支预测是一个 指令学习的过程，这就使得对分支预测的研究出现了新的趋势。本文对分支预测技术的历史和研究现状进行了归 纳，以便从总体上了解分支预测技术的发展过程。 1 引言 过去的十几年里，分支预测技术一直是提高通用处理器性能的重要方法。分支预测的本质是 克服指令控制相关，提高指令并行度，从而使得处理器的性能得到提高。在这方面学术界和工业 界都进行了大量的研究和实践，分支预测的重要性体现在以下几个方面： 首先，现在的通用处理器大多采用深度流水线和宽发射机制，分支预测是两者的关键支撑技 术。虽然前两年英特尔（Intel）的奔腾 4（Pentium4）靠深度流水提高主频一直为人所诟病，但是 同时应该注意到没有一定深度的流水，处理器频率就不可能太高，也就不会有很高的性能。目前 x86处理器一般都有 20－30级的流水线。此外展望新世纪体系结构时候，耶鲁.帕特（Yale.Patt） 预测宽发射将成为单芯片集成 10亿晶体管主要解决之一[1]，而且宽发射也是提高单片处理器 性能的重要手段之一，最近英特尔的新处理器Conroe就从原先奔腾的三发射提高到四发射，使得 处理器性能提高 30％也是例证[2]。 简单的分析明：在当前流行的深流水线宽发射体系结构中，分支预测率会严重影响取指带 宽的利用率。在 5 发射 10 级流水线条件下，预测准确率为 90%时，带宽会浪费 47%；而如果准 确率提高到 96%则带宽浪费可降低到 26%（一般处理器为 2到 8发射，此处为了计算方便假 定 5发射）。 另外，分支预测技术不仅在高性能通用处理器中采用，而且在嵌入式处理器也广泛采用，所 以作为一个处理器设计者，我们应该知道当前存在的分支预测的各种算法及其优缺点，这样才能 对功耗和性能进行权衡。事实上，一种分支预测机制可能在某些应用中可以提高运算效率，但在 另一些应用可能效果就不明显，因此设计者需要对不同应用采用不同的分支预测解决方案。 还应该指出，很好地理解分支指令对微处理器的设计至关重要，分支指令是计算机不同于计 算器的最重要区别，使得计算机得以超越简单的数字计算功能转变为可以完成各种复杂任务和运 算的信息处理装置。分支指令决定了程序从取指令到执行指令的路径，对分支指令的特性和行为 理解深刻就可以帮助处理器设计者来平衡处理器结构。在程序里面分支指令组合起来就形成了程 序分支行为，后面的介绍将说明不同分支预测机制的提出就是根据这些程序行为来进行设计和改 进的。分支行为是取指单元设计必须考虑的关键因素，而掌握更复杂的分支特性，比如分支相关， 就能很好地帮助我们对不同应用选择和改进分支预测。 综上所述，可以知道分支预测的重要性，本文就处理器的分支预测技术的过去、现在和将来 做一下总结和展望。本文首先介绍分支指令的性质和分支行为的一些属性，其次介绍分支预测的 发展历程和主要的分支预测方法，然后介绍分支预测的最新进展，最后预测未来处理器设计分支 可能会出现的问题和发展趋势。 2 分支行为 分支预测器设计的本质是在对分支指令行为认识的基础上，提出分支指令的预测机制，从而 减少分支惩罚，也就是分支预测误预测导致的流水线等待。一组分支指令组合起来就成为程序的 分支行为。程序分支行为非常复杂，国外学术界作了大量的研究。这里只介绍一些基本的特点， 以便更好地了解后面重点说明的预测机制。下面我们就分别简单介绍一下分支指令属性和程序分 支的行为。 2.1 分支指令的基本属性 分支指令总的来说有三个基本属性：分支指令的类型、分支指令发生的频率和分支指令的成 功率。分支指令的类型可以分为条件分支指令和无条件分支指令，由于分支指令目标地址的不同， 无条件分支又可以进一步分为立即分支指令，间接分支指令和返回分支指令。立即分支指令就是 分支的地址就在分支指令中，一般都是直接跳转，比如跳转（jump）这类指令；间接分支就是分 支的目标地址不在分支指令中，而是从其他寄存器中取得；返回型分支的分支目标地址是从链接 寄存器（Link register）或者堆栈中得到，一般是程序返回使用。 图 1 不同分支类型所占 SPEC程序比例 如图 1所示，统计分析SEPC程序结果表明，分支指令中 72%是条件分支，17％是无条件立即 跳转指令，10％是返回指令，1％是间接分支指令。其中立即分支跳转可以采用BTB（Branch Target Buffer，分支预测缓冲区）这种方式精确预测，返回型跳转可以采用返回地址栈(RAS1)精确预测[5] ， 间接分支跳转的预测一直没什么好的办法，在[6]中进行了讨论。所以分支预测大量的工作是进行 条件分支预测。 图 2 分支指令执行的频率分布 图 2说明了 SPEC程序条件分支预测执行的频率分布。从图中我们可以看到，大部分条件分 支在程序运行过程中，仅仅执行几次，平均来说所有分支指令的 53%仅仅执行 99 次或者更少， 只有 11％的分支执行了超过 10000次或者更多。 1 Return Address Stack 图 3 分支执行的频率占整个 SPEC分支的权重 图 3说明了不同分支指令执行在整个程序分支的权重，上面所说的执行 99次或者更少的分支 指令有 53%，图 2所统计的执行 99次或者更少的分支指令占 spec程序的 53%，但是这 53%的指 令在 spec程序分支执行比重中只占 0.2%，在柱状图上都显示不出来。而图 2所示的占 11％的分 支指令占据了所有分支执行的 87％，也就是 10％的指令占据了程序 90％的运行时间。 图 4统计了分支预测的分支成功率的分布。分支成功率是分支指令成功跳转除以整个程序运 行的分支总数。从图上统计可以看出来大概 28%的指令总是跳转或者总不跳转，另外有 32%的指 令，跳转的几率总少于 5%或者多于 95%总跳转，也就是说 60％的分支指令具有强烈的一个跳转 方向，所以可以推出，具有挑战性的工作是预测其余 40%的分支跳转。 图 4分支成功率权重分布 2.2 程序的分支属性 我们所运行的程序中有大量的分支指令，这些指令组合起来就表现为程序的分支行为，不同 应用程序的分支行为非常复杂。国际上对分支预测的研究一般都主要针对SPEC CPU（简称SPEC） 的程序，因为SPEC程序是专业测试机构精心挑选出来的、在各个行业有代表性应用的一组程序[3]， 一般国际上都是通过对比SPEC的分数来说明处理器性能。对SPEC测试程序的分析表明 5 到 7 条 指令里面就有 1条分支指令，而处理器一般都是一次取 4到 6条指令，也就是说几乎每次都可能 取到一条分支指令，这进一步说明了对分支指令研究的重要性，甚至有文章认为分支预测将来可 能是处理器性能提高的瓶颈[4]。总体而言程序分支行为有以下特点： 循环结构在现在程序中大量存在。大量的研究表明，循环结构的分支指令行为在程序中是最 为常见、重复出现的一种分支模式。一般我们可以用一个字符串来记录程序循环模式，比如一个 循环 10 次的程序可以用 1110100110来表示，其中 0 代表不跳转，1 代表跳转。前文已对分支指 令的属性作了说明和分类，而多条分支指令组合成程序的分支行为，可以根据循环的模式来进行 分支预测，这些模式在 SPEC程序几十亿指令的执行过程中会重复出现。 程序分支属性存在系统性（或者联想性）。这种形式不重复出现，但是大量存在，例如 SPEC 的 parse 程序分析一个单词“chines”，它自然会预测到下一个字母是 e，[7]的研究中表明 30%的 分支有这样的系统推测行为。但是由于程序的行为非常复杂，目前这方面研究还没什么太大进展。 程序分支之间有相关性。相关性一般多出现在程序的if-else分支[8]。研究表明如果一段程序中， 2 条同样类型的分支指令有相反的分支结果，一般这两条分支指令是相关的。这就告诉我们如果 预测成功其中一条分支指令，就可以知道另外一条分支指令的预测结果。以前的研究[7]表明 60％ 的分支指令具有相关性，这也成为后面分支预测的主要基础。 3 分支预测的预测机制 分支预测按输出结果可以分为两个问题：第一是分支指令方向预测，就是预测分支指令是跳转 （taken）还是不跳转（not taken）；第二是分支指令地址的预测，分支地址只有在流水线指令执 行阶段才能计算出来，为了避免等待，需要在译码阶段进行预测。一种常见的解决方法是采用 BTB[8]。 分支预测按工作方式可以分为静态和动态两种。静态是在程序编译时候进行分支预测，主要 是对大量的循环有效。动态与静态的主要区别是，动态分支预测器可以在程序运行时根据分支指 令执行情况进行调整，而静态分支预测在编译时完成后就不再改变了。 3.1 基本分支预测器 简单静态分支预测 最简单的静态分支预测有两种情况，要么预测分支总是执行跳转(taken)，要么预测分支总是 不执行(not taken)。这种方法实现简单且预测速度快，但是静态分支预测对不同程序表现不一样， 如果程序循环比较多，预测成功率就高，反之预测精度就低，预测精度一般都在 40%-60%之间。 BTFN预测(Back Taken, Foreword Not taken) 针对静态分支预测的缺点，有人随后提出一种改进的方法：假如分支地址是正增加的那么就 预测不跳转，如果分支地址是往回跳的就预测分支跳转，这种算法对单循环很有效。 以上两种预测机制的优点就是硬件开销很小，所以在半导体工业早期集成度还不是很高的时 候被广泛使用，比如IBM360/370[9]。现在的应用程序大概每 5－7条指令就有一条分支指令，这个 精度根本不能满足处理器对高性能的需求，所以现在的高性能处理器基本没有采用的了，但是嵌 入式处理器还有采用。 Profile预测 在静态分支预测之后，学术界开始了在编译器上开始了基于分支的profile研究[10]，即先运行 一遍程序把分支跳转的信息记录下来，然后把这些信息告诉编译器，在此基础上再进行编译，通 过增加代码来增加程序空间局部性，这样在静态分支预测基础上能提高分支预测准确率。 1位分支预测（last time） 图 5 一位分支预测 静态分支预测不能满足要求，为了 提高处理器性能又提出了动态分支预 测器，其中最简单的就是 1 位分支预 测器[11] 。基本思想就是当前分支预测 和上次分支预测有同样的结果，所以 也叫前次（last time）分支预测。1 位 分支预测器通过一个动态位来记录分 支结果，0表示分支不跳转， 1 表示分支跳转，分支指令通过地址来索引一个 1 位的表以预测分支是否成功，当分支指令提交 的时候根据实际的方向修改表。 （BHR，Branch History Register），用来记录最近 k条分支的分支结果。第二级被称作模式历 史表（PHT，Pattern History Table) 通常历史记录在一个表里，PHT的表组成可以多种多样，不过 研究表明采用 2 位分支预测器最好。用 BHR 来索引 PHT，也就是根据我们前面程序分支特性介 绍，2级分支预测的基本思想就是用分支的历史模式来索引一个 2位分支预测器。2级分支预测精 度在模拟情况下很好，达到了 97%。测试向量当时采用的是 SPEC CPU89。不过在后来的研究表 明，SPEC CPU89这套测试程序分支指令并不是很难被预测，甚至 2位分支预测采用 SPEC CPU89 的测试向量，测试精度都能达到 90％左右。 图 8基于历史的分支预测 图 9全局分支预测器 图 10 局部分支预测器 基于历史的分支预测 在发现上面分支相关问题后，S.潘、K.索和J.拉赫梅（S. Pan. K. So, and J. Rahmeh）提出了一 种新的预测机制[12]，如图 8所示，用一个全局历史寄存器去索引一个 2位分支预测表，预测结果 由 2位分支预测表给出。这种分支预测的机理是，假设以前的n条分支指令和当前分支指令相关。 但是这种分支预测机制，没有考虑地址，只考虑所关心的分支的历史，所以效果不是很明显。 全局分支预测 全局分支预测如图 9所示。与局部分支预测不一样，全局分支的基本原理是，通过记录分支的前 n次历史预测分支，来预测当前分支的输出结果。第一级是一个 BHR通过移位记录历史，第二级 是一个 2位分支预测。这样的预测机制对 if-else这样的指令相关预测非常有效，用踪迹驱动（trace driven）的模拟器研究数据表明：同样的代码，全局分支预测要比 2位分支预测好。尤其现在高 级语言里面有大量的 if-else语句，因此用全局分支预测效果就会比较好。 局部分支预测 如图 10 所示，每一个分支指令地址都分别记录在一个BHR中，这些BHR就构成了转移历史 表（BHT，branch history table)。传统的看法认为对于科学计算测试向量而言，局部分支预测要好 于全局分支预测[15]，这是因为科学计算测试程序中含有大量的循环，每一个循环有一个BHT。但 正因如此分支预测表的硬件开销很大，另外由于表一般很大，整个分支预测器训练的过程就比较 长，对小程序效果反而会变差。 组合分支预测器 2级分支预测出现后 ，大量研究表明不同的分支预测只能对某类的分支行为有效，而没有万 能的分支预测。这种情况下有人就把不同分支预测组合起来，根据分支行为来选取不同分支预测 器，这就是如图 11的混合分支预测器[16]。 图 11 混合分支预测器 图 12 alpha21264分支预测器 如图 11所示，混合分支预测器可以选用多种分支预测器，然后通过一个选择机制进行预测， 混合预测器的选择机制就成为一个需要考虑的问题。如图 12 所示，Alpha21264 就是采用局部 2 级分支预测器和全局 2 级分支预测进行混合的分支预测。全局用 12 条分支历史来索引 4k 项的 PHT；局部分支预测用一个 2级分支预测，第一级是一个 1024项的 10位历史，分别用 0和 1表 示跳转和不跳转，第二级是一个 1024项的 3位饱和分子预测器。这种预测机制使得对浮点预测达 到了 1000条指令 1条预测错误，定点 1000条指令有 11条预测错误。 以上基本上是传统分支预测器的预测机制，下表是以前工业界处理器采用分支预测机制的情 况。 处理器 分支预测器 Intel 8086 无分支预测 Intel 486 总是跳转 Sun superSparc 总是不跳转 HP 7x00 BTFN 静态分支预测 早期的 PowerPC Profile Alpha21064、AMD K5 1位分支预测 PowerPC604 、 MIPS R10000 2位分支预测 Pentium Pro、Pentium II 2级分支预测 动态分支预测 Alpha 21264 组合分支预测 表 1 一些典型商品处理器的分支预测机制 4 分支别名干扰问题 图 13 分支别名干扰问题 自从 2级分支预测器出现以来，预测精度一般都在 92％左右，无论 BHT和 PHT表如何增大， 效果也不是很明显。分支精度能不能提高成为当时超标量处理器性能提高的关键。经过大量研究 表明，分支精度不能提高的主要原因是不同分支地址访问同一个 PHT，造成分支干扰。 图 14 Gshare分子预测器 图 15 Agree分支预测 Gshare和 Gselect分支预测器 克服这一困难最简单的方法是DEC西部实验室麦克法林（McFarling）提出来的Gshare分支预 测器[16]，如图 14所示。它把分支地址和分支历史进行异或运算，然后去索引PHT，这样的好处就 是离散了原先的BHR。另外还有一种Gselect方法，分别取地址的高位和BHR的低位组合去索引 PHT，实验结果表明Gshare比Gselect好一点[16]。 Agree分支预测器 如图 15所示，在BTB中设置了一个偏差位，Gshare的分支预测器输出从是否跳转转化为是否 与BTB输出的结果一致，Agree的基本思想还是我们前面所说的分支指令 83%是具有强烈跳转或者 不跳转的偏差特性的。在[17]文中说明仿真显示Agree分支预测器对SPEC的gcc测试程序有 8%-30%的提高[17]。而且Agree的分支预测器在HP的处理器中得到实际应用。 图 16 Bi-Mode分支预测 图 17 Skewed分支预测 Bi-Mode分支预测器 如图 16所示，Bi-mode和Agree分支预测的思想一致，不过它是把容易发生跳转和不跳转的分 布放入不同的PHT[18]。它由 3 部分组成，一部分用来选择PHT，另外两部分表示PHT的方向，分 别为跳转和不跳转，PHT的方向被全局历史索引。 Skewed分支预测器 如图 17 所示，Skewed的分支预测的主要思想是，分支的别名冲突并不是因为PHT太小，仿 真发现PHT再大也不能降低别名冲突，而是组相连度不够。Skewed分支预测器把PHT分为 3个奇 偶块，通过哈希访问每一个块的 2位分支预测[19]，假如分支预测错误 3个块都更改，如果分支预 测正确则只有一个块更改。Skewed分支预测器有 1/3-2/3 的容量冗余，而且对于上下文切换，分 支的训练很慢。 图 18 Filter预测器 图 19 YAGS分支预测器 Filter分支预测器 如图 18所示，Filter分支预测的主要思想是减少PHT中的冗余信息。PHT中大量的分支预测是 高度偏向某个方向的，Filter机制是想把这些信息用一位分支预测器记录在BTB中。当一条分支指 令处理后，如果分支方向和偏向位一致，则 1位分支预测器增 1；否则 1位分支预测器置为 0，偏 向位翻转。假如 1位分支预测器饱和，则表明该分支高度偏向一个方向，偏向位被设置为预测方 向，分支指令采用PHT进行预测。Filter分支预测机制通过减少PHT的冗余消除了大量别名冲突， 然而对高度偏向的分支指令的预测效果会差[20]。 YAGS分支预测 如图 19所示，YAGS（Yet Another Global Scheme）是在总结上述预测器的基础上进行组合的一种 机制。由于 PHT包含了大量的冗余信息，而实际上分支预测器只需存储历史的偏移就可以，而不 必存储所有分支的所有内容。YAGS采用前面介绍的 Bi-mode结构存储这些偏移，只需增加标签 （tag）索引,而不用存储大量分支无关信息。不像传统缓存的标签，YAGS的标签只是地址的 低位。文章[21]仿真说明 YAGS比前面的机制预测精度高而且硬件开销也不是很大。 5 分支预测的现状 历史总是重复出现，当年 2位分支预测再也不能提高分支预测精度，发现了主要原因是没有 考虑分支相关，从而提出了 2级分支预测解决这个问题，使得预测精度大大提高。与此类似，当 2 级分支预测遇到瓶颈的时候，发现了主要原因是分支别名问题，也就是多地址访问同一个分支 历史表，造成分支干扰，学术界又提出了大量的解决方案，多种分支预测器被提出，比如 Agree， Bi-mode等，这个研究热情一直持续到 90年代末。 伴随着指令集并行为代表的超标量处理器的成熟，传统分支预测也日趋成熟。当人们觉得分 支预测已经很难再有进步的时候出现了新的转机，主要有如下原因：第一，随着新应用的出现及 新处理器结构的提出，需要有新的预测机制，如下面介绍的SMT结构的分支预测等；第二，处理 器功耗越来越重要，处理器性能和功耗的需要进行权衡，这就需要更好的理解处理器分支预测和 功耗的关系；第三，对提高处理器分支预测精度的需求依然很大，比如分支精度提高 0.5%，10000 条分支指令就能够使得预测成功率提高 50次，减少 50次流水线的刷新，对性能提升很有好处。 近几年国际上学术界开始举办分支预测大赛，神经网络分支预测器成为当前的研究热点，这方面 文章在近年的Micro2，ISCA3上出现[22][23]。 SMT分支预测器 随着超标量处理器的成熟，挖掘指令级并行性越来越困难，同时多线程（SMT，Simultaneous Multi-Threading）结构能有效挖掘线程级并行性，在现代处理器中得到广泛应用。由于 SMT的基 本特点是同时从多个线程取指令，如何设计分支预测器是个问题。是每个线程采用独立的分支预 测器，还是多个共享一个分支预测器？如果多个线程共享一个分支预测器，会不会发生线程间干 扰现象？这些问题都需要研究。 文章[24]指出，如果多个线程共享一个分支预测器，而且保持 PHT或者 BTB的大小和线程数 目成比例增长，那么各个线程之间的干扰就很小。文章[25]研究了 SMT结构分支预测器的组织结 构，把 SMT的分支预测器分为 4类，包括:多个线程共享一个分支预测、每个线程一个分支预测 器、每个线程共享 PHT分别有自己 BHT、每个线程共享 BHT分别有自己的 PHT。最后仿真结果 表明，每个线程分别有一个分支预测器比多个线程共享一个分支预测器效果要好，但差别不是很 明显。 Power Aware（节约功耗导向）分支预测 2000年以来，半导体工业进入了深亚微米，集成度越来越高，处理器规模越来越大。这就使 得处理器功耗急剧上升，此外芯片过热使得芯片封装很困难，这样 Power-aware 的处理器设计成 为研究热点。由于分支预测器对处理器性能影响很大，如何平衡它的精度和功耗是一个值得研究 的问题。文章[26][27]研究了通过分支预测来减少漏电功耗；[28]研究了分支预测和功耗的关系。 神经网络预测器 随着分支预测研究的深入，学术界认识到分支预测的本质是机器学习问题，而机器学习已经 在模式识别、自动控制等领域进行过大量研究，其中神经网络是目前机器学习的有效方法。罗格 斯（Rutgers）大学的丹尼尔.A.希梅内斯（Daniel. A. Jimenez）最先在 2001年HPCA会议上将神经 网络引入了分支预测领域[28]。文章[28]研究表明，对于 4K的硬件开销，采用SPEC CPU2000测试 程序，神经网络分支误预测率要比Gshare降低了 26%，比组合分支预测降低了 12%。将神经网络 引入分支预测领域，使得分支预测研究又开始活跃，许多新的分支预测机制被提出[29]。分支预测 2 Annual International Symposium on Microarchitecture 3 International Symposium on Computer Architecture 和神经网络都有很多内容，可以参考文章[30]。 分支预测竞赛 由于应用程序在变，程序行为也发生变化，为了进一步提高分支预测的精度以提高处理器性 能，国际上从 2004年开始每两年举行一次分支预测大赛[31]。这个竞赛对每一个参赛者的约束是： 在(64K+256)Bit的分支预测大小取得最好的分支预测精度，而不用考虑功耗、价格、延迟等影响。 提交的分支预测器通过 21个踪迹（trace）来比较，踪迹又分为 2种，一种是给每个竞赛者用的分 发的踪迹，还有一种是不给竞赛者而组织者进行测试的，每 3个踪迹又分为一组，分别为SPECfp、 SPECint、Internet、Multimedia、Productivity、Server和Workstation 7组代表不同应用。 在第一届分支预测竞赛上，美国的华人教授高洪亮（译音，Hongliang Gao）取得未分发踪迹 的第一名，而分发踪迹的第一名由法国的安德列（André）教授获得。他们的分支预测正确率都在 98％左右（作为对比，gshare大概在 95％左右），而分支预测正确率的 1％提升对于处理器性能的 提高都很大。 Hongliang Gao的分支预测是采用神经网络预测器，由此也引发了最近分支预测研究和神经网 络结合的热潮。相比而言安德列（Alpha EV8分支预测器的主要设计者[32]）的分支预测器更实用 一些，通过优化分支指令长度得到了很好效果。 6 结束语 综上所述，分支预测的发展一直伴随着高性能处理器的发展，分支预测器对处理器性能提高 起着重要作用，一直都是处理器设计的重中之重。目前分支预测技术发展遇到了一个瓶颈，其最 高精度达到 95-98%，很难进一步提高。但是随着大量新应用程序的出现，又有新的程序分支行为， 以及对硬件开销、功耗等因素考虑，分支预测技术将会有一些新的发展。例如，SPEC组织正在进 行功率测试标杆程序（Power benchmark）的研究；另外随着半导体摩尔定律的延续，分支预测器 可以越做越大（比如Alpha 21464分支预测器有 352KBit[32]，几乎和一级缓存规模相当）；此外在 分支预测器设计中如何平衡功耗是个大问题。目前神经网络分支预测器是学术界的研究热点，可 以预见近期这方面研究将有可能取得大的进展。 参考文献： [1] YN Patt, SJ Patel, DH Friendly, and J. Stark. One Billion Transistors, One Uniprocessor, One Chip, IEEE Computer, pp. 51 -- 57, Sept. 1997 [2] Introduction to Intel Core Duo Processor Architecture， Volume 10 Issue 02 May 15, 2006 [3] The Standard Performance Evaluation Corporation http://www.specbench.org/ [4] P. Ranganathan, and N. Jouppi. The relative impact of memory latency, bandwidth and branch limit to microprocessor performance. In Proceedings of the 1s Workshop on Mixing Logic and DRAM: Chips that Compute and Remember (held inconjunction with the 1997 International Symposium on Computer Architecture), June 1997. [5] D. Kaeli and P. Emma, “Branch history table predictions of moving target branches due to subroutine returns,” in 18th Annu. Int. Symp. Computer Architecture, 1991. [6] P.-Y. Chang, E. Hao, and Y. N. Patt, “Predicting indirect jumps using a target cache,” in Proc. 24th Annu. Int. Symp. Computer Architecture,1997. [7] M. Evers, S. J. Patel, R. S. Chappell, and Y. N. Patt, “An analysis ofcorrelation and predictability: What makes two-level branch predictors work,” in 25th Annu. Int. Symp. Computer Architecture, 1998. [8] DA.Patterson and JL Hennessy. Computer Architecture: A Quantitative Approach 3rd. ed. Morgan Kaufmann, San Mateo, 2003. [9] D. W. Anderson et al. The IBM System/360 model 91: Machine philosophy and instruction handling, IBM Journal (Jan. 1967), 8-24. [10] J. A. Fisher and S. M. Freudenberger, “Predicting conditional branch directions from previous runs of a program,” in 5th Int. Conf. Architectural Support for Programming Languages and Operating Systems,1992. [11] J. E. Smith, “A study of branch prediction strategies,” in 8th Int. Symp. Computer Architecture, 1981. [12] S. Pan. K. So, and J. Rahmeh. Improving the accuracy of dynamic branch prediction using branch correlation. In Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems, 1992, pp.76-84. [13] T.-Y. Yeh and Y. N. Patt, “Two-level adaptive branch prediction,” in 24th ACM/IEEE Int. Symp. Microarchitecture, 1991. [14] “Alternative implementations of two-level adaptive branch prediction,” in 19th Annu. Int. Symp. Computer Architecture, 1992. [15] C. Yound and M. Smith. Improving the accuracy of static branch prediction using branch correlation. In Proceedings of the 6thInternational Conference on Architectural Support for Programming Languages and Operating Systems, October 1994, pp. 232-241. [16] S. McFarling, “Combining branch predictors,” Digital Equipment Corporation, WRL Tech. Note TN-36, 1993. [17] E. Sprangle, R. Chappell, M. Alsup, and Y. Patt. The Agree predictor: Amechanism for reducing negative branch history interference. In Proceedings of the 24th Annual International Symposium on Computer Architecture, May 1997. [18] C.-C. Lee, I.-C. Chen, and T. Mudge. The Bi-Mode Branch Predictor. Proc. MICRO 30, Dec. 1997. [19] P. Michaud, A. Seznec, and R. Uhlig. Trading conflict and capacity aliasing in conditional branch predictors. In Proceedings of the 24th Annual International Symposium on Computer Architecture, May 1997. [20] P. Chang, M. Evers, and Y. Patt. Improving branch prediction accuracy by reducing pattern history table interference. In Proceedings of the International Conference Parallel Architecture and Compilation Techniques. October 1995. [21] A. Eden and T. Mudge, “The YAGS branch predictor,” 31th Ann. IEEE/ACM Symp. Microarchitecture (MICRO-31) Dec 1, 1998 [22] Daniel A. Jiménez, Fast Path-Based Neural Branch Prediction, Proceedings of the 36th Annual International Symposium on Microarchitecture (MICRO-36), December 2003 [23] A. Gandhi, H. Akkary, and ST Srinivasan. Reducing branch misprediction penalty via selective branch recovery. In Proceedings of The Tenth International Symposium on High-Performance Computer Architecture, pages 254--264, December 2004. [24] Branch Prediction and Simultaneous Multithreading. SCbastien Hily* and AndrC Seznec. IRISA/INRIA. Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques (PACT '96) [25] Matt Ramsay, Chris Feucht, and Mikko H. Lipasti, Exploring efficient SMT branch predictor design. Workshop on Complexity-Effective Design , in conjunction with ISCA, 2003. 26 [26] Z. Hu, P. Juang, P. Diodato, S. Kaxiras, K. Skadron, M. Martonosi,and D.W. Clark, “Managing Leakage for Transient Data: Decay and Quasi-Static Memory Cells,” Proc. 2002 Int’l Symp. Low Power Electronics and Design, pp. 52-55, Aug. 2002. [27] Z. Hu, P. Juang, K. Skadron, D. Clark, and M. Martonosi,“Applying Decay Strategies to Branch Predictors for Leakage Energy Savings,” Proc. 2002 Int’l Conf. Computer Design, pp. 442-445, Sept. 2002. [28] JIM´ENEZ, D. A. AND LIN, C. 2001. Dynamic branch prediction with perceptrons. In Proceedings of the Seventh International Symposium on High Performance Computer Architecture, 197–206. [29] Daniel A. Jiménez, Piecewise Linear Branch Prediction, Proceedings of the 32nd International Symposium on Computer Architecture (ISCA-32), June 2005 [30] Daniel A. Jiménez and Calvin Lin, Neural Methods for Dynamic Branch Prediction, ACM Transactions on Computer Systems, Vol. 20, No. 4, November 2002. [31] http://www.jilp.org/cbp [32] Design Tradeoffs for the Alpha EV8 Conditional Branch Predictor. to appear in Proceedings of the 29th IEEE-ACM International Symposium on Computer Architecture, 25-29 may 2002 作者简介： 冯子军： 中科院计算技术研究所微处理器研究中心，博士生 肖俊华： 中科院计算技术研究所微处理器研究中心，博士生 章隆兵： 中科院计算技术研究所微处理器研究中心，副研究员 多核加速串行程序技术综述 侯 锐 摘要：随着片上多核处理器（CMP4）时代的到来，如何利用多核加速串行程序成为迫切需要解决的问题。本文综 述了该领域的主要研究工作，介绍了我们目前在该领域的研究情况，总结了该领域的发展规律。 1 片上多核处理器时代的到来 回顾微处理器的发展历史,从 1940 年开始大约每十年就会提出新一代处理器结构[1]。半导体 工艺的发展和人们对性能的无止境的追求是驱动微处理器设计发展的重要因素。更有意思的是， 处理器的体系结构经历了一个否定之否定的发展过程。处理器结构经历了简单Æ复杂Æ简单Æ复 杂的螺旋式发展过程：由于当时器件工艺的限制，20世纪四五十年代的处理器结构非常简单；六 七十年代出现了流水线，向量机以及访存层次等技术，这些技术使处理器结构变得复杂起来；八 十年代，RISC体系结构的提出大大简化了处理器的复杂性；随后，为了提高性能，人们把超标量、 乱序执行以及更复杂的存储层次技术引入到RISC5体系结构中，再次使处理器的结构变得越来越 复杂。基于以下四方面的原因，我们认为处理器结构现在面临着新的变革机会，会从复杂回归到 简单[1，31]。 首先，半导体工艺的持续发展在很大程度上影响了处理器的微体系结构设计。半导体工艺的 发展提供了越来越多和运行速度越来越快的晶体管资源，这给体系结构研究者提出了非常大的挑 战，其中包括控制时钟延迟、降低功耗、控制设计和验证的复杂度，以及缩短生产周期等。 随着工艺的发展，线延迟取代晶体管的翻转速度成为影响处理器时钟频率的决定因素。在深 亚微米工艺的设计背景下，信号从芯片的一端传输到另一端需要好几个时钟周期[2]。Alpha21264 以及Pentium IV 已经开始用专门的流水级传输信号。传统的处理器设计方法受到了前所未有的挑 战。另外一个不容忽视的问题就是控制设计的复杂度。尽管EDA厂商不断推出更好的EDA工具， 处理器的设计队伍还是不得不随着芯片的晶体管数目和频率的增加而增加，需要越来越多的 师验证越来越复杂的设计。 其次，依靠提高流水线频率和复杂的结构设计来改善性能的方法现在面临非常大的障碍。工 艺的发展可以提高流水线频率，并且使得复杂的设计有实现的可能性。然而，诸如超流水和超标 量等挖掘指令级并行的技术使得处理器核的设计变得越来越复杂，以致于设计过程越来越难以控 制。可以预见，这类复杂的设计方法（增加发射宽度以及切分流水线）提高性能的空间会越来越 小。摩尔定律关于处理器主频方面的预测会逐渐失效。原因之一是巨大的能量消耗，第二是线延 迟的影响，另外的原因包括难以进一步细分流水线。 第三，功耗问题在处理器设计中变得越来越重要。目前商用处理器耗能超过 100瓦特，这给 封装和散热技术提出了非常大的挑战。人们对处理器的指标正在发生变化，从成本— 单位价 格可购得的性能（performance per dollar），到速度 — 单位时间能完成的动作（performance per second），现在逐渐变成能耗效率 — 单位功耗达到的性能（performance per watt） [1] 。 4 Chip Multiprocessing 或on-chip multiprocessor 5 Reduced Instruction Set Computing，精简指令集计算机 最后，新的应用对体系结构提出了新的要求，包括实时响应能力、流数据处理、进程或线程 级的并行性、I/O带宽以及功耗等。这些要求直接促进了新的体系结构的出现。 实际上，关于未来处理器体系结构发展方向的争论是现在体系结构研究领域非常热门的话题 之一。毫无疑问，处理器结构现在面临着新的变革机会，会从复杂而简单。未来将充满前所未有 的挑战和机遇。目前的体系结构技术主要通过挖掘三种并行性来提高性能,即指令级并行性,数据级 并行性以及线程级并行性。本文分别分析这三种并行性以及相关典型结构，探索未来体系结构的 可能的发展方向。 1． 指令级并行性（ILP6）—程序代码本质上是偏序的，这意味着可以同时发射执行多条不相关 的指令，这种指令间的可重叠性或无关性就是指令级并行性。挖掘指令级并行性有两大类方 法，一类是通过硬件动态的发现和利用指令间的并行性，比如超标量和超流水技术；另一类 是通过软件来静态识别指令级并行性，比如EPIC7和VLIW8技术。 超标量和超流水技术在 20世纪 90年代广泛用于商用处理器上。为了同时执行更多的指 令，研究人员提出许多微体系结构的技术，包括乱序执行、多层次的存储层次以及片上缓存 （cache）、各种激进的推测执行技术（比如分支预测、值预测等）。这些技术在提高性能的同 时，大大地增加了整个结构的复杂程度。更重要的是，研究表明，ILP能够挖掘的空间有限。 在目前物理设计所能实现的指令发射窗口的前提下，4 发射的超标量处理器的IPC9通常在 2 左右。另外，超流水技术以不断切分流水线的方式来提高主频，进而达到提升性能的目的。 目前高主频的处理器流水线已经很难再细分，同时更深的流水线也增加了转移预测失误的代 价。 EPIC和 VLIW技术需要依靠强大的编译器来识别 ILP。这种静态方法并不能完全识别程 序动态执行所揭示的并行性，同时对于不同的指令集需要考虑兼容性的问题。 总之，挖掘指令级并行性提高性能的方法通常以复杂的结构设计／验证／测试，低效的 资源利用率，以及高功耗为代价。事实上，挖掘指令级并行性所能够预期的性能提高空间开 始逐渐变得越来越有限。那么，如何保证性能随着晶体管数目的增加而增加？人们把目光投 向了挖掘其他层次的并行性。 2． 数据级并行性（DLP10）—数据级并行性广泛存在于科学计算，网络，媒体以及数字信号处 理等应用领域。在这些领域可以通过挖掘数据级并行性取得显著的性能提高效果。向量机在 超级计算领域仍然占有重要的地位，SIMD11技术也被广泛地用于通用处理器领域，比如 Pentium IV采用SSE2指令集和专门的硬件来支持媒体应用。尽管挖掘DLP的技术不能在高性 能通用计算领域扮演主流角色，但是该技术仍然可能以协处理器或特殊功能单元的形式发挥 重要作用。 3． 线程级并行性（TLP12）—多线程应用不仅广泛存在于商业服务器领域（比如在线事务处理、 企业资源管理、Web服务以及协同组件等），并且会随着面向对象方法和虚拟机技术的发展 大量出现在桌面应用领域。可以通过挖掘线程级并行性来提高多线程应用程序的性能，这类 研究是目前高性能处理器领域的热点问题。 6 Instruction Level Parallelism 7 Explicitly Parallel Instruction Computing-显式并行指令计算 8 Very-Long Instruction Word超长指令字 9 Instructions Per Clock Cycle每时钟周期完成的指令数 10 Data-level parallelism 11 Single Instruction Multiple Data，单指令多数据流 12 Thread-Level Parallelism，线程级并行 下面我们分析三种具有代表性的挖掘线程级并行性的体系结构： 传统多线程处理器通过时间共享的方式支持多线程的执行。专门的硬件机制以块（block）或 指令的粒度进行线程调度。对于前者而言，处理器执行来自于同一个线程的指令直到某种可能引 起长延迟的事件发生（比如缓存未命中，cache miss）,然后自动切换执行另一个线程。HEP和MTA 等系统均采用了类似的体系结构；后者则是在每个周期从不同的线程取指执行，比如MIT Sparcle.。 同时多线程处理器允许处理器在同一个周期从不同的线程取值发射执行。除了复制必要的线 程上下文相关的部件之外，不同的线程共享同一个流水线[18]。同时多线程能够有效地提高芯片上 的资源利用率，然而由于受限于共享寄存器堆栈大小的限制，同时多线程处理器很难在单核上支 持更多的线程。可扩展性方面的缺陷决定了同时多线程处理器技术不能成为未来处理器的发展方 向。