1簡(jiǎn)介

在FPGA和IC設(shè)計(jì)領(lǐng)域，經(jīng)常會(huì)面臨一個(gè)挑戰(zhàn)：多個(gè)端口同時(shí)競(jìng)爭(zhēng)一個(gè)端口的數(shù)據(jù)。在這種情況下，采用RR調(diào)度策略可能是一種解決方案。

RR（Round Robin）仲裁調(diào)度是一種常用的調(diào)度算法，廣泛應(yīng)用于操作系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)中。該算法的設(shè)計(jì)初衷是為了公平地分配資源和服務(wù)各個(gè)任務(wù)，確保每個(gè)任務(wù)都能夠獲得一定的執(zhí)行時(shí)間，從而提高系統(tǒng)的響應(yīng)速度和資源利用率。

這種輪流調(diào)度的方式確保了每個(gè)任務(wù)都能夠獲得公平的執(zhí)行機(jī)會(huì)，而且對(duì)于響應(yīng)時(shí)間敏感的任務(wù)也能夠及時(shí)得到處理。RR仲裁調(diào)度算法的簡(jiǎn)單性和公平性使其成為了許多操作系統(tǒng)和網(wǎng)絡(luò)系統(tǒng)中默認(rèn)的調(diào)度策略之一。

2RR調(diào)度原理

在RR仲裁調(diào)度算法中，任務(wù)被分配一個(gè)固定的時(shí)間片（time slice），當(dāng)任務(wù)開始執(zhí)行時(shí)，它會(huì)被允許運(yùn)行一個(gè)時(shí)間片的時(shí)間，然后被暫停，等待下一個(gè)調(diào)度周期。如果任務(wù)在一個(gè)時(shí)間片內(nèi)沒(méi)有完成，它將被放回就緒隊(duì)列的末尾，等待下一次調(diào)度。

舉例說(shuō)明一下：以下圖展示的是一個(gè)4端口仲裁的RR調(diào)度。在第0周期，優(yōu)先級(jí)為0的端口0被選中，其優(yōu)先級(jí)順序?yàn)?、1、2、3，對(duì)應(yīng)輸入信號(hào)為4'b1101，輸出信號(hào)為4'b0001。在第1周期，優(yōu)先級(jí)為1的端口1被選中，其優(yōu)先級(jí)順序?yàn)?、2、3、0，輸入信號(hào)為4'b1101，輸出信號(hào)為4'b0100。在第2周期，優(yōu)先級(jí)為2的端口2被選中，其優(yōu)先級(jí)順序?yàn)?、3、0、1，輸入信號(hào)為4'b1001，輸出信號(hào)為4'b1000。在第3周期，優(yōu)先級(jí)為3的端口3被選中，其優(yōu)先級(jí)順序?yàn)?、0、1、2，輸入信號(hào)為4'b1001，輸出信號(hào)為4'b1000。隨后依此循環(huán)。

3RR調(diào)度核心部分實(shí)現(xiàn)

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

這個(gè)是實(shí)現(xiàn)RR調(diào)度的最基本結(jié)構(gòu)，req 是輸入的請(qǐng)求信號(hào)，mask 是一個(gè)掩碼，用于標(biāo)記哪些端口在當(dāng)前時(shí)刻已經(jīng)被選擇了，grant 是輸出的授權(quán)信號(hào)，表示當(dāng)前時(shí)刻被選中的端口。

產(chǎn)生mask代碼本質(zhì)上如下（以WD = 4為例）：

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

mask 的計(jì)算邏輯是將之前的掩碼向左移動(dòng)一位，并將最低位設(shè)置為0。這樣做的目的是為了模擬一個(gè)循環(huán)移位寄存器，在每個(gè)周期內(nèi)，該掩碼會(huì)循環(huán)地向左移動(dòng)，表示當(dāng)前周期內(nèi)已經(jīng)被選中的端口。req[WD - 2:0] 表示將 req 向右偏移一個(gè)位置，以便與 mask 進(jìn)行按位或運(yùn)算。mask的作用是鎖定已經(jīng)被選中的端口，同時(shí)區(qū)分高低優(yōu)先級(jí)。mask中為1的位置表示高優(yōu)先級(jí)要去調(diào)度的區(qū)域，而為0的位置表示低優(yōu)先級(jí)要去調(diào)度的區(qū)域，因?yàn)檫@些位置已經(jīng)被調(diào)度過(guò)了。

grant 的計(jì)算邏輯是取反操作符 ~ 對(duì) mask 進(jìn)行求反，然后與 req 進(jìn)行按位與運(yùn)算。這樣做的目的是找到當(dāng)前周期內(nèi)請(qǐng)求信號(hào) req 中尚未被選中的端口，這些端口將被授予訪問(wèn)權(quán)限。

3總結(jié)

本章主要探討了RR調(diào)度的原理、用途以及其核心的實(shí)現(xiàn)方法。讀者可以自行考慮基于核心代碼的RR實(shí)現(xiàn)方法。后續(xù)將會(huì)進(jìn)一步更新RR調(diào)度的具體實(shí)現(xiàn)方法。