减少分支预测错误率的取/不取分支序列

Question

减少分支预测错误率的取/不取分支序列

mipspipelinecpu-architecturebranch-prediction

3

增加分支预测表的大小意味着程序中的两个分支不太可能共享一个公共的预测器。一个单一的预测器预测一个单一的分支指令通常比同样的预测器服务于多个分支指令更准确。

列出一系列分支被执行和未被执行的动作，以展示一个简单的2位预测器共享的示例（多个不同的分支指令被映射到预测表的同一个条目），相比于为每个分支使用单独的预测器条目的情况下，它可以降低分支错误率。（注意：一定要显示两个不同分支指令的结果，并明确它们的顺序以及它们对应的分支）

请问有人能具体解释一下这个问题要求什么吗？还有，“2位预测器共享（多个不同的分支指令被映射到预测表的同一个条目）”和“为每个分支使用单独的预测器条目”是什么意思？我一直在阅读和重复我的笔记，但是我无法理解它。我尝试在网上找到一些分支预测的例子，但是没有找到。

- user1378863

CS 320 有可能吗？ :D - nucleartide

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

“2位预测器”可能指的是两件事情中的任何一件，但更有可能是其中之一。

不太可能的可能性是它们指的是一个分支表，只有四个条目，因此使用两个位将特定分支与表中的条目相关联。这很不可能，因为4个条目的表太小了，许多分支将共享相同的表条目，因此分支预测器的准确性不会比静态分支预测（例如，总是预测向后分支为已采取，因为它们通常用于形成循环）高得多。

更有可能的可能性是使用两个位来指示分支是否可能被采取。一些最早包括分支预测的微处理器（例如Pentium，PowerPC 604）大致按照这种方式工作。基本思想是保持两位饱和计数器，并根据其当前状态进行预测。英特尔称这些状态为强烈不采取，弱不采取，弱采取，强制采取。这些将被编号为（例如）0、1、2和3，因此您可以使用两位计数器跟踪状态。每次采取分支时，您都会增加数字（除非它已经是3），每次不采取时，您都会减少它（再次，除非它已经是0）。当您需要预测分支时，如果计数器为0或1，则预测不采取该分支，如果为2或3，则预测采取¹。

每个分支指令在程序中都有自己的分支预测表条目，这意味着程序中的每个分支指令都有自己的分支预测表条目。另一种选择是将分支指令映射到表条目。例如，如果您有一个具有2²⁰个条目的表，则可以使用分支指令地址的20位，并将这些位用作索引进入表中。假设具有32位寻址和32位指令的机器，您最多可以有1024个分支指令映射到表中的任何一个条目（32-20-2 = 10，2¹⁰ = 1024）。实际上，您预计只有少量指令是分支，某些地址空间用于数据等，因此可能只有几个分支将映射到表中的一个条目。

至于基本问题的答案是什么：他们想要一个分支指令序列，当两个分支映射到分支预测器表中的相同插槽时，预测准确性会更高，而当/如果每个分支映射到表中的单独插槽时，预测准确性会更低。稍微详细地说一下（但希望不要泄露整个谜题），从一个分支通常会导致分支预测器错误的模式开始。基本上，预测器所做的是假设如果上次采取了该分支，则表示这次采取的可能性更大（反之亦然，如果上次未采取，则可能本次也不会采取）。

因此，你需要从树枝的模式开始，这些树枝的模式与之相反。然后，你想要添加第二个映射到分支预测表中相同位置的树枝，该树枝的模式将调整分支预测表中的数据，使其更准确地反映即将到来的分支而不是以前的分支。

¹技术上说，Pentium实际上并非以这种方式工作，但它被记录为这样工作，并且可能是有意为之；实际工作方式的差异似乎是一个错误。