仲裁器設(shè)計(jì)（一） -- Fixed Priority Arbiter

時(shí)間：2024-05-22 10:10:01

關(guān)鍵字：仲裁器設(shè)計(jì) Arbiter

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]仲裁器Arbiter是數(shù)字設(shè)計(jì)中非常常見的模塊，應(yīng)用也非常廣泛。定義就是當(dāng)有兩個(gè)或兩個(gè)以上的模塊需要占用同一個(gè)資源的時(shí)候，我們需要由仲裁器arbiter來(lái)決定哪一個(gè)模塊來(lái)占有這個(gè)資源。類比一下，老師上課問了一個(gè)問題，底下同學(xué)不止一個(gè)人舉手了，老師這個(gè)時(shí)候就要扮演仲裁者的角色，來(lái)指定由哪位同學(xué)站起來(lái)回答問題。一般來(lái)說，提出占有資源的模塊要產(chǎn)生一個(gè)請(qǐng)求(request)，類比于學(xué)生要舉手表示自己要回答問題。所有的請(qǐng)求送給仲裁器之后，仲裁器要返回一個(gè)許可(grant)，也就是老師要選擇一名同學(xué)，通過點(diǎn)這個(gè)同學(xué)的名字的方式，告訴這個(gè)同學(xué)可以站起來(lái)回答問題。

仲裁器Arbiter是數(shù)字設(shè)計(jì)中非常常見的模塊，應(yīng)用也非常廣泛。定義就是當(dāng)有兩個(gè)或兩個(gè)以上的模塊需要占用同一個(gè)資源的時(shí)候，我們需要由仲裁器arbiter來(lái)決定哪一個(gè)模塊來(lái)占有這個(gè)資源。類比一下，老師上課問了一個(gè)問題，底下同學(xué)不止一個(gè)人舉手了，老師這個(gè)時(shí)候就要扮演仲裁者的角色，來(lái)指定由哪位同學(xué)站起來(lái)回答問題。一般來(lái)說，提出占有資源的模塊要產(chǎn)生一個(gè)請(qǐng)求(request)，類比于學(xué)生要舉手表示自己要回答問題。所有的請(qǐng)求送給仲裁器之后，仲裁器要返回一個(gè)許可(grant)，也就是老師要選擇一名同學(xué)，通過點(diǎn)這個(gè)同學(xué)的名字的方式，告訴這個(gè)同學(xué)可以站起來(lái)回答問題。

仲裁器很重要的一點(diǎn)是只能讓一個(gè)模塊得到許可，因?yàn)檫@個(gè)資源某一時(shí)刻只能由一個(gè)模塊占用。類比一下，老師不能讓兩個(gè)同學(xué)同時(shí)站起來(lái)回答，因?yàn)閮蓚€(gè)人同時(shí)站起來(lái)說話就誰(shuí)也聽不清了。在數(shù)字電路中，總線仲裁是一個(gè)常見的例子，比如多個(gè)master要占用總線來(lái)去寫數(shù)據(jù)，那么需要仲裁器來(lái)許可哪個(gè)master來(lái)占用總線。

那么一個(gè)顯而易見的問題就是，仲裁器應(yīng)該基于什么原則來(lái)分配許可呢?這篇我們先討論最常見的方式：固定優(yōu)先級(jí) -- fixed priority。

固定優(yōu)先級(jí)，顧名思義，就是說每個(gè)模塊的優(yōu)先級(jí)是固定的，是提前分配好的，如果有兩個(gè)模塊同時(shí)產(chǎn)生request，那么優(yōu)先級(jí)高的模塊可以獲得grant。還是類比老師叫同學(xué)起來(lái)回答問題。比如，在老師心中，老師可以這樣安排一個(gè)優(yōu)先級(jí)：學(xué)號(hào)。學(xué)號(hào)是1的同學(xué)回答優(yōu)先級(jí)最高，2號(hào)其次，一直到最后一位同學(xué)N，當(dāng)大家舉手的時(shí)候，總是叫學(xué)號(hào)最小的那個(gè)。比如說如果1號(hào)同學(xué)舉手了，那就叫1號(hào);如果1號(hào)，2號(hào)都沒有舉手，3號(hào)舉手了，那就叫3號(hào)，很好理解吧?當(dāng)然，如果N個(gè)同學(xué)里只有1位舉手，那不管這個(gè)同學(xué)是幾號(hào)，都讓他回答問題。如果大家都不舉手，那么老師就不叫了(現(xiàn)實(shí)中可能不是這樣，有的老師可能會(huì)點(diǎn)名，但是咱們就不討論了，大家理解就行)。

你可能會(huì)說，那對(duì)學(xué)號(hào)大的同學(xué)不公平啊，每次都搶不過學(xué)號(hào)小的同學(xué)。你說的沒錯(cuò)，仲裁器的許可算法是有很多種的，我們說的固定優(yōu)先級(jí)只是一種最簡(jiǎn)單的許可算法，還有其他的算法會(huì)考慮到公平性，我們之后再討論。

回到仲裁器本身，如果我們要設(shè)計(jì)一個(gè)fixed priority arbiter，輸入是一個(gè)multibit request，每一個(gè)bit代表一個(gè)模塊的request，輸出一個(gè)multibit grant，每個(gè)bit代表給對(duì)應(yīng)的模塊的grant信號(hào)。我們可以把優(yōu)先級(jí)這樣安排，最低位優(yōu)先級(jí)最高，最高位優(yōu)先級(jí)最低。

我們先以3個(gè)模塊產(chǎn)生request為例，大家一般在面試的時(shí)候都會(huì)碰到給定模塊數(shù)目，比如3，讓你設(shè)計(jì)。咱們就直接上code來(lái)表示一種寫法

1 module fixed_prio_arb

2 (

3 input [2:0] req,

5 output logic [2:0] grant

6 );

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

17 endmodule: fixed_prio_arb

這里的技巧是利用verilog中的case語(yǔ)句，可以比用if else簡(jiǎn)潔，而且利用了case里的按順序evaluate語(yǔ)法規(guī)則來(lái)實(shí)現(xiàn)了優(yōu)先級(jí)。這里多說一句給verilog的初學(xué)者，盡管verilog和C看起來(lái)很像，很多關(guān)鍵字都是一樣的，比如case，但是verilog的case和C的case是不一樣的，verilog的case自帶"break"，即當(dāng)一個(gè)condition滿足之后，就只會(huì)執(zhí)行這一條冒號(hào)之后的，只有input 發(fā)生變化之后才會(huì)再次evaluate，因?yàn)檫@是描述硬件電路。而C語(yǔ)言的case里如果一條滿足之后會(huì)按照順序繼續(xù)往下執(zhí)行，如果下一個(gè)條件依然滿足，那么就會(huì)跳到下一個(gè)條件里，所以C的case語(yǔ)句我們通常要加break。

好，如果這一篇老李到此為止那就太水了，下面才是真正的干貨內(nèi)容。面試的時(shí)候如果你能夠往下發(fā)揮才能讓面試官眼前一亮。

還是那個(gè)老李一直強(qiáng)調(diào)的，如何設(shè)計(jì)一個(gè)參數(shù)化的模塊。對(duì)于上面的仲裁器來(lái)說，我們希望可以參數(shù)化產(chǎn)生請(qǐng)求的個(gè)數(shù)，即設(shè)計(jì)下面的模塊

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ǎng)合產(chǎn)生request的模塊的個(gè)數(shù)來(lái)例化同一個(gè)仲裁器，只需要改變參數(shù)即可。很明顯，上面利用case的寫法不能scalable，我們需要用更加巧妙的辦法。

首先可以想到的辦法是利用for循環(huán)，思路其實(shí)非常直接，從低位到高位依次去判斷，借助一個(gè)pre_req來(lái)記錄低位是否已經(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 );

8 logic [REQ_WIDTH-1:0] pre_req;

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

19 endmodule

有沒有更簡(jiǎn)潔的辦法呢?下面老李介紹兩種實(shí)現(xiàn)方式，code非常簡(jiǎn)潔，先來(lái)上面的設(shè)計(jì)的變體，但是不用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 );

8 logic [REQ_WIDTH-1:0] pre_req;

10 assign pre_req[0] = 1'b0;

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

14 assign gnt = req & ~pre_req;

16 endmodule

下面的這種實(shí)現(xiàn)方式就更夸張了，就一行實(shí)現(xiàn)，讀到這里的讀者可以說是賺到了，因?yàn)槔侠钏堰^，至少在各種介紹仲裁器的公眾號(hào)文章里老李從來(lái)沒有見到過這種方法。老李第一次學(xué)到的時(shí)候也是驚為天人，但是它背后的思想?yún)s非常樸素，簡(jiǎn)直不超過小學(xué)一年級(jí)的知識(shí)。

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 );

8 assign gnt = req & (~(req-1));

9 endmodule

本質(zhì)上，我們要做的是找req這個(gè)信號(hào)里從低到高第一個(gè)出現(xiàn)的1，那么我們給req減去1會(huì)得到什么?假設(shè)req的第i位是1，第0到第i-1位都是0，那么減去1之后我們知道低位不夠減，得要向高位借位，直到哪一位可以借到呢?就是第一次出現(xiàn)1的位，即從第i位借位，第0到i-1位都變成了1，而第i位變?yōu)榱?，更高位不變。然后我們?cè)俳o減1之后的結(jié)果取反，然后把結(jié)果再和req本身按位與，可以得出，只有第i位在取反之后又變成了1，而其余位都是和req本身相反的，按位與之后是0，這樣就提取出來(lái)了第一個(gè)為1的那一位，也就是我們需要的grant。再考慮一下特殊情況req全0，很明顯，按位與之后gnt依然都是全0，沒有任何問題。

聰明的同學(xué)可能已經(jīng)聯(lián)想到，減1再取反，這不是計(jì)算2的補(bǔ)碼的算法嗎?只不過我們書本上學(xué)到的給一個(gè)數(shù)求2的補(bǔ)碼的方法是取反再加1，這里倒過來(lái)，減1再取反，本質(zhì)上是一樣的。這其實(shí)是2的補(bǔ)碼的一個(gè)特性，即一個(gè)數(shù)和它的補(bǔ)碼相與，得到的結(jié)果是一個(gè)獨(dú)熱碼，獨(dú)熱碼為1的那一位是這個(gè)數(shù)最低的1。所以這個(gè)仲裁器的設(shè)計(jì)方法用一句話概括：request和它的2的補(bǔ)碼按位與。如果同學(xué)們?cè)诿嬖嚨臅r(shí)候被問到設(shè)計(jì)優(yōu)先級(jí)固定仲裁器，只要記住這句話，那么你就可以驚艷面試官。