仲裁器設(shè)計(一) -- Fixed Priority Arbiter里面提到了，固定優(yōu)先級仲裁的一個問題就是公平性。以上篇文章里同學(xué)舉手老師點名的例子來說，如果老師每次都叫學(xué)號小的，那學(xué)號大的同學(xué)會覺得不公平，因為被老師點到的機(jī)會小。單純回答問題的話可能還好，如果我們假設(shè)每回答一個問題積一分，最后成績按照回答問題的個數(shù)來計算的話，那么很顯然這種方式對學(xué)號大的同學(xué)太不公平了。所以，仲裁器的公平性問題是在設(shè)計中我們必須要考慮的。

Round Robin就是考慮到公平性的一種仲裁算法。其基本思路是，當(dāng)一個requestor 得到了grant許可之后，它的優(yōu)先級在接下來的仲裁中就變成了最低，也就是說每個requestor的優(yōu)先級不是固定的，而是會在最高(獲得了grant)之后變?yōu)樽畹?，并且根?jù)其他requestor的許可情況進(jìn)行相應(yīng)的調(diào)整。這樣當(dāng)有多個requestor的時候，grant可以依次給每個requestor，即使之前高優(yōu)先級的requestor再次有新的request，也會等前面的requestor都grant之后再輪到它。

我們以4個requestor為例來說明，下面這個表格Req[3:0]列表示實際的request，為1表示產(chǎn)生了request;RR Priority這一列為當(dāng)前的優(yōu)先級，為0表示優(yōu)先級最高，為3表示優(yōu)先級最低;RR Grant這一列表示根據(jù)當(dāng)前Round Robin的優(yōu)先級和request給出的許可;Fixed Grant表示如果是固定優(yōu)先級，即按照3210，給出的grant值。

Req[3:0]RR PriorityRR Grant[3:0]Fixed Grant

Cycle 00101321000010001

Cycle 10101210301000001

Cycle 20011032100010001

Cycle 30010210300100010

Cycle 41000103210001000

第一個周期，初始狀態(tài)，我們假設(shè)req[0]的優(yōu)先級最高，req[1]其次，req[3]最低，當(dāng)req[2]和req[0]同時為1的時候，根據(jù)優(yōu)先級，req[0]優(yōu)先級高于req[2]，grant = 0001。

第二個周期，因為req[2]在前一個周期并沒有獲得grant，那么它繼續(xù)為1，而這個時候req[0]又來了一個新的request，這個時候就能夠看出round robin和fixed priority的差別了。對于fixed priority， grant依然給0，即0001。但是round robin算法的要求是：因為上一個周期req[0]已經(jīng)被grant了，那么它的優(yōu)先級變?yōu)樽畹偷?，相應(yīng)的，req[1]的優(yōu)先級變?yōu)樽罡?，因為它本來就是第二高的?yōu)先級，那么當(dāng)req[0]優(yōu)先級變?yōu)樽畹土酥笏匀贿f補到最高，那么這個時候產(chǎn)生的許可grant就不能給到req[0]，而是要給到req[2]。

同理，第三個周期，req[2]因為在前一個周期grant過，它的優(yōu)先級變?yōu)?最低，req[3]的優(yōu)先級變?yōu)樽罡?。后面的周期大家可以自己順著分析下來?

換句話說，因為被grant的那一路優(yōu)先級在下一個周期變?yōu)樽畹?，這樣讓其他路request都會依次被grant到，而不會出現(xiàn)其中某一路在其他路有request的情況下連續(xù)被grant的情況，所以round-robin在中文中也被翻譯成“輪詢調(diào)度”。

好，下面我們來講round robin的RTL 實現(xiàn)。老李這次就不講特例了，直接介紹幾種參數(shù)化的寫法。

首先看第一種思路，即優(yōu)先級是變化的，回想一下我們之前講的Fixed Priority Design，我們都假定了從LSB到MSB優(yōu)先級是由高到低排列的。那么我們有沒有辦法先設(shè)計一個fixed priority arbiter，它的優(yōu)先級是一個輸入呢?看下面的RTL

1 module arbiter_base #(parameter NUM_REQ = 4)

2 (

3 input [NUM_REQ-1:0] req,

4 input [NUM_REQ-1:0] base,

5 output [NUM_REQ-1:0] gnt

6 );

7

8 wire[2*NUM_REQ-1:0] double_req = {req,req};

9

10 wire[2*NUM_REQ-1:0] double_gnt = double_req & ~(double_req - base);

11

12 assign gnt = double_gnt[NUM_REQ-1:0] | double_gnt[2*NUM_REQ-1:NUM_REQ];

13 endmodule

在這個模塊中，base是一個onehot的信號，它為1的那一位表示這一位的優(yōu)先級最高，然后其次是它的高位即左邊的位，直到最高位后回到第0位繞回來，優(yōu)先級依次降低，直到為1那一位右邊的這位為最低。咱們以4位為例，如果base = 4'b0100, 那么優(yōu)先級是bit[2] > bit[3] > bit[0] > bit[1]。

這個設(shè)計的思路和老李前一篇仲裁器設(shè)計(一) -- Fixed Priority Arbiter最后那個1行設(shè)計的思路很像，里面double_req & ~(double_req-base)其實就是利用減法的借位去找出base以上第一個為1的那一位，只不過由于base值可能比req值要大，不夠減，所以要擴(kuò)展為{req, req}來去減。當(dāng)base=4‘b0001的時候就是咱們上一篇里面的最后的算法。當(dāng)然base=4'b0001的時候不存在req不夠減的問題，所以不用擴(kuò)展。

那么好了，既然有了可以根據(jù)輸入給定優(yōu)先級的固定優(yōu)先級仲裁器(這句話有點繞，你仔細(xì)琢磨一下)，那么接下來的任務(wù)就簡單了，每次grant之后，我把我的優(yōu)先級調(diào)整一下就可以了唄。而且這個設(shè)計妙就妙在，base要求是一個onehot signal，而且為1的那一位優(yōu)先級最高。我們前面說過，grant一定是onehot，grant之后被grant的那一路優(yōu)先級變?yōu)樽畹?，它的?位優(yōu)先級變?yōu)樽罡?，所以，我只需要一個history_reg，來去記錄之前最后grant的值，然后只需要將grant的值左移一下就變成了下一個周期的base。比如說，假設(shè)我上一個周期grant為4'b0010，那么bit[2]要變?yōu)樽罡邇?yōu)先級，那只需要base是grant的左移即可。RTL代碼如下

module round_robin_arbiter #(parameter NUM_REQ = 4)

(

input clk,

input rstn,

input [NUM_REQ-1:0] req,

output [NUM_REQ-1:0] gnt

);

logic [NUM_REQ-1:0] hist_q, hist_d;

always_ff@(posedge clk) begin

if(!rstn)

hist_q <= {{NUM_REQ-1{1'b0}}, 1'b1};

else

if(|req)

hist_q <= {gnt[NUM_REQ-2:0, gnt[NUM_REQ-1]};

end

arbiter_base #(

.NUM_REQ(NUM_REQ)

) arbiter(

.req (req),

.gnt (gnt),

.base (hist_q)

);

endmodule

我們注意到，和Fixed Priority Arbiter不同，Round robin arbiter不再是純的組合邏輯電路，而是要有時鐘和復(fù)位信號，因為里面必須要有個寄存器來記錄之前grant的狀態(tài)。

上面這個Round Robin Arbiter的設(shè)計，好處就是思路簡單明了，代碼行數(shù)也很短，在你理解了Fixed Priority Arbiter之后，理解這個設(shè)計就很容易。但是這個設(shè)計也有缺點，即在面積和timing上的優(yōu)化不夠好。相比于我們接下來要介紹的設(shè)計，在request位數(shù)大(比如64位)的時候timing和area都要差一些，所以其實老李見并沒有見到公司里采用這個設(shè)計，而更多的時候采用的是下面的設(shè)計。

前面的思路是換優(yōu)先級，而request不變，另一個思路是優(yōu)先級不變，但是我們從request入手：當(dāng)某一路request已經(jīng)grant之后，我們?nèi)藶榈匕堰M(jìn)入fixed priority arbiter的這一路req給屏蔽掉，這樣相當(dāng)于只允許之前沒有g(shù)rant的那些路去參與仲裁，grant一路之后就屏蔽一路，等到剩余的request都依次處理完了再把屏蔽放開，重新來過。這就是利用屏蔽mask的辦法來實現(xiàn)round robin的思路。

這個思路還是會用到前面一講里Fixed Priority Arbiter的寫法，如何來產(chǎn)生屏蔽信號mask呢?回看下面這段RTL

1 module prior_arb #(

2 parameter REQ_WIDTH = 16

3 )(

4 input [REQ_WIDTH-1:0] req,

5 output [REQ_WIDTH-1:0] gnt

6 );

7

8 logic [REQ_WIDTH-1:0] pre_req;

9

10 assign pre_req[0] = 1'b0;

11

12 assign pre_req[REQ_WIDTH-1:1] = req[REQ_WIDTH-2:0] | pre_req[REQ_WIDTH-2:0];

13

14 assign gnt = req & ~pre_req;

15

16 endmodule

里面的pre_req的意義是什么?就是如果第i位的req為第一個1，那么pre_req從i+1位開始每一位都是1，而第0位到第i位都是0。這其實就是我們要找的mask! 只需要把req和上一個周期的pre_req AND起來，那么我們自然就得到了一個新的request，這個request里之前grant的位以及之前的位都被mask掉了，允許通過的是在之前優(yōu)先級更低的那些位，如果那些位上之前有request但是沒有被grant，現(xiàn)在就可以輪到他們了。每次新的grant之后mask里0的位數(shù)會變多，從而mask掉更多位，直到所有的低優(yōu)先級的request都被grant了一次之后，req AND mask的結(jié)果變成全0了，這個時候就說明我們已經(jīng)輪詢完畢，要重新來過了。

硬件實現(xiàn)上我們需要兩個并行的Fixed Priority Arbiter，它們一個的輸入是request AND mask之后的masked_request，另一個就是原本的request，然后我們在它們兩個arbiter的output中選擇一個grant。如下圖所示

當(dāng)masked_request不是全0，即存在沒有被mask掉的request時，我們選擇上面的這一路Mask Grant，否則我們選擇下面這一路Unmasked Grant。

而又因為對于上面這一路來說，當(dāng)masked_request為全0的時候，Mask Grant也是全0，這個時候可以把Mask Grant和Unmask Grant直接按位OR起來就行，所以其實圖上最后顯示的Mux可以用下面簡單的AND門和OR門實現(xiàn)

下面是這個設(shè)計的代碼，依然是參數(shù)化的表達(dá)，可以滿足任意數(shù)目的request。

module round_robin_arbiter #(

parameter N = 16

)(

input clk,

input rst,

input [N-1:0] req,

output[N-1:0] grant

);

logic [N-1:0] req_masked;

logic [N-1:0] mask_higher_pri_reqs;

logic [N-1:0] grant_masked;

logic [N-1:0] unmask_higher_pri_reqs;

logic [N-1:0] grant_unmasked;

logic no_req_masked;

logic [N-1:0] pointer_reg;

// Simple priority arbitration for masked portion

assign req_masked = req & pointer_reg;

assign mask_higher_pri_reqs[N-1:1] = mask_higher_pri_reqs[N-2: 0] | req_masked[N-2:0];

assign mask_higher_pri_reqs[0] = 1'b0;

assign grant_masked[N-1:0] = req_masked[N-1:0] & ~mask_higher_pri_reqs[N-1:0];

// Simple priority arbitration for unmasked portion

assign unmask_higher_pri_reqs[N-1:1] = unmask_higher_pri_reqs[N-2:0] | req[N-2:0];

assign unmask_higher_pri_reqs[0] = 1'b0;

assign grant_unmasked[N-1:0] = req[N-1:0] & ~unmask_higher_pri_reqs[N-1:0];

// Use grant_masked if there is any there, otherwise use grant_unmasked.

assign no_req_masked = ~(|req_masked);

assign grant = ({N{no_req_masked}} & grant_unmasked) | grant_masked;

// Pointer update

always @ (posedge clk) begin

if (rst) begin

pointer_reg <= {N{1'b1}};

end else begin

if (|req_masked) begin // Which arbiter was used?

pointer_reg <= mask_higher_pri_reqs;

end else begin

if (|req) begin // Only update if there's a req

pointer_reg <= unmask_higher_pri_reqs;

end else begin

pointer_reg <= pointer_reg ;

end

end

end

end

endmodule

這里稍微多講解幾句，當(dāng)no_req_masked之后，pointer_reg并不是要更新到1111或是1110，而是要根據(jù)這個時候的request來，比如說這個時候request是0010，那么新的mask就要調(diào)整為1100，重新把bit[0], bit[1]都mask掉。

可以看出，這個設(shè)計利用兩個N位的arbiter并行計算，critical path只比單獨的fixed priority arbiter多了mask這一步和最后的mux這一級，在timing上表現(xiàn)是非常好的。面積上相比于前面一種做法2N的加法器也要少一些。

關(guān)于Round-robin還有其他的思路，比如將request進(jìn)行rotate，從而達(dá)到改換優(yōu)先級的目的，然后再根據(jù)history來rotate 回來。還有比如并行放N個fixed priority arbiter，把所有的priority order都實現(xiàn)了，然后再在N個grant中選擇一個，這些設(shè)計在面積和時序上都各有犧牲，而且參數(shù)化設(shè)計不是很容易寫，老李這里就不細(xì)講了。感興趣的同學(xué)可以點擊原文鏈接，看一篇論文里的詳細(xì)講解，老李關(guān)于方法2的設(shè)計也來自于這篇論文，里面還有不同設(shè)計的面積時序比較。