隨機仲裁器的算法實現(xiàn)

01仲裁機制

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

仲裁器只能讓一個模塊得到許可，因為資源（總線）同一時刻只能由一個模塊占用。

常見的仲裁機制有以下三種:

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

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

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

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

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

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

偽隨機： 通過偽隨機算法隨機賦予請求優(yōu)先級。

02算法實現(xiàn)

1、Fixed Arbiter

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

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

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

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

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

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

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

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

gnt_o = req_i & ~(req_i-1);

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

2、Round Robin Arbiter

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

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

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

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

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

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

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