FPGA基础：RR仲裁调度算法

1简介

在FPGA和IC设计领域，经常会面临一个挑战：多个端口同时竞争一个端口的数据。在这种情况下，采用RR调度策略可能是一种解决方案。

RR(Round Robin)仲裁调度是一种常用的调度算法，广泛应用于操作系统和计算机网络中。该算法的设计初衷是为了公平地分配资源和服务各个任务，确保每个任务都能够获得一定的执行时间，从而提高系统的响应速度和资源利用率。

这种轮流调度的方式确保了每个任务都能够获得公平的执行机会，而且对于响应时间敏感的任务也能够及时得到处理。RR仲裁调度算法的简单性和公平性使其成为了许多操作系统和网络系统中默认的调度策略之一。

2RR调度原理

在RR仲裁调度算法中，任务被分配一个固定的时间片(time slice)，当任务开始执行时，它会被允许运行一个时间片的时间，然后被暂停，等待下一个调度周期。如果任务在一个时间片内没有完成，它将被放回就绪队列的末尾，等待下一次调度。

举例说明一下：以下图展示的是一个4端口仲裁的RR调度。在第0周期，优先级为0的端口0被选中，其优先级顺序为0、1、2、3，对应输入信号为4'b1101，输出信号为4'b0001。在第1周期，优先级为1的端口1被选中，其优先级顺序为1、2、3、0，输入信号为4'b1101，输出信号为4'b0100。在第2周期，优先级为2的端口2被选中，其优先级顺序为2、3、0、1，输入信号为4'b1001，输出信号为4'b1000。在第3周期，优先级为3的端口3被选中，其优先级顺序为3、0、1、2，输入信号为4'b1001，输出信号为4'b1000。随后依此循环。

3RR调度核心部分实现

wire [WD - 1:0] mask = {req[WD - 2:0] | mask[WD - 2:0], 1'b0};wire [WD - 1:0] grant = ~mask & req;

这个是实现RR调度的最基本结构，req 是输入的请求信号，mask 是一个掩码，用于标记哪些端口在当前时刻已经被选择了，grant 是输出的授权信号，表示当前时刻被选中的端口。

产生mask代码本质上如下(以WD = 4为例)：

mask[0] = 0mask[1] = mask[0] | req[0]mask[2] = mask[1] | req[1]mask[3] = mask[2] | req[2]

mask 的计算逻辑是将之前的掩码向左移动一位，并将最低位设置为0。这样做的目的是为了模拟一个循环移位寄存器，在每个周期内，该掩码会循环地向左移动，表示当前周期内已经被选中的端口。req[WD - 2:0] 表示将 req 向右偏移一个位置，以便与 mask 进行按位或运算。mask的作用是锁定已经被选中的端口，同时区分高低优先级。mask中为1的位置表示高优先级要去调度的区域，而为0的位置表示低优先级要去调度的区域，因为这些位置已经被调度过了。

grant 的计算逻辑是取反操作符 ~ 对 mask 进行求反，然后与 req 进行按位与运算。这样做的目的是找到当前周期内请求信号 req 中尚未被选中的端口，这些端口将被授予访问权限。

3总结

本章主要探讨了RR调度的原理、用途以及其核心的实现方法。读者可以自行考虑基于核心代码的RR实现方法。后续将会进一步更新RR调度的具体实现方法。