01仲裁機(jī)制

提出占用資源的模塊需要產(chǎn)生一個(gè)訪問(wèn)請(qǐng)求request，所有的請(qǐng)求輸入仲裁器之后，仲裁器需要根據(jù)仲裁算法，返回一個(gè)grant來(lái)響應(yīng)某一模塊的請(qǐng)求。

仲裁器只能讓一個(gè)模塊得到許可，因?yàn)橘Y源（總線）同一時(shí)刻只能由一個(gè)模塊占用。

常見(jiàn)的仲裁機(jī)制有以下三種:

• 固定優(yōu)先級(jí)仲裁器Fixed Priority Arbiter
• 輪詢(xún)仲裁器Round Robin Arbiter
• 偽隨機(jī)仲裁器Pseudo Random Arbiter

固定優(yōu)先級(jí)： 即事先確定好各個(gè)模塊的訪問(wèn)優(yōu)先級(jí)，當(dāng)多個(gè)請(qǐng)求發(fā)起時(shí)，按照優(yōu)先級(jí)從高到低來(lái)給出許可，某些情況下，部分請(qǐng)求的優(yōu)先級(jí)必須高于其它請(qǐng)求（比如車(chē)控系統(tǒng)中的剎車(chē)請(qǐng)求），這時(shí)就要采用固定優(yōu)先級(jí)的仲裁算法；

輪詢(xún)： 當(dāng)某次請(qǐng)求被許可之后，則下一個(gè)優(yōu)先級(jí)的請(qǐng)求會(huì)被置成最高，若下一次需要仲裁的請(qǐng)求中沒(méi)有最高優(yōu)先級(jí)對(duì)應(yīng)的請(qǐng)求，則維持優(yōu)先級(jí)順序（按照基礎(chǔ)優(yōu)先級(jí)順序執(zhí)行本輪仲裁），直到最高優(yōu)先級(jí)請(qǐng)求被響應(yīng)。

例如：初始優(yōu)先級(jí)從高到低1-2-3，現(xiàn)在來(lái)了一波請(qǐng)求序列123-13-23-123-13，那么每輪分別是哪個(gè)請(qǐng)求被許可？

答：每輪最高優(yōu)先級(jí) 1-2-2-3-1，被響應(yīng)許可的順序 1-1-2-3-1

*也有一種輪詢(xún)機(jī)制是優(yōu)先級(jí)反轉(zhuǎn)的，一個(gè)請(qǐng)求被響應(yīng)許可之后，它的優(yōu)先級(jí)就降到最低。

偽隨機(jī)： 通過(guò)偽隨機(jī)算法隨機(jī)賦予請(qǐng)求優(yōu)先級(jí)。

02算法實(shí)現(xiàn)

1、Fixed Arbiter

設(shè) req_i [3:0], 由于是固定優(yōu)先級(jí)，可以事先約定：低位優(yōu)先級(jí)高，高位優(yōu)先級(jí)低

(注意仲裁器的輸入端口已經(jīng)確定好優(yōu)先級(jí)，因此外部請(qǐng)求信號(hào)連接時(shí)應(yīng)根據(jù)仲裁器規(guī)定的優(yōu)先級(jí)順序按需求連接)

在這個(gè)前提下，仲裁的本質(zhì)其實(shí)就是從低位到高位尋找第一個(gè)“1”

那么有沒(méi)有什么邏輯操作可以快速定位一個(gè)序列中從低到高的第一個(gè)“1”呢？

顯然，減1操作就符合這個(gè)需求。在二進(jìn)制的減1操作中，低位如果是0，就會(huì)向前借位，結(jié)果是1，直到借位的那一位是1，結(jié)果才得0，因此只需要根據(jù)結(jié)果從低到高的第一個(gè)0在哪一位就能確定哪一位該被許可響應(yīng)。

假設(shè)這次請(qǐng)求req_i = 4'b1010,即第二和第四個(gè)設(shè)備發(fā)起了請(qǐng)求，那么req_i-1 = 4’b1001，可以從低到高的第一個(gè)0位于第二位，也就是req_i[1]對(duì)應(yīng)的請(qǐng)求可以被響應(yīng)。

那么如何將這個(gè)算法用簡(jiǎn)單的邏輯實(shí)現(xiàn)呢，用序列檢測(cè)的方法去遍歷req_i-1的結(jié)果顯然過(guò)于復(fù)雜且耗時(shí)，會(huì)大大拖累性能。最好能用一個(gè)簡(jiǎn)單的組合邏輯就把這個(gè)0所在的位找出來(lái)。

可以觀察到，對(duì)req_i-1的結(jié)果按位取反后，得到~（req_i-1）= 4‘b0110，與req_i只有一位相同，且那一位就是被響應(yīng)許可的位。于是gnt [3:0]的邏輯就呼之欲出了：

gnt_o = req_i & ~(req_i-1);

其實(shí)也很好理解，減1操作，相當(dāng)于對(duì)參與運(yùn)算的低兩位10進(jìn)行了取反，對(duì)于被減數(shù)來(lái)說(shuō)，前兩位10其實(shí)并沒(méi)有變化，直接落到結(jié)果對(duì)應(yīng)的位上，所以對(duì)結(jié)果進(jìn)行取反得到0110，再和被減數(shù)本身按位與，得到的結(jié)果是0010，直接篩選出了被借位的那個(gè)“1”

2、Round Robin Arbiter

有了固定優(yōu)先級(jí)仲裁器的珠玉在前，輪詢(xún)仲裁器的算法自然就躍然紙上。既然核心思想就是通過(guò)減1操作來(lái)找出需要被響應(yīng)的請(qǐng)求，那么已經(jīng)響應(yīng)過(guò)的請(qǐng)求直接讓它不參與減1計(jì)算即可。被減數(shù)是外部輸入的req_i，是不能動(dòng)的，但是減數(shù)是可以操作的，假如req_i[0]的請(qǐng)求剛被響應(yīng)過(guò)，那么只需要讓減數(shù)的1左移一位得到0010，就相當(dāng)于讓最低位不參與計(jì)算，那么按照輪詢(xún)規(guī)則，下一個(gè)被響應(yīng)的請(qǐng)求就是req_i[1]

但凡事皆有例外，固定優(yōu)先級(jí)的減1操作可以保證一定能檢索到優(yōu)先級(jí)最高的那個(gè)請(qǐng)求（只要req_i不是全0），但是輪詢(xún)算法因?yàn)闇p數(shù)的移位會(huì)把低位排除計(jì)算，可能出現(xiàn)沒(méi)被排除計(jì)算的請(qǐng)求位沒(méi)有1，而被排除的請(qǐng)求位有1的情況，如下圖所示，此時(shí)根據(jù)我們的算法得到的結(jié)果是0000，低兩位的設(shè)備發(fā)起了請(qǐng)求，但是仲裁器卻沒(méi)有輸出，出現(xiàn)了功能錯(cuò)誤。

這是由于我們沒(méi)有將被排除計(jì)算的低位請(qǐng)求加入循環(huán)移位的仲裁機(jī)制中，如果高位均沒(méi)有發(fā)起請(qǐng)求，仲裁器還是需要按照約定的優(yōu)先級(jí)順序給低位的請(qǐng)求發(fā)起響應(yīng)。

根據(jù)這個(gè)思路，自然就能想到：當(dāng)高位沒(méi)有發(fā)起請(qǐng)求，而低位有請(qǐng)求時(shí)，按照固定優(yōu)先級(jí)順序算法再計(jì)算一次。但是問(wèn)題又來(lái)了，引入新的邏輯來(lái)判斷gnt_o的輸出以及再進(jìn)行一次仲裁又會(huì)拖慢響應(yīng)速度，最好有個(gè)一步到位的算法，能同時(shí)解決兩種情況下的輪詢(xún)仲裁。

回歸到優(yōu)先級(jí)算法的本質(zhì)，上圖中 gnt_o輸出全0的原因是向上借位溢出，向上借位的本質(zhì)又是高幾位進(jìn)行減1操作，那么讓req_i變成我們需要借位的那個(gè)“高幾位”不就行了嗎？

如圖，將req_i和gnt_o進(jìn)行double拓寬，這樣就能兼顧高位有無(wú)請(qǐng)求兩種情況了。最后一步，就是將double過(guò)的gnt_o再變回原來(lái)的位寬。根據(jù)算法，double_gnt_o要么高四位有效，要么低四位有效，而且是獨(dú)熱的（One-hot），因此只需要將前四位與后四位進(jìn)行按位或操作就可以得到正確的gnt_o

assign double_reqs = {2{reqs_i}};
assign double_gnts = ~(double_reqs - priority_flag) & double_reqs;
assign gnts_o = double_gnts[2*REQ_NUM:REQ_NUM] | double_gnts[REQ_NUM-1:0];

3、Pseudo random Arbiter

隨機(jī)仲裁器其實(shí)就很好實(shí)現(xiàn)了，每次有請(qǐng)求到來(lái)時(shí)，讓減數(shù)中獨(dú)熱的那一位出現(xiàn)在隨機(jī)的位置上，就實(shí)現(xiàn)了優(yōu)先級(jí)的隨機(jī)生成。本文不再贅述。