仲裁器設(shè)計(jì)（二）-- Round Robin Arbiter

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

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

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

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

Cycle 00101321000010001

Cycle 10101210301000001

Cycle 20011032100010001

Cycle 30010210300100010

Cycle 41000103210001000

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

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

同理，第三個(gè)周期，req[2]因?yàn)樵谇耙粋€(gè)周期grant過，它的優(yōu)先級(jí)變?yōu)?最低，req[3]的優(yōu)先級(jí)變?yōu)樽罡?。后面的周期大家可以自己順著分析下來?

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

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

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

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

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

那么好了，既然有了可以根據(jù)輸入給定優(yōu)先級(jí)的固定優(yōu)先級(jí)仲裁器(這句話有點(diǎn)繞，你仔細(xì)琢磨一下)，那么接下來的任務(wù)就簡(jiǎn)單了，每次grant之后，我把我的優(yōu)先級(jí)調(diào)整一下就可以了唄。而且這個(gè)設(shè)計(jì)妙就妙在，base要求是一個(gè)onehot signal，而且為1的那一位優(yōu)先級(jí)最高。我們前面說過，grant一定是onehot，grant之后被grant的那一路優(yōu)先級(jí)變?yōu)樽畹?，它的?位優(yōu)先級(jí)變?yōu)樽罡?，所以，我只需要一個(gè)history_reg，來去記錄之前最后grant的值，然后只需要將grant的值左移一下就變成了下一個(gè)周期的base。比如說，假設(shè)我上一個(gè)周期grant為4'b0010，那么bit[2]要變?yōu)樽罡邇?yōu)先級(jí)，那只需要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不再是純的組合邏輯電路，而是要有時(shí)鐘和復(fù)位信號(hào)，因?yàn)槔锩姹仨氁袀€(gè)寄存器來記錄之前grant的狀態(tài)。

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

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

這個(gè)思路還是會(huì)用到前面一講里Fixed Priority Arbiter的寫法，如何來產(chǎn)生屏蔽信號(hào)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為第一個(gè)1，那么pre_req從i+1位開始每一位都是1，而第0位到第i位都是0。這其實(shí)就是我們要找的mask! 只需要把req和上一個(gè)周期的pre_req AND起來，那么我們自然就得到了一個(gè)新的request，這個(gè)request里之前grant的位以及之前的位都被mask掉了，允許通過的是在之前優(yōu)先級(jí)更低的那些位，如果那些位上之前有request但是沒有被grant，現(xiàn)在就可以輪到他們了。每次新的grant之后mask里0的位數(shù)會(huì)變多，從而mask掉更多位，直到所有的低優(yōu)先級(jí)的request都被grant了一次之后，req AND mask的結(jié)果變成全0了，這個(gè)時(shí)候就說明我們已經(jīng)輪詢完畢，要重新來過了。

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

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

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

下面是這個(gè)設(shè)計(jì)的代碼，依然是參數(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ù)這個(gè)時(shí)候的request來，比如說這個(gè)時(shí)候request是0010，那么新的mask就要調(diào)整為1100，重新把bit[0], bit[1]都mask掉。

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

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