NoC组件之Router微架构解析（四）仲裁
Chapter 4: Arbitration Logic
（本文版权归作者所有，任何形式的转载都请注明出处）
- 通常的仲裁模块可以抽象为以下模型，其特性包括：
- 输入请求：表示 Active 状态的请求
Request[N-1:0]； - 输出授权：仲裁结果
Grant[N-1:0]，One-Hot 编码； - 时序：每个 Cycle 可连续仲裁；
- 优先级状态寄存器：每个请求的 Priority State，位宽取决于仲裁算法；
- 优先级更新逻辑：由仲裁算法决定。
- 输入请求：表示 Active 状态的请求
固定优先级算法：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：非活跃 / LP0b01：非活跃 / HP0b10：活跃 / LP0b11：活跃 / 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。
- 若