当前位置：首页 > news >正文

NoC组件之Router微架构解析（四）仲裁

news 2026/6/16 5:10:46

Chapter 4: Arbitration Logic

（本文版权归作者所有，任何形式的转载都请注明出处）

通常的仲裁模块可以抽象为以下模型，其特性包括：
- 输入请求：表示 Active 状态的请求Request[N-1:0]；
- 输出授权：仲裁结果Grant[N-1:0]，One-Hot 编码；
- 时序：每个 Cycle 可连续仲裁；
- 优先级状态寄存器：每个请求的 Priority State，位宽取决于仲裁算法；
- 优先级更新逻辑：由仲裁算法决定。

固定优先级算法：bit0 → bitN 优先级逐次降低。设Request = {Rn, Rn-1, ..., R1, R0}，则仲裁结果表达式为：
G[i]=R[i]⋅R[i−1]‾⋅...⋅R[1]‾⋅R[0]‾G[i] = R[i] \cdot \overline{R[i-1]} \cdot ... \cdot \overline{R[1]} \cdot \overline{R[0]}G[i]=R[i]⋅R[i−1]⋅...⋅R[1]⋅R[0]
也就是说该逻辑为「找最低位的 1」，具体实现方式有以下几种：
a. 从 bit0 向上查找，遍历整个Request[N-1:0]，复杂度 O(N)：
```
for(i=0;i<N;i++)if(R[i]){G[i]=1;break;}
```
b.G = R & (~R + 1)（即 R 与 R 的补码按位与），逻辑级数取决于加法计算的位宽。例如：若R = 0110_0100，R 的补码为1001_1100，则G = 0110_0100 & 1001_1100 = 0000_0100。
c. 二叉树查找：每一级子树比较两 bit 大小，选择右侧最大值，逐级筛选 Request，复杂度 O(log N)：
轮询（Round-Robin）算法：将整个Request[N-1:0]通过 Priority 分成高优先级段（HP）和低优先级段（LP）。定义映射f(Req[i], Pri[i]) = 2 * Req[i] + Pri[i]，将活跃请求与优先级转化为 2 bit 编码：
- 0b00：非活跃 / LP
- 0b01：非活跃 / HP
- 0b10：活跃 / LP
- 0b11：活跃 / HP
即可套用上述二叉树查找，每一级子树比较右侧最大值，逐级筛选 Request。仲裁成功后，需要通过移位把 Pri 向量更新——例如若Grant = 0001_0000，则下次 Pri 更新为1110_0000，目的是将上次仲裁成功的请求挪到 LP，规律是由低到高轮询。

利用二维优先级矩阵，可以实现更多复杂仲裁算法。图中矩阵元素P(i, j)代表输入 i 与 j 的优先级关系：
- 若P(i, j) = 1，表示输入 i 优先级高于输入 j；
- 若P(i, j) = 0，表示输入 i 优先级低于输入 j；
- 其中P(i, i)无意义，固定为 0。
每行 1 的数量总和可以反映出量化的优先级——sum 越大，优先级越高。若某一列中有 1，表示自己并非最高优先级，则无法获得 Grant。此外，仲裁时还需要判断输入请求是否活跃，非活跃的请求需要屏蔽掉对应行和列的 1。
如Fig 4.8所示，输入请求req = {0, 1, 1}，由于req[0]非活跃，需要屏蔽第 0 行和第 0 列，将剩余第 1、2 列做或非运算，得到Grant = {x, 0, 1}，即本轮仲裁 req2 获胜（具体电路如 Fig. 4.9 所示）。
利用不同的矩阵更新策略，可以实现多种仲裁算法：
- LRU（Least Recently Used）：本轮仲裁获胜的输入 i，将其优先级降为最低——将 i 行全部清 0，i 列全部置 1，即P(i, *) = 0，P(*, i) = 1。
- MRU（Most Recently Used）：本轮仲裁获胜的输入 i，将其优先级升为最高——将 i 行全部置 1，i 列全部清 0，即P(i, *) = 1，P(*, i) = 0。
- RR（Incremental Round Robin）：无论是否活跃，每一轮仲裁都将最高优先级的输入降为最低。
- FCFS + LRU（Hybrid First-Come First Served and Least Recently Used）：检测到新请求 i 上升沿时，若 j 非活跃，则将其优先级提高到大于其他非活跃请求 j，即P(i, j) = 1；若 i、j 同样活跃，则优先级不变；若输入 i 在本轮仲裁获胜，则将优先级置为最低，即P(i, *) = 0，P(*, i) = 1。