logo资料库

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

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：0.47M 资料格式：pdf 举报 版权申诉
第1页 / 共11页
第2页 / 共11页
第3页 / 共11页
第4页 / 共11页
第5页 / 共11页
第6页 / 共11页
第7页 / 共11页
第8页 / 共11页
资料共11页，剩余部分请下载后查看
    1 引言
    2 分支行为
    2.1 分支指令的基本属性
    2.2 程序的分支属性
    3 分支预测的预测机制
    3.1 基本分支预测器
    4 分支别名干扰问题
    5 分支预测的现状
    6 结束语
    处理器分支预测研究的历史和现状 冯子军 肖俊华 章隆兵 摘要 在过去十几年中，分支预测技术一直是提高处理器性能的重要方法，工业界和学术界对之进行了大量研究。 分支预测的本质是克服指令控制相关，提高指令并行度。随着研究的不断深入，当前学术界认为分支预测是一个 指令学习的过程，这就使得对分支预测的研究出现了新的趋势。本文对分支预测技术的历史和研究现状进行了归 纳，以便从总体上了解分支预测技术的发展过程。 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%的分支跳转。 2.2 程序的分支属性 图 4 分支成功率权重分布 我们所运行的程序中有大量的分支指令，这些指令组合起来就表现为程序的分支行为，不同 应用程序的分支行为非常复杂。国际上对分支预测的研究一般都主要针对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） 静态分支预测不能满足要求，为了 提高处理器性能又提出了动态分支预 测器，其中最简单的就是 1 位分支预 测器[11] 。基本思想就是当前分支预测 和上次分支预测有同样的结果，所以 也叫前次（last time）分支预测。1 位 分支预测器通过一个动态位来记录分 支结果，0 表示分支不跳转， 图 5 一位分支预测 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 早期的 PowerPC 无分支预测 总是跳转 总是不跳转 BTFN Profile Alpha21064、AMD K5 1 位分支预测 PowerPC604 、 MIPS R10000 Pentium Pro、Pentium II Alpha 21264 2 位分支预测 2 级分支预测 组合分支预测 表 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 结构存储这些偏移，只需增加标签
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料