多優先級通用路由仲裁器的設計實現

周剛華，鄒德財，盧曉春

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

2(中國科學院精密導航定位與定時技術重點實驗室，西安 710600)

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

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

E-mail：18829269702@163.com

1 引 言

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

本文通過對目前常用的仲裁方式進行學習研究，設計實現了兩種融合固定仲裁和輪循仲裁的多優先級通用仲裁器.在采用多優先級仲裁后，仲裁器可并行處理多路由多模塊的仲裁請求，提高了數據處理和通信的速度，并且當需要仲裁的路由請求總數相同時：無論是在芯片資源占用還是最大工作頻率和最大輸出時延上，多優先級仲裁器的指標都要優于單優先級仲裁器的指標.

2 仲裁機制

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

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

圖1 FP仲裁器仲裁機理

將路由請求信號輸入仲裁基本塊中進行仲裁，仲裁優先級從上到下依次降低.高優先級仲裁塊的輸出信號Ci作為控制信號控制其下一級仲裁模塊的仲裁輸出結果，同時與～req[i]相與后得到Ci+1作為下下一級的控制信號，如此，高優先級的路由請求信號對低優先級具有絕對的壓制，所以固定優先級仲裁容易出現“餓死”和“撐死”現象[8].

圖2 RR仲裁器仲裁機理

與固定優先級仲裁器不同的是，輪循優先級仲裁器把前面的仲裁結果作為反饋信號與上級仲裁模塊的輸出信號Ci相或后成為控制信號控制此級的仲裁輸出，此次的仲裁結果g[i]輸入到update priority模塊，update priority模塊根據此次的仲裁結果調整下次各請求信號的仲裁優先級，循環往復，達到相對公平的仲裁請求結果.

為應對實際路由請求中需要不同仲裁方式的情況，在兩種通用仲裁器中融合固定優先級仲和輪循優先級兩種仲裁方式.當需要對某路由請求進行最優先仲裁或者路由請求信號數較少且無沖突時，為減少響應時間，提高數據處理速度時，采用FP仲裁；進行沖突路由請求仲裁時則采用RR仲裁，保證信息傳遞的有效性，避免餓死現象.

3 多優先級仲裁器

3.1 多優先級matrix仲裁器

3.1.1 多優先級matrix仲裁器原理

常見matrix仲裁器的原理是將n位輸入請求req生成n*n的優先級矩陣A[7]，Ai,j的值即req[i]與req[j]的優先級關系，矩陣A的轉置對應位值相同，對角線值為1.為應對片上路由網絡里出現多個路由中的多個模塊同時請求仲裁的情況，在此提出一種多優先級matrix仲裁器的設計.

圖3中的sel模塊是具有one-hot控制信號的多路復用器，reduce模塊具有判斷請求信號那幾段存在請求信號的功能，gate模塊根據輸入的選擇信號選擇輸出對應部分的仲裁結果，lod模塊功能是檢測第一個輸入高位的位置，圖3中間的部分是儲存優先級矩陣的值.對輸入的路由請求進行多優先級仲裁的過程可分為兩部分，一部分對所有輸入請求分別進行優先級仲裁，另一部分對每個分組路由的請求信號進行檢測縮減得到選擇信號sel，sel信號再對上一部分得到的優先級仲裁結果選擇輸出.

圖3 多優先級matrix仲裁器RTL原理圖

3.1.2 matrix仲裁器功能實現仿真圖

由圖4可知,無論是單優先級還是多優先級，update信號為0時執行的是FP仲裁器功能，為1時對應RR仲裁器功能.單優先級matrix仲裁器執行的是普通的輪詢仲裁功能，在仲裁一次數據請求(請求信號設定的是同一路由內的多個模塊請求仲裁)后，對下一級的仲裁請求進行優先級更新，所以仲裁輸出值不斷循環變化，而多優先級matrix仲裁器不僅可以對同一路由的不同模塊的仲裁請求有著優先級仲裁(請求信號設定的是多個路由內的多個模塊請求仲裁)，同時也可以在不同路由網絡之間進行優先級仲裁，在仿真結果里可以看見有多個路由網絡的仲裁結果在并行輸出且同一路由請求的仲裁結果不斷變化.多優先級仲裁器相比單優先級仲裁器的優勢在于：多優先級仲裁器可以并行處理多組需要仲裁的請求信號，單優先級仲裁器同時只能對一組請求信號進行仲裁，而且在處理相同數量的路由請求信號時，多優先級仲裁器的關鍵路徑時延更低，占用的硬件資源更少.

圖4 單優先級和多優先級matrix仲裁器仿真結果

3.2 多優先級prefix仲裁器

3.2.1 多優先級prefix仲裁器原理

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

圖5 多優先級prefix仲裁器RTL原理圖

圖5中encode模塊將one-hot碼轉換為二進制碼.decode模塊則是將二進制碼解碼成one-hot碼.prefix_base模塊是prefix仲裁器的核心—是基于前綴樹的循環仲裁器基本塊，前綴樹網絡和根據輸入的前綴得到仲裁結果在這里實現.sel、reduce、gate和lod模塊與多優先級matrix仲裁器中的模塊功能相同.

3.2.2 prefix仲裁器功能實現仿真圖

相同的，update的值決定著實際運行中仲裁方式的類型，但prefix仲裁器與matrix仲裁器的不同之處在于prefix仲裁器可以通過外部輸入對prefix_base模塊中的prio_port端口進行掩碼輸入，實時的改變片上路由網絡里的路由單元進行仲裁的優先級，不再類似于其他輪循仲裁器對路由系統內的仲裁優先級一直循環變換保證相對公平的仲裁結果，所以prefix仲裁器在某些特定的應用情況下可以實時地設置各個路由請求的優先級，在短時間內迅速處理某些指定的路由請求，提高路由網絡的路由服務質量.除了解決通信沖突外，效率也是評價仲裁器的一個重要指標，從prefix仲裁器的仿真結果圖可得出與matrix仲裁器相同的結論，多優先級仲裁器由于可將數據信號并行處理，能在一定程度上提高數據通信的效率.

4 仲裁器仿真分析

下面若干表皆為在Xilinx公司的vivado開發軟件環境下使用Verilog語言對仲裁器模塊進行綜合實現(同樣的路由請求數時)的系統指標情況，對應的FPGA開發板為Xilinx公司virtex-7系列里的VC707開發板.

圖6 單優先級和多優先級prefix仲裁器仿真結果

4.1 仲裁器資源占用情況和片內功率

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

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

圖8 仲裁器片內功率

圖8為在不同請求總數下對四種仲裁器進行功耗分析得到的開發板片內功率(包括靜態和動態).同理可知，在路由請求較低時，單優先級仲裁器和多優先級仲裁器占用的資源接近，所以此時板卡上運行單優先級仲裁器的片內功率與板卡上運行多優先級的matrix仲裁器的片內功率接近，但隨著路由請求的增加，無論是matrix仲裁器還是prefix仲裁器，多優先級仲裁器的片內功率都會遠低于單優先級仲裁器的片內功率.

4.2 仲裁器最大工作頻率和最大輸出時延

在vivado中對四種仲裁器在不同路由請求總數下進行綜合映射，得到各種情況下的Timing Report，由時序報告分析得到四種仲裁器最大工作頻率的對比圖.由圖9可知：當路由請求數較少時，多優先級仲裁器的最大工作頻率稍微高于單優先級仲裁器的最大工作頻率，但隨著路由請求總數的增加，無論是多優先級matrix仲裁器還是多優先級prefix仲裁器的最大工作頻率都高于相對應的單優先級仲裁器的最大工作頻率.當路由請求數為45個時，多優先級matrix仲裁器最大工作頻率比單優先級matrix仲裁器高13%，多優先級prefix仲裁器最大工作頻率比單優先級prefix仲裁器高134%；當路由請求數為60個時，多優先級matrix仲裁器最大工作頻率比單優先級matrix仲裁器高19%，多優先級prefix仲裁器最大工作頻率比單優先級prefix仲裁器高145%.

圖9 仲裁器最大工作頻率

圖10 仲裁器最大輸出時延

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

本文實現的多優先級仲裁器與文獻[9]中設計的混合并行仲裁器和文獻[10]設計的有序仲裁器在面對相同請求路數時，最大工作頻率方面多優先級仲裁器和混合并行仲裁器的數據較為接近，多優先級仲裁器的最大輸出時延指標則明顯優于混合并行仲裁器和有序仲裁器.在相同的路由請求下，路由網絡采用多優先級仲裁器進行仲裁在一定程度上可以得到更高的路由服務質量.

5 結束語

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