仲裁器設(shè)計（一） -- Fixed Priority Arbiter
仲裁器Arbiter是數(shù)字設(shè)計中非常常見的模塊，應(yīng)用也非常廣泛。定義就是當有兩個或兩個以上的模塊需要占用同一個資源的時候，我們需要由仲裁器arbiter來決定哪一個模塊來占有這個資源。類比一下，老師上課問了一個問題，底下同學不止一個人舉手了，老師這個時候就要扮演仲裁者的角色，來指定由哪位同學站起來回答問題。一般來說，提出占有資源的模塊要產(chǎn)生一個請求(request)，類比于學生要舉手表示自己要回答問題。所有的請求送給仲裁器之后，仲裁器要返回一個許可(grant)，也就是老師要選擇一名同學，通過點這個同學的名字的方式，告訴這個同學可以站起來回答問題。
仲裁器很重要的一點是只能讓一個模塊得到許可，因為這個資源某一時刻只能由一個模塊占用。類比一下，老師不能讓兩個同學同時站起來回答，因為兩個人同時站起來說話就誰也聽不清了。在數(shù)字電路中，總線仲裁是一個常見的例子，比如多個master要占用總線來去寫數(shù)據(jù)，那么需要仲裁器來許可哪個master來占用總線。
那么一個顯而易見的問題就是，仲裁器應(yīng)該基于什么原則來分配許可呢?這篇我們先討論最常見的方式：固定優(yōu)先級 -- fixed priority。
固定優(yōu)先級，顧名思義，就是說每個模塊的優(yōu)先級是固定的，是提前分配好的，如果有兩個模塊同時產(chǎn)生request，那么優(yōu)先級高的模塊可以獲得grant。還是類比老師叫同學起來回答問題。比如，在老師心中，老師可以這樣安排一個優(yōu)先級：學號。學號是1的同學回答優(yōu)先級最高，2號其次，一直到最后一位同學N，當大家舉手的時候，總是叫學號最小的那個。比如說如果1號同學舉手了，那就叫1號;如果1號，2號都沒有舉手，3號舉手了，那就叫3號，很好理解吧?當然，如果N個同學里只有1位舉手，那不管這個同學是幾號，都讓他回答問題。如果大家都不舉手，那么老師就不叫了(現(xiàn)實中可能不是這樣，有的老師可能會點名，但是咱們就不討論了，大家理解就行)。
你可能會說，那對學號大的同學不公平啊，每次都搶不過學號小的同學。你說的沒錯，仲裁器的許可算法是有很多種的，我們說的固定優(yōu)先級只是一種最簡單的許可算法，還有其他的算法會考慮到公平性，我們之后再討論。
回到仲裁器本身，如果我們要設(shè)計一個fixed priority arbiter，輸入是一個multibit request，每一個bit代表一個模塊的request， 輸出一個multibit grant，每個bit代表給對應(yīng)的模塊的grant信號。我們可以把優(yōu)先級這樣安排，最低位優(yōu)先級最高，最高位優(yōu)先級最低。
我們先以3個模塊產(chǎn)生request為例，大家一般在面試的時候都會碰到給定模塊數(shù)目，比如3，讓你設(shè)計。咱們就直接上code來表示一種寫法
1 module fixed_prio_arb
2 (
3 input [2:0] req,
4
5 output logic [2:0] grant
6 );
7
8 always_comb begin
9 case (1'b1)
10 req[0]: grant = 3'b001;
11 req[1]: grant = 3'b010;
12 req[2]: grant = 3'b100;
13 default:grant = 3'b000;
14 endcase
15 end
16
17 endmodule: fixed_prio_arb
這里的技巧是利用verilog中的case語句，可以比用if else簡潔，而且利用了case里的按順序evaluate語法規(guī)則來實現(xiàn)了優(yōu)先級。這里多說一句給verilog的初學者，盡管verilog和C看起來很像，很多關(guān)鍵字都是一樣的，比如case，但是verilog的case和C的case是不一樣的，verilog的case自帶"break"，即當一個condition滿足之后，就只會執(zhí)行這一條冒號之后的，只有input 發(fā)生變化之后才會再次evaluate，因為這是描述硬件電路。而C語言的case里如果一條滿足之后會按照順序繼續(xù)往下執(zhí)行，如果下一個條件依然滿足，那么就會跳到下一個條件里，所以C的case語句我們通常要加break。
好，如果這一篇老李到此為止那就太水了，下面才是真正的干貨內(nèi)容。面試的時候如果你能夠往下發(fā)揮才能讓面試官眼前一亮。
還是那個老李一直強調(diào)的，如何設(shè)計一個參數(shù)化的模塊。對于上面的仲裁器來說，我們希望可以參數(shù)化產(chǎn)生請求的個數(shù)，即設(shè)計下面的模塊
1 module priority_arbiter #(
2 parameter REQ_WIDTH = 16
3 )(
4 input [REQ_WIDTH-1:0] req,
5 output [REQ_WIDTH-1:0] gnt
6 );
這樣我們可以根據(jù)不同場合產(chǎn)生request的模塊的個數(shù)來例化同一個仲裁器，只需要改變參數(shù)即可。很明顯，上面利用case的寫法不能scalable，我們需要用更加巧妙的辦法。
首先可以想到的辦法是利用for循環(huán)，思路其實非常直接，從低位到高位依次去判斷，借助一個pre_req來記錄低位是否已經(jīng)有了request， 如果第i位有了request，那么第i+1位一直到最高位的pre_req都是1。
1 module prior_arb #(
2 parameter REQ_WIDTH = 16
3 )(
4 input logic [REQ_WIDTH-1:0] req,
5 output logic [REQ_WIDTH-1:0] grant
6 );
7
8 logic [REQ_WIDTH-1:0] pre_req;
9
10 always_comb begin
11 pre_req[0] = req[0];
12 grant[0] = req[0];
13 for (int i = 1; i < REQ_WIDTH; i = i + 1) begin
14 grant[i] = req[i] & !pre_req[i-1]; // current req & no higher priority request
15 pre_req[i] = req[i] | pre_req[i-1]; // or all higher priority requests
16 end
17 end
18
19 endmodule
有沒有更簡潔的辦法呢?下面老李介紹兩種實現(xiàn)方式，code非常簡潔，先來上面的設(shè)計的變體，但是不用for循環(huán)，本質(zhì)上是一樣的，只有3行code。
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 preq_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
下面的這種實現(xiàn)方式就更夸張了，就一行實現(xiàn)，讀到這里的讀者可以說是賺到了，因為老李搜過，至少在各種介紹仲裁器的公眾號文章里老李從來沒有見到過這種方法。老李第一次學到的時候也是驚為天人，但是它背后的思想?yún)s非常樸素，簡直不超過小學一年級的知識。
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 assign gnt = req & (~(req-1));
9 endmodule
本質(zhì)上，我們要做的是找req這個信號里從低到高第一個出現(xiàn)的1，那么我們給req減去1會得到什么?假設(shè)req的第i位是1，第0到第i-1位都是0，那么減去1之后我們知道低位不夠減，得要向高位借位，直到哪一位可以借到呢?就是第一次出現(xiàn)1的位，即從第i位借位，第0到i-1位都變成了1，而第i位變?yōu)榱?，更高位不變。然后我們再給減1之后的結(jié)果取反，然后把結(jié)果再和req本身按位與，可以得出，只有第i位在取反之后又變成了1，而其余位都是和req本身相反的，按位與之后是0，這樣就提取出來了第一個為1的那一位，也就是我們需要的grant。再考慮一下特殊情況req全0，很明顯，按位與之后gnt依然都是全0，沒有任何問題。
聰明的同學可能已經(jīng)聯(lián)想到，減1再取反，這不是計算2的補碼的算法嗎?只不過我們書本上學到的給一個數(shù)求2的補碼的方法是取反再加1，這里倒過來，減1再取反，本質(zhì)上是一樣的。這其實是2的補碼的一個特性，即一個數(shù)和它的補碼相與，得到的結(jié)果是一個獨熱碼，獨熱碼為1的那一位是這個數(shù)最低的1。所以這個仲裁器的設(shè)計方法用一句話概括：request和它的2的補碼按位與。如果同學們在面試的時候被問到設(shè)計優(yōu)先級固定仲裁器，只要記住這句話，那么你就可以驚艷面試官。
下載文檔
