趙琳

（西安航空學(xué)院計(jì)算機(jī)學(xué)院，陜西西安710077）

在共享總線系統(tǒng)中由于多個(gè)設(shè)備要爭(zhēng)用總線來(lái)和其他設(shè)備進(jìn)行互訪以及資源共享，從而引出總線仲裁的概念。總線仲裁就是實(shí)現(xiàn)將總線控制權(quán)從一個(gè)設(shè)備向另一個(gè)設(shè)備轉(zhuǎn)移和指定的過(guò)程。

目前，在高復(fù)雜度、高集成度的系統(tǒng)芯片Soc設(shè)計(jì)中，微處理器、微控制器等主模塊與存儲(chǔ)器、外圍設(shè)備等從模塊進(jìn)行通信時(shí)，由于多個(gè)主模塊同時(shí)申請(qǐng)總線請(qǐng)求傳輸，而引起的有限總線資源競(jìng)爭(zhēng)已經(jīng)成為影響系統(tǒng)性能的重要因素[1]。

因此，多路設(shè)備同時(shí)發(fā)出總線請(qǐng)求時(shí)就會(huì)沖突，為使總線資源有效利用，對(duì)競(jìng)爭(zhēng)設(shè)備進(jìn)行仲裁并根據(jù)結(jié)果對(duì)設(shè)備賦權(quán)的策略稱為仲裁算法，仲裁算法對(duì)于系統(tǒng)性能的影響起著重要的作用[2]。目的帶寬比與實(shí)際賦權(quán)比的吻合程度是衡量仲裁算法的重要因素，越吻合，算法越具廣泛適用性。近幾年的研究多以此項(xiàng)指標(biāo)進(jìn)行仲裁器的性能評(píng)估[3]。

仲裁賦權(quán)決策多由不依賴于硬件的仲裁算法確定，本文利用Visual Stidio設(shè)計(jì)了仿真平臺(tái)，充分利用軟件的優(yōu)點(diǎn)對(duì)仲裁算法進(jìn)行檢驗(yàn)[6]。

1 常用仲裁算法介紹

1.1 經(jīng)典仲裁算法

固定優(yōu)先級(jí)仲裁算法[7-9]就是各個(gè)設(shè)備優(yōu)先級(jí)保持不變。仲裁時(shí)總是先響應(yīng)優(yōu)先級(jí)較高的設(shè)備。它的優(yōu)點(diǎn)在于電路簡(jiǎn)單，硬件開(kāi)銷少；缺點(diǎn)在于容易導(dǎo)致高優(yōu)先級(jí)設(shè)備長(zhǎng)時(shí)間占用總線，而低優(yōu)先級(jí)設(shè)備長(zhǎng)時(shí)間爭(zhēng)用不到總線，容易出現(xiàn)“撐死”或者“餓死”的情況，適用范圍有限。

循環(huán)優(yōu)先級(jí)仲裁算法[10-12]指設(shè)備的優(yōu)先級(jí)循環(huán)變化，最高優(yōu)先級(jí)在每個(gè)設(shè)備之間進(jìn)行輪轉(zhuǎn)。該算法中，每個(gè)總線設(shè)備都能上升為最高優(yōu)先級(jí)設(shè)備，可以保證每個(gè)設(shè)備都能占用到總線。缺點(diǎn)在于各設(shè)備優(yōu)先級(jí)過(guò)于公平，忽視設(shè)備本身優(yōu)先級(jí)高低的差異。

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

1.2 靜態(tài)和動(dòng)態(tài)算法

常用的仲裁算法分為靜態(tài)算法和動(dòng)態(tài)算法。在算法中主模塊的優(yōu)先級(jí)是確定的稱為靜態(tài)算法。在仲裁過(guò)程中主模塊自身優(yōu)先級(jí)可變稱為動(dòng)態(tài)算法。固定優(yōu)先級(jí)仲裁算法、循環(huán)優(yōu)先級(jí)仲裁算法、彩票仲裁算法都是靜態(tài)優(yōu)先級(jí)算法。

2 本文仲裁算法

為了彌補(bǔ)固定優(yōu)先級(jí)仲裁算法和循環(huán)優(yōu)先級(jí)仲裁算法中的不足，兼顧主模塊本身的優(yōu)先級(jí)和公平性的要素。文獻(xiàn)[16-18]設(shè)計(jì)應(yīng)用了兩層仲裁系統(tǒng)，第一層使用固定優(yōu)先級(jí)算法進(jìn)行快速仲裁響應(yīng)，第二層以輪詢仲裁算法保證公平性原則。為了保證目的帶寬比與實(shí)際帶寬比吻合這一性能指標(biāo)，文獻(xiàn)[3-6]中都根據(jù)彩票仲裁算法的思想為主設(shè)備本身的特點(diǎn)預(yù)先賦值彩票數(shù)，從而達(dá)到滿足目的帶寬比的性能要求。

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

為了彌補(bǔ)雙層仲裁算法的不足，本文在借鑒固定優(yōu)先級(jí)仲裁算法和彩票仲裁算法的基礎(chǔ)上，提出了一種改進(jìn)的有序仲裁算法。其原理如圖1所示。

圖1 本文算法流程

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

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

3 算法仿真

3.1 仿真平臺(tái)

仲裁算法大多不依賴于硬件設(shè)備，文獻(xiàn)[6]中介紹了一種在Visual Studio編譯環(huán)境下進(jìn)行算法仿真的方法。本文借鑒了該方法并在此軟件基礎(chǔ)上增設(shè)了排隊(duì)功能，驗(yàn)證本文仲裁算法的結(jié)果。

3.2 仿真方法

在仿真中通過(guò)含有3個(gè)域的變量來(lái)模擬設(shè)備，一個(gè)是整型域用來(lái)表示設(shè)備編號(hào)，一個(gè)是布爾型域表示設(shè)備的請(qǐng)求，另一個(gè)還是整型域用于表示該設(shè)備的彩票值。彩票值根據(jù)每個(gè)設(shè)備的目的帶寬比確定。這樣每個(gè)設(shè)備構(gòu)成了一個(gè)具有3個(gè)域的設(shè)備向量。用隊(duì)列實(shí)現(xiàn)沖突狀態(tài)下多個(gè)設(shè)備的排序。仲裁算法用函數(shù)設(shè)計(jì)，設(shè)備向量作為仲裁函數(shù)的輸入，在仲裁函數(shù)內(nèi)部，根據(jù)隊(duì)列的判空來(lái)確定是進(jìn)行快速賦權(quán)還是從隊(duì)獲取仲裁設(shè)備賦權(quán)。經(jīng)仲裁后形成仲裁向量與設(shè)備向量進(jìn)行邏輯加如表達(dá)式（1）所示，最后將賦權(quán)設(shè)備輸出。

表達(dá)式（1）中X表示設(shè)備向量，W表示仲裁向量，Z表示仲裁結(jié)果。

在函數(shù)中設(shè)置了累加器和每個(gè)主設(shè)備被賦權(quán)次數(shù)的計(jì)算器，用于計(jì)算每個(gè)主設(shè)備的實(shí)際帶寬比。比較實(shí)際帶寬比與目的帶寬比的吻合程度測(cè)試算法的性能。

3.3 參數(shù)設(shè)置

本文使用四主設(shè)備爭(zhēng)用總線模型作為測(cè)試對(duì)象。4個(gè)主設(shè)備的固定優(yōu)先級(jí)如表1所示。4個(gè)主設(shè)備的彩票值（目的帶寬比）如表2所示。4個(gè)設(shè)備發(fā)出總線請(qǐng)求的比例如表3所示。驗(yàn)證在4個(gè)設(shè)備同時(shí)具有總線請(qǐng)求的沖突狀況下進(jìn)行。

表1 4個(gè)主設(shè)備的固定優(yōu)先級(jí)

表2 4個(gè)主設(shè)備目的帶寬比（彩票值）

表3 4個(gè)主設(shè)備發(fā)出請(qǐng)求的比例

本文在驗(yàn)證時(shí)對(duì)固定優(yōu)先級(jí)仲裁算法和彩票仲裁算法進(jìn)行了比對(duì)，用于分析目的帶寬比與實(shí)際帶寬比的吻合程度結(jié)果如圖2、圖3所示。

圖2 目的帶寬比（4:3:2:1）下算法驗(yàn)證

圖3 目的帶寬比（3:2:2:1）下算法驗(yàn)證

3.4 結(jié)果分析

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

本文仲裁算法很好的借鑒了了固定優(yōu)先級(jí)和彩票優(yōu)先級(jí)算法的優(yōu)點(diǎn)，在優(yōu)先級(jí)比較高的設(shè)備中使用總線的概率明顯要高于固定優(yōu)先級(jí)仲裁算法、仲裁公平性方面優(yōu)于彩票優(yōu)先級(jí)。由于每個(gè)主設(shè)備根據(jù)目的帶寬比設(shè)置了預(yù)設(shè)彩票就給算法應(yīng)用增加了更多的靈活性，可在優(yōu)先級(jí)一定的情況下動(dòng)態(tài)修改彩票權(quán)值即根據(jù)應(yīng)用環(huán)境設(shè)置在一次循環(huán)中一個(gè)設(shè)備訪問(wèn)總線的門限值。更能滿足實(shí)際中關(guān)于總線仲裁的各種應(yīng)用[19-21]。

4 結(jié) 論

本文以雙層仲裁算法為基礎(chǔ)，借鑒彩票仲裁算法以及排隊(duì)思想，彌補(bǔ)了雙層仲裁算法的不足。在高沖突律的狀態(tài)下提高了總線的利用率，并通過(guò)在賦權(quán)的同時(shí)對(duì)未被響應(yīng)的設(shè)備進(jìn)行排隊(duì)，提高仲裁算法的公平性。從仿真結(jié)果看，本文的仲裁算法很好的滿足了目的帶寬比與實(shí)際帶寬比相吻合這一重要指標(biāo)，有廣泛的適用范圍。

參考文獻(xiàn)：

[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]吳睿振，楊銀堂，張麗，等.一種基于權(quán)重與輪詢的雙層仲裁算法[J].電子與信息學(xué)報(bào)，2013，12（12）:3024-3029.

[4]楊哲，張萍，馬佩軍，等.基于動(dòng)態(tài)混合優(yōu)先級(jí)算法的仲裁器設(shè)計(jì)[J].電子器件，2011，6（3）:307-311.

[5]吳睿振，楊銀堂，張麗，等.自調(diào)整附加權(quán)動(dòng)態(tài)仲裁算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2014，9（9）：1494-1500.

[6]劉露，周小鋒，朱樟明，等.一種采用雙層仲裁機(jī)制的新型總線仲裁器[J].西安電子科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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]楊冬勤，黃航，張小燕，等.多路有序優(yōu)先級(jí)和有序環(huán)形仲裁器設(shè)計(jì)[J].計(jì)算機(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]龔丁禧，曹長(zhǎng)榮.基于卷積神經(jīng)網(wǎng)絡(luò)的植物葉片分類[J].計(jì)算機(jī)與現(xiàn)代化，2014（4）:12-15.

[17]程江華，高貴，庫(kù)錫樹(shù)，等.高分辨率SAR圖像道路交叉口檢測(cè)與識(shí)別新方法[J].雷達(dá)學(xué)報(bào)，2012，1（1）：100-108．

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

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

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

[21]侯亞玲，李敏.智能優(yōu)化算法在波導(dǎo)縫隙陣天線設(shè)計(jì)中的應(yīng)用[J].自動(dòng)化與儀器儀表，2017（8）:50-52.