基于任務(wù)劃分算法的基準(zhǔn)程序研究

徐 瑩

同濟(jì)大學(xué)計算機(jī)科學(xué)與技術(shù)系，上海 201804

0 引言

隨著多媒體應(yīng)用的不斷發(fā)展，無論是在教學(xué)、娛樂、咨詢還是軍事領(lǐng)域，多媒體技術(shù)都被廣泛地應(yīng)用，特別是圖像和視頻方面。由于通用處理器的靈活性，大多數(shù)多媒體任務(wù)在通用處理器上通過軟件編程的方式實現(xiàn)，并得到了很好地應(yīng)用。但對于實時性較強的嵌入式系統(tǒng)，在CPU性能不高的情況下，多媒體任務(wù)的處理會占據(jù)大量CPU資源，而且處理的實時性不是很強。為了提高多媒體任務(wù)處理的效率，同時也為減輕通用處理器的運算壓力，針對多媒體任務(wù)處理的可重構(gòu)媒體處理器應(yīng)運而生。它們作為通用處理器的協(xié)處理器，與微處理器一起構(gòu)成了可重構(gòu)計算系統(tǒng)，能很好地解決多媒體處理問題。

可重構(gòu)計算（Reconfigurable Computing）是一種新的計算系統(tǒng)范例，綜合了通用處理器和ASIC的長處，通過對可重構(gòu)硬件進(jìn)行配置，使之由一個通用的計算平臺轉(zhuǎn)化為一個專用的硬件系統(tǒng)，以完成具體的計算任務(wù)，相當(dāng)于計算任務(wù)同時在時間和空間上展開，兼顧靈活性和計算高性能，因此在多媒體處理[2]、嵌入式系統(tǒng)[3]、密碼學(xué)[4]、圖像壓縮[5]等計算密集型應(yīng)用中發(fā)揮了巨大的優(yōu)勢，成為當(dāng)前的研究熱點。在提供強有力的計算平臺的同時，可重構(gòu)計算也提出了一些新的研究課題，面向數(shù)據(jù)流圖（DFG）的任務(wù)劃分就是其中之一。

1 任務(wù)劃分

可重構(gòu)計算系統(tǒng)的典型結(jié)構(gòu)包括一個微處理器和可編程硬件。由于可重構(gòu)硬件能夠提供的資源是有限的，當(dāng)計算任務(wù)所需的資源大于硬件資源時，就要對任務(wù)進(jìn)行劃分，任務(wù)劃分即把一個任務(wù)在時間上劃分成相互關(guān)聯(lián)的子任務(wù)（稱作模塊）[6]，每個模塊分時復(fù)用硬件資源，從而完成整個任務(wù)。

任務(wù)劃分建模：

可重構(gòu)系統(tǒng)的高層綜合中，通常采用有向無環(huán)圖作為中間表達(dá)形式，例如，數(shù)據(jù)流圖（DFG）、控制流圖（CFG）、信號流圖（SFG）等。任務(wù)劃分也采用DFG圖作為任務(wù)的中間表達(dá)形式，進(jìn)行建模。因此，任務(wù)劃分問題從根本上可以歸結(jié)為一種任務(wù)圖劃分問題。

1）定義1：任務(wù)的DFG圖是一個有向無環(huán)圖（DAG），定義為四元組 G=＜V，E，D，S>。其中，頂點集V= {vi| vi表示運算符，1≤i≤n}，|V| =n表示節(jié)點個數(shù)；邊集E={eij| eij =＜vi，vj>，1≤i，j≤n}，eij表示節(jié)點vi和節(jié)點vj的依賴關(guān)系，|E|=m表示邊的數(shù)量；延遲集D={di| di代表vi的延遲，1≤i≤n}；通信量集合W= {si| si是節(jié)點vi所需的面積，1≤i≤n}。

2）定義 2：={P1，P2，……PN}是 DFG G=＜V，E，D，W>的一個劃分。Pi為G中部分節(jié)點的集合，稱為模塊。

圖1是一個待劃分任務(wù)的DFG圖。圖中每個節(jié)點表示一個操作，每條邊代表節(jié)點之間的依賴關(guān)系。在滿足面積約束、前后依賴約束的情況下，該任務(wù)被劃分成6個模塊，分別用P1、P2、P3、P4、P5、P6表示。由圖可見，模塊1、2、3之間沒有依賴關(guān)系，模塊4依賴于模塊1，模塊5依賴于模塊2和3，而模塊6依賴于模塊4和模塊5。在執(zhí)行該任務(wù)時，要保證時間上的先后性，即讓模塊1、2、3先于模塊4、5執(zhí)行，模塊4、5先于模塊6執(zhí)行；同時，保證任務(wù)之間的并行性，讓盡可能多的任務(wù)能夠同時進(jìn)行。這樣可以實現(xiàn)在資源受限的動態(tài)重構(gòu)的系統(tǒng)上，執(zhí)行規(guī)模較大的應(yīng)用。任務(wù)劃分實例如圖1所示：

圖1 任務(wù)劃分實例

通過上例可以得出，在進(jìn)行任務(wù)劃分的時候，需要考慮很多因素，細(xì)分下來有如下幾點：

1）模塊數(shù)量。模塊數(shù)量和配置次數(shù)有關(guān)，模塊越多，配置所需時間越長，則總執(zhí)行時間就越長；

2）模塊并行度。每個模塊中可以并行的操作越多，其關(guān)鍵路徑越短，系統(tǒng)總處理時間就越少，效率就越高；

3）模塊間通信。模塊之間的通信量體現(xiàn)為模塊之間的邊數(shù)。邊數(shù)越多，表示模塊之間依賴關(guān)系越強，用于塊間傳遞數(shù)據(jù)的時間越久，影響總的執(zhí)行時間。

2 性能基準(zhǔn)程序的原理和方法

性能基準(zhǔn)程序是以單個良好定義的任務(wù)或者一組任務(wù)形式出現(xiàn)的，用來度量計算機(jī)系統(tǒng)或構(gòu)件性能的一個測試。這些任務(wù)被稱為工作負(fù)載[7]。在基準(zhǔn)程序法中，必須明確規(guī)定所選用的基準(zhǔn)程序及其特性、運行方式，并規(guī)定評估指標(biāo)體系。

2.1 基于任務(wù)劃分的性能基準(zhǔn)程序

任務(wù)劃分是可重構(gòu)系統(tǒng)高層綜合的一個步驟，目前沒有針對這一特定應(yīng)用的性能基準(zhǔn)程序，不同的算法提出者采用不同的基準(zhǔn)程序?qū)λ惴ㄐ阅苓M(jìn)行評定，給任務(wù)劃分算法的橫向比較帶來了一定的困難。考慮借鑒已有基準(zhǔn)的構(gòu)造方法，結(jié)合任務(wù)劃分算法的主要性能指標(biāo)和多媒體的典型應(yīng)用，按照如下原則選取基準(zhǔn)程序：

1）具備基準(zhǔn)程序的基本特性

（1）可再現(xiàn)性；（2）代表性；（3）可擴(kuò)展性；（4）可觀測性：可通過基準(zhǔn)的劃分結(jié)果，對算法進(jìn)行比較。

2）具有流媒體運算的典型性

復(fù)雜的流媒體、音視頻應(yīng)用一般包括幾個子任務(wù)，每個子任務(wù)都有不同的特點。這些任務(wù)分為低層、中層、高層。其中低層任務(wù)占整個處理的絕大部分，以MPEG-2視頻編碼為例，包括DCT、ME等底層操作占了整個任務(wù)的89%。因此，我們從流媒體應(yīng)用的低層任務(wù)中選擇基準(zhǔn)程序，按照計算量從小到大，選擇不同的基準(zhǔn)程序（體現(xiàn)在DFG圖中就是節(jié)點數(shù)量的多少），從而體現(xiàn)出任務(wù)規(guī)模對于劃分模塊數(shù)這一指標(biāo)的影響。

3）具有內(nèi)在并行性

選擇的基準(zhǔn)具有內(nèi)在并行性，適合于在可重構(gòu)陣列上執(zhí)行。考慮在任務(wù)規(guī)模相同的情況下，選擇并行度不同的基準(zhǔn)程序，以便反映出不同的并行度對于任務(wù)劃分的任務(wù)執(zhí)行時間和塊間通信的影響。

2.2 所選基準(zhǔn)定性分析

所選的有限脈沖響應(yīng)濾波器（FIR）、快速傅里葉變換（FFT）、離散余弦變換（DCT）等基準(zhǔn)程序都是多媒體音、視頻信號編碼/解碼，壓縮/解壓縮中常用的計算，具有一定的代表性。對其中一些基準(zhǔn)進(jìn)行如下的定性分析：

1）FIR

數(shù)字濾波器通常應(yīng)用于修正或改變時域或頻域中信號的屬性，在通信、模式識別、語音和圖像處理等領(lǐng)域都有著廣泛的應(yīng)用。FIR（有限脈沖響應(yīng)）濾波器是數(shù)字濾波器中最常用的一種，它具有很好的穩(wěn)定性，并且容易分析。

帶有常系數(shù)的FIR濾波器是一種線性時不變數(shù)字濾波器。N階或者長度為N的FIR輸出對應(yīng)于輸入時間序列x[k]的關(guān)系由一種有限卷積數(shù)量形式給出，具體形式如下：

在實際應(yīng)用中，對多媒體信號的處理通常要求具有實時性和靈活性，而現(xiàn)有的軟件和硬件實現(xiàn)方式則難以同時滿足這兩方面的要求。隨著可編程邏輯器件的發(fā)展，可以通過可重構(gòu)器件實現(xiàn)FIR濾波器，利用FIR對信號處理中的相頻特性就可以實現(xiàn)實時性的要求，又兼顧了一定的靈活性。

2）DCT

離散余弦變換與傅里葉變換很相似，在傅里葉變換的展開式中，如果被展開的函數(shù)是偶函數(shù)，那么其傅里葉級數(shù)中只包含余弦項，再將其離散化可導(dǎo)出余弦變換。這個原理可以應(yīng)用到圖像中，圖像是由很多像素構(gòu)成的，每個像素都會帶有X，Y坐標(biāo)，利用點陣將像素翻譯為亮度值或者灰度值。在進(jìn)行RGB圖像壓縮時，需要進(jìn)行三遍壓縮，利用坐標(biāo)變換得到像素的三維表示方法，通過DCT變換將空間表達(dá)式轉(zhuǎn)化為頻譜表達(dá)式或者頻率域，將像素信息集中到少數(shù)的頻率分量，從而達(dá)到數(shù)據(jù)壓縮的目的。

設(shè)源圖像像素點坐標(biāo)為x(i，j)，變換后矩陣元素為X(u，v)，0≤i，j，u，v≤7。二維DCT變換的數(shù)學(xué)定義為：

3）FDCT

有DCT分析可看出，二維DCT的運算量很大，耗費很多的運算時間，因此對快速離散余弦變換進(jìn)行研究很有必要。二維DCT的一個重要特性是可分解性，即二維的DCT運算可以分解一維DCT來運算。目前的快速DCT算法都是先按行進(jìn)行8次8點的一維DCT來運算，再按列進(jìn)行8次8點的一維DCT。8點的一維DCT需要64次乘法和64次加減法，一個8×8大小的塊需要作8+8=16次一維DCT，一共是1024次實數(shù)乘法和加減法才能完成。這是行列分解后基本的運算量。8點的一維DCT運算的數(shù)學(xué)定義為：

0≤i，u≤7 其中，x（i）為輸入序列，X（u）為輸出序列。

3 結(jié)論

任務(wù)劃分可將任務(wù)在時間上劃分成相互關(guān)聯(lián)的子任務(wù)，每個子任務(wù)分時復(fù)用硬件資源，在完成整個任務(wù)的同時，還可以提高硬件資源的利用率。本文在考慮任務(wù)劃分的3個優(yōu)化目標(biāo)的基礎(chǔ)上，借鑒已有的基準(zhǔn)程序構(gòu)造方法，并結(jié)合多媒體應(yīng)用的特點，提出了任務(wù)劃分算法的基準(zhǔn)程序的構(gòu)造方法。采用此方法，選取了一組基準(zhǔn)程序，并對FFT、FIR、DCT和FDCT等基準(zhǔn)進(jìn)行了定性分析。

[1]Estrin G，Bussel B et al.Parallel Processing in aRestructurable Computer System [J].IEEE Transactions onElectronic Computers，1963，12(6)：747-755.

[2]Barat F，Jayapala M，de Beeck P O，etal.Reconfigurable instruction set processors: animplementation platform for interactive multimediaapplications.In: Conference Record of the Thirty-FifthAsilomar Conference，Asilomar，IEEE CS Press，January2001：481-485.

[3]Campi F，TomaM，LodiA，et al.A VLIW processor withreconfigurable instruction set for embedded applications[J].IEEE Journal of Solid-State Circuits，2003，38(11)：1876-1886.

[4]M Rencher，B L Hutchings，Automated targetrecognition on SPLASH2. In: Proceedings of IEEE Symposiumon Field-Programmable Custom Computing Machines，NapaValley，IEEE CS Press，April 1997：481-485.

[5]S Hauck，W D Wilson.Runlength compressiontechniques for FPGA configurations.In: Seventh IEEESymposium on Field-Programmable Custom ComputingMachines，California，IEEE CS Press，April 1999：286-297.

[6]孫康.可重構(gòu)計算相關(guān)研究[D]，浙江大學(xué)，2007.

[7]江建慧.嵌入式系統(tǒng)性能評估的基準(zhǔn)程序法[J].機(jī)械與電子，2002(124).

[8]汪泓澄.嵌入式系統(tǒng)的性能基準(zhǔn)程序及任務(wù)時限違背率[D].同濟(jì)大學(xué)，2006.

[9]周麗萍，安虹，徐光.多媒體基準(zhǔn)測試程序中的流并行性分析[J].計算機(jī)科學(xué)，2009，36(5)：287-290.