王永博，楊明，趙冬媛

(遼寧大學(xué)信息學(xué)院，遼寧沈陽(yáng)110036)

現(xiàn)代多媒體、數(shù)字信號(hào)處理器和數(shù)據(jù)傳輸都有非常密集的數(shù)據(jù)處理要求。使用單一處理器并不能滿足總的數(shù)據(jù)處理能力要求，而使用多處理器又會(huì)受到多方面的限制，如系統(tǒng)面積、能耗大小、系統(tǒng)上市時(shí)間等。數(shù)據(jù)處理能力需求與系統(tǒng)限制之間的平衡要求，促進(jìn)了自動(dòng)化式系統(tǒng)設(shè)計(jì)的產(chǎn)生和發(fā)展。自動(dòng)化式系統(tǒng)設(shè)計(jì)主要是指軟硬件協(xié)同設(shè)計(jì)，主要包括3個(gè)部分：第一，選擇系統(tǒng)使用的處理器元件(ASIC或者通用CPU);第二，分配所有任務(wù)到具體的處理器件，并建立處理器件間的通訊連接結(jié)構(gòu);第三，安排所有任務(wù)的開(kāi)始和結(jié)束時(shí)間，即時(shí)間調(diào)度。由于處理分配和調(diào)度安排是熟悉的NP-Compelete[1-2]結(jié)構(gòu)，因此本文在多處理器任務(wù)的分配和調(diào)度中使用啟發(fā)式算法。

若提高處理能力需要系統(tǒng)進(jìn)行流水式的快速執(zhí)行，而僅僅在必備的執(zhí)行環(huán)節(jié)使用硬件，則不能滿足增長(zhǎng)的處理能力要求，因此處理器件需要被安排到并行的執(zhí)行平臺(tái)[3]。很多算法被引入到含有選擇處理器件和映射任務(wù)的軟硬件協(xié)同設(shè)計(jì)當(dāng)中，但是它們往往受限于單CPU和共用總線結(jié)構(gòu)[4]。本文提供了一種用于處理器件分配和流水化式處理的算法。該算法基于任務(wù)的優(yōu)先級(jí)，交替進(jìn)行器件選擇和任務(wù)映射，把流水化平臺(tái)建立在分配處理過(guò)程當(dāng)中，避免了冗余平臺(tái)的殘留。

1 已有算法簡(jiǎn)介

Wolf提出了一種結(jié)構(gòu)協(xié)同算法[5]。其算法以不規(guī)則的拓?fù)浞植紴槟繕?biāo)，能夠處理多CPU和多硬件協(xié)同問(wèn)題。首先，所有的任務(wù)映射到最快的處理器件上;然后，重新分配任務(wù)，目標(biāo)設(shè)為減少數(shù)據(jù)傳輸量;最后，數(shù)據(jù)傳輸通道被分配到處理器件間的通訊上。該算法很好地區(qū)分了選擇和分配過(guò)程。但是增加硬件有可能降低效率，因?yàn)橛布?jīng)常是滿負(fù)荷工作，而且很可能永遠(yuǎn)不能從系統(tǒng)中移除出去。任務(wù)未進(jìn)行流水化的處理，因此不能滿足高數(shù)據(jù)量處理能力的要求。

Bakshi和Gajski提出的協(xié)同算法是首先將任務(wù)分配到硬件上，不考慮其他任何參數(shù)，然后軟件處理器被盡可能地搜索。當(dāng)任務(wù)不能被安排在當(dāng)前流水平臺(tái)時(shí)，該算法會(huì)創(chuàng)建新的流水平臺(tái)。該算法的問(wèn)題在于，對(duì)于給定的任務(wù)不能使任務(wù)安排器件在軟件和硬件間交換。算法沒(méi)有考慮增加一個(gè)CPU的硬件成本，不同任務(wù)的數(shù)據(jù)傳輸時(shí)間有時(shí)會(huì)超過(guò)任務(wù)執(zhí)行時(shí)間。該算法還忽略了任務(wù)的傳輸時(shí)間。

另一種協(xié)同算法是由Chatha和Vemuri[4]提出。該算法以數(shù)據(jù)流應(yīng)用為目標(biāo)，分支和邊界的劃分是算法的中心。啟發(fā)式的方法用于初始系統(tǒng)劃分，然后用分支和邊界算法探測(cè)軟硬件選擇。該算法為流水式，通過(guò)啟發(fā)的方式選擇數(shù)據(jù)相關(guān)性，之后創(chuàng)建流水平臺(tái)，這樣能夠減少流水式緩沖需要的內(nèi)存。然而任務(wù)的分配和流水化沒(méi)有考慮相互的作用，流水化沒(méi)有考慮目標(biāo)時(shí)間，因此該算法執(zhí)行后有可能產(chǎn)生冗余的流水平臺(tái)。另外，該算法只考慮系統(tǒng)中一個(gè)軟件處理器，并受到分支和邊界劃分法采用的指數(shù)時(shí)間限制。

2 處理器件選擇、任務(wù)分配以及流水化

本文提出的算法，把任務(wù)劃分為軟件或硬件執(zhí)行，其過(guò)程包括處理器件的選擇(軟件或者硬件)和任務(wù)的分配，而且建立了流水平臺(tái)，以滿足較高的數(shù)據(jù)處理能力約束。

2.1 處理器件選擇

處理器件選擇是本文算法的第一步。根據(jù)軟件和硬件對(duì)系統(tǒng)的性能影響和面積消耗，選擇軟件或者硬件添加到系統(tǒng)中。選擇過(guò)程對(duì)所有可能選項(xiàng)計(jì)算選擇系數(shù)，選擇系數(shù)包含2個(gè)因子：性能提高因子和面積消耗因子。為了描述這兩個(gè)因子，首先要定義若干個(gè)變量。TSW表示當(dāng)前系統(tǒng)中沒(méi)有專用硬件資源的任務(wù)數(shù)，PESW和PEHW分別表示軟件和硬件處理器件。SYSPESW和SYSPEHW分別表示系統(tǒng)內(nèi)當(dāng)前的軟件和硬件資源數(shù)?；谶@些變量，定義累加的軟件和硬件執(zhí)行時(shí)間分別為：

硬件提高因子是對(duì)特定任務(wù)添加某一硬件資源使系統(tǒng)獲得的性能提高：

其中Ti表示能夠在PENEW上執(zhí)行的任務(wù)。

使用這些變量，定義之前和之后的系統(tǒng)執(zhí)行時(shí)間為：

面積成本因子(PEAREA_FACTOR)表示特定處理器件的面積消耗。面積消耗按照MAX_AREA進(jìn)行正態(tài)劃分，MAX_AREA是所有可行器件的最大面積消耗。面積成本因子的計(jì)算公式為：

通過(guò)性能提高因子和面積消耗因子，將得到選擇系數(shù)，它是性能提高因子和面積因子的加權(quán)和。

所有的處理器件都要計(jì)算PESELECT。而具有最大選擇系數(shù)的器件將被添加到系統(tǒng)中。

2.2 任務(wù)分配與流水化

將任務(wù)分配到已添加到系統(tǒng)中的處理器件上，流水處理與任務(wù)分配即可同時(shí)進(jìn)行。首先給每一個(gè)任務(wù)分配優(yōu)先級(jí)，優(yōu)先級(jí)分配可以采用多種方法，本文從執(zhí)行的角度出發(fā)，對(duì)每一節(jié)點(diǎn)從任務(wù)圖尾部開(kāi)始累計(jì)它最小的執(zhí)行時(shí)間之和，并對(duì)相應(yīng)路徑的后續(xù)節(jié)點(diǎn)設(shè)置最高優(yōu)先級(jí)。這種優(yōu)先級(jí)測(cè)量方法非常普遍，在文獻(xiàn)[4]中被廣泛使用。除了使用最小執(zhí)行時(shí)間，還有其他統(tǒng)計(jì)學(xué)指標(biāo)也可以被使用，比如平均或者中位執(zhí)行時(shí)間。但是，最小執(zhí)行時(shí)間測(cè)量方法能給出更好的結(jié)果。

流水化分配是尋找每一個(gè)處理器上分配任務(wù)的開(kāi)始和結(jié)束時(shí)間。每一個(gè)任務(wù)開(kāi)始時(shí)間被定義為EarliestStartTime，具體定義如下：

EarliestStartTime(Ti)=MAX(FinishTime(PRED(Ti)))，其中PRED(Ti)是Ti的前序任務(wù)

PEIdleTime(PEj)=FinishTime(Last_task_on_PEj)

算法定義了任務(wù)Ti被分配到處理器件PEj上時(shí)的數(shù)據(jù)通訊時(shí)間，這個(gè)時(shí)間是把所有需要的數(shù)據(jù)傳送給PEj的時(shí)間。該時(shí)間定義如下：

通過(guò)EarliestStartTime、PEIdleTime和CommTime，可以定義任務(wù)起始時(shí)間和結(jié)束時(shí)間(Ti分配到上PEj)：

StartTime(Ti，PEj)=MAX(EarliestStartTime(Ti)，PEIdleTime(PEj)

FinishTime(Ti，PEj)=StartTime(Ti，PEj)+CommTime(Ti，PEj)+ExecTime(Ti，PEj)通過(guò)這些公式可以計(jì)算已經(jīng)準(zhǔn)備好且具有最高優(yōu)先級(jí)的任務(wù)的完成時(shí)間，準(zhǔn)備好的任務(wù)是指前序任務(wù)都已經(jīng)分配完的任務(wù)。當(dāng)前任務(wù)分配在有最早完成時(shí)間的PE上。如果最早完成時(shí)間超過(guò)了流水時(shí)間限制，那么將會(huì)生成新的流水平臺(tái)。任務(wù)的最早開(kāi)始時(shí)間EarliestStartTime將被置零，所有PE將會(huì)重新計(jì)算完成時(shí)間FinishTime。如果最早完成時(shí)間在新流水平臺(tái)再次超過(guò)流水時(shí)間限制，那么該條件下的流水分配失敗，需要返回并為系統(tǒng)添加處理器件。算法流程如圖1所示。

3 實(shí)驗(yàn)結(jié)果

某個(gè)應(yīng)用的任務(wù)數(shù)據(jù)流描述如圖2所示。每一節(jié)點(diǎn)表示應(yīng)用的一個(gè)任務(wù)，邊界表示數(shù)據(jù)依賴，邊界上的數(shù)字表示傳輸?shù)狡渌蝿?wù)的數(shù)據(jù)量。本文算法假定在可用資源上任務(wù)的執(zhí)行時(shí)間是可知的。對(duì)硬件資源的執(zhí)行時(shí)間信息能夠人為或者使用文獻(xiàn)[6]中的算法獲得。對(duì)軟件資源的執(zhí)行時(shí)間信息能夠通過(guò)模擬獲取。因此。該應(yīng)用的任務(wù)執(zhí)行時(shí)間信息與面積信息如表1所示。

圖1 算法流程

圖2 任務(wù)數(shù)據(jù)流

本文算法在一定的時(shí)間和面積約束下執(zhí)行，每次測(cè)試的結(jié)果被記錄下來(lái)。本文算法輸出的結(jié)果包括任務(wù)分配給器件的具體開(kāi)始時(shí)間和結(jié)束時(shí)間的分配和流水平臺(tái)。

圖3顯示了在面積和執(zhí)行時(shí)間約束下算法獲得的實(shí)際結(jié)果。約束條件按照面積、執(zhí)行時(shí)間成組顯示。圖3中使用的約束是：(3 200，30)，(3 100，40)，(2 400，55)，(2 250，65)和(1 200，75)。結(jié)果顯示算法能夠滿足所有的約束?；趫?zhí)行時(shí)間的要求，執(zhí)行被劃分成若干個(gè)流水平臺(tái)。流水平臺(tái)數(shù)量從3(最初)變到1(最后)。

第一個(gè)測(cè)試的具體結(jié)果如表2所示。執(zhí)行時(shí)間和面積要求是30個(gè)時(shí)間單位和3 200個(gè)面積單位。本文算法能夠找到一個(gè)流水平臺(tái)時(shí)長(zhǎng)27個(gè)時(shí)間單位系統(tǒng)調(diào)度。算法選擇了4個(gè)處理器件(3次使用3號(hào)件，1次2號(hào)件)，系統(tǒng)面積3 015個(gè)單位。執(zhí)行被劃分為流水平臺(tái)。任務(wù)B在第二平臺(tái)被執(zhí)行，任務(wù)E在第三平臺(tái)執(zhí)行。

4 結(jié)論

本文提出了一種處理器件選擇、任務(wù)分配和流水化的新算法。新算法區(qū)分了資源選擇和任務(wù)分配。為了滿足增長(zhǎng)的數(shù)據(jù)處理量的要求，對(duì)任務(wù)執(zhí)行進(jìn)行了流水化處理。同時(shí)，避免了冗余流水平臺(tái)的生成。本文算法根據(jù)面積信息和執(zhí)行時(shí)間，提出了反復(fù)選擇處理器件的啟發(fā)式方法。與其他算法不同的是，本文算法將數(shù)據(jù)通訊時(shí)間納入了考慮，同樣的算法能夠處理多硬件和多軟件資源。

表1 處理器件任務(wù)時(shí)間與面積信息

表2 試驗(yàn)結(jié)果(執(zhí)行時(shí)間30，面積3 200)

圖3 測(cè)試結(jié)果

[1] Garey M R，Johnson D S.Computers and Interactability：A Guide to the Theory of NP-Completeness[M].San Francisco：Freeman，1979.

[2] Kwok Y K，Ahmad I.Dynamic critical-path scheduling：An effective technique for allocating task graphs to multiprocessors[J].IEEE Transactions on Parallel Distributed Systems，1996，7(5)：506-521.

[3] Bakshi S，Gajaski D D.Partitioning and pielining for performance constrained hardware/software systems[J].IEEE Transactions on Very Large Scale Integration Systems，1999，7(4)：419-432.

[4] Chatha K S，Vemuri R.Hardware-Software Partitioning and Pipelined Scheduling of Trans formative Applications[J].IEEE Transactions on Very Large Scale Integration Systems，2002，10(3)：193-208.

[5] Wolf W.An architectural co-synthesis algorithm for distributed，embedded computing systems[J].IEEE Transactions on VLSI Systems，1997，5(6)：218-229.

[6] Henkel J，Ernst R.A Path-Based Estimation Technique for Estimating Hardware Runtime in HW/SW Co-synthesis[C]//IEEE ACM Proc of 8th Intl Symposium on System Synthesis，2005.