多路總線仲裁算法優化研究

趙琳

（西安航空學院計算機學院，陜西西安710077）

在共享總線系統中由于多個設備要爭用總線來和其他設備進行互訪以及資源共享，從而引出總線仲裁的概念。總線仲裁就是實現將總線控制權從一個設備向另一個設備轉移和指定的過程。

目前，在高復雜度、高集成度的系統芯片Soc設計中，微處理器、微控制器等主模塊與存儲器、外圍設備等從模塊進行通信時，由于多個主模塊同時申請總線請求傳輸，而引起的有限總線資源競爭已經成為影響系統性能的重要因素[1]。

因此，多路設備同時發出總線請求時就會沖突，為使總線資源有效利用，對競爭設備進行仲裁并根據結果對設備賦權的策略稱為仲裁算法，仲裁算法對于系統性能的影響起著重要的作用[2]。目的帶寬比與實際賦權比的吻合程度是衡量仲裁算法的重要因素，越吻合，算法越具廣泛適用性。近幾年的研究多以此項指標進行仲裁器的性能評估[3]。

仲裁賦權決策多由不依賴于硬件的仲裁算法確定，本文利用Visual Stidio設計了仿真平臺，充分利用軟件的優點對仲裁算法進行檢驗[6]。

1 常用仲裁算法介紹

1.1 經典仲裁算法

固定優先級仲裁算法[7-9]就是各個設備優先級保持不變。仲裁時總是先響應優先級較高的設備。它的優點在于電路簡單，硬件開銷少；缺點在于容易導致高優先級設備長時間占用總線，而低優先級設備長時間爭用不到總線，容易出現“撐死”或者“餓死”的情況，適用范圍有限。

循環優先級仲裁算法[10-12]指設備的優先級循環變化，最高優先級在每個設備之間進行輪轉。該算法中，每個總線設備都能上升為最高優先級設備，可以保證每個設備都能占用到總線。缺點在于各設備優先級過于公平，忽視設備本身優先級高低的差異。

彩票仲裁算法[14-15]是指將所有設備按照自身帶寬比需求的不同賦值一個彩票抽取范圍，仲裁器隨機抽取彩票所在范圍的設備賦予總線使用權限。彩票仲裁算法理想情況下能夠很好的實現目的帶寬比。缺點在于仲裁受到概率的影響，且對電路的開銷較大。

1.2 靜態和動態算法

常用的仲裁算法分為靜態算法和動態算法。在算法中主模塊的優先級是確定的稱為靜態算法。在仲裁過程中主模塊自身優先級可變稱為動態算法。固定優先級仲裁算法、循環優先級仲裁算法、彩票仲裁算法都是靜態優先級算法。

2 本文仲裁算法

為了彌補固定優先級仲裁算法和循環優先級仲裁算法中的不足，兼顧主模塊本身的優先級和公平性的要素。文獻[16-18]設計應用了兩層仲裁系統，第一層使用固定優先級算法進行快速仲裁響應，第二層以輪詢仲裁算法保證公平性原則。為了保證目的帶寬比與實際帶寬比吻合這一性能指標，文獻[3-6]中都根據彩票仲裁算法的思想為主設備本身的特點預先賦值彩票數，從而達到滿足目的帶寬比的性能要求。

在眾多的雙層仲裁器算法中，仲裁器需要逐一對主設備進行判斷和詢問，這樣會產生判斷順序的問題并使得主模塊的優先級更加復雜[6]。另外在雙層算法中要對兩種仲裁算法分別設計仲裁模塊，增加了總線的延遲和損耗，兩層算法在切換時也會增加額外的總線周期影響總線利用率[5]。

為了彌補雙層仲裁算法的不足，本文在借鑒固定優先級仲裁算法和彩票仲裁算法的基礎上，提出了一種改進的有序仲裁算法。其原理如圖1所示。

圖1 本文算法流程

本文仲裁算法中的工作方法為：在第一次共享總線上有設備進行總線請求時，若只有一個設備則直接將總線使用權賦予該設備。若為多個設備請求總線使用權，則根據每個主設備的固定優先級進行總線仲裁。其余未被賦權的主設備按照固定優先級進行排隊。當本次總線使用結束后，總線仲裁設備將直接從排隊中按照先入先出的順序進行多設備的總線賦權。為了保障目的帶寬比與實際帶寬比相吻合這一指標，給每個設備按照目的帶寬比賦予彩票值。每個設備被進行了總線賦權之后，該設備的彩票值減1。在每次循環第一次仲裁之外的其他仲裁，仲裁器都是從排隊中獲得需要被賦權的設備。但是在每次賦權之前首先進行彩票值的判斷，若彩票值為0則屏蔽掉改設備的總線申請并將該設備從排隊中刪除。若排隊設備為空，則說明或者為輪空狀態或者所有設備的彩票值都已經為0了。此時，按照目的帶寬比給所有設備重新賦值。并按照固定優先級的仲裁算法開始新一輪的總線仲裁和排隊過程。

綜合改進后的順序仲裁算法，從主設備本身所具有的不同優先級來看待設備之間的關系，賦予各設備不同的固定的優先級。根據目的帶寬比賦予各設備不同的彩票值。根據每個設備提出請求的順序不同而進行申請排序。在每個循環周期開始根據固定優先級仲裁，其余仲裁按照FIFO的原則進行賦權操作，每進行完一次總線賦權操作便將相應主設備上的彩票值減1。在按照FIFO的原則進行賦權之前判斷一下各設備的彩票值是否全部為0，以此為依據來決定是否開始下一輪重新賦權循環仲裁。本文算法中根據彩票值規定每個設備在一個仲裁循環周期中能否訪問總線的門限值，保證目的帶寬比。通過排隊保證一個循環周期內的仲裁順序。各設備固定優先級用于每個周期最初的賦權操作。本算法在保證目的帶寬比的情況下，通過排隊兼顧了仲裁算法的公平性，彌補了固定優先級算法的“餓死”或者“撐死”的現象。

3 算法仿真

3.1 仿真平臺

仲裁算法大多不依賴于硬件設備，文獻[6]中介紹了一種在Visual Studio編譯環境下進行算法仿真的方法。本文借鑒了該方法并在此軟件基礎上增設了排隊功能，驗證本文仲裁算法的結果。

3.2 仿真方法

在仿真中通過含有3個域的變量來模擬設備，一個是整型域用來表示設備編號，一個是布爾型域表示設備的請求，另一個還是整型域用于表示該設備的彩票值。彩票值根據每個設備的目的帶寬比確定。這樣每個設備構成了一個具有3個域的設備向量。用隊列實現沖突狀態下多個設備的排序。仲裁算法用函數設計，設備向量作為仲裁函數的輸入，在仲裁函數內部，根據隊列的判空來確定是進行快速賦權還是從隊獲取仲裁設備賦權。經仲裁后形成仲裁向量與設備向量進行邏輯加如表達式（1）所示，最后將賦權設備輸出。

表達式（1）中X表示設備向量，W表示仲裁向量，Z表示仲裁結果。

在函數中設置了累加器和每個主設備被賦權次數的計算器，用于計算每個主設備的實際帶寬比。比較實際帶寬比與目的帶寬比的吻合程度測試算法的性能。

3.3 參數設置

本文使用四主設備爭用總線模型作為測試對象。4個主設備的固定優先級如表1所示。4個主設備的彩票值（目的帶寬比）如表2所示。4個設備發出總線請求的比例如表3所示。驗證在4個設備同時具有總線請求的沖突狀況下進行。

表1 4個主設備的固定優先級

表2 4個主設備目的帶寬比（彩票值）

表3 4個主設備發出請求的比例

本文在驗證時對固定優先級仲裁算法和彩票仲裁算法進行了比對，用于分析目的帶寬比與實際帶寬比的吻合程度結果如圖2、圖3所示。

圖2 目的帶寬比（4:3:2:1）下算法驗證

圖3 目的帶寬比（3:2:2:1）下算法驗證

3.4 結果分析

固定優先級仲裁算法、彩票優先級仲裁算法、本文優先級仲裁算法，在四設備高沖突律的情況下。固定優先級在不同的目的帶寬比和不同的主設備請求比例的情況下都出現了“撐死”和“餓死”的情況。而彩票仲裁法和本文仲裁法在預設了每個主設備彩票值的情況下目的帶寬比在兩種不同的主設備請求比例的狀態下都能夠很好的被滿足。但彩票仲裁法受到概率的影響，且忽視了設備請求順序這一實際情況，使得仲裁公平性受到影響。本文仲裁法在高沖突率的狀態下較好的滿足了目的帶寬比，由于采用了排隊的思想，考慮了各個主設備提出仲裁的順序，體現了仲裁算法的公平性原則，高沖突率下的總線利用率為100%，避免了輪空現象。

本文仲裁算法很好的借鑒了了固定優先級和彩票優先級算法的優點，在優先級比較高的設備中使用總線的概率明顯要高于固定優先級仲裁算法、仲裁公平性方面優于彩票優先級。由于每個主設備根據目的帶寬比設置了預設彩票就給算法應用增加了更多的靈活性，可在優先級一定的情況下動態修改彩票權值即根據應用環境設置在一次循環中一個設備訪問總線的門限值。更能滿足實際中關于總線仲裁的各種應用[19-21]。

4 結 論

本文以雙層仲裁算法為基礎，借鑒彩票仲裁算法以及排隊思想，彌補了雙層仲裁算法的不足。在高沖突律的狀態下提高了總線的利用率，并通過在賦權的同時對未被響應的設備進行排隊，提高仲裁算法的公平性。從仿真結果看，本文的仲裁算法很好的滿足了目的帶寬比與實際帶寬比相吻合這一重要指標，有廣泛的適用范圍。

參考文獻：

[1]Bachanna P，Jalad V，Shetkar S.Design and Analysis of High Speed Low Power Reusable on Chip Bus Based on Wishbone[C]//Proceedings of the 2014 5th International Conference on Signal and ImageProcessing.Piscataway:IEEE，2014:197-200.

[2]YANG Yan-fei，ZHU Zhang-ming，ZHOU Duan，etal.Delay-independent asynchronous dynamic priority arbiter for the network on chips[J].Journal of Xidian University，2012.39（1）:42-48.

[3]吳睿振，楊銀堂，張麗，等.一種基于權重與輪詢的雙層仲裁算法[J].電子與信息學報，2013，12（12）:3024-3029.

[4]楊哲，張萍，馬佩軍，等.基于動態混合優先級算法的仲裁器設計[J].電子器件，2011，6（3）:307-311.

[5]吳睿振，楊銀堂，張麗，等.自調整附加權動態仲裁算法[J].計算機輔助設計與圖形學學報，2014，9（9）：1494-1500.

[6]劉露，周小鋒，朱樟明，等.一種采用雙層仲裁機制的新型總線仲裁器[J].西安電子科技大學學報：自然科學版，2017，2（1）：12-18.

[7]Abdel-Hafeez S and Harb S.A VLSI highperformance priority encoder using standard CMOS library[J].IEEE Transactionson Circuitsand Systems II:Express Bricfs，2006，53（8）:597-601.

[8]Dimitrakopoulos G，Chrysos N，Galanopoulos K.Fastarbiters for on-chip network switches[C]//IEEE InternationalConference on Computer Design，Lake Tahoe，2008:664-670.

[9]Ciresan D C，Meier U，Gameardella L M，et al.Convolutional neural network committees for handwritten character classification[C]//Proceedings of the International Conference on Document Analysis and Recognition.Priscataway:IEEE Computer Society，2011:1135-1139.

[10]Ugurdag H F，Baskirt O.An in-depth look at prior art in fast round-robin arbiter circuits[R].Ozyegin University，2011.

[11]Ugurdag H F，Temizkan F，Baskirt O.Fast twopick n2n round-robin arbiter circuit[J].Electronics Letters，2012，48（13）:759-760.

[12]Medion G，Lee M S，Tang C K.A computational framework for segmentation and grouping[M].New York:Elsevier，2000.

[13]楊冬勤，黃航，張小燕，等.多路有序優先級和有序環形仲裁器設計[J].計算機工程，2011，12（24）：236-238.

[14]Singh A K，Shrivastava A，Tomar G S.Design and implementation of high performance AHB reconfigurable arbiter for on-chip bus architecture[C]//Proceedings of International Conference on Communication Systems and Network Technologies.Los Alamitos:IEEE Computer Society Press，2011:455-459.

[15]Khanam R，Sharma H，Gaur S.Design a Low latency arbiter for on chip communication architecture[C]//International Conference on Computing，Communication&Automation.Piscataway:IEEE，2015:1421-1426.

[16]龔丁禧，曹長榮.基于卷積神經網絡的植物葉片分類[J].計算機與現代化，2014（4）:12-15.

[17]程江華，高貴，庫錫樹，等.高分辨率SAR圖像道路交叉口檢測與識別新方法[J].雷達學報，2012，1（1）：100-108．

[18]苗則朗.基于多特征的高分辨率遙感影像道路提取算法研究[D].徐州:中國礦業大學，2014.

[19]姜寧，陳建春，王沛，等.基于FPGA的PCIe接口實現[J].電子科技，2014（10）：188-191.

[20]徐震，邵波，王云鵬.無線傳感器網絡分布式數據采集功率控制研究[J].電力信息與通信技術，2017（2）:115-120.

[21]侯亞玲，李敏.智能優化算法在波導縫隙陣天線設計中的應用[J].自動化與儀器儀表，2017（8）:50-52.