徐 瑩

同濟大學計算機科學與技術系，上海 201804

0 引言

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

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

1 任務劃分

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

任務劃分建模：

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

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

圖1 任務劃分實例

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

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

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

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

2 性能基準程序的原理和方法

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

2.1 基于任務劃分的性能基準程序

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

1）具備基準程序的基本特性

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

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

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

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

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

2.2 所選基準定性分析

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

1）FIR

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

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

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

2）DCT

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

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

3）FDCT

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

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

3 結(jié)論

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

[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)計算相關研究[D]，浙江大學，2007.

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

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

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