乱序执行与推测执行

概念

流水线 那一章留下的账是：流水线让指令重叠，但一遇到数据相关就得停。而 lw 的数据要到 MEM 段末才有，一条 load 后面的加法指令一定得等——这段等待里流水线基本空转。

乱序执行（out-of-order execution，简称 OoO）就是对这件事的回答：

硬件在不改变程序语义的前提下，打乱指令的实际执行顺序，让"能做的先做"，把停顿填满。

它是 并行与多核 里那张"四个层次"表中指令级并行（ILP）最激进的一档：流水线已经让相邻指令重叠了，乱序执行还要让相隔几十条的指令互相填空。

原理

一、顺序执行的浪费长什么样

看这段 MIPS（三条访存、三条加法，交替排列）：

lw   r1, 0(r10)      # 访存，要 6 拍才有数据
add  r2, r1, r3      # 依赖 r1，必须等
lw   r4, 4(r10)
add  r5, r4, r6      # 依赖 r4
lw   r7, 8(r10)
add  r8, r7, r9      # 依赖 r7

在严格顺序执行的机器上，第二条指令要等第一条出数，紧接着的第三条 lw 也只能排在后面干等——流水线里明明有地方可以放它，就是不给放。

算下来：6 条指令要跑 20 拍，IPC 只有 0.3。三条本来可以完全重叠的访存，被硬生生串成了三串。

二、三类相关：只有一类是真的

指令之间"不能乱动"的原因分三类，只有一个是真的：

相关	名字	例子	是真约束吗
RAW	真相关（写后读）	add r1,r2,r3 → sub r4,r1,r5	是。后面的要用前面的结果，改不了
WAR	反相关（读后写）	sub r4,r1,r5 → add r1,r6,r7	不是。只是"名字撞了"
WAW	输出相关（写后写）	add r1,r2,r3 → mul r1,r4,r5	不是。谁最后写，谁说了算

看 WAR 的例子：第二条指令要写 r1，可第一条还在读 r1。这个"不能先写"的限制并不是逻辑需要，只是因为两条指令用了同一个名字 r1。 如果给第二条分配一个别的寄存器来写，冲突就消失了——程序的结果完全不变。

WAR 与 WAW 合称"假相关"（name dependency，名字相关）。它们唯一的来源是寄存器名字太少、被反复复用。

三、寄存器重命名：把假相关消掉

寄存器重命名（register renaming）就是干这件事：

• 架构寄存器（architectural）：程序里看得见的 32 个，r1、r4……
• 物理寄存器（physical）：硬件里实际更多的一份，比如 160 个。

每条指令写寄存器时，硬件给它分配一个当时空闲的物理寄存器，并在表里记下"现在我这里的 r1 指的是物理寄存器 P37"。后面读 r1 的指令按表去找对应那一个。

效果：WAW/WAR 直接消失（两条指令写的其实是不同的物理寄存器），只剩 RAW 必须等。

用个数感受一下：物理寄存器越多，能同时"在飞行中"的指令就越多。这也是"重命名表有多大"成为 CPU 关键指标的原因。

四、Tomasulo：保留站 + 公共数据总线

Tomasulo 算法（1967 年，IBM 360/91）是第一个成熟的乱序执行方案，三个部件：

部件	干什么
保留站（reservation station）	每条发射出去的指令在这里等操作数，等齐了就走
公共数据总线（CDB）	功能单元算完结果后广播出去；所有等这个结果的保留站同时听到
寄存器状态表	记下"某个寄存器当前由哪个保留站/物理寄存器负责"

关键变化在于：指令可以"发射出去但暂时不能执行"。

顺序流水线里，"发射"和"开始执行"几乎是一回事；Tomasulo 把它们解开了：发射只管把指令放进保留站（只要站里空），真正的等待发生在保留站里。于是后面的独立指令可以先发射、先执行——这就是乱序的起点。

CDB 的广播也很关键：结果一出来，所有依赖它的指令同一个周期都拿到值，不必一个个去读寄存器堆。

五、ROB：乱序执行，按序提交

乱序执行带来一个麻烦：如果中途出错（比如缺页、除零），程序状态已经乱成一团，没法回到"出错指令之前"的干净状态。

解法是重排序缓冲区（ROB, Reorder Buffer）：

• 指令发射按程序序进入 ROB；
• 执行可以乱序；
• 但提交（commit / retire）必须严格按程序序——只有 ROB 队头那条指令完成了，才允许它真正修改架构寄存器与内存。

这一条"乱序执行、按序提交"是整个机制的关键：对外看，程序状态永远像是"一条一条按顺序执行"的；对内看，硬件放开了手脚。

它还顺手解决了两个问题：

1. 精确异常：ROB 队头之前的都提交了，之后的全丢弃 → 异常发生时机器状态恰好停在"出错指令之前"。
2. 推测执行的回滚：见下一节。

六、推测执行：先赌，赌错再回滚

推测执行（speculative execution）是乱序的延伸：遇到分支时不等结果，先按预测方向往下执行。

• 猜对了：白赚了一段已完成的执行，代价为零。
• 猜错了：ROB 里那些猜错路径上的指令全部丢弃，寄存器状态照 ROB 队头重建，然后跳到正确地址重新取指。

误预测的代价就是"罚拍"：从发现预测错，到重新填满流水线，中间全是空转。深流水线的惩罚尤其重——15 段流水线，误预测一次就要罚 15 拍。

拿实际数字感受一下（口径：误预测罚 15 拍，平均每 5 条指令遇到 1 个分支）：

预测准确率	误预测率	每 5 条摊到的损失	CPI（基准 1.0）
99%	0.010	0.150	1.0300
95%	0.050	0.750	1.1500
90%	0.100	1.500	1.3000
80%	0.200	3.000	1.6000

准确率从 99% 掉到 80%，CPI 从 1.03 涨到 1.60——性能掉了一半还多。所以现代 CPU 在分支预测上投的资源，不比在运算部件上少。

七、窗口大小决定一切

乱序能"填"多久，取决于它能把多少条指令同时装进来——这个容量叫指令窗口（ROB 大小 + 保留站大小）。

• 窗口太小：想提前做的指令还在门外排队，乱序退化成顺序。
• 窗口够大：能覆盖住长延迟操作（访存、除法）的等待时间。
• 窗口再大：边际收益很快见顶——因为"能提前做的事"本身是有限的。

判据不是"窗口越大越好"，而是"窗口装不装得下足够填缝的独立工作"。这句话后面会用数字验证。

八、代价

乱序不是白来的：

代价	说明
面积	重命名表、ROB、保留站、多端口寄存器堆、CDB，都是大块电路
功耗	每周期要检查几十上百条指令的相关性，这一部分能耗与"干了多少活"无关
验证复杂度	乱序 + 推测 + 精确异常，是所有硬件里最难验证的部分之一
存储器序变复杂	硬件重排了访存顺序，多核之间"看到"的顺序就成了问题——这是下一章的主题

示例

例 1：数一数三类相关（C）

看一段含"名字冲突"的指令序列，把三类相关各数出来：

#include <stdio.h>

#define N 5
#define R 16

/* 5 条指令：写哪个寄存器（-1 = 不写），读哪两个（-1 = 不读） */
static const int WR[N]    = {1, 4, 1, 8, 4};
static const int RD[N][2] = {{-1, -1}, {1, -1}, {6, 7}, {1, -1}, {8, 10}};

int main(void) {
    /* 按程序序收集每个寄存器的访问序列：0 = 读，1 = 写 */
    int seq[R][2 * N], len[R];
    for (int r = 0; r < R; r++) len[r] = 0;
    for (int i = 0; i < N; i++) {
        for (int k = 0; k < 2; k++)
            if (RD[i][k] >= 0) {
                int r = RD[i][k];
                seq[r][len[r]++] = 0;
            }
        if (WR[i] >= 0) {
            int r = WR[i];
            seq[r][len[r]++] = 1;
        }
    }

    /* 只看相邻两次访问同一寄存器：写后读 RAW / 读后写 WAR / 写后写 WAW */
    int raw = 0, war = 0, waw = 0;
    for (int r = 0; r < R; r++)
        for (int k = 0; k + 1 < len[r]; k++) {
            int a = seq[r][k], b = seq[r][k + 1];
            if (a == 1 && b == 0)      raw++;
            else if (a == 0 && b == 1) war++;
            else if (a == 1 && b == 1) waw++;
        }

    printf("  RAW（真相关，重命名消不掉）: %d\n", raw);
    printf("  WAR（反相关，重命名可消除）: %d\n", war);
    printf("  WAW（输出相关，重命名可消除）: %d\n", waw);
    printf("  重命名后仍需等待 %d 条，消除 %d 条（%.1f%%）\n",
           raw, war + waw, 100.0 * (war + waw) / (raw + war + waw));
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

  RAW（真相关，重命名消不掉）: 3
  WAR（反相关，重命名可消除）: 1
  WAW（输出相关，重命名可消除）: 1
  重命名后仍需等待 3 条，消除 2 条（40.0%）

三组数字对应三处具体冲突：

相关	出处	重命名后
RAW ×3	第 1 条写 r1 → 第 2 条读 r1；第 3 条写 r1 → 第 4 条读 r1；第 4 条写 r8 → 第 5 条读 r8	保留（真的要用这个值）
WAR ×1	第 2 条读 r1 → 第 3 条写 r1	消除（换成写另一个物理寄存器即可）
WAW ×1	第 2 条写 r4 → 第 5 条写 r4	消除（谁最后写谁说了算，中间的顺序无关）

重命名把 5 条相关砍到 3 条。这 2 条"砍掉"的，就是硬件白赚的并行度。

例 2：模拟乱序执行，看它把停顿填成什么（Python）

C 段只数了相关个数。这里做一个周期级模拟：同一段代码，分别用"严格顺序执行"与"乱序执行 + 不同 ROB 容量"跑一遍，看总周期数怎么变。

def dw(s):
    return sum(2 if ord(c) > 0x2000 else 1 for c in str(s))


def pad(s, w):
    return str(s) + " " * max(0, w - dw(str(s)))


def table(head, rows, gap=2):
    data = [[str(c) for c in r] for r in rows]
    w = [max([dw(head[i])] + [dw(r[i]) for r in data]) + gap for i in range(len(head))]
    print("  " + "".join(pad(head[i], w[i]) for i in range(len(head))))
    for r in data:
        print("  " + "".join(pad(r[i], w[i]) for i in range(len(head))))


def simulate(instrs, rob=8, in_order=False):
    """instrs: (名字, 单元, 延迟, 依赖下标列表)
       单元：ALU 两个、MUL 一个、LD 一个，都是流水化的（启动间隔 II = 1 拍）
       完成周期 = 开始执行周期 + 延迟 - 1；依赖者最早在完成周期 + 1 开始
       提交按程序序，每拍 1 条；ROB 容量 rob 决定能'先发射'多少条"""
    n = len(instrs)
    issue, start, done, commit = [None] * n, [None] * n, [None] * n, [None] * n
    II = {"ALU": 1, "MUL": 1, "LD": 1}
    units = {"ALU": [1, 1], "MUL": [1], "LD": [1]}
    nxt, committed, t = 0, 0, 1
    while committed < n:
        # 1) 提交（按序，每拍最多 1 条）
        if committed < nxt and done[committed] is not None and done[committed] <= t:
            commit[committed] = t
            committed += 1
        # 2) 发射（每拍 1 条，且不超过 ROB 容量）
        if nxt < n and (nxt - committed) < rob:
            issue[nxt] = t
            nxt += 1
        # 3) 派发执行：挑出操作数就绪、单元空闲的指令
        while True:
            pick = None
            for i in range(n):
                if issue[i] is None or start[i] is not None:
                    continue
                if in_order and i > 0 and start[i - 1] is None:
                    break                      # 顺序执行：不能越过
                if any(done[d] is None for d in instrs[i][3]):
                    continue                   # 操作数还没好
                rd = issue[i]
                for d in instrs[i][3]:
                    rd = max(rd, done[d] + 1)
                if in_order and i > 0:
                    rd = max(rd, start[i - 1])
                best = min(((max(rd, f), k)
                            for k, f in enumerate(units[instrs[i][1]])), default=None)
                if best is not None and best[0] <= t:
                    pick = (i, best[1], t)
                    break
            if pick is None:
                break
            i, k, when = pick
            start[i] = when
            done[i] = when + instrs[i][2] - 1
            units[instrs[i][1]][k] = when + II[instrs[i][1]]
        t += 1
    return commit[-1], issue, start, done, commit


INSTR = [
    ("lw   r1, 0(r10)", "LD", 6, []),
    ("add  r2, r1, r3", "ALU", 1, [0]),
    ("lw   r4, 4(r10)", "LD", 6, []),
    ("add  r5, r4, r6", "ALU", 1, [2]),
    ("lw   r7, 8(r10)", "LD", 6, []),
    ("add  r8, r7, r9", "ALU", 1, [4]),
]

print("=== 1. 四种取指/执行策略下的总周期数 ===")
rows = []
for name, rob, inord in [("顺序执行（不能越过）", 8, True),
                         ("乱序执行 ROB=2（窗口太小）", 2, False),
                         ("乱序执行 ROB=4", 4, False),
                         ("乱序执行 ROB=8", 8, False)]:
    total, _, _, _, _ = simulate(INSTR, rob, inord)
    rows.append([name, str(total), "%.4f" % (6.0 / total)])
table(["策略", "总周期", "IPC"], rows)
print()

print("=== 2. 乱序（ROB=8）是怎样把停顿填掉的 ===")
total, issue, start, done, commit = simulate(INSTR, 8, False)
rows = [[INSTR[i][0], str(issue[i]), str(start[i]), str(done[i]), str(commit[i])]
        for i in range(len(INSTR))]
table(["指令", "发射", "开始执行", "完成", "提交"], rows)
print("  三条 lw 都在第 1、3、5 拍发射，第 6、8、10 拍才出数 —— 三条访存完全重叠。")
print("  依赖它们的 add 各自等到操作数就绪，互不牵连。")
print()

print("=== 3. 顺序执行同一段代码 ===")
total2, issue2, start2, done2, commit2 = simulate(INSTR, 8, True)
rows = [[INSTR[i][0], str(issue2[i]), str(start2[i]), str(done2[i]), str(commit2[i])]
        for i in range(len(INSTR))]
table(["指令", "发射", "开始执行", "完成", "提交"], rows)
print("  第 2 条 add 要等到第 7 拍才能开始，可它后面的两条 lw 也被挡在门外 ——")
print("  人闲着，访存也在排队，这就是顺序执行的代价。")
print()
print("  结论：乱序 %d 拍 vs 顺序 %d 拍，快 %.4f 倍。" % (total, total2, total2 / total))
print()

print("=== 4. ROB 越小越像顺序执行 ===")
rows = []
for rob in [2, 3, 4, 5, 6, 8]:
    tot, _, _, _, _ = simulate(INSTR, rob, False)
    rows.append([str(rob), str(tot), "%.4f" % (6.0 / tot)])
table(["ROB 容量", "总周期", "IPC"], rows)
print("  ROB=2 时只能同时装两条，第 3 条之后的指令发不出去，乱序几乎退回顺序（%d 拍，"
      "顺序是 %d 拍）。" % (simulate(INSTR, 2, False)[0], simulate(INSTR, 8, True)[0]))
print("  窗口开到 5 条就装得下三条访存指令，收益到位（%d 拍）；再开大也不会更好 ——"
      % simulate(INSTR, 5, False)[0])
print("  窗口的价值在于'装得下足够填缝的独立工作'，不在于数字大小。")
print()

print("=== 5. 分支预测错一次的代价 ===")
rows = []
for acc in [0.99, 0.95, 0.90, 0.80]:
    miss = 1 - acc
    rows.append(["%.0f%%" % (acc * 100),
                 "%.3f" % miss,
                 "%.3f" % (miss * 15),
                 "%.4f" % (1 + miss * 15 / 5)])
table(["预测准确率", "误预测率", "每 5 条摊到的损失", "CPI（基准 1.0）"], rows)
print("  口径：流水线 15 段，误预测罚 15 拍；平均每 5 条指令遇到 1 个分支。")
print("  准确率从 99% 掉到 80%，CPI 从 1.03 涨到 1.60 —— 推测得越深，赌注越大。")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== 1. 四种取指/执行策略下的总周期数 ===
  策略                        总周期  IPC     
  顺序执行（不能越过）        20      0.3000  
  乱序执行 ROB=2（窗口太小）  18      0.3333  
  乱序执行 ROB=4              13      0.4615  
  乱序执行 ROB=8              12      0.5000  

=== 2. 乱序（ROB=8）是怎样把停顿填掉的 ===
  指令             发射  开始执行  完成  提交  
  lw   r1, 0(r10)  1     1         6     6     
  add  r2, r1, r3  2     7         7     8     
  lw   r4, 4(r10)  3     3         8     9     
  add  r5, r4, r6  4     9         9     10    
  lw   r7, 8(r10)  5     5         10    11    
  add  r8, r7, r9  6     11        11    12    
  三条 lw 都在第 1、3、5 拍发射，第 6、8、10 拍才出数 —— 三条访存完全重叠。
  依赖它们的 add 各自等到操作数就绪，互不牵连。

=== 3. 顺序执行同一段代码 ===
  指令             发射  开始执行  完成  提交  
  lw   r1, 0(r10)  1     1         6     6     
  add  r2, r1, r3  2     7         7     8     
  lw   r4, 4(r10)  3     7         12    12    
  add  r5, r4, r6  4     13        13    14    
  lw   r7, 8(r10)  5     13        18    18    
  add  r8, r7, r9  6     19        19    20    
  第 2 条 add 要等到第 7 拍才能开始，可它后面的两条 lw 也被挡在门外 ——
  人闲着，访存也在排队，这就是顺序执行的代价。

  结论：乱序 12 拍 vs 顺序 20 拍，快 1.6667 倍。

=== 4. ROB 越小越像顺序执行 ===
  ROB 容量  总周期  IPC     
  2         18      0.3333  
  3         15      0.4000  
  4         13      0.4615  
  5         12      0.5000  
  6         12      0.5000  
  8         12      0.5000  
  ROB=2 时只能同时装两条，第 3 条之后的指令发不出去，乱序几乎退回顺序（18 拍，顺序是 20 拍）。
  窗口开到 5 条就装得下三条访存指令，收益到位（12 拍）；再开大也不会更好 ——
  窗口的价值在于'装得下足够填缝的独立工作'，不在于数字大小。

=== 5. 分支预测错一次的代价 ===
  预测准确率  误预测率  每 5 条摊到的损失  CPI（基准 1.0）  
  99%         0.010     0.150              1.0300           
  95%         0.050     0.750              1.1500           
  90%         0.100     1.500              1.3000           
  80%         0.200     3.000              1.6000           
  口径：流水线 15 段，误预测罚 15 拍；平均每 5 条指令遇到 1 个分支。
  准确率从 99% 掉到 80%，CPI 从 1.03 涨到 1.60 —— 推测得越深，赌注越大。

四条结论：

1. 乱序 12 拍、顺序 20 拍，快 1.6667 倍。省下来的全是"等访存"的时间。
2. 对比第 2、3 节两张表：乱序表里 lw r4 在第 3 拍就开始执行，顺序表里拖到第 7 拍——就这么一处差别，后面全被推着走（lw r7 从第 5 拍拖到第 13 拍）。
3. ROB=2 时几乎退回顺序（18 拍）。窗口装不下"提前做的事"，乱序就无从谈起。
4. ROB 从 5 开到 8，一点没变（都是 12 拍）。窗口的价值有天花板——因为这段代码里能填缝的独立工作就那么多。

考点

考点

1. 三类相关，一真两假

相关	别名	真约束吗	消除手段
RAW（写后读）	真相关	是	只能等（或转发）
WAR（读后写）	反相关	不是	寄存器重命名
WAW（写后写）	输出相关	不是	寄存器重命名

记法：后一条要"用"前一条的结果，就必须等（RAW）；后一条只是撞了名字，改名即可（WAR/WAW）。

2. 寄存器重命名

• 架构寄存器（程序可见的 32 个）↔ 物理寄存器（硬件里更多的一份）。
• 每次写就分配一个新物理寄存器 → WAR/WAW 彻底消失，只剩 RAW。
• 重命名表越大，在飞的指令越多。

3. Tomasulo 三个部件

保留站（等操作数的地方）、公共数据总线 CDB（结果广播，所有等待者同拍拿到）、寄存器状态表（哪个寄存器归谁管）。

关键点：发射与执行被解开——指令能"发射了但还在等"，后面的独立指令因此可以先跑。

4. 「乱序执行、按序提交」

• ROB 队头提交，只有它提交时才真正修改架构状态。
• 好处一：精确异常（异常前的都提交了，之后的全丢弃）。
• 好处二：推测执行可以无条件回滚。

5. 推测执行的代价

• 猜对零代价；猜错丢弃 ROB 里猜错路径上的全部指令 + 罚拍重新取指。
• 误预测惩罚随流水线深度线性增长（15 段 → 罚 15 拍）。
• 准确率 95% → 90%，CPI 从 1.15 涨到 1.30。分支预测器是现代 CPU 的核心部件。

6. 指令窗口

窗口 = ROB 大小 + 保留站大小。窗口太小 → 乱序退化成顺序；窗口够大之后边际收益迅速见顶。

7. 与顺序流水线的对照（务必能说出差别）

	顺序流水线	乱序执行
停顿粒度	一停全停（整条流水线空转）	只有依赖链上那条在等，别的照跑
解决手段	转发 / 停顿 / 编译调度	重命名 + 乱序 + 推测
load 后的使用者	必停若干拍	从别处找活干，未必真停

8. 易错点清单

• 认为 WAW 也是真相关：不是，它只影响"谁最后写"，重命名即可消除。
• 认为乱序执行会改变程序结果：不会——"按序提交"是硬约束。
• 把"发射"与"执行"当成一回事：Tomasulo 的突破正在于把它们分开。
• 以为 ROB 越大越好：收益有天花板（本章例 2 从 5 加到 8 毫无变化）。
• 忘了误预测的代价随流水线加深而变大：深流水线是"要么大赚，要么大亏"的赌局。
• 认为推测执行错了会"算错结果"：ROB 保证它只是白算一场，不会污染状态。
• 忽略乱序给多核带来的麻烦：硬件重排了访存顺序，才有了下一章的内存一致性问题。

小结

• 顺序执行最大的浪费不是"算得慢"，而是"有事不能做"；乱序执行把"发射"与"执行"解开，让能做的先做。
• 三类相关里只有 RAW 是真的，WAR/WAW 都是"名字撞了"——寄存器重命名一改名字就没了。
• 乱序执行、按序提交：对内放开手脚，对外保持"像是一条条顺序跑的"。精确异常与推测回滚都靠 ROB。
• 推测执行是一场赌局：赢了白赚，输了罚拍。流水线越深，赌注越大，所以分支预测器值得投重金。
• 窗口的价值在于"装得下足够填缝的独立工作"，而不在于数字大小。

回到主线：本章讲清了"一个核里的指令可以乱序"。可这个"乱序"一旦牵扯到多个核，麻烦就来了——A 核改了一个变量，B 核什么时候能看见？两个核改的顺序会不会不一致？ 这已经不是乱序执行的问题，而是整个系统的规则问题。下一章讲的就是这套规则：内存一致性模型。

下一篇：内存一致性模型