總線任務隨機調度技術研究

陶永耀 陽昕 趙新中

炬力集成電路設計有限公司, 廣東 珠海 郵政編碼 519085

引言

多媒體處理器要肩負著大量的音視頻數據存取任務。大量多媒體數據讀寫任務將周期性頻繁出現，當某一任務被執行時，就會相應延遲了總線對其他任務的響應[1]。因此，研究如何在多媒體處理器總線對多媒體處理任務的調度十分必要而且迫切。

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

本文主要研究如何兼顧考慮優先級別和公平性原則，并調度決策過程引入隨機性因素，避免瞬時任務激增的情況影響。

1 加權公平調度

在多媒體處理器的任務隊列中，如不采用專門的調度機制，則以先來先服務的原則進行處理。先來先服務最大的缺點就是缺少時間敏感性，排在長任務后面的短任務要等待很長的時間。為此，在先來先服務的基礎上可以增加按優先級排隊的原則，就能使優先級高的任務優先得到服務。但是，這種按優先級排隊的方式也會帶來一個問題，就是在高優先級隊列中有任務時，低優先級隊列中的任務就長期得不到服務。這導致了不公平。

為了兼顧優先級和公平性，本文提出了加權公平調度方式。即對每種優先級的任務設置一個隊列，對隊列i指派一個權重wi，于是隊列i得到的平均服務時間為wi/∑wi。這樣，多媒體處理器總線的數據率為R，那么隊列i將得到的有保證數據率Ri為

2 隨機性權重

由于多媒體處理器的總線上任務不斷會發生變化，導致了每個隊列中的任務數量也時刻變化。因此，預先給每個隊列指派一個固定的權重，會給往后的任務調度造成影響。我們設計出一種新的隨機性權重指派方法。

對隊列i，先指派一個值相對較大的權重wi，按總線調度的每個時刻計算概率pi，即

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

這里采用平均隊列長度的意義在于克服多媒體處理器瞬時任務激增情況導致的調度算法執行不穩定。其計算方式如下

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

δ為0到1之間的數。

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

圖1 概率p的計算方式

最后，隊列i將得到的有保證數據率Ri修改為

3 結束語

本文主要研究了多媒體處理器在總線任務調度時的原則與技術，提出了加權公平調度和隨機性加權公平調度兩種技術方案，為芯片處理低功耗發揮作用。

[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]王知學嵌入式操作系統調度算法研究[D].北京中國科學院自動化研究所博士學位論文，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]陳琳，汪健甄，安萬先，熊華鋼.多路數據總線任務調度和仿真評價技術[J]. 電光與控制，2005，第2期,22-26

[5]陳科明，劉鵬，王維東，姚慶棟.用于多處理器媒體SOC設計的實時總線調度優化策略[J].浙江大學學報，Vol.41，No.9, 2007, 1546-1551