一種確定多媒體應(yīng)用程序內(nèi)層循環(huán)的子字并行編譯方法

1、一種確定多媒體應(yīng)用程序內(nèi)層循環(huán)的子字并行編譯方法         08-07-15 15:39:00     作者：未知    編輯：studa0714摘要:多媒體程序是數(shù)據(jù)密集型應(yīng)用,其核心代碼部分占用了大部分的執(zhí)行時間,因此,對多媒體應(yīng)用程序的研究大多針對其核心代碼部分.本文圍繞多媒體應(yīng)用程序的核心內(nèi)層循環(huán),分析其子字并行特點,提出了一種新穎的按位數(shù)據(jù)流分析方法,能夠確定程序的內(nèi)層循環(huán),為進(jìn)一步深入研究奠定基礎(chǔ).關(guān)鍵詞:多媒體;子字

2、并行;內(nèi)層循環(huán);數(shù)據(jù)流1引言隨著多媒體技術(shù)和網(wǎng)絡(luò)的迅猛發(fā)展,多媒體產(chǎn)業(yè)正在以驚人的速度擴(kuò)展,卓越的多媒體處理能力成為對現(xiàn)代計算機(jī)的必然要求之一.從體系結(jié)構(gòu)研究方面,研究人員在通用處理器中增加新的多媒體功能處理部件以及相應(yīng)的多媒體處理指令,或者設(shè)計專用的多媒體處理器(ASIP),都能夠完成對多媒體信息的高效處理.但是,與多媒體處理器的發(fā)展相比,面向多媒體的編譯技術(shù)明顯滯后.出于多媒體應(yīng)用程序與科學(xué)計算或其他通用應(yīng)用程序的特殊性,開發(fā)人員往往還是會采用復(fù)雜低效且易出錯的手工編碼方式產(chǎn)生代碼.因此,我們認(rèn)為,無論是從計算機(jī)體系結(jié)構(gòu)、還是從編譯器等多方面來提高計算機(jī)的多媒體處理能力,首先必須要針對多媒

3、體應(yīng)用特點,對多媒體應(yīng)用程序的特征進(jìn)行分析和研究.縱觀歷史,有許多面向程序特征提高計算機(jī)性能的典范,證明了對程序特征的分析和研究直接影響到計算機(jī)性能的優(yōu)化和設(shè)計.例如,IBM公司與美國加利福尼亞大學(xué)通過對應(yīng)用程序的統(tǒng)計和研究發(fā)現(xiàn),CISC指令集80%的指令只在20%的運(yùn)行時間內(nèi)用到,因此簡化了計算機(jī)指令集結(jié)構(gòu),提出了RISC指令集結(jié)構(gòu),從而提高了機(jī)器性能,減輕設(shè)計人員負(fù)擔(dān).循環(huán)是多媒體應(yīng)用程序的核心,在程序的運(yùn)行過程中幾乎占了90%的時間,而核心循環(huán)體-內(nèi)層循環(huán)又是循環(huán)的關(guān)鍵.有實驗數(shù)據(jù)表明,大多數(shù)多媒體應(yīng)用在最內(nèi)層循環(huán)花費了80%90%的執(zhí)行時間.因此,要挖掘多媒體應(yīng)用的程序特征,深入核心循

4、環(huán)體的內(nèi)層循環(huán)提取特征是非常有必要的.本文圍繞多媒體應(yīng)用程序的特點,對其核心代碼內(nèi)層循環(huán)和并行性進(jìn)行深入的分析,針對當(dāng)前編譯技術(shù)的不足提出一種確定內(nèi)層循環(huán)的數(shù)據(jù)流分析方法.本文第二部分介紹并分析多媒體應(yīng)用程序的核心代碼,以及其固有的子字并行性.第三部分介紹相關(guān)編譯技術(shù)的研究發(fā)展.第四部分介紹按位的數(shù)據(jù)流分析.第五部分給出結(jié)論.2多媒體應(yīng)用程序內(nèi)核分析通過對多媒體應(yīng)用程序定性研究分析,多媒體應(yīng)用不同于科學(xué)計算和通用應(yīng)用,它具有自身固有的特征:(1)內(nèi)在的并行性(2)數(shù)據(jù)類型的連續(xù)性(3)實時響應(yīng)性:如視頻會議和電子商務(wù)等,需要可靠迅捷的實時響應(yīng)(4)數(shù)據(jù)有序性:由于弱的空間局部性,多媒體的很多數(shù)

5、據(jù)與操作都具有強(qiáng)烈的有序性(5)高網(wǎng)絡(luò)帶寬性:隨著網(wǎng)絡(luò)的發(fā)展,多媒體應(yīng)用對網(wǎng)絡(luò)帶寬的要求越來越高,如網(wǎng)絡(luò)游戲、網(wǎng)上視頻點播等(6)高存儲帶寬性:因為多媒體應(yīng)用程序處理的數(shù)據(jù)量往往很大、甚至海量,所以,對存儲帶寬的要求也很高.多媒體應(yīng)用程序往往包含一個或多個代碼核心,代表了大部分的動態(tài)指令執(zhí)行,在程序運(yùn)行過程中幾乎占據(jù)了90%的時間,所以,除開以上介紹的多媒體應(yīng)用程序的這些特點,從編譯的角度,我們更關(guān)心其核心部分代碼內(nèi)層循環(huán).一般來說,這些核心部分執(zhí)行的操作具有并行和計算密集的特點,且代碼控制結(jié)構(gòu)規(guī)則,需要對大量的、連續(xù)的、流的、可變精度的數(shù)據(jù)進(jìn)行操作.首先,并行性的特征源于多媒體應(yīng)用程序?qū)Υ罅?/p>

6、獨立的數(shù)據(jù)集合實現(xiàn)相同的操作,因此,這些操作能夠并行執(zhí)行.第二,大量的計算密集型的操作和代碼的控制結(jié)構(gòu)并不復(fù)雜,與典型的整型程序相比,多媒體應(yīng)用程序中通常幾乎不帶有分支,控制結(jié)構(gòu)非常規(guī)則.第三,輸入輸出數(shù)據(jù)幾乎不存在時間局部性,因此具有流特性,流數(shù)據(jù)即時被操作即時丟棄,結(jié)果或者直接寫回內(nèi)存或者傳送至網(wǎng)絡(luò)作為輸出數(shù)據(jù)流,如流視頻幀、流音頻采樣.第四,根據(jù)不同的數(shù)據(jù)類型,數(shù)據(jù)元素的精度要求是可變的,如8位的圖像像素、16位的音頻采樣.一般來說,多媒體應(yīng)用程序處理的數(shù)據(jù)大小為8位、16位、32位、64位整型,或32位單精度浮點、64位雙精度浮點.多媒體應(yīng)用程序的每個數(shù)據(jù)以“子字”(subword)的

7、形式進(jìn)行操作,因此這種并行性稱為“子字并行”(subword paral-lelism).傳統(tǒng)的通用處理器是以字為單位進(jìn)行處理的,一般是32位或64位,而圖像信息通常以大量的低精度或短數(shù)據(jù)類型的形式出現(xiàn),為了不浪費數(shù)據(jù)通路寬度,充分高效的利用處理器上的多個計算單元,提高處理器性能和處理多媒體信息的效率,子字并行的處理方式應(yīng)運(yùn)而生.子字并行1是一種特殊的數(shù)據(jù)并行,在子字并行中,一個字就是一個數(shù)據(jù)集.子字是包含在字中的更低精度的數(shù)據(jù)單元.我們將若干個子字封裝到一個字中,然后對整個字進(jìn)行處理.子字并行允許在一個計算單元(字單元)內(nèi)對2個、4個或8個操作(子字)同時進(jìn)行.圖1(a)所示的是一個普通的3

8、2位操作與相應(yīng)的子字并行處理進(jìn)行比較,圖1(b)為展示的是在子字單元上如何進(jìn)行子字并行處理.顯然,與全字長的處理相比,子字并行操作可以帶來更大的并行度.子字并行是處理多媒體類型數(shù)據(jù)應(yīng)用的最自然的方式,它能夠充分利用多媒體算法數(shù)據(jù)精度小、內(nèi)部循環(huán)多的特點.對于處理器設(shè)計來說,子字并行大大提高了處理器的并行度,節(jié)省了數(shù)據(jù)通路和寄存器資源;多媒體指令的擴(kuò)展又提供了更高的處理速度;同時,對于嵌入式多媒體處理器來說,為支持子字并行而組織數(shù)據(jù)通路,也可以獲得更低的并行開銷和更少的控制重復(fù).有了子字并行的處理器方式,單一的一條LOAD/STORE指令就可以在存儲器和寄存器之間同時移動若干個被封裝的子字,因而

9、,存儲能力也得到了提高.因此,不論是通用微處理器還是多媒體微處理器或DSP,子字并行都是提高處理器性能、加速多媒體處理的有效方式.3相關(guān)研究子字并行的處理器方式雖然很有效,但圖像處理程序主要還是以串行程序方式編寫(如:C),結(jié)果卻需要以并行的方式執(zhí)行,因而對編譯器提出了很高的要求,需要編譯器來決定如何將子字?jǐn)?shù)據(jù)按照正確的順序封裝入源寄存器,進(jìn)行相應(yīng)子字對之間的運(yùn)算,運(yùn)算結(jié)束后,按照需求,將結(jié)果以正確的順序從目標(biāo)寄存器中提取出來.因此,和子字并行在體系結(jié)構(gòu)研究上取得的成功相比,通用編譯器技術(shù)卻不能自動的從應(yīng)用程序中提取這種并行性,進(jìn)而無法充分利用這類特殊的指令集,編譯技術(shù)在自動高效的識別、產(chǎn)生和

10、處理子字并行指令方面,尚未取得令人滿意的結(jié)果.以MMX24為代表,借鑒SIMD陣列處理技術(shù)如向量處理來產(chǎn)生優(yōu)化代碼,采用向量處理編譯技術(shù),能夠獲得1.5到6.5的加速比,這樣的結(jié)果已經(jīng)相當(dāng)不錯.因為對于多媒體應(yīng)用這類的計算密集型應(yīng)用,內(nèi)層循環(huán)是代碼中最關(guān)鍵的部分,也是體現(xiàn)最多并行的部分,所以向量處理的目的在于識別內(nèi)層循環(huán),采用循環(huán)變換來得到向量操作,而這些操作就可以用子字并行指令實現(xiàn).向量處理包括:循環(huán)分析,循環(huán)正規(guī)化,依賴性分析,標(biāo)量擴(kuò)展,循環(huán)分布,向量化和循環(huán)分段.MIT的Larsen和Amarasinghe提出superword5的概念,認(rèn)為子字并行不僅僅是一種數(shù)據(jù)并行,還是一種指令級并行的方式,因此,對于一個基本塊中按相同順序執(zhí)行的相同的操作,都可以進(jìn)行并行處理.這種方法與傳統(tǒng)的向量編譯方法的不同在于它的向量化是對一個基本塊內(nèi)部指令的向量化.該方法基于SUIF5實現(xiàn),并應(yīng)用于Motorola的AltiVec擴(kuò)展.這種方法解決了基本塊內(nèi)部的并行處理問題,但是只適用于基本塊結(jié)構(gòu)簡單的情