乱序执行

乱序执行允许处理器在操作数就绪后立即执行指令，而不是严格按照程序顺序执行，它利用寄存器重命名和缓冲来暴露并行性，同时仍能产生按序结果。

Definition

乱序执行是一种微架构技术，处理器动态地重新排序指令执行，以便在操作数可用时运行独立的指令，同时利用缓冲和重命名来保持顺序、按序完成的表象。

Scope

本主题涵盖动态调度：保留站、用于消除假依赖的寄存器重命名、强制按序提交的重排序缓冲区，以及推测执行恢复。它直接建立在Tomasulo算法之上。它不包括分支方向预测（分支预测）和更广泛的并行性存在程度（指令级并行）的概念，而是侧重于重排序机制本身。

Core questions

• 处理器如何能在程序乱序执行的情况下仍然产生正确的按序结果？
• 寄存器重命名如何消除写后读和写后写依赖？
• 保留站和重排序缓冲区有什么作用？
• 乱序核心中如何精确地恢复异常和预测错误？

Key concepts

• 动态调度
• 保留站
• 寄存器重命名
• 公共数据总线
• 重排序缓冲区
• 按序提交
• 精确异常
• 推测执行恢复

Key theories

Tomasulo算法

Tomasulo方案使用保留站和公共数据总线来重命名寄存器，并在操作数可用时将指令分派到功能单元，从而实现只尊重真正数据依赖的乱序执行。

通过按序提交实现精确异常

重排序缓冲区保存乱序指令的结果并按程序顺序提交它们，这样就可以精确处理异常和预测错误，就好像执行是严格顺序的一样。

Mechanisms

解码后的指令被重命名到物理寄存器并放置在保留站或发射队列中，在那里它们等待通过结果总线广播的操作数。准备就绪后，它们以任意顺序在可用的功能单元上执行。重排序缓冲区跟踪原始程序顺序并按序提交结果，在预测错误或异常时丢弃推测结果，从而使架构状态始终精确。

Clinical relevance

乱序执行是高性能CPU的核心引擎，通过寻找独立的任务来隐藏内存和执行延迟。它也具有安全隐患：由于推测性的乱序工作在被清除之前可以暂时访问数据，这使得Spectre和Meltdown等微架构侧信道攻击成为可能。

History

Tomasulo于1967年在IBM System/360 Model 91中引入了动态调度。与1980年代开发的用于精确异常的重排序缓冲区的结合，使得乱序执行对于通用处理器变得实用，并从1990年代中期开始成为高性能设计的标准。

Debates

性能与复杂性、功耗和安全性之间的权衡

乱序执行提供了强大的单线程性能，但硬件复杂性和功耗成本高昂，而且其推测已被证明可被利用；这引发了关于激进推测与偏爱更简单、更高效或更安全设计之间的争论。

Key figures

• Robert Tomasulo
• Yale Patt
• James E. Smith
• John L. Hennessy

Seminal works

• tomasulo1967
• hennessy2019

Frequently asked questions

如果指令乱序执行，程序如何仍然正确？

处理器只重新排序执行，而不是结果。寄存器重命名确保它尊重真正的数据依赖，并且重排序缓冲区按原始程序顺序提交结果，因此可见的架构状态与顺序执行产生的结果完全相同。

什么是寄存器重命名？

寄存器重命名将指令中命名的架构寄存器映射到更大的物理寄存器池中。这消除了因重复使用寄存器名称而产生的假（名称）依赖，从而允许更多独立的指令并行执行，而不会因寄存器存储冲突。