對于包含多主設(shè)備的片上系統(tǒng)，采用共享總線的結(jié)構(gòu)具有實(shí)現(xiàn)簡單和硬件開銷較少的優(yōu)勢,，已成為設(shè)計的主要手段,。在共享總線結(jié)構(gòu)中,，多個總線主設(shè)備競爭使用總線控制權(quán)，不可避免地會產(chǎn)生競爭和沖突,，為有效解決沖突,，設(shè)計了總線仲裁器來決定總線上哪個主設(shè)備獲得總線的使用權(quán)。但是,，各總線主設(shè)備會有不同的實(shí)時性和帶寬的要求,，所以，總線仲裁器必須采取合理的策略和高性能的調(diào)度算法來滿足各主設(shè)備的要求,。目前,，常用的總線仲裁算法有：固定/動態(tài)優(yōu)先權(quán)算法FP/DP(Fix/Dynamic Priority)、時分復(fù)用算法TDMA(Time Division Multiple Access),、時間片輪轉(zhuǎn)算法RR(Round Robin)和彩票算法(Lottery),。文獻(xiàn)[1]-[3]已經(jīng)證明了這些傳統(tǒng)算法不能很好地滿足各主設(shè)備實(shí)時性和帶寬要求。目前,，不少學(xué)者對傳統(tǒng)算法進(jìn)行了改進(jìn),，如文獻(xiàn)[4]把Lottery算法改進(jìn)成三級總線仲裁機(jī)制；文獻(xiàn)[5]通過自適應(yīng)的動態(tài)調(diào)整“彩票”數(shù)來改進(jìn)Lottery算法,；文獻(xiàn)[6]則提出了一種基于傳輸時間精確預(yù)測的仲裁算法,。但是，這些改進(jìn)算法也都沒有考慮主設(shè)備請求總線服務(wù)的緩急程度,。因此,，本文提出一種基于搶占閾值的最小空閑時間優(yōu)先PT-LSF(Preemption Threshold-Least Slack First)服務(wù)的片上總線仲裁算法。該算法在收集主設(shè)備請求(服務(wù)時間和截止時間等)特性參數(shù)和總線傳輸狀態(tài)信息的基礎(chǔ)上,，通過PT-LSF算法的調(diào)度結(jié)果,，實(shí)時動態(tài)地改變主設(shè)備優(yōu)先權(quán)，以滿足主設(shè)備強(qiáng)實(shí)時性要求,。
1 基于最小空閑時間優(yōu)先的總線仲裁算法原理及實(shí)現(xiàn)
1.1 算法原理
    記空閑時間Si定義為從當(dāng)前時刻t直到其截止期di的時間與其剩余服務(wù)時間ci(t)之間的差，則最小空閑時間優(yōu)先調(diào)度算法的策略是：按照主設(shè)備的空閑時間動態(tài)地分配優(yōu)先級p,，可由式(1)確定：
    p_i=p_max-S_i    (1)
    空閑時間越短,，主設(shè)備的優(yōu)先級就越高，因此選擇具有最小空閑時間的主設(shè)備獲得總線的使用權(quán),。假設(shè)某個主設(shè)備Ti發(fā)出請求總線服務(wù)請求時,，總線正被具有更高優(yōu)先級的其他主設(shè)備Tj所占用，從而阻止了Ti使用總線,。隨著時間的推移,，Ti的空閑時間嚴(yán)格單調(diào)遞減直至小于正占用總線的主設(shè)備Tj的空閑時間時，按照調(diào)度策略,，總線必須切換到服務(wù)Ti,。
1.1.1 總線顛簸現(xiàn)象
    由于等待主設(shè)備的空閑時間隨時間嚴(yán)格遞減,，當(dāng)有多個任務(wù)等待主設(shè)備時，其空閑時間不斷變化,，所以會出現(xiàn)多個主設(shè)備相互交叉搶占總線服務(wù)的現(xiàn)象,。每次搶占都發(fā)生一次總線切換，造成總線服務(wù)顛簸現(xiàn)象,。由于總線服務(wù)切換的時間不可忽略,，而且會加大仲裁器的設(shè)計難度，浪費(fèi)資源,，因此必須有效地避免顛簸現(xiàn)象,。顛簸現(xiàn)象的產(chǎn)生主要是因?yàn)榈却?wù)主設(shè)備Ti的空閑時間Si一旦小于服務(wù)主設(shè)備Tj的空閑時間Sj，就馬上進(jìn)行總線服務(wù)切換,，所以選擇合適的切換時機(jī)可以有效地解決顛簸現(xiàn)象,。本文引入搶占閾值來擴(kuò)展最小空閑時間優(yōu)先服務(wù)的總線仲裁算法。
1.1.2 搶占閾值的確定
    記pi為主設(shè)備Ti的優(yōu)先級,，hi為主設(shè)備Ti的切換閾值,。根據(jù)之前的分析，主設(shè)備的優(yōu)先值越大,，其優(yōu)先級就越高,，所以主設(shè)備的切換閾值必須大于其優(yōu)先值，即hi>pi,。因?yàn)閜i的值是動態(tài)變化的,，所以hi值不能事先確定，需要隨時間進(jìn)行動態(tài)修改,?？紤]到總線仲裁過程實(shí)時性要求很高，hi值的確定不宜過于復(fù)雜,，所以本文采用線性法來設(shè)計,。對于任意Ti，hi的值由式(2)確定：
 
1.2 算法流程
    算法流程如下：
    (1)算法初始化,；
    (2)檢測是否有主設(shè)備請求總線服務(wù),，有則初始化主設(shè)備(假設(shè)為Ti)的參數(shù)(優(yōu)先級pi=pmax；切換閾值hi=hmax,；空閑時間Si),，并加入等待服務(wù)主設(shè)備隊列T′中；
    (3)對T′中的每個主設(shè)備計算Si,；
    (4)判斷總線是否正在服務(wù),，是則轉(zhuǎn)(5)，否則轉(zhuǎn)(7)；
    (5)對T′中的所有Ti,，計算Si-Sj,，結(jié)果小于0則加入就緒服務(wù)主設(shè)備隊列T″中，轉(zhuǎn)(6),；
    (6)判斷T″是否為空,，是則轉(zhuǎn)(9)，否則對T″中的每個主設(shè)備計算pi=pi-hj,，如果max(pi)>0設(shè)置Ti的優(yōu)先級最高,，減小pj，轉(zhuǎn)(7),；
    (7)對優(yōu)先級最高的Ti進(jìn)行服務(wù),，轉(zhuǎn)(8)；
    (8)修改各主設(shè)備參數(shù),，按照式(1)修改pi,，式(2)修改hi；判斷T′中的主設(shè)備是否服務(wù)完,，是則轉(zhuǎn)(9),，否則轉(zhuǎn)(2)；
    (9)算法結(jié)束,。
1.3 算法實(shí)現(xiàn)
    基于閾值的最小空閑時間優(yōu)先服務(wù)的片上總線仲裁算法由4個基本模塊組成：算法控制模塊,、優(yōu)先級調(diào)節(jié)器、帶寬調(diào)節(jié)器和總線傳輸控制器,。另外,，算法所需的主設(shè)備訪問總線特性參數(shù)（服務(wù)時間、截止時間等）和總線服務(wù)參數(shù)信息由信號提取模塊完成,，信號的控制和實(shí)際數(shù)據(jù)的傳輸由信號授權(quán)模塊完成,，其總體結(jié)構(gòu)如圖1所示。

    （1）優(yōu)先級調(diào)節(jié)器
    該模塊的主要作用是實(shí)現(xiàn)對主設(shè)備優(yōu)先級的動態(tài)調(diào)節(jié),以滿足主設(shè)備的實(shí)時性要求,。該模塊從信號提取模塊中獲得各個主設(shè)備實(shí)時性相關(guān)的參數(shù)(主設(shè)備請求總線服務(wù)時間,、最大截止時間、請求訪問從設(shè)備的地址及從設(shè)備傳輸響應(yīng)時間等),，然后進(jìn)行簡單的處理后,，傳入算法控制模塊，經(jīng)過算法控制模塊的運(yùn)算,，最終得到各個主設(shè)備調(diào)整后的優(yōu)先級。優(yōu)先級調(diào)節(jié)器根據(jù)該結(jié)果通過信號授權(quán)模塊動態(tài)調(diào)整各個主設(shè)備的優(yōu)先級,。
    （2）帶寬調(diào)節(jié)器
    該模塊的主要作用是監(jiān)視總線上主設(shè)備實(shí)際傳輸帶寬和由算法控制的應(yīng)該配置帶寬之間的變化,，實(shí)時反饋信息給算法控制模塊來保證帶寬精確分配。該模塊從信號提取模塊中獲得各個主設(shè)備帶寬要求相關(guān)的參數(shù)(主設(shè)備每次數(shù)據(jù)傳輸?shù)拈L度、主設(shè)備帶寬需求以及總線帶寬利用情況等),，然后進(jìn)行簡單的處理,，傳入算法控制模塊，經(jīng)過算法控制模塊的運(yùn)算,，最終得到各個主設(shè)備調(diào)整后的帶寬要求,，帶寬調(diào)節(jié)器根據(jù)該結(jié)果通過信號授權(quán)模塊動態(tài)調(diào)整各個主設(shè)備的帶寬配置。
    （3）總線傳輸控制器
    該模塊的主要作用是監(jiān)視總線帶寬的狀態(tài),，準(zhǔn)確預(yù)測出各設(shè)備請求的響應(yīng)時間,，并將該結(jié)果傳入算法控制模塊，經(jīng)過算法控制模塊的運(yùn)算,，得到新的總線帶寬分配方案,。總線傳輸控制器通過信號授權(quán)模塊來協(xié)調(diào)各個主設(shè)備使用總線,。
    （4）算法控制模塊
    算法控制模塊的硬件邏輯包括：時間片定時器,、判據(jù)寄存器組、比較邏輯和算法控制狀態(tài)機(jī),。其中,，判據(jù)寄存器組的初始值通過離線計算獲得，在總線服務(wù)過程時,，通過主設(shè)備特性參數(shù)提取模塊獲得實(shí)時參數(shù)值,，作為新的判據(jù)寄存器數(shù)據(jù)提供給算法控制狀態(tài)機(jī)。比較邏輯負(fù)責(zé)對算法運(yùn)行產(chǎn)生的新結(jié)果與判據(jù)寄存器組進(jìn)行比較,，并對判據(jù)寄存器組內(nèi)的數(shù)據(jù)進(jìn)行更新,。
    算法控制狀態(tài)機(jī)采用Mealy有限狀態(tài)機(jī)來實(shí)現(xiàn)總線仲裁算法流程，完成對各主設(shè)備的優(yōu)先級,、帶寬分配等屬性的動態(tài)調(diào)節(jié),。另外對各主設(shè)備請求使用總線服務(wù)進(jìn)行仲裁，實(shí)現(xiàn)各主設(shè)備協(xié)調(diào)使用總線所提供的服務(wù),。
2 實(shí)驗(yàn)及結(jié)果分析
    為驗(yàn)證基于閾值的最小空閑時間優(yōu)先服務(wù)總線仲裁器的性能,，本文對基于動態(tài)優(yōu)先級的仲裁器、基于時間輪轉(zhuǎn)的仲裁器和本文提出的仲裁器進(jìn)行了實(shí)驗(yàn),，并進(jìn)行了比較,。
2.1 實(shí)驗(yàn)平臺
    實(shí)驗(yàn)硬件平臺為Core 2 Duo CPU(主頻為2 GHz)，內(nèi)存4 GB,，操作系統(tǒng)是Windows XP,，仿真軟件使用ModelSim6.4。在實(shí)驗(yàn)平臺上,，共實(shí)現(xiàn)了6個主設(shè)備,、1個從設(shè)備和1個總線仲裁器。6個主設(shè)備的類型和相關(guān)參數(shù)如表1所示(在表1中，R表示有實(shí)時性要求,，NR表示沒有實(shí)時性要求,；B表示有帶寬要求，NB表示沒有帶寬要求),。

2.2 實(shí)驗(yàn)結(jié)果
    首先,，定義兩種性能指標(biāo)：
    (1)服務(wù)請求截止期錯失率MDP（Missed Deadline Percentage）=“所有截止期錯失的總線服務(wù)請求/所有主設(shè)備總線服務(wù)請求之和”。
    (2)服務(wù)切換次數(shù)SSN(Service Switch Num)=“從未完成的總線服務(wù)請求到搶占的總線服務(wù)請求切換次數(shù)”+“從完成總線服務(wù)請求到另一總線服務(wù)請求的切換次數(shù)”,。
    在此基礎(chǔ)上,，對表1中所示的6個主設(shè)備分別采用4種總線仲裁算法進(jìn)行仿真實(shí)驗(yàn)，得到如下結(jié)果,。
    (1)對于不同總線負(fù)載ρ
    取公式（2）中的α=5,，圖2和圖3分別表示對于不同總線負(fù)載ρ(0.5≤ρ≤2.0)情況下，4種總線仲裁算法的MDP比較,。其中圖2是在每個主設(shè)備請求100個總線服務(wù)下的MDP,，圖3是每個主設(shè)備請求200個總線服務(wù)下的MDP。從圖2和圖3中可以看出,，最小空閑時間優(yōu)先總線仲裁器得到的MDP要明顯小于其他兩種總線仲裁器,。當(dāng)ρ≤1時，最小空閑時間總線仲裁器可以保證每個主設(shè)備都滿足其總線服務(wù)截止期要求,；當(dāng)ρ>1時,，會出現(xiàn)主設(shè)備部分總線服務(wù)請求不能滿足其服務(wù)截止期要求的情況，但其MDP要明顯小于其他兩種總線仲裁器,。

    (2)對于不同比例系數(shù)α
    取ρ=1.3,，圖4和圖5分別給出了在不同比例系數(shù)α時的MDP和SSN變化情況。
    從圖4中可以看出,，對于MDP的影響,，并不是搶占次數(shù)越多（比例系數(shù)α越小）調(diào)度效果就越好,，而是當(dāng)α=12時,，MDP最小,；而當(dāng)α=1時,，MDP達(dá)到最大。從圖5中可以看出,，SSN的值隨著ρ的變大而逐漸變小,，但是，當(dāng)α的值大到一定量時,，SSN的值變化不明顯,；當(dāng)α接近1時,，SSN變化顯著。究其原因,，從公式（2）中可以看出：當(dāng)α=1時，hi=pi,，即主設(shè)備的搶占閾值等于其優(yōu)先級,，則搶占閾值就沒有起到作用，即變成了完全搶占模式,，該情況下,，主設(shè)備頻繁地?fù)屨伎偩€服務(wù)，造成過多的總線服務(wù)切換,，浪費(fèi)了總線帶寬資源,，從而影響總線服務(wù)的性能；當(dāng)α=16時主設(shè)備的搶占閾值為最高優(yōu)先級,，造成永遠(yuǎn)不能被其他主設(shè)備搶占的情況,，成為非搶占模式。以上兩種情況都會造成總線服務(wù)質(zhì)量的下降,，所以,，比例系數(shù)α的選擇應(yīng)當(dāng)保證MDP最小的情況下，相應(yīng)的SSN值不能太大,，結(jié)合圖4和圖5可以看出,，α=12為最優(yōu)比例系數(shù)。

2.3 試驗(yàn)結(jié)果分析
    在PT-LSF算法中,，總線仲裁器在收集主設(shè)備請求特性參數(shù)和總線傳輸狀態(tài)信息基礎(chǔ)上,，結(jié)合主設(shè)備請求總線服務(wù)的緩急程度來實(shí)時地改變主設(shè)備優(yōu)先權(quán)，以滿足主設(shè)備強(qiáng)實(shí)時性要求,。通過與常用的動態(tài)優(yōu)先級算法,、時間片輪轉(zhuǎn)算法和Lottery算法的實(shí)驗(yàn)分析比較可以看出，本文提出的PT-LSF算法在服務(wù)請求截止期錯失率（MDP）上有顯著優(yōu)勢,。當(dāng)總線負(fù)載在0.5～1.0范圍內(nèi)時,，PT-LSF算法的MDP值為0；當(dāng)總線負(fù)載在1.0～2.0范圍內(nèi)時,，PT-LSF算法的MDP值比時間片輪轉(zhuǎn)算法平均減少了50.8%,，比動態(tài)優(yōu)先級算法平均減少了43.6%，比Lottery算法平均減少了36.3%,。綜合對比,，PT-LSF算法的MDP比其他算法平均減少了43.8%，能很好地滿足各主設(shè)備在各種情況下的強(qiáng)實(shí)時要求,。另外,，在PT-LSF算法中,，使總線服務(wù)達(dá)到最優(yōu)時，并不是搶占次數(shù)越多（比例系數(shù)α越大）越好,，而是取一個中間合適值,。在本文中，系統(tǒng)最大優(yōu)先級為16,，最小優(yōu)先級為1,，最優(yōu)比例系數(shù)α為12，該結(jié)果為搶占閾值比例系數(shù)?琢的確定提供了實(shí)驗(yàn)依據(jù),。
    本文提出了基于最小空閑時間優(yōu)先的總線仲裁算法,，并給出了算法的實(shí)現(xiàn)流程和組成結(jié)構(gòu)。將其與動態(tài)優(yōu)先級算法,、時間片輪轉(zhuǎn)算法和Lottery算法進(jìn)行比較,。實(shí)驗(yàn)結(jié)果顯示：該總線仲裁算法在MDP方面比其他兩種算法平均減少了43.8%，能更好地保證主設(shè)備的強(qiáng)實(shí)時要求,。該總線仲裁算法對于共享總線的片上系統(tǒng)設(shè)計具有重要的參考價值,。
參考文獻(xiàn)
[1] POLETTI F，BERTOZZI D,，BENINI L,，et al.Performance analysis of arbitration policies for SoC communication architectures[J].Journal of Design Automation for Embedded  Systems，2003(8)：189-210.
[2] LISNER J C.Efficiency of dynamic arbitration in TDMA protocols[C].EDCC2005,，Berlin,，2005：91-102.
[3] ZHANG Y.Architecture and performance comparison of a statistic-based Lottery arbiter for shared bus on chip[C]. //Proceedings of Asia South Pacific Design Automation  Conference，Yokohama,，2004：1313-1316
[4] Bu-Ching Lin,，Geeng-Wei Lee，Juinn-Dar Huang,，et al.A Precise bandwidth control arbitration algorithm for hard real-time SoC buses.IEEE,，2007：165-170.
[5] 徐懿，李麗,，杜高明,，等.一款基于多處理器片上系統(tǒng)的動態(tài)自適應(yīng)仲裁器[J].計算機(jī)研究與發(fā)展，2008,，45(6)：1085-1092.
[6] 孟海波,，張志敏.基于傳輸時間精確預(yù)測的片上總線仲裁算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2008,，20(7)：830-837.