基于最小空閑時間優(yōu)先的片上總線仲裁算法

摘 要： 提出一種基于搶占閾值的最小空閑時間優(yōu)先服務的總線仲裁算法。主設備總線服務請求的空閑時間越短，獲得總線服務就越快，引入搶占閾值降低了總線服務頻繁切換造成的顛簸現(xiàn)象。實驗結果表明，該算法的MDP比常見的算法平均減少了43.8%,滿足了各主設備總線服務請求的強實時要求。
關鍵詞： 片上總線；仲裁算法；最小空閑時間優(yōu)先；搶占閾值；截止期錯失率

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

1.2 算法流程
算法流程如下：
(1)算法初始化；
(2)檢測是否有主設備請求總線服務，有則初始化主設備(假設為Ti)的參數(shù)(優(yōu)先級pi=pmax；切換閾值hi=hmax；空閑時間Si)，并加入等待服務主設備隊列T′中；
(3)對T′中的每個主設備計算Si；
(4)判斷總線是否正在服務，是則轉(5)，否則轉(7)；
(5)對T′中的所有Ti，計算Si-Sj，結果小于0則加入就緒服務主設備隊列T″中，轉(6)；
(6)判斷T″是否為空，是則轉(9)，否則對T″中的每個主設備計算pi=pi-hj，如果max(pi)>0設置Ti的優(yōu)先級最高，減小pj，轉(7)；
(7)對優(yōu)先級最高的Ti進行服務，轉(8)；
(8)修改各主設備參數(shù)，按照式(1)修改pi，式(2)修改hi；判斷T′中的主設備是否服務完，是則轉(9)，否則轉(2)；
(9)算法結束。
1.3 算法實現(xiàn)
基于閾值的最小空閑時間優(yōu)先服務的片上總線仲裁算法由4個基本模塊組成：算法控制模塊、優(yōu)先級調(diào)節(jié)器、帶寬調(diào)節(jié)器和總線傳輸控制器。另外，算法所需的主設備訪問總線特性參數(shù)（服務時間、截止時間等）和總線服務參數(shù)信息由信號提取模塊完成，信號的控制和實際數(shù)據(jù)的傳輸由信號授權模塊完成，其總體結構如圖1所示。

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

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

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

2.3 試驗結果分析
在PT-LSF算法中，總線仲裁器在收集主設備請求特性參數(shù)和總線傳輸狀態(tài)信息基礎上，結合主設備請求總線服務的緩急程度來實時地改變主設備優(yōu)先權，以滿足主設備強實時性要求。通過與常用的動態(tài)優(yōu)先級算法、時間片輪轉算法和Lottery算法的實驗分析比較可以看出，本文提出的PT-LSF算法在服務請求截止期錯失率（MDP）上有顯著優(yōu)勢。當總線負載在0.5～1.0范圍內(nèi)時，PT-LSF算法的MDP值為0；當總線負載在1.0～2.0范圍內(nèi)時，PT-LSF算法的MDP值比時間片輪轉算法平均減少了50.8%，比動態(tài)優(yōu)先級算法平均減少了43.6%，比Lottery算法平均減少了36.3%。綜合對比，PT-LSF算法的MDP比其他算法平均減少了43.8%，能很好地滿足各主設備在各種情況下的強實時要求。另外，在PT-LSF算法中，使總線服務達到最優(yōu)時，并不是搶占次數(shù)越多（比例系數(shù)α越大）越好，而是取一個中間合適值。在本文中，系統(tǒng)最大優(yōu)先級為16，最小優(yōu)先級為1，最優(yōu)比例系數(shù)α為12，該結果為搶占閾值比例系數(shù)?琢的確定提供了實驗依據(jù)。
本文提出了基于最小空閑時間優(yōu)先的總線仲裁算法，并給出了算法的實現(xiàn)流程和組成結構。將其與動態(tài)優(yōu)先級算法、時間片輪轉算法和Lottery算法進行比較。實驗結果顯示：該總線仲裁算法在MDP方面比其他兩種算法平均減少了43.8%，能更好地保證主設備的強實時要求。該總線仲裁算法對于共享總線的片上系統(tǒng)設計具有重要的參考價值。
參考文獻
[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)自適應仲裁器[J].計算機研究與發(fā)展，2008，45(6)：1085-1092.
[6] 孟海波，張志敏.基于傳輸時間精確預測的片上總線仲裁算法[J].計算機輔助設計與圖形學學報，2008，20(7)：830-837.