一種FIFO隊列的總線仲裁器的設(shè)計

朱麗，蔡瑞

（中航飛機西安飛機分公司，西安 710089）

0 引言

進(jìn)入納米加工時代以來，集成電路芯片的特征尺寸越來越小，單位芯片上的晶體管也越來越多，因此在單一集成電路芯片實現(xiàn)復(fù)雜的電子系統(tǒng)已成為學(xué)者們研究的熱門課題之一，集成電路設(shè)計也迎來了SOC片上系統(tǒng)（System on Chip）時代。

隨著SOC的高速發(fā)展，同一芯片上集成的模塊越來越多，系統(tǒng)各模塊之間的通信總線技術(shù)也隨之成為SOC的關(guān)鍵問題之一。各類總線技術(shù)、通信架構(gòu)和資源調(diào)配已經(jīng)被廣泛研究和試驗驗證。

總線架構(gòu)和仲裁調(diào)度是解決片上系統(tǒng)資源沖突主要辦法，當(dāng)片上系統(tǒng)上有多個主設(shè)備同時發(fā)出請求信息時，就會出現(xiàn)對資源的競爭，這時就應(yīng)該對設(shè)備進(jìn)行合理的調(diào)度，避免出現(xiàn)毫無秩序的一擁而上，而造成擁塞或者數(shù)據(jù)的丟失，因而設(shè)計出合理、公平、高效的仲裁機制尤為重要。為此，本文提出了一種基于隊列的混合優(yōu)先級仲裁機制，從而避免了“死鎖”和“饑餓”。

1 仲裁機制的基本原理

在系統(tǒng)中，總線可以看成是共享資源，多個主設(shè)備對總線的請求可以看成是資源的競爭，仲裁器是管理機構(gòu)，監(jiān)視每個主設(shè)備發(fā)出的請求，根據(jù)其設(shè)定的仲裁算法而響應(yīng)相應(yīng)的主設(shè)備，并給出控制信號。所有的仲裁機制都還應(yīng)滿足：每一時刻至多只能有一個主設(shè)備訪問總線；每次的訪問都不能被打斷；先請求者先響應(yīng)，若有多個主設(shè)備在同一時刻發(fā)出請求時，按優(yōu)先級的高低依次響應(yīng)；算法應(yīng)相對公平，保證每個主設(shè)備有同樣的概率訪問總線。常用的仲裁算法有：固定優(yōu)先級（FP）和循環(huán)優(yōu)先級（RR）。

固定優(yōu)先級：各個主設(shè)備的優(yōu)先級是確定的，不會因為其他外在的條件而改變。當(dāng)多個主設(shè)備同時請求總線時，仲裁器可以快速的響應(yīng)高優(yōu)先級的設(shè)備，以便有效的利用總線，這種算法的優(yōu)點是使得主要的設(shè)備可以及時快速的得到響應(yīng)。但缺點在于當(dāng)高優(yōu)先級的主設(shè)備一直占用總線資源的時候，低優(yōu)先級的主設(shè)備得不到響應(yīng)，而造成高優(yōu)先級“撐死”和低優(yōu)先級“餓死”的現(xiàn)象。

循環(huán)優(yōu)先級：各個主設(shè)備的優(yōu)先級隨著請求訪問的過程在變化，且根據(jù)輪轉(zhuǎn)的規(guī)律變化，隨著主設(shè)備訪問總線的結(jié)束，其優(yōu)先級變?yōu)樽畹停谄浜蟮闹髟O(shè)備優(yōu)先級就變?yōu)樽罡?。這種算法在某種程度上來講保證了公平性，但是當(dāng)某個主設(shè)備需要對總線進(jìn)行多次訪問請求時，會由于優(yōu)先級的降低而增加訪問延時，降低效率。

基于以上兩種算法的特點，在實際中往往將兩種算法結(jié)合起來，從而構(gòu)成更靈活的仲裁機制。

2 仲裁算法設(shè)計

2.1 設(shè)計思想

FIFO隊列（Queue）是一種先來先服務(wù)的存儲器，包括一個存儲塊和一個能對數(shù)據(jù)進(jìn)出通道進(jìn)行管理的控制器，一是數(shù)據(jù)進(jìn)出有序，先進(jìn)先出；二是輸入輸出口獨立[1]。隊列有兩個地址指針，一個讀指針和一個寫指針，讀指針用于讀出下一個有效單元的數(shù)據(jù)，寫指針用于將數(shù)據(jù)寫入下一個有效單元。在讀寫操作時，隊列會先判斷是否空或滿。

本文采用的設(shè)計思路是先將頻繁訪問總線的主設(shè)備的優(yōu)先級確定為最高，如果有請求則優(yōu)先響應(yīng)，基于循環(huán)隊列的仲裁算法就是利用了以上隊列的特性，當(dāng)只有一個主設(shè)備請求總線時，將仲裁結(jié)果進(jìn)入隊列。由于隊列先來先服務(wù)的特性，可以先申請先得到響應(yīng)，當(dāng)有多個主設(shè)備請求總線時，先采用仲裁算法進(jìn)行仲裁，然后根據(jù)優(yōu)先級的高低依次進(jìn)入隊列，最后依次進(jìn)行響應(yīng)。在進(jìn)入和出隊列時，每次要先進(jìn)行判斷隊列是否空或滿，如果空，說明當(dāng)前隊列中沒有對總線發(fā)出請求的設(shè)備，如果滿，說明在有對總線發(fā)出請求的設(shè)備時，已無法入隊列，只有當(dāng)隊列中有其他設(shè)備出隊列后，才能再次進(jìn)入隊列。

這種設(shè)計方法的即保證了高優(yōu)先級主設(shè)備的優(yōu)先性，又保證了其他主設(shè)備的公平性，且響應(yīng)時間短，采用隊列的方式不會由于同時訪問總線而產(chǎn)生“死鎖”和“饑餓”現(xiàn)象。

2.2 仲裁器的組成分析與設(shè)計實現(xiàn)

本文設(shè)定有6個主設(shè)備，且主設(shè)備1和2的優(yōu)先級最高（主設(shè)備1的優(yōu)先級高于主設(shè)備2），對于主設(shè)備3、4、5和6采用循環(huán)優(yōu)先級的方式進(jìn)行優(yōu)先級的判斷，優(yōu)先級的算法如表1所示。

表1 優(yōu)先級算法

本設(shè)計采用自頂向下的設(shè)計方法可分為H_round_arb/L_round_arb、H_queue_ram/L_queue_ram（H表示高優(yōu)先級，L表示低優(yōu)先級）和grant五個模塊，頂層設(shè)計原理如圖1所示。

圖1 總線仲裁器頂層設(shè)計原理圖

H_round_arb/L__round_arb模塊：此模塊的功 能是完成對請求總線主設(shè)備的仲裁，對同一時刻有多個主設(shè)備請求總線時H_round_arb采用固定優(yōu)先級進(jìn)行仲裁，L_round_arb采用循環(huán)優(yōu)先級進(jìn)行仲裁。具體流程如圖2所示。

圖2 仲裁過程設(shè)計原理圖

H_queue_ram/L_queue_ram模塊：此模塊的功能是根據(jù)仲裁模塊產(chǎn)生的主模塊先后順序依次寫入隊列中，隊列可直接利用FPGA中的FIFO進(jìn)行實現(xiàn)。具體流程如圖3所示。

圖3 隊列寫入原理圖

Grant模塊：此模塊的功能是根據(jù)隊列中的順序依次對主設(shè)備響應(yīng)總線。當(dāng)ctrl=1時，響應(yīng)高優(yōu)先級隊列，當(dāng)ctrl=0時響應(yīng)低優(yōu)先級隊列。具體流程如圖4所示。

3 實驗驗證情況

本設(shè)計采用Verilog HDL硬件描述語言進(jìn)行了RTL級的代碼描述，在Modelsim6.4a環(huán)境下進(jìn)行了功能仿真驗證，并采用Altera CycloneIV E系列芯片，在Altera的QuartusII11.0上進(jìn)行了設(shè)計及布局布線，用SignalTap II Logic Analyzer觀察波形，所得設(shè)計仿真波形如圖5所示。

圖4 隊列讀與響應(yīng)原理圖

圖5 仿真波形

當(dāng)所有的設(shè)備向總線發(fā)出請求時，總線會優(yōu)先響應(yīng)1和2主設(shè)備，當(dāng)高優(yōu)先級響應(yīng)完時，接著根據(jù)循環(huán)優(yōu)先級的判斷來依次響應(yīng)主設(shè)備，如圖中的主設(shè)備3、4、5、6，當(dāng)主設(shè)備5響應(yīng)完時由于主設(shè)備2發(fā)出了請求，因此要優(yōu)先響應(yīng)，當(dāng)響應(yīng)完主設(shè)備2之后，接著響應(yīng)之前未響應(yīng)的在隊列中的主設(shè)備6，然后依次響應(yīng)主設(shè)備3，當(dāng)主設(shè)備3響應(yīng)完后，此時主設(shè)備4的優(yōu)先級較高，因此當(dāng)主設(shè)備3、4、5、6同時請求時，優(yōu)先響應(yīng)主設(shè)備4。HGRANT=0和HMASTER=0表示當(dāng)前總線空閑。仿真結(jié)果表明，該設(shè)計達(dá)到了預(yù)期的目標(biāo)。

4 總結(jié)

在基于總線協(xié)議的SOC系統(tǒng)中仲裁算法有著廣泛的應(yīng)用，本文提出的算法結(jié)合了固定仲裁算法和循環(huán)優(yōu)先級算法的優(yōu)勢，并通過隊列存儲的方式有效的解決了“死鎖”問題，避免了擁塞現(xiàn)象，同時本設(shè)計既保證了高優(yōu)先級的優(yōu)先響應(yīng)，又保證了低優(yōu)先級的公平性，且本算法的響應(yīng)時間短，設(shè)計實現(xiàn)簡單可靠。

[1]周先譜,仝曉梅.基于FIFO隊列的PCI總線仲裁器的設(shè)計與FPGA實現(xiàn)[J].現(xiàn)代電子技術(shù),2007(22).

[2]楊冬勤,黃航,張小燕,于忠臣.多路有序優(yōu)先級和有序環(huán)形仲裁器設(shè)計[J].計算機工程,2011,24.

[3]Banerjee,B.LS,Bangalore,India.TREAT THY SECONDARY(ALMOST)LIKE THY PRIMARY-A FAIRARBITERIN MASTER-SLAVECONFIGURATION[J].IEEE Xplore,2013:184-190.

[4]楊哲,張萍,馬佩軍,李康,史江一,舒保健.基于動態(tài)混合優(yōu)先級算法的仲裁器設(shè)計[J].電子器件,2011,34(3).

[5]李耀榮,王光軍,梁利平 等.SoC總線仲裁算法的研究[J].微型計算機信息,2007.23(6-2):113-115.

[6]夏宏,王媛,李文娟.基于混合優(yōu)先權(quán)算法的AHB總線仲裁器設(shè)計[J].中國電力教育,2008,(S1).

[7]李玲,王祖強.AHB總線仲裁器的設(shè)計[J].電子工程師,2005(1).