3.11 Branch prediction in AMD K8 and K10
BTB organization
The branch prediction mechanism of the K8 and K10 AMD processors is connected to the code cache. The level-1 code cache has 1024 lines of 4*16 bytes each, 2-way set associative.
Each 16-bytes block in the code cache has an associated set of branch indicators. There are nine branch indicators, associated with byte number 0, 1, 3, 5, 7, 9, 11, 13 and 15 of the code block. Most branch instructions are two or more bytes long. A branch instruction that is two or more bytes long will have at least one branch indicator even when there are only indicators for the odd addresses and address 0. The extra indicator at byte 0 covers the case where a branch instruction crosses a 16-bytes boundary and ends at byte 0.
Each branch indicator has two bits of information to cover the following cases: (0) no branch or never jump, (1) use branch selector 1, (2) use branch selector 2, (3) use branch selector 3. There are three branch selectors in addition to the nine branch indicators. Each branch selector has an index into the branch target buffer as well as a local branch prediction information. The local branch prediction information can be 'never jump', 'always jump', 'use dynamic prediction', or 'use return stack buffer'. There is also an indication of whether the branch is a call. This is used for pushing a return address on the return address stack (see page 34).
The branch target addresses are saved in the branch target buffer (BTB), which has 2048 entries. Return addresses are stored in the return address stack, which has 12 entries in K8 and 24 entries in K10.
The branch prediction mechanism works as follows: A branch that is never taken gets no branch indicator, no branch selector and no BTB entry. The first time a branch is taken, it gets a branch selector which is set to 'always jump' and a BTB entry to indicate the target address. If the branch is later not taken, then the branch selector is changed to 'use dynamic prediction'. It never goes back from 'use dynamic prediction' to 'always jump' or 'never jump'. The dynamic prediction mechanism is described below. The predictor bits can indicate at least the following values: 'no jump', 'always jump', 'use dynamic prediction', 'use return stack buffer'. The K10 also has predictors for indirect jumps.
Some documents say that return instructions occupy a branch target entry which is used when the return stack buffer is exhausted, but experiments seem to indicate that returns are always mispredicted when the return stack buffer is exhausted.
The branch indicators and part of the local branch prediction information is copied to the level-2 cache when evicted from the level-1 cache. The index into the BTB is not copied to the level-2 cache due to lack of space. There is a branch target address calculator which can calculate the target address for direct jumps and calls in case a BTB entry is missing or the BTB index has been lost due to eviction to the level-2 cache. The calculation of a lost branch target address takes an extra 4 clock cycles, according to my measurements, which is less than the cost of a complete misprediction. This allows conditional and unconditional jumps and calls to be predicted correctly, even if they have been evicted from the BTB and/or the level-1 cache. The branch target address calculator cannot calculate the targets of indirect jumps and returns, of course. Returns are mispredicted if they have been evicted from the level-1 cache even they are still in the return stack buffer.
A drawback of this design is that there can be no more than three control transfer instructions for every aligned 16-bytes block of code, except for branches that are never taken. If there are more than three taken branches in the same 16-bytes block of code then they will keep stealing branch selectors and BTB entries from each other and cause two mispredictions for every execution. It is therefore important to avoid having more than three jumps, branches, calls and returns in a single aligned 16-bytes block of code. Branches that are never taken do not count. The three branch limit can easily be exceeded if for example a switch/case statement is implemented as a sequence of dec / jz instructions.
A further problem is that the design allows only one control transfer instruction for every two bytes of code. Most control transfer instructions use more than one byte of code, but return instructions can be coded as a single-byte instruction. This can cause two kinds of problems. This first kind of problem occurs if two branches share the same branch selector. If a branch instruction ending at an even address if followed by a single-byte return instruction at the following odd address, then the two instructions will share the same branch selector and will therefore be mispredicted most of the time.
The second kind of problem relates to single-byte return instructions having no branch selector. This can happen when there is a jump directly to a single-byte return instruction or a single-byte return instruction follows immediately after a mispredicted branch. If the single-byte return instruction is at an even address not divisible by 16 then the branch selector will not be loaded in these situations, and the return will be mispredicted.
The first kind of problem can be avoided by placing the single-byte return instruction at an even address, the second kind of problem by placing it at an odd address (or an address divisible by 16). Both kinds of problem can be avoided by making the return instruction longer than one byte. This can be done by inserting a segment prefix or F3 prefix before the return instruction to make it two bytes long, or by coding the return instruction with an offset operand of zero, which makes it three bytes long. It is recommended to make return instructions longer than one byte if there is a conditiona
剩余内容已隐藏，支付完成后下载完整资料
译文
分支预测
3.11在AMD K8和K10中的分支预测
BTB的组织
K8和K10 AMD处理器的分支预测机制被连接到代码高速缓存中。 每个一级的代码缓存有1024行的4*16个字节，2路组相联。
在代码高速缓存中的每个16字节的块具有的分支指标一组相关联。有九个分枝的指标，与相关联的字节数为0，1，3，5，7，9，11，13和15中的代码块。大多数分支指令是两个或多个字节长。分支指令是两个或多个字节长，即使有对奇数地址和地址0在字节0的额外指标覆盖的情况下只有指示器中的至少一个分支指示器，其中一个分支指令跨越16字节的边界并在字节0结束。
每个分支指示器具有的两个信息位，以覆盖以下情况：（0）没有分支或不跳转，（1）使用分支选择器1，（2）使用分支选择器2，（3）使用分支选择器3有三个分支选择器除了九个分支的指标。每个分支选择器具有一个指数到转移目标缓冲器以及一个本地分支预测信息。当地的分支预测信息可以是“从不跳”，“跃总”，“使用动态预测”，或“使用返回堆栈缓冲区”。还有的分支是否是调用的指示。这是用于在返回地址堆栈按下一个返回地址（参见第34页）。
分支目标地址被保存在转移目标缓冲器（BTB），其具有2048的条目。返回地址存储在返回地址堆栈，其中有以K8 12项和K10 24项。
分支预测机制的工作原理如下：这是从来没有一个分支得到没有分支指示器，没有分支选择，没有进入BTB。第一次分支，它获取被设置为“总是跳”和BTB条目以指示目标地址的分支选择器。如果以后不采取转移，则该分支选择器变更为“使用动态预测”。它从来不从后“使用动态预测”到“总跳”或“总不跳”。下面的动态预测机制描述。预测位可表示至少有以下值：“不跳”，“总跳”，“使用动态预测”，“使用返回栈缓冲区”。该K10还具有预测间接跳转。
一些文件说返回指令占据时返回堆栈缓冲器耗尽其用于分支目标条目，但实验似乎表明，当返回堆栈缓冲器耗尽返回总是错误预测。
分支指标和局部分支预测信息的一部分被复制到二级缓存从1级高速缓存逐出时。中的索引BTB不被复制到2级高速缓存由于缺乏空间。有一个分支目标地址计算器可以计算出目标地址直接跳转和调用的情况下，BTB项丢失或BTB指数已丢失，由于驱逐到2级高速缓存。丢失的分支目标地址的计算需要一个额外的4个时钟周期，根据我的测量，这是小于一个完整的错误预测的成本。这允许有条件和无条件跳转和调用正确预测，即使他们被赶出了BTB和/或1级高速缓存。该分支目标地址计算器不能计算间接的跳跃和收益的目标，当然。回报是错误预测，如果他们被赶出的1级高速缓存，即使它们仍然在返回堆栈的缓冲区。
这种设计的一个缺点是，可以存在用于每个代码排列16个字节块不超过三个控制转移指令，但不包括那些从来没有采取分支。如果在代码相同的16个字节块超过三个分支采取那么他们将继续互相窃取分支选择和BTB条目，并导致两个预测失误对每个执行。因此，重要的是要避免在一个单一的代码排列16个字节块多于三个跳转，分支，调用和返回。这是从来没有采取分支不计。可以很容易地超过三个分支的限制，如果例如switch/ case语句实现为DEC / JZ指令序列。
还有一个问题是，该设计允许每两个字节的代码只有一个控制转移指令。大多数控制转移指令用的代码多于一个字节，但返回指令可以被编码为一个单字节指令。这可能会导致两类问题。如果两个分支共享同一支路选择该第一类型的问题会发生。如果分支指令终止于一个如果随后在下列奇数地址单字节返回指令偶数地址，那么两条指令将共享相同的分支选择器，因此将错误预测在大多数时候。
第二类问题涉及不具有分支选择器单字节返回指令。当存在直接跳转到一个单字节返回指令或单字节返回指令一个错误预测转移之后紧跟就会发生这种情况。如果单字节返回指令是在偶数地址不是由16然后在该分支选择器将不会在这些情况下，被加载整除，返回将被错误预测。
第一类问题可被避免通过将单字节返回指令在偶数地址，第二类问题，通过将其放置在奇数地址（或地址被16整除）。这两种问题可避免通过使返回指令长于一个字节。这可以通过插入一个段前缀或F3前缀返回指令之前，使其两个字节长，或由编码返回指令为零的偏移操作数，这使得它的三个字节长来完成。建议使返回指令大于一个字节，如果有立即收到一个条件跳转，或是否有直接的跳跃到它。返回前，调用立即指令应当由跳转代替。
预测失败惩罚
AMD手册说，分支预测失败代价是10个时钟周期，如果代码段基址是零，12个时钟如果代码段基址为非零。在我的测试，我已经找到了分别为12和13个时钟周期最小分支预测错误惩罚。该代码段基址是在大多数32位操作系统和所有64位系统上为零。它几乎总是非零的16位系统（见第165页）。在误预测惩罚对应于流水线的长度。远跳转，调用和返回没有预测。
在条件跳转下的模式识别
在AMD使用两级自适应分支预测器具有全局8位或12位的历史，第14页解释的。简单重复的模式和一个重复小环路计数到9或13可以通过该机制来预测。 13页的规则告诉其重复分支模式可以完美地预测。
AMD的优化指南告诉全局模式的历史表有16K项。这个表由8或12位的全局历史结合分支地址的一部分的索引。我的在K8试验表明，它是由一个8位的历史索引和位分支指令的最后字节的地址的数4-9。这使得16k的条目，如果没有的比特相结合。这可能是一些的比特相异或彼此和/或与该分支目标地址的一部分。
分支始终走一样的路不影响全局分支历史寄存器。这是通过存储在分支选择器块中的信息来完成的。一个分支被假定为不跳转，直到它第一次跳转。后一个分支已经跳转首次假设总是跳转直到它下次不跳转。经过一个分支已经跳转然后不跳转它被标记为需要动态预测。它然后预测使用两级自适应算法具有一个8位的全局历史。这种机制使得有可能预测环路与重复计数到9或13，即使它们包含分支，只要分支总是同路。
我在K8的测试表明，动态分支预测往往比什么可以从上面和该模式的学习时间所描述的设计来预期可能相当长得多失败。我对这个没有解释，但是它可能是分支模式历史表是比指示的较小或该机制比这里描述的更复杂。
间接分支预测
K10具有512项间接跳转和间接调用一个单独的目标缓冲区。它可能共享与分支部双向12位的历史计数器。间接跳转有多个目标，如果他们遵循规律由此可以预测的。早期的处理器预测间接跳转到总是以同样的方式，如下所述。
返回堆栈缓冲区
返回堆栈缓冲区在K8 12项和在k10 24项。这是绰绰有余的，除了递归过程的正常应用。对于返回堆栈缓冲区的说明，请参见第34页。
3.12分支预测在AMD推土机，打桩机和压路机
AMD的推土机有一个新的分支预测设计，它没有连接到代码缓存，不同于以往的模式。该预测机制被描述为与局部预测器和一个全局预测器的混合体。最有可能的分支预测是基于感知器。一个感知器类似于一个神经元，它获知通过在分支历史跟踪的相关性。不像自适应两级预测，感知器预测可以学到很长的分支模式。分支目标缓冲器（BTB）有两个层次，按AMD的软件优化指南。 Level-1的BTB组织与128组*4路=512项一组相联高速缓存。2级BTB在推土机和打桩机中1024组*5路=5120项，大概10240项在压路机中。
BTB中和预测器在计算单元的两个核之间共享。
我测试表明，复杂的重复模式后的一定时间的学习以及预测。似乎有没有明显限制的分支模式的长度可以被预测，甚至很长模式可以预测的。似乎有没有循环计数器，并嵌套循环没有预测特别好。间接分支预测都很好。预测成功率是有点比以前的型号更高在压路机。
预测失败惩罚
该预测失败惩罚规定为至少20个时钟周期的条件和间接的分支机构和15个时钟周期为无条件跳跃和返回。我测试结果显示高达19个时钟周期的条件分支和22个时钟周期的返回。
返回堆栈缓冲区
返回堆栈缓冲区有24项。
3.13在AMD的Bobcat架构和Jaguar架构的分支预测
BTB组织
跳转和分支的位置被存储在两个阵列中，“稀疏分支标记阵列”，它可容纳2个分支的每个64字节高速缓存线，和一个“密集分支标记阵列”，它可容纳2个分支对每个8个字节的代码，根据文章下面引用。在测试中，Bobcat可以预测每64个字节的代码2个分支中的2级高速缓存，这表明在稀疏分支阵列，但不是密集分支阵列，耦合到这两个级别的高速缓存。如果两个阵列使用，我们所期望的最高数额为64个字节的1级高速缓存18个分支。在我的测试中，Bobcat和jaguar能够预测每1级高速缓存线16或17个分支，根据分支的位置，而不是18。有这些多个分支机构被超过时许多预测失误，作为分支保持驱逐对方的阵列。被从未采取分支包括在分支标记阵列。
预测失败惩罚
下面所引用的文章指出的13个时钟周期错误预测损失。在测试中，然而，预测失败惩罚从8至19个时钟周期不等根据后续指令。有这方面的整数和浮点代码之间没有一致的差异。
模式识别条件跳转
分支预测大致表现为一个两级自适应分支预测具有全局26位的历史（参见第14页），或稍微好一点。没有专门的循环预测。这意味着，循环拥有很多分支或其他循环内进行了预测是不佳。我对模式历史表的大小没有信息，但是我们能够可靠地假定它是小于226。总是采取分支都包括在历史缓存器，而无条件跳转和从来没有转移的分支都没有。
间接分支预测
该处理器可以预测间接跳转具有多于两个不同的目标，但预测失误频繁。
返回堆栈缓冲区
返回堆栈缓冲区有12项在Bobcat和jaguar的16项，根据我的测量。
3.14在旧的处理器中的间接跳转
间接跳转，间接调用和返回可能每次都去不同的地址。该预测方法间接跳转或间接调用，在比PM和K10更老的处理器中，简单地预测，它会去同一个目标，因为它是执行最后一次。第一次间接跳转或间接调用所看到的，它被预测为进入后立即指令。因此，间接跳转或调用应始终遵循以有效的代码。间接跳转或调用后，不要立即把跳转地址的列表。这样的列表应该优选被放置在数据段，而不是代码段。
一个多路分支（switch语句）被实现为使用跳跃地址的列表间接跳转，或作为分支指令的树。间接跳转有缺点，它在很多处理器中预测不佳，但分支树方法具有其它缺点，即，它消耗更多的BTB条目和许多处理器在密集或连续分支上性能差。
3.15返回（除P1所有处理器）
更好的方法是用于返回。一个后进先出缓冲器，称为返回堆栈的缓冲区，每次调用指令执行时间记住的返回地址，并使用该预测，其中相应的返回会去。这个机制可以确保返回指令被正确预测时相同的子程序从几个不同的位置调用。
在P1没有返回堆栈缓冲区，但使用相同的方法作为回报间接跳跃。后来处理器有一个返回堆栈的缓冲区。这个缓冲器的大小是4在PMMX中，在Atom中是8，在AMD K8是12,在PPro，P2，P3，P4 P4E，PM酷睿2和Nehalem中是16，并在AMD的K10中是24。这个尺寸似乎相当小，但它足以在大多数情况下，因为只有最内子程序事宜中的执行时间。返回堆栈缓冲器可能不足，虽然，是在一个深深嵌套递归函数的情况。
为了使这一机制工作，你必须确保所有调用都与返回相匹配。从来没有跳转一个子程序没有返回，从不使用返回作为间接跳转。它是确定的，但是，以取代用JMP MYPROC在CALL MYPROC/ RET序列16位和32位模式。在64位模式下中，服从栈对齐的标准，可以用JMP MYPROC取代SUB RSP，8/ CALL MYPROC/ ADD RSP，8/ RET。
在大多数处理器上中，您必须确保远调用与远的返回及近调用附近返回相匹配。这可能是有问题的16位代码，因为汇编器将取代远远调用程序在同一网段用PUSH CS随后近调用。即使你防止汇编由硬编码在远调用这样做，链接器可能转化远调用PUSH CS和近调用。在连接使用/ NOFARCALLTRANSLATION选项，以防止这一点。建议使用小型或平面内存模式，使您不必远调用中，因为无论如何远调用和返回是昂贵的。
3.16静态预测
第一次分支指令被看到，预测是根据静态预测的原理制成的。
P1和PMMX的静态预测
控制传输指令一直没有见过或不是分支目标缓冲器（BTB）总是预测落空在P1和PMMX上。分支指令不会得到BTB一个条目;如果它总是落空。一旦它被调用一次中，它会进入BTB。在PMMX中，它会留在BTB不管多少次落空。任何控制转移指令，跳转到地址立即下本身不会得到BTB的条目，因此总会有预测失败的惩罚。
在PPro，P2，P3，P4 P4E静态预测
在PPro，P2，P3，P4和P4E中，控制转移指令，它以前未见过，或者是不在BTB中中，预测落空，如果去向前，并且该有待转移如果去向后（如一个循环）。静态预测与这些处理器动态预测来比需要较长的时间。在P4和P4E中，您可以通过添加预测提示前缀改变静态预测。前缀3EH将使分支预测在第一时间被使用，和前缀2EH将使预测在第一时间不被采用。这些前缀可以以这样的方式被编码。
; Example 3.6. P4/P4E static branch prediction hint
DB 3EH ; Prediction hint prefix
JBE LL ; Predicted taken first time
预测提示前缀实际上是段的前缀，这不会产生影响，在其它处理器上没有坏处。这是很不值得努力去考虑静态预测。几乎是任何的分支在执行通常足以为它的时机有任何效果显著有可能留在BTB。因此，只有动态的预测数。静态预测只有一个显著影响，如果是在上下文切换或任务切换非常频繁发生时。通常情况下，
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[499538]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
