为什么不预测两个分支？

Question

CPU使用分支预测来加速代码,但仅限于实际采用第一个分支.

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

if(x)Bl else Br;

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

实际上,不需要预测电路,并且所有用于此的设计可以用于处理两个分支.

任何想法,如果这是可行的？

Answer 1

从两种途径中获取指令的历史透视

第一个类似的建议(据我所知)在讨论这个 1968年的专利.我知道你只是要求从两个分支机构取指令,但请跟我一点.在该专利中,列出了三种广泛的策略,其中一种是遵循两条路径(直通路径和分支路径).也就是说,不仅从两个路径获取指令,而且还执行两个路径.当解析条件分支指令时,丢弃其中一个路径.它仅作为专利介绍中的一个想法被提及,但专利本身是关于另一个发明.

1977年晚些时候,IBM发布了一款名为IBM 3033处理器的商用处理器.这是第一个完全按照你的建议实现的处理器(据我所知).我很惊讶地看到维基百科页面没有提到处理器从两个路径获取指令.描述IBM 3033的论文标题为"IBM 3033:内部外观".不幸的是,我找不到报纸.但是关于IBM 3090的论文确实提到了这个事实.所以你提出的建议确实有意义,并且在大约五年前在真正的处理器中实现了.

1981年提交了一项专利,并于1984年批准了具有两个存储器的处理器,并且可以同时从两个存储器中取出指令.我引用了专利摘要:

具有两个单端口微程序存储器的双重取指微序列器,其中可以同时预取二进制条件分支的顺序和跳转地址微指令,每个存储器一个.组装微程序,使得每个分支的顺序和跳跃地址具有相反的奇/偶极性.因此,利用一个存储器中的所有奇数地址甚至另一个存储器中的所有奇数地址,可以始终同时预取两个可能路径的第一条指令.当条件分支微指令被加载到执行寄存器中时,其跳转地址或与其对应的值被传送到适当微程序存储器的地址寄存器.执行寄存器中的微指令的地址递增并传送到另一个微程序存储器的地址寄存器.从而减少了预取延迟.而且,当没有提供有效的条件跳转地址时,该微程序存储器可以在该微循环期间透明地重叠.

从两种途径中获取和执行指令的历史透视

在80年代和90年代发表了大量关于提出和评估技术的研究,通过这些技术,即使对于多个条件分支,来自两个路径的指令不仅被获取而且被执行.这将有可能获取两个路径所需数据的额外开销.的想法分支预测信心在提出此纸在1996年和使用通过更选择性关于哪些路径为获取和执行,以改善这样的技术.1998年发表的另一篇论文(Threaded Multiple Path Execution)提出了一种利用同步多线程(SMT)在条件分支之后运行多条路径的架构.2002年发表的另一篇论文(双路径指令处理)建议从两个路径中获取,解码和重命名但不执行指令.

讨论

从两个路径获取指令到一个或多个高速缓存中通常会降低高速缓存的有效容量,因为通常,其中一个路径将比另一个路径更频繁地执行(在某些情况下,可能是高度不规则的模式).想象一下,进入L3缓存,它实际上总是在所有内核之间共享,并保存指令和数据.这可能会对L3缓存保存有用数据的能力产生负面影响.获取更小的L2缓存甚至可能导致更差的性能,尤其是当L3包含时.从所有核心的多个条件分支的两个路径获取指令可能导致高速缓存中保存的热数据被频繁驱逐并带回.因此,您提出的技术的极端变体会降低现代架构的整体性能.然而,不太激进的变体可能是有益的.

我不知道有任何真正的现代处理器在它们看到条件分支时获取两条路径上的指令(可能有一些,但它没有公开披露).但是指令预取已经被广泛研究并且仍然是.这里需要解决的一个重要问题是:当预测路径被证明是错误路径时,来自其他路径的足够数量的指令已经存在于缓存中的概率是多少？如果概率很高,则从两条路径获取指令的动机很小.否则,确实有机会.根据英特尔的一篇旧论文(错误路径指令预取),在测试的基准测试中,在错误预测的路径上访问的超过50%的指令后来在正确的路径执行期间被访问.这个问题的答案当然取决于所设计的处理器的目标域.