多處理器片上系統中實時自適用仲裁器的設計與分析*

陳利平，高金華

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

1 引言

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

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

2 背景及相關研究

常用的仲裁算法有固定優先級、時分復用、Lottery、RT －Lottery、動態自適用。

2.1 固定優先級仲裁算法

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

2.2 時分復用仲裁算法

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

2.3 靜態的Lottery總線仲裁

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

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

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

圖1 靜態Lottery bus仲裁機制示例

2.4 動態的Lottery總線仲裁

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

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

圖2 動態Lottery bus仲裁機制示例

3 實時動態自適應機制

Lottery總線采用了高效的仲裁機制并能有效控制總線各主設備所占總線帶寬，但是預先為每個設備設定準確的“彩票”數是很困難的。因此本文提出了硬實時和自適應的動態調整“彩票”數的方法，以期改進標準Lottery總線的仲裁機制。

3.1 實時自適應仲裁機制

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

3.2 模擬模型

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

圖3 二級硬實時鐘裁模型

從每一個主設備發出的交通信號有四種:

(1)Rcycles(實時周期)

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

(2)跳數和概率

它定義由主設備發出的觸發數的概率。

(3)間隔周期和概率

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

(4)主設備類型

根據交通行為主設備分為三種類型:

·D 型( 依賴類型)

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

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

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

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

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

3.3 實時處理

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

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

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

3.4 動態自適用ATM交換仲裁機制

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

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

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

4 仿真平臺和結果

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

圖5 ATM交換仲裁器結構示意

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

表1 綜合性能比較

5 結論

靜態lottery總線機制和動態lottery總線機制可以解決優先級算法的問題，而lottery總線機制也有一些缺點。實時ATM交換機制是基于概率總線分配算法，它不僅考慮了實時要求，同時也考慮了帶寬要求，還解決了偽隨機數大于總彩票值時線性反饋移位寄存器(LFSR)特征消失的問題。這種機制可用VHDL建模，提供的模擬結果表明，硬實時ATM交換機制可以減少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的設計與實現［J］.微電子學與計算機，2005，22(7):76 －78.

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