为什么不直接预测两个分支？

Question

CPU使用分支预测来加快代码运行速度，但只有在第一个分支被执行的情况下才会使用。为什么不同时执行两个分支呢？也就是说，假设两个分支都会被执行，缓存两边，然后在必要时选择正确的分支。缓存不需要失效。虽然这需要编译器提前加载两个分支（更多内存，合适的布局等），但我想合适的优化可以使两者都流线型，从而可以从单个预测器中获得接近最佳的结果。也就是说，加载两个分支需要更多的内存(对于N个分支而言呈指数级增长)，大多数情况下，在分支被执行之前能够快速地用新代码“重新缓存”失败的分支。

如果(x) Bl else Br;

不是假设Bl被执行，而是假设Bl和Br都被执行(一些类型的并行处理或特殊交错)，并且在分支实际确定之后，一个分支就无效了，缓存就可以被释放以供使用（可能需要某种特殊技术来正确填充和使用它）。

事实上，不需要任何预测电路，所有设计都可以用来处理两个分支。

您认为这是否可行？

- AbstractDissonance

---

我有一种感觉，分配给这个并行推测执行的（可能相当大量的）额外资源在其他地方利用会更好。试着实现一些常见的分支预测器，并将其与您的方法进行比较（有合理的限制，否则这基本上是欺骗）。我相信这个想法以前已经被探索过了。维基百科有一个关于“急切执行”的段落，作为一种推测执行形式，您可能想查看该节的来源。 - Blender

可能是 https://dev59.com/MITba4cB1Zd3GeqP5mne#26471960 的重复问题，尽管下面的好答案绝对值得保留。无论如何，问题在于这会呈指数级增长。还要了解一下预测执行，本质上就是这个。 - Leeor

指令缓存永远不需要被清除。但我认为当你说“缓存”时，实际上你是指“执行”。但是，即使你用“重排序缓冲区”或其他CPU用于跟踪投机性和乱序执行中的指令的内部结构替换“缓存”，你的主要段落也几乎没有任何意义。 - Peter Cordes

显然，您正在询问有关预测分支的两个方面的问题，但不清楚具体是什么。Hadi刚刚以一般性回答了您的问题可能具有的任何意义。如果您使用正确的术语提出特定问题，例如关于（预）获取到L1d缓存或推测执行的问题，那将是一个更好的问题。这是有很大区别的。 - Peter Cordes

尽管我对这些东西很熟悉，但从第三句开始，我也感到困惑，因为OP认为分支预测主要是关于指令缓存的，从未提到它真正关注的内容：获取、解码、执行。缓存只是其中的一小部分，而且确实不是问题所在：如果某个分支被频繁地错误预测，那么两边都会很快被缓存，因为根据定义，两边都经常被采取。你得到了一个好答案，因为标题中的问题很清楚——但其余部分只会让人分心。 - BeeOnRope

Answer 1

从历史角度看获取指令的两种路径

据我所知，第一个类似的提议是在此1968年的专利中讨论的。我知道你只是询问从两个分支获取指令的问题，但请跟我坚持一下。在那项专利中，提出了三种广泛的策略之一是跟随两条路径(顺序执行路径和分支路径)。也就是说，不仅从两条路径获取指令，而且还要执行两条路径。当条件分支指令解析后，其中一条路径将被丢弃。它只是在专利介绍中作为一个想法提到，但该专利本身是关于另一项发明的。

后来在1977年，IBM发布了一款商用处理器，称为IBM 3033处理器。这是我所知道的第一款完全实现了您提出的内容的处理器。我惊讶地发现Wikipedia页面没有提到该处理器从两个路径获取指令。描述IBM 3033的论文标题为“IBM 3033:内部视图”。不幸的是，我找不到这篇论文。但是IBM 3090上的paper提到了这个事实。因此，您提出的做法是有意义的，并且在真正的处理器中实现了大约半个世纪。

在1981年提交了一项专利，并在1984年获得了关于具有两个存储器的处理器，可以同时从两个存储器中获取指令。我引用该专利摘要中的内容：

双取指微程序控制器具有两个单口微程序存储器，其中二进制条件分支的顺序和跳转地址微指令可以同时预取，一个从每个存储器中取出。微程序是按照分支的每个顺序和跳转地址具有相反的奇/偶极性组装的。因此，当一个存储器中所有奇地址，而在另一个存储器中所有偶地址时，两个可能路径的第一个指令总是可以同时预取。当条件分支微指令加载到执行寄存器中时，它的跳转地址或相应值被传输到适当微程序存储器的地址寄存器中。执行寄存器中的微指令的地址被递增并传输到另一个微程序存储器的地址寄存器中。因此，预取延迟被减少。此外，当未提供有效的条件跳转地址时，该微程序存储器在该微周期内可以被透明覆盖。

对同时从两个路径中获取和执行指令的历史视角

在80年代和90年代，有大量关于提出和评估技术的研究，通过这些技术不仅可以获取指令，而且可以执行多个条件分支，这将潜在地增加获取两条路径所需数据的开销。1996年，这篇论文提出了“分支预测置信度”的概念，并用于改进这种技术，通过更加选择性地获取和执行路径。另一篇论文（Threaded Multiple Path Execution）发表于1998年，提出了一种利用同时多线程（SMT）来运行多个条件分支路径的架构。2002年发表的另一篇论文（Dual Path Instruction Processing）提出从两个路径中获取、解码和重命名指令，但不执行指令。

从两个路径中获取指令并将其存储到一个或多个缓存中会降低缓存的有效容量，因为通常情况下，其中一条路径会比另一条路径执行得更频繁（以某种潜在的高度不规则的模式）。想象一下将其存储到L3缓存中，该缓存实际上总是在所有核心之间共享，并且同时保存指令和数据。这可能会对L3缓存存储有用数据的能力产生负面影响。将其存储到较小的L2缓存中甚至可能导致性能大幅下降，特别是当L3是包容性的时候。在所有核心的多个条件分支中从两个路径中获取指令可能会导致缓存中持有的热数据经常被逐出并重新加载。因此，你提出的技术的极端变体将降低现代架构的整体性能。然而，不那么激进的变体可能会有益。

我不知道有任何现代处理器会在看到条件分支时同时获取两条路径的指令（也许有些处理器会这样做，但这并没有公开）。但指令预取已经得到广泛研究。这里需要回答一个重要问题：当预测的路径是错误的路径时，其他路径上已经存在足够数量的指令的概率是多少？如果概率很高，那么就没有动机从两个路径获取指令。否则，确实有机会。根据英特尔（Wrong-Path Instruction Prefetching）的一篇老文章所述，在测试基准中，超过50％的误判路径上访问的指令在正确路径执行期间稍后被访问。这个问题的答案肯定取决于正在设计的处理器的目标领域。

- Hadi Brais