采取或不采取分支的顺序，可降低分支错误预测率

Question

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

列出已执行和未执行的分支操作序列，以显示 2 位预测器共享的简单示例（多个不同的分支指令映射到预测表的同一条目中），与为每个分支使用单独的预测变量条目的情况相比，该示例可降低分支错误预测率。（注意：请务必显示两个不同分支指令的结果，并特别指出这些结果的顺序以及它们对应于哪个分支）

有人可以向我解释这个问题具体要求什么吗？另外，“2 位预测器共享（几个不同的分支指令映射到预测表的同一条目）”和“每个分支使用单独的预测器条目”是什么意思？我一直在阅读和重读我的笔记，但我无法弄清楚。我试图在网上找到一些分支预测示例，但找不到任何示例。

Answer 1

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

不太可能的是，它们意味着只有四个条目的分支表，因此两个位用于将特定分支与表中的条目相关联。这不太可能，因为4条目的表非常小，许多分支将共享相同的表条目，所以分支预测器不会比静态分支预测更准确(例如，总是预测后向分支被采用，因为它们通常用于形成循环)。

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

用于每个分支的单独预测器条目意味着程序中的每个分支指令在分支预测表中都有自己的条目。另一种方法是从分支html" target="_blank">指令到表条目的某种映射。例如，如果您有一个包含 2 20 个条目的表，则可以使用分支指令地址中的²⁰ 位，并将这些位用作表中的索引。假设一台具有 32 位寻址和 32 位指令的机器，您最多有 1024 条分支指令可以映射到表中的任何一个条目 （32-20-2 = 10， 2¹⁰ = 1024）。实际上，您只期望一小部分指令是分支，一些地址空间用于数据等，因此可能只有少数分支映射到表中的一个条目。

至于它要求的基本问题：他们想要一个分支指令序列，当两个分支映射到分支预测器表中的同一插槽时，这些分支将（巧合地）比当/如果每个分支映射到表中的单独插槽时更准确地预测。为了更详细地介绍（但希望不会泄露整个难题），请从分支预测器通常是错误的分支模式开始。预测器基本上所做的是假设如果上次采用分支，则表明这次更有可能采用分支（相反，如果上次没有采用，则这次可能不会）。

所以，你从一个完全相反的分支模式开始。然后，您希望在分支预测表中的同一点添加第二个分支映射，该映射将遵循分支模式，该模式将调整分支预测表的数据，以便它更准确地反映即将到来的分支，而不是前一个分支。

¹从技术上讲，奔腾实际上并没有以这种方式工作，但这就是它被记录工作的方式，并且可能打算工作;它实际工作方式的差异似乎是一个错误。