多優(yōu)先級(jí)通用路由仲裁器的設(shè)計(jì)實(shí)現(xiàn)

周剛?cè)A，鄒德財(cái)，盧曉春

1(中國科學(xué)院國家授時(shí)中心，西安 710600)

2(中國科學(xué)院精密導(dǎo)航定位與定時(shí)技術(shù)重點(diǎn)實(shí)驗(yàn)室，西安 710600)

3(中國科學(xué)院大學(xué)，北京 100049)

4(中國科學(xué)院大學(xué) 天文與空間科學(xué)學(xué)院，北京 101048)

E-mail：18829269702@163.com

1 引 言

伴隨著芯片設(shè)計(jì)越來越復(fù)雜和以多核為核心的片上網(wǎng)絡(luò)(Network on Chip,NOC)系統(tǒng)優(yōu)點(diǎn)的不斷凸顯[1]，研究者們對(duì)在片上網(wǎng)絡(luò)上實(shí)現(xiàn)路由功能也越來越關(guān)注，而仲裁器作為路由功能實(shí)現(xiàn)中的重要模塊，為路由器優(yōu)化分配路由資源，其時(shí)延、功耗等特性對(duì)路由器的服務(wù)質(zhì)量有著重要的影響.文獻(xiàn)[2，3]結(jié)合動(dòng)態(tài)優(yōu)先級(jí)算法，根據(jù)從設(shè)備被主設(shè)備訪問不同的任務(wù)情況，建立了動(dòng)態(tài)分組轉(zhuǎn)發(fā)的模型,更好地處理數(shù)據(jù)傳輸問題.文獻(xiàn)[4-6]設(shè)計(jì)了不同類型的輪循仲裁器，文獻(xiàn)[4]提出能提供更低延遲的乒乓仲裁器，文獻(xiàn)[5]提出了可用于n2n循環(huán)仲裁的快速并行邏輯電路，文獻(xiàn)[6]則設(shè)計(jì)實(shí)現(xiàn)了可用于高性能NOC里的并行偽循環(huán)仲裁器.隨著芯片的集成度越來越高，片上網(wǎng)絡(luò)內(nèi)可容納的主機(jī)和模塊也越來越多，為快速高效地仲裁請(qǐng)求信號(hào)來分配總線等共享資源，提高數(shù)據(jù)通信的效率，并行仲裁處理路由請(qǐng)求成為如今提高路由服務(wù)質(zhì)量的重要手段之一，如何設(shè)計(jì)一個(gè)性能優(yōu)良的并行仲裁器是提高路由網(wǎng)絡(luò)效率必須解決的重要問題.

本文通過對(duì)目前常用的仲裁方式進(jìn)行學(xué)習(xí)研究，設(shè)計(jì)實(shí)現(xiàn)了兩種融合固定仲裁和輪循仲裁的多優(yōu)先級(jí)通用仲裁器.在采用多優(yōu)先級(jí)仲裁后，仲裁器可并行處理多路由多模塊的仲裁請(qǐng)求，提高了數(shù)據(jù)處理和通信的速度，并且當(dāng)需要仲裁的路由請(qǐng)求總數(shù)相同時(shí)：無論是在芯片資源占用還是最大工作頻率和最大輸出時(shí)延上，多優(yōu)先級(jí)仲裁器的指標(biāo)都要優(yōu)于單優(yōu)先級(jí)仲裁器的指標(biāo).

2 仲裁機(jī)制

目前常用的仲裁機(jī)制為：固定優(yōu)先級(jí)(Fixed-Priority)仲裁器、輪循(Round-Robin)優(yōu)先級(jí)仲裁器、基于權(quán)重的優(yōu)先級(jí)仲裁器 、彩票仲裁器(Lottery arbiter)等[7,8]，本文主要對(duì)FP仲裁和RR仲裁方式進(jìn)行了學(xué)習(xí)研究.

Round-Robin和Fixed-Priority仲裁器的仲裁機(jī)理可用圖1和圖2簡要表示.

圖1 FP仲裁器仲裁機(jī)理

將路由請(qǐng)求信號(hào)輸入仲裁基本塊中進(jìn)行仲裁，仲裁優(yōu)先級(jí)從上到下依次降低.高優(yōu)先級(jí)仲裁塊的輸出信號(hào)Ci作為控制信號(hào)控制其下一級(jí)仲裁模塊的仲裁輸出結(jié)果，同時(shí)與～req[i]相與后得到Ci+1作為下下一級(jí)的控制信號(hào)，如此，高優(yōu)先級(jí)的路由請(qǐng)求信號(hào)對(duì)低優(yōu)先級(jí)具有絕對(duì)的壓制，所以固定優(yōu)先級(jí)仲裁容易出現(xiàn)“餓死”和“撐死”現(xiàn)象[8].

圖2 RR仲裁器仲裁機(jī)理

與固定優(yōu)先級(jí)仲裁器不同的是，輪循優(yōu)先級(jí)仲裁器把前面的仲裁結(jié)果作為反饋信號(hào)與上級(jí)仲裁模塊的輸出信號(hào)Ci相或后成為控制信號(hào)控制此級(jí)的仲裁輸出，此次的仲裁結(jié)果g[i]輸入到update priority模塊，update priority模塊根據(jù)此次的仲裁結(jié)果調(diào)整下次各請(qǐng)求信號(hào)的仲裁優(yōu)先級(jí)，循環(huán)往復(fù)，達(dá)到相對(duì)公平的仲裁請(qǐng)求結(jié)果.

為應(yīng)對(duì)實(shí)際路由請(qǐng)求中需要不同仲裁方式的情況，在兩種通用仲裁器中融合固定優(yōu)先級(jí)仲和輪循優(yōu)先級(jí)兩種仲裁方式.當(dāng)需要對(duì)某路由請(qǐng)求進(jìn)行最優(yōu)先仲裁或者路由請(qǐng)求信號(hào)數(shù)較少且無沖突時(shí)，為減少響應(yīng)時(shí)間，提高數(shù)據(jù)處理速度時(shí)，采用FP仲裁；進(jìn)行沖突路由請(qǐng)求仲裁時(shí)則采用RR仲裁，保證信息傳遞的有效性，避免餓死現(xiàn)象.

3 多優(yōu)先級(jí)仲裁器

3.1 多優(yōu)先級(jí)matrix仲裁器

3.1.1 多優(yōu)先級(jí)matrix仲裁器原理

常見matrix仲裁器的原理是將n位輸入請(qǐng)求req生成n*n的優(yōu)先級(jí)矩陣A[7]，Ai,j的值即req[i]與req[j]的優(yōu)先級(jí)關(guān)系，矩陣A的轉(zhuǎn)置對(duì)應(yīng)位值相同，對(duì)角線值為1.為應(yīng)對(duì)片上路由網(wǎng)絡(luò)里出現(xiàn)多個(gè)路由中的多個(gè)模塊同時(shí)請(qǐng)求仲裁的情況，在此提出一種多優(yōu)先級(jí)matrix仲裁器的設(shè)計(jì).

圖3中的sel模塊是具有one-hot控制信號(hào)的多路復(fù)用器，reduce模塊具有判斷請(qǐng)求信號(hào)那幾段存在請(qǐng)求信號(hào)的功能，gate模塊根據(jù)輸入的選擇信號(hào)選擇輸出對(duì)應(yīng)部分的仲裁結(jié)果，lod模塊功能是檢測第一個(gè)輸入高位的位置，圖3中間的部分是儲(chǔ)存優(yōu)先級(jí)矩陣的值.對(duì)輸入的路由請(qǐng)求進(jìn)行多優(yōu)先級(jí)仲裁的過程可分為兩部分，一部分對(duì)所有輸入請(qǐng)求分別進(jìn)行優(yōu)先級(jí)仲裁，另一部分對(duì)每個(gè)分組路由的請(qǐng)求信號(hào)進(jìn)行檢測縮減得到選擇信號(hào)sel，sel信號(hào)再對(duì)上一部分得到的優(yōu)先級(jí)仲裁結(jié)果選擇輸出.

圖3 多優(yōu)先級(jí)matrix仲裁器RTL原理圖

3.1.2 matrix仲裁器功能實(shí)現(xiàn)仿真圖

由圖4可知,無論是單優(yōu)先級(jí)還是多優(yōu)先級(jí)，update信號(hào)為0時(shí)執(zhí)行的是FP仲裁器功能，為1時(shí)對(duì)應(yīng)RR仲裁器功能.單優(yōu)先級(jí)matrix仲裁器執(zhí)行的是普通的輪詢仲裁功能，在仲裁一次數(shù)據(jù)請(qǐng)求(請(qǐng)求信號(hào)設(shè)定的是同一路由內(nèi)的多個(gè)模塊請(qǐng)求仲裁)后，對(duì)下一級(jí)的仲裁請(qǐng)求進(jìn)行優(yōu)先級(jí)更新，所以仲裁輸出值不斷循環(huán)變化，而多優(yōu)先級(jí)matrix仲裁器不僅可以對(duì)同一路由的不同模塊的仲裁請(qǐng)求有著優(yōu)先級(jí)仲裁(請(qǐng)求信號(hào)設(shè)定的是多個(gè)路由內(nèi)的多個(gè)模塊請(qǐng)求仲裁)，同時(shí)也可以在不同路由網(wǎng)絡(luò)之間進(jìn)行優(yōu)先級(jí)仲裁，在仿真結(jié)果里可以看見有多個(gè)路由網(wǎng)絡(luò)的仲裁結(jié)果在并行輸出且同一路由請(qǐng)求的仲裁結(jié)果不斷變化.多優(yōu)先級(jí)仲裁器相比單優(yōu)先級(jí)仲裁器的優(yōu)勢在于：多優(yōu)先級(jí)仲裁器可以并行處理多組需要仲裁的請(qǐng)求信號(hào)，單優(yōu)先級(jí)仲裁器同時(shí)只能對(duì)一組請(qǐng)求信號(hào)進(jìn)行仲裁，而且在處理相同數(shù)量的路由請(qǐng)求信號(hào)時(shí)，多優(yōu)先級(jí)仲裁器的關(guān)鍵路徑時(shí)延更低，占用的硬件資源更少.

圖4 單優(yōu)先級(jí)和多優(yōu)先級(jí)matrix仲裁器仿真結(jié)果

3.2 多優(yōu)先級(jí)prefix仲裁器

3.2.1 多優(yōu)先級(jí)prefix仲裁器原理

無論是matrix仲裁器還是其他被廣泛使用的輪循優(yōu)先級(jí)仲裁器，相對(duì)于已經(jīng)成型的片上路由網(wǎng)絡(luò)，其資源仲裁結(jié)果對(duì)于網(wǎng)絡(luò)中的每個(gè)路由單元都是相對(duì)較為公平的，而在實(shí)際的路由應(yīng)用中，設(shè)置某些特定的路由單元在某時(shí)擁有更高的優(yōu)先級(jí)能顯著提高路由服務(wù)質(zhì)量.prefix仲裁器相比較于matrix仲裁器不再是生成一個(gè)n*n的優(yōu)先級(jí)矩陣，而是基于樹狀圖的理念，將輸入請(qǐng)求生成m個(gè)n輸入的向量組，根據(jù)不同的輸入前綴來仲裁決定此時(shí)的各路由請(qǐng)求優(yōu)先級(jí)，并可據(jù)此開始優(yōu)先級(jí)輪詢.

圖5 多優(yōu)先級(jí)prefix仲裁器RTL原理圖

圖5中encode模塊將one-hot碼轉(zhuǎn)換為二進(jìn)制碼.decode模塊則是將二進(jìn)制碼解碼成one-hot碼.prefix_base模塊是prefix仲裁器的核心—是基于前綴樹的循環(huán)仲裁器基本塊，前綴樹網(wǎng)絡(luò)和根據(jù)輸入的前綴得到仲裁結(jié)果在這里實(shí)現(xiàn).sel、reduce、gate和lod模塊與多優(yōu)先級(jí)matrix仲裁器中的模塊功能相同.

3.2.2 prefix仲裁器功能實(shí)現(xiàn)仿真圖

相同的，update的值決定著實(shí)際運(yùn)行中仲裁方式的類型，但prefix仲裁器與matrix仲裁器的不同之處在于prefix仲裁器可以通過外部輸入對(duì)prefix_base模塊中的prio_port端口進(jìn)行掩碼輸入，實(shí)時(shí)的改變片上路由網(wǎng)絡(luò)里的路由單元進(jìn)行仲裁的優(yōu)先級(jí)，不再類似于其他輪循仲裁器對(duì)路由系統(tǒng)內(nèi)的仲裁優(yōu)先級(jí)一直循環(huán)變換保證相對(duì)公平的仲裁結(jié)果，所以prefix仲裁器在某些特定的應(yīng)用情況下可以實(shí)時(shí)地設(shè)置各個(gè)路由請(qǐng)求的優(yōu)先級(jí)，在短時(shí)間內(nèi)迅速處理某些指定的路由請(qǐng)求，提高路由網(wǎng)絡(luò)的路由服務(wù)質(zhì)量.除了解決通信沖突外，效率也是評(píng)價(jià)仲裁器的一個(gè)重要指標(biāo)，從prefix仲裁器的仿真結(jié)果圖可得出與matrix仲裁器相同的結(jié)論，多優(yōu)先級(jí)仲裁器由于可將數(shù)據(jù)信號(hào)并行處理，能在一定程度上提高數(shù)據(jù)通信的效率.

4 仲裁器仿真分析

下面若干表皆為在Xilinx公司的vivado開發(fā)軟件環(huán)境下使用Verilog語言對(duì)仲裁器模塊進(jìn)行綜合實(shí)現(xiàn)(同樣的路由請(qǐng)求數(shù)時(shí))的系統(tǒng)指標(biāo)情況，對(duì)應(yīng)的FPGA開發(fā)板為Xilinx公司virtex-7系列里的VC707開發(fā)板.

圖6 單優(yōu)先級(jí)和多優(yōu)先級(jí)prefix仲裁器仿真結(jié)果

4.1 仲裁器資源占用情況和片內(nèi)功率

本文利用vivado對(duì)四種仲裁器在不同路由請(qǐng)求總數(shù)下分別進(jìn)行綜合映射，得到了在VC707開發(fā)板上實(shí)現(xiàn)仲裁器功能所占用的硬件資源.從圖7可以看出，當(dāng)需要處理的路由請(qǐng)求較少時(shí)，四種仲裁器實(shí)現(xiàn)所占用的資源基本接近，但隨著同時(shí)需要處理的路由請(qǐng)求總數(shù)增加，單優(yōu)先級(jí)的prefix和matrix仲裁器模塊實(shí)現(xiàn)占用的資源比多優(yōu)先級(jí)仲裁器實(shí)現(xiàn)占用的FPGA硬件資源更多，這一點(diǎn)在matrix仲裁器上更為凸顯.在處理45和60個(gè)路由請(qǐng)求時(shí)，單優(yōu)先級(jí)matrix仲裁器占用了3020和5465個(gè)的硬件資源，單優(yōu)先級(jí)prefix仲裁器需要533和849的資源總數(shù)，而多優(yōu)先級(jí)matrix仲裁器和多優(yōu)先級(jí)prefix仲裁器實(shí)現(xiàn)相同的功能只需要300左右的硬件資源.由此可知，在仲裁較多的路由請(qǐng)求時(shí)，采用多優(yōu)先級(jí)仲裁器實(shí)現(xiàn)相同的功能可以節(jié)省有限的硬件資源.

圖7 仲裁器資源(LUT+FF+IO+BUFG)占用

圖8 仲裁器片內(nèi)功率

圖8為在不同請(qǐng)求總數(shù)下對(duì)四種仲裁器進(jìn)行功耗分析得到的開發(fā)板片內(nèi)功率(包括靜態(tài)和動(dòng)態(tài)).同理可知，在路由請(qǐng)求較低時(shí)，單優(yōu)先級(jí)仲裁器和多優(yōu)先級(jí)仲裁器占用的資源接近，所以此時(shí)板卡上運(yùn)行單優(yōu)先級(jí)仲裁器的片內(nèi)功率與板卡上運(yùn)行多優(yōu)先級(jí)的matrix仲裁器的片內(nèi)功率接近，但隨著路由請(qǐng)求的增加，無論是matrix仲裁器還是prefix仲裁器，多優(yōu)先級(jí)仲裁器的片內(nèi)功率都會(huì)遠(yuǎn)低于單優(yōu)先級(jí)仲裁器的片內(nèi)功率.

4.2 仲裁器最大工作頻率和最大輸出時(shí)延

在vivado中對(duì)四種仲裁器在不同路由請(qǐng)求總數(shù)下進(jìn)行綜合映射，得到各種情況下的Timing Report，由時(shí)序報(bào)告分析得到四種仲裁器最大工作頻率的對(duì)比圖.由圖9可知：當(dāng)路由請(qǐng)求數(shù)較少時(shí)，多優(yōu)先級(jí)仲裁器的最大工作頻率稍微高于單優(yōu)先級(jí)仲裁器的最大工作頻率，但隨著路由請(qǐng)求總數(shù)的增加，無論是多優(yōu)先級(jí)matrix仲裁器還是多優(yōu)先級(jí)prefix仲裁器的最大工作頻率都高于相對(duì)應(yīng)的單優(yōu)先級(jí)仲裁器的最大工作頻率.當(dāng)路由請(qǐng)求數(shù)為45個(gè)時(shí)，多優(yōu)先級(jí)matrix仲裁器最大工作頻率比單優(yōu)先級(jí)matrix仲裁器高13%，多優(yōu)先級(jí)prefix仲裁器最大工作頻率比單優(yōu)先級(jí)prefix仲裁器高134%；當(dāng)路由請(qǐng)求數(shù)為60個(gè)時(shí)，多優(yōu)先級(jí)matrix仲裁器最大工作頻率比單優(yōu)先級(jí)matrix仲裁器高19%，多優(yōu)先級(jí)prefix仲裁器最大工作頻率比單優(yōu)先級(jí)prefix仲裁器高145%.

圖9 仲裁器最大工作頻率

圖10 仲裁器最大輸出時(shí)延

圖10為四種不同類型的仲裁器在不同路由請(qǐng)求數(shù)下的最大輸出時(shí)延對(duì)比.從圖10中可知：隨著路由請(qǐng)求數(shù)的增加，無論是matrix還是prefix仲裁器，多優(yōu)先級(jí)的仲裁器的最大輸出時(shí)延與單優(yōu)先級(jí)仲裁器的最大輸出時(shí)延之間的差值越來越大.計(jì)算6種路由請(qǐng)求數(shù)下四種仲裁器的平均最大輸出時(shí)延可得：多優(yōu)先級(jí)matrix仲裁器比單優(yōu)先級(jí)matrix仲裁器最大輸出時(shí)延降低了7.1%，多優(yōu)先級(jí)prefix仲裁器比單優(yōu)先級(jí)prefix仲裁器平均最大輸出時(shí)延降低了23.8%.

本文實(shí)現(xiàn)的多優(yōu)先級(jí)仲裁器與文獻(xiàn)[9]中設(shè)計(jì)的混合并行仲裁器和文獻(xiàn)[10]設(shè)計(jì)的有序仲裁器在面對(duì)相同請(qǐng)求路數(shù)時(shí)，最大工作頻率方面多優(yōu)先級(jí)仲裁器和混合并行仲裁器的數(shù)據(jù)較為接近，多優(yōu)先級(jí)仲裁器的最大輸出時(shí)延指標(biāo)則明顯優(yōu)于混合并行仲裁器和有序仲裁器.在相同的路由請(qǐng)求下，路由網(wǎng)絡(luò)采用多優(yōu)先級(jí)仲裁器進(jìn)行仲裁在一定程度上可以得到更高的路由服務(wù)質(zhì)量.

5 結(jié)束語

本文對(duì)片上路由網(wǎng)絡(luò)仲裁機(jī)制進(jìn)行研究，提出2種多優(yōu)先級(jí)的集成了FP和RR仲裁方式的通用仲裁器,仿真分析得出使用多優(yōu)先級(jí)仲裁器對(duì)比于使用單優(yōu)先級(jí)仲裁器能更少的占用板卡資源、更高的工作頻率、更低的輸出時(shí)延、更低的片內(nèi)功率，在面對(duì)多路由的多模塊的仲裁請(qǐng)求時(shí)能提供更好的路由服務(wù)質(zhì)量.多優(yōu)先級(jí)matrix仲裁器擁有更強(qiáng)的仲裁公平性和更高的最大工作頻率，但matrix仲裁器本身的局限性在于隨著路由請(qǐng)求的增加，其仲裁機(jī)制里生成的優(yōu)先級(jí)矩陣占用的資源越大，所以，matrix仲裁器更適用于較少的路由請(qǐng)求條件下；多優(yōu)先級(jí)prefix仲裁器占用的硬件資源少且能實(shí)時(shí)地更改仲裁請(qǐng)求優(yōu)先級(jí)，可在特定時(shí)間內(nèi)優(yōu)先對(duì)特定的路由請(qǐng)求進(jìn)行仲裁處理，為更好的路由服務(wù)質(zhì)量提供保障.對(duì)兩種通用仲裁器結(jié)構(gòu)進(jìn)行改良優(yōu)化，并設(shè)計(jì)實(shí)現(xiàn)一種兼容兩者優(yōu)點(diǎn)的通用仲裁器是接下來的研究目標(biāo).