多處理器片上系統(tǒng)中實(shí)時(shí)自適用仲裁器的設(shè)計(jì)與分析*

陳利平，高金華

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 模擬模型

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

圖3 二級(jí)硬實(shí)時(shí)鐘裁模型

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

(1)Rcycles(實(shí)時(shí)周期)

這是主設(shè)備在時(shí)鐘周期的實(shí)時(shí)請(qǐng)求，對(duì)于大多數(shù)沒(méi)有實(shí)時(shí)請(qǐng)求的主設(shè)備不必定義。

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

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

(3)間隔周期和概率

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

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

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

·D 型( 依賴(lài)類(lèi)型)

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

·D－R型(實(shí)時(shí)依賴(lài)型)

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

·ND－R型(實(shí)時(shí)非依賴(lài)型)

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

3.3 實(shí)時(shí)處理

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

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

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

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

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

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

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

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

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

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

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

表1 綜合性能比較

5 結(jié)論

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

［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è)計(jì)與實(shí)現(xiàn)［J］.微電子學(xué)與計(jì)算機(jī)，2005，22(7):76 －78.

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