總線任務(wù)隨機(jī)調(diào)度技術(shù)研究

陶永耀 陽昕 趙新中

炬力集成電路設(shè)計(jì)有限公司, 廣東 珠海 郵政編碼 519085

引言

多媒體處理器要肩負(fù)著大量的音視頻數(shù)據(jù)存取任務(wù)。大量多媒體數(shù)據(jù)讀寫任務(wù)將周期性頻繁出現(xiàn)，當(dāng)某一任務(wù)被執(zhí)行時(shí)，就會相應(yīng)延遲了總線對其他任務(wù)的響應(yīng)[1]。因此，研究如何在多媒體處理器總線對多媒體處理任務(wù)的調(diào)度十分必要而且迫切。

調(diào)度的方法有很多文獻(xiàn)[2-5]進(jìn)行了研究，其主要的關(guān)注點(diǎn)在于制定優(yōu)先級別和制定公平性原則。但這兩者往往是矛盾的。以優(yōu)先級別為主的原則，優(yōu)先級別高的任務(wù)會占據(jù)了大量的處理器時(shí)間和資源，導(dǎo)致其余低級別任務(wù)無法被服務(wù)。而以公平性為主的原則，會忽略任務(wù)的重要性，每種類型的任務(wù)都按平均時(shí)間進(jìn)行服務(wù)，這無疑是會把一些不重要的任務(wù)搶先占據(jù)處理器的時(shí)間和資源。

本文主要研究如何兼顧考慮優(yōu)先級別和公平性原則，并調(diào)度決策過程引入隨機(jī)性因素，避免瞬時(shí)任務(wù)激增的情況影響。

1 加權(quán)公平調(diào)度

在多媒體處理器的任務(wù)隊(duì)列中，如不采用專門的調(diào)度機(jī)制，則以先來先服務(wù)的原則進(jìn)行處理。先來先服務(wù)最大的缺點(diǎn)就是缺少時(shí)間敏感性，排在長任務(wù)后面的短任務(wù)要等待很長的時(shí)間。為此，在先來先服務(wù)的基礎(chǔ)上可以增加按優(yōu)先級排隊(duì)的原則，就能使優(yōu)先級高的任務(wù)優(yōu)先得到服務(wù)。但是，這種按優(yōu)先級排隊(duì)的方式也會帶來一個(gè)問題，就是在高優(yōu)先級隊(duì)列中有任務(wù)時(shí)，低優(yōu)先級隊(duì)列中的任務(wù)就長期得不到服務(wù)。這導(dǎo)致了不公平。

為了兼顧優(yōu)先級和公平性，本文提出了加權(quán)公平調(diào)度方式。即對每種優(yōu)先級的任務(wù)設(shè)置一個(gè)隊(duì)列，對隊(duì)列i指派一個(gè)權(quán)重wi，于是隊(duì)列i得到的平均服務(wù)時(shí)間為wi/∑wi。這樣，多媒體處理器總線的數(shù)據(jù)率為R，那么隊(duì)列i將得到的有保證數(shù)據(jù)率Ri為

2 隨機(jī)性權(quán)重

由于多媒體處理器的總線上任務(wù)不斷會發(fā)生變化，導(dǎo)致了每個(gè)隊(duì)列中的任務(wù)數(shù)量也時(shí)刻變化。因此，預(yù)先給每個(gè)隊(duì)列指派一個(gè)固定的權(quán)重，會給往后的任務(wù)調(diào)度造成影響。我們設(shè)計(jì)出一種新的隨機(jī)性權(quán)重指派方法。

對隊(duì)列i，先指派一個(gè)值相對較大的權(quán)重wi，按總線調(diào)度的每個(gè)時(shí)刻計(jì)算概率pi，即

其中， 是概率pi的最大值，Liav是隊(duì)列i的平均隊(duì)列長度，Tmax和Tmin是平均隊(duì)列長度的兩個(gè)閾值。

這里采用平均隊(duì)列長度的意義在于克服多媒體處理器瞬時(shí)任務(wù)激增情況導(dǎo)致的調(diào)度算法執(zhí)行不穩(wěn)定。其計(jì)算方式如下

Liav=(1-δ)×歷史的Liav+δ×當(dāng)前隊(duì)列長度Li （3）

δ為0到1之間的數(shù)。

按以上原則，可以分析概率的變化如圖1所示

圖1 概率p的計(jì)算方式

最后，隊(duì)列i將得到的有保證數(shù)據(jù)率Ri修改為

3 結(jié)束語

本文主要研究了多媒體處理器在總線任務(wù)調(diào)度時(shí)的原則與技術(shù)，提出了加權(quán)公平調(diào)度和隨機(jī)性加權(quán)公平調(diào)度兩種技術(shù)方案，為芯片處理低功耗發(fā)揮作用。

[1]T.D.Riehardson, C.NicoPoulos, P.Dongkook,etal. A Hy-brid SoC Interconnect with Dynamie TDMA-Based Transaction-Less Buses and On-ChiP Networks[C].Pro-ceeding of the 19th International Conference on VLSI De-sign, Hyderabad, India, Jan 3-7, IEEE,2006, pp. 657-664.

[2]王知學(xué)嵌入式操作系統(tǒng)調(diào)度算法研究[D].北京中國科學(xué)院自動化研究所博士學(xué)位論文，2003

[3]Chen J Y,Jone W B,Wang J S,et al, Segmented Bus De-sign for Low-Power System[J]. IEEE Transactions on VLSI Systems, vol.7, no.1, 25-29,1999

[4]陳琳，汪健甄，安萬先，熊華鋼.多路數(shù)據(jù)總線任務(wù)調(diào)度和仿真評價(jià)技術(shù)[J]. 電光與控制，2005，第2期,22-26

[5]陳科明，劉鵬，王維東，姚慶棟.用于多處理器媒體SOC設(shè)計(jì)的實(shí)時(shí)總線調(diào)度優(yōu)化策略[J].浙江大學(xué)學(xué)報(bào)，Vol.41，No.9, 2007, 1546-1551