cpu - 为什么不只预测两个分支？

Question

CPU 使用分支预测来加速代码，但前提是实际采用第一个分支。

为什么不简单地采取两个分支？也就是说，假设两个分支都将被命中，缓存两边，并在必要时采用适当的分支。缓存不需要失效。虽然这需要编译器事先加载两个分支(更多内存、适当的布局等)，但我认为适当的优化可以简化两者，以便可以从单个预测器中获得接近最佳的结果。也就是说，加载两个分支需要更多内存(对于 N 个分支来说是指数级的)，大多数情况下应该能够在执行分支之前足够快地用新代码“重新缓存”失败的分支.

如果 (x) Bl 否则 Br;

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

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

如果这可行，有什么想法吗？

Answer 1

从两条路径获取指令的历史视角
第一个类似的提议(据我所知)在 this 中讨论过。 1968年专利。我知道您只是询问从两个分支获取指令，但请耐心等待。在该专利中，提出了三个广泛的策略，其中之一是遵循两条路径(下落路径和分支路径)。也就是说，不仅从两条路径中获取指令，而且还执行两条路径。当条件分支指令被解析时，路径之一被丢弃。它只是在专利介绍中作为一个想法被提及，但专利本身是关于另一项发明的。
1977 年晚些时候，IBM 发布了一款商用处理器，名为 IBM 3033处理器。这是第一个(据我所知)完全实现您所提议的处理器。我很惊讶地看到维基百科页面没有提到处理器从两个路径中获取指令。描述 IBM 3033 的论文的标题是“IBM 3033:内幕”。不幸的是，我找不到论文。但是paper在 IBM 3090确实提到了这个事实。所以你的提议确实有意义，并且在大约五年前在真正的处理器中实现。
一项专利于 1981 年提交并于 1984 年授予关于具有两个内存的处理器并且可以同时从两个内存中获取指令的专利。我引用专利摘要:

A dual fetch microsequencer having two single-ported microprogrammemories wherein both the sequential and jump addressmicroinstructions of a binary conditional branch can be simultaneouslyprefetched, one from each memory. The microprogram is assembled sothat the sequential and jump addresses of each branch have oppositeodd/even polarities. Accordingly, with all odd addresses in one memoryand even in the other, the first instruction of both possible pathscan always be prefetched simultaneously. When a conditional branchmicroinstruction is loaded into the execution register, its jumpaddress or a value corresponding to it is transferred to the addressregister for the appropriate microprogram memory. The address of themicroinstruction in the execution register is incremented andtransferred to the address register of the other microprogram memory.Prefetch delays are thereby reduced. Also, when a valid conditionaljump address is not provided, that microprogram memory may betransparently overlayed during that microcycle.

从两条路径获取和执行指令的历史视角
80 年代和 90 年代发表了大量关于提出和评估技术的研究，通过这些技术，不仅可以从两条路径中获取指令，还可以执行这些技术，即使对于多个条件分支也是如此。这将有潜在的额外 overhead获取两条路径所需的数据。 this中提出了分支预测置信度的思想1996 年发表的论文，并通过对获取和执行的路径更具选择性来改进此类技术。另一个 paper (Threaded Multiple Path Execution) 发表于 1998 年，提出了一种架构，该架构利用同步多线程 (SMT) 在条件分支之后运行多个路径。另一个 paper (Dual Path Instruction Processing) 于 2002 年发布，建议从两条路径中获取、解码和重命名指令，但不执行指令。
讨论
从两条路径获取指令到一个或多个高速缓存中通常会降低高速缓存的有效容量，因为通常其中一个路径的执行频率将比另一个更频繁(在某些可能非常不规则的模式中)。想象一下获取 L3 缓存，它实际上总是在所有内核之间共享并保存指令和数据。这会对 L3 缓存保存有用数据的能力产生负面影响。获取到更小的 L2 缓存甚至会导致性能大幅下降，尤其是当 L3 包含在内时。从所有内核的多个条件分支上的两条路径获取指令可能会导致缓存中保存的热数据经常被驱逐和带回。因此，您提议的技术的极端变体会降低现代架构的整体性能。然而，攻击性较小的变体可能是有益的。
我不知道有任何真正的现代处理器在看到条件分支时在两条路径上获取指令(也许有些人这样做，但没有公开披露)。但是指令预取已经被广泛研究并且仍然是。这里需要解决的一个重要问题是:当预测的路径是错误的路径时，来自另一条路径的足够数量的指令已经存在于缓存中的概率是多少？如果概率很高，那么从两条路径获取指令的动机就很小。否则，确实有机会。据老 paper来自英特尔(错误路径指令预取)，在测试的基准测试中，超过 50% 在错误预测路径上访问的指令后来在正确路径执行期间被访问。这个问题的答案当然取决于正在设计的处理器的目标域。