陳利平，高金華

(湖南工學(xué)院計算機(jī)與信息科學(xué)系，衡陽421002)

1 引言

多處理器片上系統(tǒng)(MPSOC)一般由多個處理器單元、專用功能模塊甚至混和信號電路組成，構(gòu)建一個復(fù)雜的集成計算系統(tǒng)，從而滿足市場對于系統(tǒng)在計算性能、功耗、實時性與成本等方面的需求。MPSOC不是簡單的片上多處理器(chip multiprocessor)，后者強(qiáng)調(diào)將更多的處理器放在單片上以提高單位面積晶體管密度，并不考慮平衡應(yīng)用的需求。MPSOC則通過定制體系結(jié)構(gòu)來滿足不同應(yīng)用在成本和功耗等方面的需求，已廣泛地用于通信、消費類電子產(chǎn)品和網(wǎng)絡(luò)多媒體等諸多領(lǐng)域［1］。

MPSOC的性能主要取決于處理器之間的高效通信和其計算量的平衡分配，而不僅僅是單個處理器的速度。盡管對于MPSOC目前有很多可供選擇的通信架構(gòu)，共享總線架構(gòu)仍然是小規(guī)模MPSOC的常用方案，因為它簡單，硬件消耗少而且面積效率高。在基于總線的系統(tǒng)中，仲裁器是決定系統(tǒng)性能的關(guān)鍵部分，它負(fù)責(zé)分配各個處理器訪問共享資源的優(yōu)先級，有效的競爭解決機(jī)制必須合理地分配和控制各個處理器占據(jù)的總線帶寬，避免低優(yōu)先級傳輸?shù)酿囸I現(xiàn)象。首先介紹了MPSOC仲裁算法領(lǐng)域目前的研究狀況，針對靜態(tài)［2］、動態(tài)［3］、實時［4］的lottery總線仲裁算法進(jìn)行了分析，并在高性能的基礎(chǔ)上進(jìn)行改進(jìn)，提出一款算法簡單的基于ATM交換架構(gòu)的實時Lottery bus仲裁機(jī)制。它為兩級仲裁機(jī)制，第一級為實時處理;第二級為基于ATM交換機(jī)制的lottery bus仲裁，它基于概率總線分配算法，可以解決lottery總線存在的問題。

2 背景及相關(guān)研究

常用的仲裁算法有固定優(yōu)先級、時分復(fù)用、Lottery、RT －Lottery、動態(tài)自適用。

2.1 固定優(yōu)先級仲裁算法

固定優(yōu)先級仲裁算法大量應(yīng)用于現(xiàn)代總線中［5］。在該仲裁方法中每個處理器訪問共享資源的優(yōu)先級是固定的，傳輸任務(wù)較重的主設(shè)備優(yōu)先級相對較高，如果幾個總線主設(shè)備同時申請總線使用權(quán)，優(yōu)先級高的設(shè)備將獲取控制權(quán)。這種仲裁算法的優(yōu)點在于設(shè)計簡單，硬件消耗小，容易實現(xiàn);缺點是它缺乏對總線資源分配的控制，低優(yōu)先級的主設(shè)備等待時間過長，容易造成饑餓現(xiàn)象。

2.2 時分復(fù)用仲裁算法

時分復(fù)用仲裁算法(Time division multiplexed TDM)［6］是將總線上的使用時間分成時段，再把時段分配給要求使用總線的主設(shè)備。有時，某主設(shè)備對總線使用的申請可能需要多個時段來完成所有要求的傳輸;然而，在該結(jié)構(gòu)中，該主設(shè)備只能通過使用兩級仲裁協(xié)議交替地訪問總線來完成所要求的傳輸。第1級仲裁采用時間段輪轉(zhuǎn)的方式來選擇相應(yīng)的主設(shè)備，如果一個主設(shè)備在它的保留時段中沒有申請使用總線，第2級仲裁機(jī)制會將該時段分配給其他發(fā)出請求而且優(yōu)先級最高的主設(shè)備。這種仲裁算法的優(yōu)點是容易實現(xiàn);缺點是導(dǎo)致數(shù)據(jù)傳輸錯誤，高優(yōu)先級設(shè)備的總線等待時間過長。

2.3 靜態(tài)的Lottery總線仲裁

Lottery［2］總線的核心是采用加權(quán)隨機(jī)算法的“Lottery仲裁器”，總線上每個主設(shè)備固定分配一定數(shù)量的“彩票(ticket)”，“彩票”越多，該主設(shè)備被授權(quán)的概率越大，如圖1所示。如果仲裁器產(chǎn)生的隨機(jī)數(shù)是某個主設(shè)備所持“彩票”，則該設(shè)備就獲得總線使用權(quán)。各主設(shè)備Ci獲得總線授權(quán)的概率如式(1)所示:

其中 t1，t2，…，tn依次為主設(shè)備 1，2，…，n 的“彩票”數(shù)，r1，r2，…，tn是一系列布爾類型的變量，表示各個設(shè)備發(fā)出請求的情況。如有請求，ri=1，否則 ri為0。

Lottery Bus機(jī)制允許Master設(shè)備發(fā)出多字請求，同時為了避免其中某一Master設(shè)備獨占總線，還設(shè)定了最大總線占用周期以限制最大傳輸量。靜態(tài)的lottery總線仲裁的優(yōu)點是可以很好地控制網(wǎng)絡(luò)交換應(yīng)用的帶寬分配和公平的平均反應(yīng)時延，缺點是沒有硬實時考慮、不能獨立控制響應(yīng)時延和帶寬分配。

圖1 靜態(tài)Lottery bus仲裁機(jī)制示例

2.4 動態(tài)的Lottery總線仲裁

動態(tài)Lottery總線仲裁器［3］如圖2所示，增加了各總線主設(shè)備的“彩票”數(shù)目ti作為輸入，而且每個響應(yīng)的主設(shè)備當(dāng)前擁有的彩票數(shù)目是由彩票產(chǎn)生器產(chǎn)生的。在該機(jī)構(gòu)中，不僅當(dāng)前的彩票范圍是動態(tài)變化的，而且可以選任意值;而靜態(tài)lottery中，彩票是固定的。Lottery仲裁器用來分配和控制每個主設(shè)備占用的總線帶寬。線性反饋移位寄存器(LFSR)用來產(chǎn)生要求范圍之內(nèi)的隨機(jī)數(shù)，從而保證每個主設(shè)備都有一定的概率被授權(quán)，防止饑餓現(xiàn)象。采用該仲裁方法使得高優(yōu)先級設(shè)備在不同的請求序列中響應(yīng)延遲較小，而優(yōu)先級較低的設(shè)備總線延遲偏長，而且在各個主設(shè)備傳輸負(fù)載相差較大的情況下，由于實際運行下各處理器的傳輸負(fù)載可能超過或不足于請求的情況，它們實際分配到的總線帶寬并不符合預(yù)先設(shè)定的值，如果偽隨機(jī)數(shù)大于總彩票數(shù)時，則所有的主設(shè)備都不能獲得授權(quán)信號。

文獻(xiàn)［5］中提到一種基于Lottery總線的滿足所有硬實時性要求的仲裁算法 RT－Lottery，而文獻(xiàn)［6－7］則提出了其他改進(jìn)型 Lottery總線仲裁器來減小總線緩存大小或者提高總線帶寬控制能力等。它們的算法都較為復(fù)雜，增加了設(shè)計電路的難度和仲裁器所消耗的硬件資源。文獻(xiàn)［8］提出的動態(tài)自適應(yīng)仲裁器算法簡單易于設(shè)計，提高了系統(tǒng)性能，減少了處理器平均等待時間和最大等待時間，但沒有針對實時性進(jìn)行設(shè)計。

圖2 動態(tài)Lottery bus仲裁機(jī)制示例

3 實時動態(tài)自適應(yīng)機(jī)制

Lottery總線采用了高效的仲裁機(jī)制并能有效控制總線各主設(shè)備所占總線帶寬，但是預(yù)先為每個設(shè)備設(shè)定準(zhǔn)確的“彩票”數(shù)是很困難的。因此本文提出了硬實時和自適應(yīng)的動態(tài)調(diào)整“彩票”數(shù)的方法，以期改進(jìn)標(biāo)準(zhǔn)Lottery總線的仲裁機(jī)制。

3.1 實時自適應(yīng)仲裁機(jī)制

Lottery概念仲裁算法不能處理硬實時請求，因此提出一個兩級的仲裁算法——實時自適用ATM交換機(jī)制。第一級為硬實時處理器，用來處理硬實時請求;第二級為動態(tài)自適用ATM交換機(jī)制，用來處理總線的帶寬，可根據(jù)當(dāng)前總線傳輸情況自動調(diào)節(jié)各個處理器占據(jù)的總線帶寬。

3.2 模擬模型

在該模型中，假定主設(shè)備擁有總線時，其它主設(shè)備不能訪問總線;直到擁有總線的主設(shè)備釋放總線，其它主設(shè)備才能訪問總線;每個處理是非搶占式的。如圖3所示的系統(tǒng)架構(gòu)中，有四個主設(shè)備，每個主設(shè)備都有交通發(fā)生器，每個發(fā)生器的動作是由設(shè)計者給定的。仲裁器從所有主設(shè)備收到請求后，再決定授權(quán)給哪一個主設(shè)備。

圖3 二級硬實時鐘裁模型

從每一個主設(shè)備發(fā)出的交通信號有四種:

(1)Rcycles(實時周期)

這是主設(shè)備在時鐘周期的實時請求，對于大多數(shù)沒有實時請求的主設(shè)備不必定義。

(2)跳數(shù)和概率

它定義由主設(shè)備發(fā)出的觸發(fā)數(shù)的概率。

(3)間隔周期和概率

它由主設(shè)備發(fā)出的兩個相繼請求之間的間隔時間決定，但決定間隔時間的規(guī)則是隨主設(shè)備的不同類型而變化的。

(4)主設(shè)備類型

根據(jù)交通行為主設(shè)備分為三種類型:

·D 型( 依賴類型)

D 型主設(shè)備沒有實時請求，且下一個請求的發(fā)出必須依賴當(dāng)前請求的完成時間。對于D 型主設(shè)備，兩個相繼請求的間隔時間是從前一次請求的發(fā)出時間到后一個請求的完成時間。在時鐘周期2中，假定交通發(fā)生器產(chǎn)生一個4 跳的觸發(fā)，而這個請求直到時鐘周期5 才被授權(quán)，時鐘周期9 完成。若間隔時間是10，則下一個請求是在時鐘周期19 發(fā)出( 后者請求的發(fā)出時間是前者請求的完成時間加10 個時鐘周期) 。

·D－R型(實時依賴型)

D－R型主設(shè)備除了和D型有相同的依賴之外，它還有實時請求。主設(shè)備有實時請求，Rcycles為10，因此請求在時鐘周期2發(fā)出，則它一定在時鐘周期12完成(2+Rcycles=12)。如果這個請求不能在時鐘周期12之前完成，它就違反了實時規(guī)則。

·ND－R型(實時非依賴型)

ND－R型主設(shè)備請求的發(fā)出時間是不依賴于前一個請求的完成時間，且間隔時間是兩個相繼請求的時鐘周期。如圖所示，假設(shè)間隔時間是15，第二個請求是在時鐘周期17發(fā)出，它直接依賴于第一個請求的發(fā)出時間(時鐘周期2)，而不是完成時間(時鐘周期9)。因此，當(dāng)前的請求一定在下一個請求之前完成，Rcycles的合理值應(yīng)該小于最小間隔時間，使設(shè)計者重置較緊的實時請求。為了確保合理的 Rcycles，定義 Rcycles=Min(tmin－interval，tuser－given)，tmin－interval是最小可能的間隔時間，tuser－given是設(shè)計者給定的實時請求。

3.3 實時處理

實時處理根據(jù)實時請求為主設(shè)備設(shè)置實時計數(shù)器，當(dāng)一個主設(shè)備發(fā)出請求時，響應(yīng)的實時計數(shù)器就設(shè)置為主設(shè)備的Rcycles，實時計數(shù)器每時鐘周期遞減1，直到該主設(shè)備被授權(quán)為止。警告期是一個全局常量，用來提醒仲裁者授權(quán)給最緊迫的主設(shè)備。如果響應(yīng)的實時計數(shù)器在警告期以下，則該主設(shè)備將有較高的優(yōu)先級，當(dāng)兩個或多個實時計數(shù)器的主設(shè)備獲得授權(quán)，如圖4所示，當(dāng)M1在時鐘周期3發(fā)出請求，M1的實時計數(shù)器就設(shè)為30(Rcycles=30)，所有其它的主設(shè)備在此時發(fā)出請求，而只有M2的實時計數(shù)器在警告期以下，則M2首先被授權(quán)。M2的請求是8跳觸發(fā)，該請求在時鐘周期11完成，此時，其它發(fā)出請求的主設(shè)備的實時計數(shù)器遞減8，M1和M3的實時計數(shù)器同時在警告期以下，而M3的實時計數(shù)器較小，因此，M3獲得授權(quán)。

圖4 M1的Rcycles=30，Warning－line=20的實時處理圖

由上式可知:在最壞情況下，有最大跳數(shù)的D型主設(shè)備發(fā)出最大跳數(shù)請求時可獲得授權(quán);在下個時鐘周期，有實時請求的其它主設(shè)備都發(fā)出請求，在D型主設(shè)備請求完成后，一定要保證滿足這些主設(shè)備的請求。

3.4 動態(tài)自適用ATM交換仲裁機(jī)制

在該仲裁機(jī)制中，仲裁器的輸入?yún)?shù)為請求、彩票、自適用信號三個。請求和彩票是靜態(tài)總線分配的輸入;自適用信號作為附加輸入，常用來提高總線授權(quán)的概率。這個自適用信號是從因該主設(shè)備傳輸任務(wù)較重而需要比其它主設(shè)備多授權(quán)而發(fā)出的，如圖5所示。我們不知道哪個IP用在高級的SOC設(shè)計的共享總線上，因此自適應(yīng)信號給定具體參數(shù)。主設(shè)備計算存儲ATM信元的緩沖位置，如果數(shù)據(jù)接近極限量時，產(chǎn)生自適用信號提高命中概率，則主設(shè)備Ci獲得授權(quán)的概率如(2)式。

上式顯示了每個主設(shè)備的共享總線概率。待處理的請求和彩票值常用來獲得每一個主設(shè)備Ci的共享概率，為了提高主設(shè)備的授權(quán)概率，ai可從查找表獲得，并與要完成請求的主設(shè)備請求進(jìn)行比特法與操作，ai是附加的彩票值，用來解決總裁判值小于偽隨機(jī)數(shù)時，以優(yōu)先級倒置方式將總線分配給主設(shè)備。

ATM交換機(jī)制的優(yōu)點是自適用信號解決了偽隨機(jī)數(shù)大于總彩票值時線性反饋移位寄存器(LFSR)特征消失的問題。

4 仿真平臺和結(jié)果

為驗證實時動態(tài)自適用ATM交換仲裁器的性能，本文用VHDL來設(shè)計靜態(tài)Lottery總線仲裁器、動態(tài)Lottery總線仲裁器和硬實時動態(tài)自適用ATM交換仲裁器(見圖5)，并使用VHDK測試平臺測試3種仲裁機(jī)制的性能參數(shù)，測試時，數(shù)據(jù)的長度未考慮，并假設(shè)只有一個時鐘周期，模擬結(jié)果如表1所示。

圖5 ATM交換仲裁器結(jié)構(gòu)示意

表1中對不同仲裁機(jī)制的每個主設(shè)備的平均時延，平均等待時間，平均帶寬，實時性能和帶寬性能等做了比較。綜合以上的實驗結(jié)果，采用實時ATM交換仲裁機(jī)制性能是最佳的，它不僅考慮了實時要求，而且考慮了帶寬要求，并減少了平均時延、平均等待時間，提高了資源的整體運行效率，從而改善了系統(tǒng)性能。

表1 綜合性能比較

5 結(jié)論

靜態(tài)lottery總線機(jī)制和動態(tài)lottery總線機(jī)制可以解決優(yōu)先級算法的問題，而lottery總線機(jī)制也有一些缺點。實時ATM交換機(jī)制是基于概率總線分配算法，它不僅考慮了實時要求，同時也考慮了帶寬要求，還解決了偽隨機(jī)數(shù)大于總彩票值時線性反饋移位寄存器(LFSR)特征消失的問題。這種機(jī)制可用VHDL建模，提供的模擬結(jié)果表明，硬實時ATM交換機(jī)制可以減少49%的總線請求延遲。

［1］Abmed Jerraya，Hannu Tenbunen，Wayne Wolf.Multiprocessor systems－ on － chips［J］.IEEE Computer，2005，38(7):36－40.

［2］K Lahiri，A Raghunathan.The LOTTERY BUS on － chip communication architecture［C］.Trans.On VLSI system，June 2006 IEEE.

［3］Dinesh Padole，P R Bajaj，et al.Dynamic Lottery Bus Arbiter for Shared Bus－System on－chip:A Design Approach with VHDL［C］.First international conference on Emerging Trends in Engineering and Technology 2008 IEEE.

［4］C Chen，G Lee，J Huang，et al.A real－ time and bandwidth guaranteed arbitration algorithm for SOC bus communication［C］.Asia and South Pacific Design Automation Conference，Yokohama，Japan，2006.

［5］K A Kettler，J P Lehoezky，J K Ttrosnider.Modeling bus scheduling policies for real－ time systems［C］.The 16th IEEE Real－ Time Systems Symposium，Oakland，USA，1995.

［6］F Poletti，D Bertozzi，L Benini，A Bogliolo.Performance Analysis of Arbitration Policies for SoC Communication Architectures［J］.Journal of Design Automation for Embedded Systems，2003:618 －621.

［7］潘杰，胡丹，張志敏.LotteryBus的設(shè)計與實現(xiàn)［J］.微電子學(xué)與計算機(jī)，2005，22(7):76 －78.

［8］徐懿，李麗，杜高明，等.一款基于多處理器片上系統(tǒng)的動態(tài)自適用仲裁器［J］.計算機(jī)研究與發(fā)展，2008，45(6):1085－1092.