Chapter 4: Arbitration Logic

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

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

2. 固定优先级算法：bit0 → bitN 优先级逐次降低。设 Request = {Rn, Rn-1, ..., R1, R0}，则仲裁结果表达式为：

   $$G[i]=R[i]\cdot \overline{R[i-1]}\cdot ...\cdot \overline{R[1]}\cdot \overline{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)：

   

3. 轮询（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，规律是由低到高轮询。

4. 利用二维优先级矩阵，可以实现更多复杂仲裁算法。图中矩阵元素 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。