仲裁与唤醒

硬件描述 1 — 最不起眼但最关键的电路

仲裁器（arbiter）是发射逻辑中最不起眼但最关键的组件——它每周期从$N$个就绪指令中选出$M$个送往执行单元。在一个96项发射队列、4-wide发射的处理器中，仲裁器需要在不到50 ps内完成96-to-4的优先级编码，同时保证最老优先（oldest-first）策略以避免饥饿。这50 ps仅够约10级逻辑门——对于96输入的仲裁器来说，每一级门延迟都弥足珍贵。设计不良的仲裁器不仅降低IPC（因为错误的选择策略），更可能成为整个处理器的频率瓶颈——仲裁延迟每增加一级门，时钟频率可能下降3%$\sim$5%。

设计提示

统一视角。处理器设计的本质是在有限的晶体管预算和功耗约束下，通过投机和并行的层层叠加来逼近指令吞吐率的理论上限。仲裁器决定了"并行"的实际利用率——即使处理器拥有8个功能单元的并行执行能力（第 30.0 章将讨论功能单元的延迟如何影响唤醒），如果仲裁器每周期只能选出2条指令，实际并行度就只有2。仲裁器的选择策略和速度将发射队列的ILP潜力（第 27.0 章）转化为功能单元的实际利用率。投机唤醒则是发射流水线中"投机"的集中体现——它假设Load将按预期完成，提前唤醒依赖链（第 28.0 章），一旦假设失败则触发重发射。

在第 28.0 章中，我们讨论了发射过程的流水线组织——从标签广播、CAM比较到选择和操作数读出。在那些讨论中，我们对选择逻辑（select logic）和唤醒逻辑（wakeup logic）只是简要提及，将其作为流水线中的一个抽象阶段来处理。然而，选择和唤醒正是发射逻辑中最关键、最复杂的部分——它们的设计质量直接决定了处理器能否实现背靠背（back-to-back）发射，也决定了发射队列的规模上限和时钟频率。

本章深入讨论四个核心主题：（1）仲裁电路——如何从多个就绪指令中公平且高效地选择$N$条进行发射；（2）唤醒逻辑——如何在指令完成执行后尽快通知等待其结果的后续指令；（3）推测唤醒——如何在Load指令完成之前就推测性地唤醒依赖指令，以及推测失败时的恢复机制；（4）依赖矩阵调度器——一种替代传统CAM调度器的矩阵式设计，在时序和功耗方面具有独特优势。

仲裁电路的设计

在超标量处理器的发射队列中，每个周期可能有多条指令同时处于就绪状态（所有源操作数已就绪），但执行单元的数量有限——一个$N$-wide的处理器每周期最多发射$N$条指令。因此，需要一个仲裁电路（arbiter）从$M$个就绪指令中选择$N$个进行发射（$N \leq M$）。仲裁电路的设计目标是：

1. 正确性：每个周期选出的$N$条指令不能重复。

2. 公平性：长时间等待的指令不应被无限期地饿死（starvation-free）。

3. 性能：优先选择"最有价值"的指令（通常是最老的指令，因为它们更接近退休，释放ROB资源）。

4. 速度：仲裁逻辑的延迟必须足够小，以适应单个时钟周期的时间预算。

1-of-M的仲裁电路

最简单的仲裁问题是从$M$个请求中选择1个授权——即1-of-$M$仲裁。这是所有仲裁电路的基础构建块。

固定优先级仲裁器

最直接的实现是固定优先级仲裁器（fixed-priority arbiter）：给每个请求者分配一个静态优先级（例如，请求0的优先级最高，请求$M-1$的优先级最低），当多个请求同时有效时，总是选择优先级最高的那个。

链式固定优先级仲裁器：请求0的优先级最高

逐步推导布尔方程

让我们从最基本的原理出发，逐步推导固定优先级仲裁器的布尔方程。仲裁器的核心约束是互斥——在任何时刻最多只有一个grant信号为1。为了实现这一约束，我们引入一个抑制链（inhibit chain）信号$\text{kill}[i]$，表示"请求$i$及之前的请求中是否存在有效请求"：

$$\begin{aligned} \text{kill}[0] &= \text{req}[0] \\ \text{kill}[i] &= \text{req}[i] \vee \text{kill}[i-1] \quad (i \geq 1) \end{aligned}$$

基于抑制链，grant信号可以简洁地表达为：

$$\begin{aligned} \text{gnt}[0] &= \text{req}[0] \\ \text{gnt}[i] &= \text{req}[i] \wedge \overline{\text{kill}[i-1]} \quad (i \geq 1) \end{aligned}$$

将$\text{kill}$展开，可得到直接形式：

$$\begin{aligned} \text{gnt}[0] &= \text{req}[0] \\ \text{gnt}[1] &= \text{req}[1] \wedge \overline{\text{req}[0]} \\ \text{gnt}[2] &= \text{req}[2] \wedge \overline{\text{req}[0]} \wedge \overline{\text{req}[1]} \\ \text{gnt}[3] &= \text{req}[3] \wedge \overline{\text{req}[0]} \wedge \overline{\text{req}[1]} \wedge \overline{\text{req}[2]} \\ &\vdots \\ \text{gnt}[i] &= \text{req}[i] \wedge \bigwedge_{j=0}^{i-1} \overline{\text{req}[j]} \end{aligned}$$

注意公式(eq:ch29-gnti)中的两种等价表达：直接形式使用$i$个反相输入的AND门，需要$(i+1)$输入AND门；而基于抑制链的形式只需要一个2输入AND门和一个反相器，但引入了抑制链的串行依赖。两种实现的选择决定了电路的延迟特性。

链式结构的延迟分析

基于抑制链的实现（公式(eq:ch29-gnti)）中，$\text{kill}[i]$依赖于$\text{kill}[i-1]$，形成一个从$\text{req}[0]$到$\text{kill}[M-1]$的优先级链（priority chain）。我们精确分析其延迟：

• $\text{kill}[0] = \text{req}[0]$：0级门延迟（直连）。

• $\text{kill}[1] = \text{req}[1] \vee \text{kill}[0]$：1级门延迟（1个OR门）。

• $\text{kill}[i] = \text{req}[i] \vee \text{kill}[i-1]$：在$\text{kill}[i-1]$之后再加1级OR门。

• $\text{kill}[M-1]$的总延迟：$(M-1)$级OR门。

• $\text{gnt}[M-1] = \text{req}[M-1] \wedge \overline{\text{kill}[M-2]}$：在$\text{kill}[M-2]$之后再加1级反相器+1级AND门。

因此，$\text{gnt}[M-1]$的最坏情况延迟为$(M-1)+2 = M+1$级逻辑门（实际上，使用复合门NOR/NAND可以将OR+INV合并，延迟降低到约$M$级）。对于$M=64$，这意味着约64级逻辑门的延迟。假设每级逻辑门延迟约为$10$ ps（5 nm工艺），总延迟约为640 ps——远超5 GHz时钟周期（200 ps）。

直接形式的延迟

如果使用直接形式（宽AND门），$\text{gnt}[M-1]$需要一个$M$输入的AND门。$M$输入AND门可以用树形结构实现，延迟为$\lceil \log_2 M \rceil$级。对于$M=64$，延迟为$\lceil \log_2 64 \rceil = 6$级。但问题在于所有$M$个$\text{gnt}$信号不能共享中间结果——每个$\text{gnt}[i]$需要独立的$(i+1)$输入AND门。虽然每个独立的AND门延迟为$O(\log i)$，但整体电路的面积为$O(M^2)$（所有AND门的输入总数为$1+2+\cdots+M = M(M+1)/2$）。

树形仲裁器结构

为了在延迟和面积之间取得平衡，可以使用树形仲裁器。基本思路是将$M$个请求分组并使用层次化结构处理：

1. 将$M$个请求分为$M/k$个组，每组包含$k$个请求（$k$通常取4或8）。

2. 每组内部使用一个$k$路的固定优先级仲裁器，同时产生一个$\text{any}$信号（$\text{any}_g = \bigvee_{i \in g} \text{req}[i]$）。

3. 所有组的$\text{any}$信号送入一个第二级$(M/k)$路仲裁器。

4. 第二级仲裁器选择一个组，然后该组内部的仲裁器选择具体的请求者。

5. 最终的grant = 组内grant AND 组间grant。

两级树形仲裁器：8个请求者分为2组，每组4路

两级树形结构的关键路径延迟为：

$$T_{\text{tree}} = T_{\text{group}} + T_{\text{select}} + T_{\text{AND}} = O(k) + O(M/k) + O(1)$$

当$k = \sqrt{M}$时取最小值$T_{\text{tree}} = O(2\sqrt{M}) = O(\sqrt{M})$。多级树形结构可以进一步降低到$O(\log M)$。

请求数$M$	链式延迟	两级树形	多级树形$O(\log M)$
8	8	$2\times3 = 6$	6
16	16	$2\times4 = 8$	8
32	32	$2\times6 \approx 12$	10
64	64	$2\times8 = 16$	12
128	128	$2\times12 \approx 24$	14

链式与树形仲裁器延迟对比（以逻辑门级数计）

对于$M=64$，两级树形结构的延迟约为16级逻辑门——相比链式结构的64级有了显著改善。多级树形结构可以进一步降至12级。

优先级编码器

优先级编码器（Priority Encoder）是固定优先级仲裁器的编码输出版本——它不仅确定哪个请求被授权，还输出被授权请求的索引（编号）。优先级编码器是仲裁电路的核心构建块。

基本优先级编码器

一个$M$输入的优先级编码器接受$M$个请求位，输出$\lceil\log_2 M\rceil$位的索引和一个"有效"（valid）位：

• 如果没有任何请求有效，则valid=0，索引无意义。

• 如果有一个或多个请求有效，则valid=1，索引为最高优先级有效请求的编号。

4位优先级编码器的门级推导

以4位优先级编码器为例，逐步推导其门级实现。输入为$\text{req}[3:0]$，输出为2位索引$\text{idx}[1:0]$和有效位$\text{valid}$。请求0的优先级最高。

首先，写出真值表的关键行（仅列出至少有一个请求有效的情况）：

req[3]	req[2]	req[1]	req[0]	idx[1]	idx[0]	valid
X	X	X	1	0	0	1
X	X	1	0	0	1	1
X	1	0	0	1	0	1
1	0	0	0	1	1	1
0	0	0	0	–	–	0

从真值表推导布尔方程：

$$\begin{aligned} \text{valid} &= \text{req}[0] \vee \text{req}[1] \vee \text{req}[2] \vee \text{req}[3] \\ \text{idx}[0] &= \overline{\text{req}[0]} \wedge \text{req}[1] \vee \overline{\text{req}[0]} \wedge \overline{\text{req}[1]} \wedge \overline{\text{req}[2]} \wedge \text{req}[3] \\ &= \overline{\text{req}[0]} \wedge (\text{req}[1] \vee \overline{\text{req}[2]} \wedge \text{req}[3]) \\ \text{idx}[1] &= \overline{\text{req}[0]} \wedge \overline{\text{req}[1]} \wedge (\text{req}[2] \vee \text{req}[3]) \end{aligned}$$

门级实现需要：$\text{valid}$需要一个4输入OR门（1级）；$\text{idx}[1]$需要2个反相器、1个2输入OR门、1个3输入AND门（2级）；$\text{idx}[0]$需要2个反相器、2个AND门、1个OR门（3级）。总延迟约3级逻辑门。

module priority_enc_4 (
  input  logic [3:0] req,
  output logic [1:0] idx,
  output logic       valid
);
  always_comb begin
    valid = |req;           // 任意一个请求有效
    casez (req)
      4'b???1: idx = 2'd0;  // req[0] 最高优先
      4'b??10: idx = 2'd1;
      4'b?100: idx = 2'd2;
      4'b1000: idx = 2'd3;
      default: idx = 2'd0;
    endcase
  end
endmodule

树形优先级编码器的两级实现

对于大规模的优先级编码器（$M \geq 8$），使用树形递归结构可以显著降低延迟。以8位优先级编码器为例，将其分解为两个4位子编码器。

第一级：将$\text{req}[7:0]$分为低半部分$\text{req}[3:0]$和高半部分$\text{req}[7:4]$，分别送入两个4位优先级编码器，产生：

• 低半部分：$\text{idx\_lo}[1:0]$, $\text{valid\_lo}$

• 高半部分：$\text{idx\_hi}[1:0]$, $\text{valid\_hi}$

第二级：使用$\text{valid\_lo}$作为选择信号，合成最终结果：

$$\begin{aligned} \text{valid} &= \text{valid\_lo} \vee \text{valid\_hi} \\ \text{idx}[2] &= \overline{\text{valid\_lo}} \wedge \text{valid\_hi} \\ \text{idx}[1:0] &= \text{valid\_lo}\ ?\ \text{idx\_lo}[1:0] : \text{idx\_hi}[1:0] \end{aligned}$$

第二级的逻辑只需要1个OR门、1个AND门和一个2-to-1 MUX（约2级门延迟）。总延迟 = 第一级（3级） + 第二级（2级） = 5级逻辑门。

树形优先级编码器：将8位编码器分解为两个4位编码器

16位和32位编码器的级联

树形结构可以递归扩展到任意规模：

16位编码器：将两个8位编码器的结果合成。第一级为两个8位编码器（延迟5级），第二级为合成逻辑（延迟2级），总延迟 = 5 + 2 = 7级逻辑门。

32位编码器：将两个16位编码器的结果合成。总延迟 = 7 + 2 = 9级逻辑门。

64位编码器：总延迟 = 9 + 2 = 11级逻辑门。

一般地，$M$位树形优先级编码器的延迟公式为：

$$T_{\text{tree-enc}}(M) = T_{\text{base}} + 2 \cdot (\log_2 M - \log_2 M_{\text{base}})$$

其中$T_{\text{base}}$是基本编码器的延迟（对于4位基本编码器，$T_{\text{base}} = 3$），每增加一级递归增加2级门延迟（MUX + 最高位生成）。

硬件描述 2 — 树形优先级编码器的延迟汇总

以4位编码器为基础单元，树形递归扩展的延迟：

编码器规模	递归层数	总延迟（逻辑门级数）
4位（基础）	0	3级
8位	1	5级
16位	2	7级
32位	3	9级
64位	4	11级
128位	5	13级

延迟公式：$T = 3 + 2 \cdot (\log_2 M - 2) = 2\log_2 M - 1$（$M \geq 4$时）。这验证了每级递归增加约2个门延迟的结论。

轮转优先级仲裁器

固定优先级仲裁器的一个主要缺点是饥饿问题——低优先级的请求者可能永远无法获得授权。轮转优先级仲裁器（Round-Robin Arbiter）通过动态旋转优先级指针来解决这个问题。

轮转仲裁的布尔方程

轮转仲裁器维护一个优先级指针$\text{ptr}$，指示当前优先级最高的请求位置。每次仲裁完成后，$\text{ptr}$移动到被授权请求的下一个位置。

设$M$个请求为$\text{req}[M-1:0]$，优先级指针为$\text{ptr}$。轮转仲裁等价于以$\text{ptr}$为起点的环形固定优先级仲裁：

$$\begin{aligned} \text{gnt}[i] = \text{req}[i] \wedge \bigwedge_{j \neq i, j \text{ 在 } i \text{ 之前（从ptr开始逆时针）}} \overline{\text{req}[j]} \end{aligned}$$

这个公式可以用屏蔽优先级仲裁器（Masked Priority Arbiter）实现：

1. 生成屏蔽向量：$\text{mask}[i] = 1$当且仅当$i$在$\text{ptr}$到$M-1$的范围内（含$\text{ptr}$，环形）。

2. 高优先级部分：$\text{masked\_req}[i] = \text{req}[i] \wedge \text{mask}[i]$——只保留$\text{ptr}$之后的请求。

3. 对$\text{masked\_req}$进行固定优先级仲裁，得到$\text{gnt\_hi}$。

4. 如果$\text{masked\_req}$全为0（$\text{ptr}$之后没有请求），则对原始$\text{req}$进行固定优先级仲裁，得到$\text{gnt\_lo}$。

5. 最终结果：$\text{gnt} = |\text{masked\_req}|\ ?\ \text{gnt\_hi} : \text{gnt\_lo}$。

module round_robin_arb #(
  parameter M = 8
)(
  input  logic           clk, rst_n,
  input  logic [M-1:0]   req,
  output logic [M-1:0]   gnt
);
  logic [$clog2(M)-1:0]  ptr;      // 优先级指针
  logic [M-1:0]          mask;     // 屏蔽向量
  logic [M-1:0]          masked_req;
  logic [M-1:0]          gnt_hi, gnt_lo;

  // 生成屏蔽向量: mask[i]=1 if i >= ptr
  always_comb begin
    for (int i = 0; i < M; i++)
      mask[i] = (i >= ptr);
    masked_req = req & mask;
  end

  // 两个固定优先级仲裁器
  fixed_priority_arb #(.M(M)) arb_hi (
    .req(masked_req), .gnt(gnt_hi));
  fixed_priority_arb #(.M(M)) arb_lo (
    .req(req),        .gnt(gnt_lo));

  // 选择
  assign gnt = (|masked_req) ? gnt_hi : gnt_lo;

  // 更新指针: 指向被授权请求的下一个位置
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n)
      ptr <= '0;
    else if (|gnt) begin
      for (int i = 0; i < M; i++)
        if (gnt[i]) ptr <= (i + 1) % M;
    end
  end
endmodule

轮转仲裁的延迟分析

轮转仲裁器需要两个固定优先级仲裁器并行工作，然后用一个MUX选择。总延迟为：

$$T_{\text{RR}} = \max(T_{\text{mask}}, T_{\text{FPA}}) + T_{\text{MUX}} = \max(1, T_{\text{FPA}}) + 1 = T_{\text{FPA}} + 1$$

屏蔽向量的生成（$T_{\text{mask}} = 1$级比较器/译码器）与固定优先级仲裁器并行，不增加关键路径。因此轮转仲裁器的延迟仅比固定优先级仲裁器多1级MUX（约1$\sim$2级FO4）。

轮转仲裁在发射队列中的应用

轮转仲裁器在发射队列中的典型应用场景是多个功能单元共享同一个发射端口时的仲裁。例如，如果一个发射端口同时连接ALU和乘法器，当ALU指令和乘法指令同时就绪时，轮转仲裁确保两者公平地交替使用该端口。

然而，在发射队列的主调度器中，轮转仲裁通常不是最佳选择——因为发射队列需要的是最老优先而非公平轮转。最老优先保证ROB表项被尽快释放，而轮转仲裁可能选择年轻的指令先发射，导致ROB满阻塞。

N-of-M的仲裁电路

在超标量处理器中，每个周期需要从$M$个就绪指令中选择$N$条进行发射（$N$通常为4$\sim$8，$M$为发射队列大小，通常为32$\sim$128）。这就是$N$-of-$M$仲裁问题，它比简单的1-of-$M$仲裁复杂得多。

级联式仲裁

最直接的实现方式是将$N$个1-of-$M$仲裁器级联（cascade）：

1. 第一个仲裁器从$M$个请求中选出优先级最高的一个，设为$g_1$。

2. 将$g_1$对应的请求位屏蔽掉（设为0），将剩余的$M-1$个请求送入第二个仲裁器。

3. 第二个仲裁器选出剩余请求中优先级最高的一个，设为$g_2$。

4. 重复上述过程，直到选出$N$个。

级联式$N$-of-$M$仲裁：$N$个1-of-$M$仲裁器串行连接

级联式仲裁的问题在于延迟是$O(N \times T_{\text{1-of-M}})$——$N$个仲裁器是串行的，因为每个仲裁器的输入依赖于前一个仲裁器的输出。

级联式仲裁的延迟分析

让我们详细分析4-of-64级联仲裁器的延迟。每个1-of-64树形仲裁器的延迟约为$2\log_2 64 - 1 = 11$级逻辑门。在级联中，每一级还需要额外的屏蔽逻辑（将上一级的grant输出译码为独热向量，然后与请求向量取AND-NOT），屏蔽逻辑的延迟约为2级（译码器 + AND门）。因此每级的有效延迟为$11 + 2 = 13$级：

$$T_{\text{cascade}} = N \times (T_{\text{1-of-M}} + T_{\text{mask}}) = 4 \times (11 + 2) = 52\text{级逻辑门}$$

在5 GHz频率下（200 ps周期），即使每级逻辑门延迟仅3 ps（激进的3 nm工艺），52级也需要156 ps——几乎占满整个周期。如果考虑到线延迟和扇出，实际延迟将超过一个时钟周期。

前缀和方案

级联式仲裁的根本问题在于串行依赖——第$k$个仲裁器必须等第$k-1$个完成后才能开始。前缀和（prefix sum）方案通过并行计算来打破这种串行依赖。

基本思想是：首先并行计算每个请求位的"前缀请求计数"——即该位之前有多少个有效请求。然后，第$k$个被选中的请求就是前缀计数等于$k-1$的第一个有效请求。

以$N=2$, $M=8$为例。定义前缀和$S[i] = \sum_{j=0}^{i-1} \text{req}[j]$（$S[0]=0$）。则：

$$\begin{aligned} \text{gnt}_1[i] &= \text{req}[i] \wedge (S[i] == 0) \quad \text{（第1个授权：前面没有请求）} \\ \text{gnt}_2[i] &= \text{req}[i] \wedge (S[i] == 1) \quad \text{（第2个授权：前面恰好1个请求）} \end{aligned}$$

前缀和$S[i]$可以使用并行前缀电路（parallel prefix circuit）在$O(\log M)$级门延迟内计算完成——这与级联方案的$O(N \times \log M)$相比，消除了对$N$的依赖。

前缀和的位宽为$\lceil \log_2(N+1) \rceil$位（需要表示0到$N$之间的值）。对于$N=4$, $M=64$，前缀和宽度为3位，并行前缀电路的延迟约为$3 \times \log_2 64 = 18$级门延迟（每位$\log_2 M$级），加上最终的比较逻辑（约3级），总延迟约21级——远优于级联方案的52级。

硬件描述 3 — 前缀和仲裁的硬件开销

对于$N$-of-$M$前缀和仲裁器（$N=4$, $M=64$）：

• 前缀和电路：64个3位加法器，以Brent-Kung或Kogge-Stone拓扑排列。总面积约$64 \times 3 \times 6 = 1152$个等效门。

• 比较逻辑：64组3位比较器$\times$ 4个目标值，约$64 \times 4 \times 4 = 1024$个等效门。

• 总面积约2200个等效门——比级联方案（4个独立的64路仲裁器，约$4 \times 400 = 1600$门）略大，但延迟优势显著。

• 延迟约21级逻辑门——仅为级联方案（52级）的40%。

前缀和方案的门级实现

以$N=2$, $M=8$的具体例子来展示前缀和方案的门级实现。每个前缀和$S[i]$是1位（因为$\lceil\log_2(2+1)\rceil = 2$位，但$N=2$时只需检查$S[i]==0$或$S[i]==1$）。

首先定义：$S[0] = 0$，$S[i] = S[i-1] + \text{req}[i-1]$（$1 \leq i \leq 8$）。

直接计算$S[i]$等价于计算$\text{req}[0]$到$\text{req}[i-1]$的前缀OR（对于$N=2$，只需1位前缀和即可区分"0个"vs"$\geq 1$个"前置请求）。但对于一般的$N$，需要多位前缀加法。

使用Kogge-Stone并行前缀电路：

Kogge-Stone拓扑以$O(M \log M)$面积实现$O(\log M)$延迟的前缀计算。对于8个1位输入，结构如下：

1. 第0级（输入）：$P_0[i] = \text{req}[i]$（propagate），$G_0[i] = 0$（generate，这里简化为纯前缀OR）。

2. 第1级：$P_1[i] = P_0[i] \vee P_0[i-1]$，每个位与偏移1的位合并。

3. 第2级：$P_2[i] = P_1[i] \vee P_1[i-2]$，偏移2合并。

4. 第3级：$P_3[i] = P_2[i] \vee P_2[i-4]$，偏移4合并。

3级后，$P_3[i] = \text{req}[0] \vee \text{req}[1] \vee \cdots \vee \text{req}[i]$，这就是前缀OR。

总延迟：3级OR门 = 3级FO4。加上最终的grant生成逻辑：

$$\begin{aligned} \text{gnt}_1[i] &= \text{req}[i] \wedge \overline{P_3[i-1]} \quad (1\text{级AND+INV}) \\ \text{gnt}_2[i] &= \text{req}[i] \wedge P_3[i-1] \wedge \overline{P_3[i-2] \wedge \text{req}[i-1]} \quad (\text{更复杂}) \end{aligned}$$

对于$N>2$，grant生成逻辑需要多位前缀和的比较，复杂度增加。

并行式仲裁

为了降低$N$-of-$M$仲裁的延迟，另一种方案是使用并行式仲裁：将$M$个请求分为$N$个不重叠的组（每组$M/N$个请求），每个组使用一个独立的1-of-$(M/N)$仲裁器。$N$个仲裁器可以并行工作，总延迟仅为一个1-of-$(M/N)$仲裁器的延迟。

并行式$N$-of-$M$仲裁：将请求分组后并行仲裁

并行式仲裁的主要缺点是负载不均衡：如果就绪指令的分布不均匀（某些组有很多就绪指令，某些组没有），则整体吞吐率会低于理想的$N$条/周期。为了缓解这个问题，可以在组间增加溢出仲裁（overflow arbitration）逻辑：当某个组没有就绪指令时，它的仲裁器可以从相邻组"借"一个请求来处理。但溢出仲裁增加了组间的逻辑依赖，延长了关键路径。

混合式仲裁

实际的高性能处理器通常采用混合策略——在组内使用优先级编码器实现1-of-$(M/N)$仲裁，在组间使用年龄信息来决定优先级（而不是简单的固定分组）。这种设计在延迟和灵活性之间取得了较好的平衡。

$N$-of-$M$仲裁方案的综合对比

方案	延迟（门级数）	面积	选择质量
级联式	$4 \times 13 = 52$	$4 \times 400 = 1600$门	全局最优
前缀和	$\sim$21	$\sim$2200门	全局最优
并行式（固定分组）	$\sim$9	$\sim$400门	受分组限制
并行式（带溢出）	$\sim$14	$\sim$800门	接近全局最优
混合式（组内编码+组间年龄）	$\sim$15	$\sim$1200门	近似全局最优

$N$-of-$M$仲裁方案对比（$N$=4, $M$=64）

在实际高性能处理器中，混合式仲裁和前缀和方案是最常用的选择。混合式方案在延迟和灵活性之间提供了最好的权衡，适合分区化的发射队列设计。前缀和方案适合需要全局最优选择的统一发射队列。

仲裁公平性与效率的权衡

仲裁器的设计目标不仅是速度，还需要在公平性和效率之间取得平衡：

• 严格公平（如轮转仲裁）：保证每个请求者获得相同的授权机会。在发射队列中，严格公平意味着所有就绪指令获得平等的发射机会，不考虑年龄。这可能导致年轻指令先于老指令发射，增加ROB占用时间。

• 年龄优先：总是选择最老的就绪指令。这最大化了ROB利用率和退休吞吐率，但需要年龄矩阵等硬件支持，增加了延迟和面积。

• 关键路径优先：优先选择位于关键路径上的指令（即依赖链最长的指令）。这在理论上可以最大化ILP利用率，但在硬件中检测关键路径代价很高——需要遍历整个依赖图。某些学术工作提出了近似关键路径检测的方案，但商业处理器中很少使用。

在实践中，最老优先被证明是最佳的通用策略——它在各种工作负载上表现稳定，且硬件实现的复杂度可控。研究表明，最老优先相对于理想的"完美关键路径感知"策略，IPC差距仅为1%$\sim$3%——这个微小的差距不值得关键路径检测的硬件代价。

年龄矩阵

在29.1.1 节中讨论的固定优先级仲裁器有一个严重的问题：饿死（starvation）。低优先级的请求者如果持续面对高优先级请求者的竞争，可能永远无法获得授权。在发射队列的场景中，这意味着较年轻的指令可能一直无法发射——虽然在实践中这种极端情况不常出现（因为老指令终会执行完毕并释放），但一个更根本的问题是：哪个指令应该被优先发射？

答案通常是最老优先（oldest-first）策略——优先发射程序顺序中最老的就绪指令。最老优先有两个核心优势：

1. 避免饿死：最老的指令总是具有最高优先级，不会被更年轻的指令阻塞。

2. 优化ROB利用率：老指令更接近ROB的头部（退休端），优先执行它们能更早地退休并释放ROB表项，为新指令腾出空间。

实现最老优先需要知道发射队列中所有指令之间的相对年龄关系。年龄矩阵（Age Matrix）是实现这一目标的经典数据结构。

年龄矩阵的定义

年龄矩阵是一个$N \times N$的位矩阵$A$（$N$为发射队列的表项数），其中$A[i][j]$表示表项$i$中的指令是否比表项$j$中的指令更老：

$$A[i][j] = \begin{cases} 1, & \text{如果表项 } i \text{ 的指令比表项 } j \text{ 的指令更老} \\ 0, & \text{否则} \end{cases}$$

年龄矩阵具有反对称性：$A[i][j] = \overline{A[j][i]}$（对于$i \neq j$），并且对角线元素$A[i][i] = 0$。因此，一个$N \times N$的年龄矩阵只需要存储$N(N-1)/2$位信息（上三角或下三角部分）。

年龄矩阵的维护

年龄矩阵在指令分配到发射队列时更新。当一条新指令$X$被分配到表项$k$时：

1. 将行$k$全部清零：$A[k][*] = 0$（新指令$X$比所有已有指令都年轻）。

2. 将列$k$的所有有效行设为1：对所有有效表项$i$（$i \neq k$），设置$A[i][k] = 1$（所有已有指令都比$X$更老）。

3. 当同一周期内有多条新指令（$W$-wide分配）时，按照程序顺序设置新指令之间的年龄关系。

4表项年龄矩阵的详细实例

让我们用一个$N=4$的具体例子，逐步演示年龄矩阵的完整生命周期。初始状态：4个表项全部为空，矩阵全零。

步骤1：指令A分配到表项0。 A是第一条指令，没有需要比较的对象：

$A$	0	1	2	3
0 (A)	–	0	0	0
1	0	–	0	0
2	0	0	–	0
3	0	0	0	–

valid = {1, 0, 0, 0}