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

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

摘要:多媒體程序是數(shù)據(jù)密集型應(yīng)用，其核心代碼部分占用了大部分的執(zhí)行時(shí)間，因此，對(duì)多媒體應(yīng)用程序的研究大多針對(duì)其核心代碼部分.本文圍繞多媒體應(yīng)用程序的核心內(nèi)層循環(huán)，分析其子字并行特點(diǎn)，提出了一種新穎的按位數(shù)據(jù)流分析方法，能夠確定程序的內(nèi)層循環(huán)，為進(jìn)一步深入研究奠定基礎(chǔ).關(guān)鍵詞:多媒體;子字并行;內(nèi)層循環(huán);數(shù)據(jù)流1引言隨著多媒體技術(shù)和網(wǎng)絡(luò)的迅猛發(fā)展，多媒體產(chǎn)業(yè)正在以驚人的速度擴(kuò)展，卓越的多媒體處理能力成為對(duì)現(xiàn)代計(jì)算機(jī)的必然要求之一.從體系結(jié)構(gòu)研究方面，研究人員在通用處理器中增加新的多媒體功能處理部件以及相應(yīng)的多媒體處理指令，或者設(shè)計(jì)專(zhuān)用的多媒體處理器(ASIP)，都能夠完成對(duì)多媒體信息的高效處理.但是，與多媒體處理器的發(fā)展相比，面向多媒體的編譯技術(shù)明顯滯后.出于多媒體應(yīng)用程序與科學(xué)計(jì)算或其他通用應(yīng)用程序的特殊性，開(kāi)發(fā)人員往往還是會(huì)采用復(fù)雜低效且易出錯(cuò)的手工編碼方式產(chǎn)生代碼.因此，我們認(rèn)為，無(wú)論是從計(jì)算機(jī)體系結(jié)構(gòu)、還是從編譯器等多方面來(lái)提高計(jì)算機(jī)的多媒體處理能力，首先必須要針對(duì)多媒體應(yīng)用特點(diǎn)，對(duì)多媒體應(yīng)用程序的特征進(jìn)行分析和研究.縱觀歷史，有許多面向程序特征提高計(jì)算機(jī)性能的典范，證明了對(duì)程序特征的分析和研究直接影響到計(jì)算機(jī)性能的優(yōu)化和設(shè)計(jì).例如，IBM公司與美國(guó)加利福尼亞大學(xué)通過(guò)對(duì)應(yīng)用程序的統(tǒng)計(jì)和研究發(fā)現(xiàn)，CISC指令集80%的指令只在20%的運(yùn)行時(shí)間內(nèi)用到，因此簡(jiǎn)化了計(jì)算機(jī)指令集結(jié)構(gòu)，提出了RISC指令集結(jié)構(gòu)，從而提高了機(jī)器性能，減輕設(shè)計(jì)人員負(fù)擔(dān).循環(huán)是多媒體應(yīng)用程序的核心，在程序的運(yùn)行過(guò)程中幾乎占了90%的時(shí)間，而核心循環(huán)體-內(nèi)層循環(huán)又是循環(huán)的關(guān)鍵.有實(shí)驗(yàn)數(shù)據(jù)表明，大多數(shù)多媒體應(yīng)用在最內(nèi)層循環(huán)花費(fèi)了80%~90%的執(zhí)行時(shí)間.因此，要挖掘多媒體應(yīng)用的程序特征，深入核心循環(huán)體的內(nèi)層循環(huán)提取特征是非常有必要的.本文圍繞多媒體應(yīng)用程序的特點(diǎn)，對(duì)其核心代碼———內(nèi)層循環(huán)和并行性進(jìn)行深入的分析，針對(duì)當(dāng)前編譯技術(shù)的不足提出一種確定內(nèi)層循環(huán)的數(shù)據(jù)流分析方法.本文第二部分介紹并分析多媒體應(yīng)用程序的核心代碼，以及其固有的子字并行性.第三部分介紹相關(guān)編譯技術(shù)的研究發(fā)展.第四部分介紹按位的數(shù)據(jù)流分析.第五部分給出結(jié)論.2多媒體應(yīng)用程序內(nèi)核分析通過(guò)對(duì)多媒體應(yīng)用程序定性研究分析，多媒體應(yīng)用不同于科學(xué)計(jì)算和通用應(yīng)用，它具有自身固有的特征:(1)內(nèi)在的并行性(2)數(shù)據(jù)類(lèi)型的連續(xù)性(3)實(shí)時(shí)響應(yīng)性:如視頻會(huì)議和電子商務(wù)等，需要可靠迅捷的實(shí)時(shí)響應(yīng)(4)數(shù)據(jù)有序性:由于弱的空間局部性，多媒體的很多數(shù)據(jù)與操作都具有強(qiáng)烈的有序性(5)高網(wǎng)絡(luò)帶寬性:隨著網(wǎng)絡(luò)的發(fā)展，多媒體應(yīng)用對(duì)網(wǎng)絡(luò)帶寬的要求越來(lái)越高，如網(wǎng)絡(luò)游戲、網(wǎng)上視頻點(diǎn)播等(6)高存儲(chǔ)帶寬性:因?yàn)槎嗝襟w應(yīng)用程序處理的數(shù)據(jù)量往往很大、甚至海量，所以，對(duì)存儲(chǔ)帶寬的要求也很高.多媒體應(yīng)用程序往往包含一個(gè)或多個(gè)代碼核心，代表了大部分的動(dòng)態(tài)指令執(zhí)行，在程序運(yùn)行過(guò)程中幾乎占據(jù)了90%的時(shí)間，所以，除開(kāi)以上介紹的多媒體應(yīng)用程序的這些特點(diǎn)，從編譯的角度，我們更關(guān)心其核心部分代碼———內(nèi)層循環(huán).一般來(lái)說(shuō)，這些核心部分執(zhí)行的操作具有并行和計(jì)算密集的特點(diǎn)，且代碼控制結(jié)構(gòu)規(guī)則，需要對(duì)大量的、連續(xù)的、流的、可變精度的數(shù)據(jù)進(jìn)行操作.首先，并行性的特征源于多媒體應(yīng)用程序?qū)Υ罅开?dú)立的數(shù)據(jù)集合實(shí)現(xiàn)相同的操作，因此，這些操作能夠并行執(zhí)行.第二，大量的計(jì)算密集型的操作和代碼的控制結(jié)構(gòu)并不復(fù)雜，與典型的整型程序相比，多媒體應(yīng)用程序中通常幾乎不帶有分支，控制結(jié)構(gòu)非常規(guī)則.第三，輸入輸出數(shù)據(jù)幾乎不存在時(shí)間局部性，因此具有流特性，流數(shù)據(jù)即時(shí)被操作即時(shí)丟棄，結(jié)果或者直接寫(xiě)回內(nèi)存或者傳送至網(wǎng)絡(luò)作為輸出數(shù)據(jù)流，如流視頻幀、流音頻采樣.第四，根據(jù)不同的數(shù)據(jù)類(lèi)型，數(shù)據(jù)元素的精度要求是可變的，如8位的圖像像素、16位的音頻采樣.一般來(lái)說(shuō)，多媒體應(yīng)用程序處理的數(shù)據(jù)大小為8位、16位、32位、64位整型，或32位單精度浮點(diǎn)、64位雙精度浮點(diǎn).多媒體應(yīng)用程序的每個(gè)數(shù)據(jù)以“子字”(subword)的形式進(jìn)行操作，因此這種并行性稱(chēng)為“子字并行”(subwordparal-lelism).傳統(tǒng)的通用處理器是以字為單位進(jìn)行處理的，一般是32位或64位，而圖像信息通常以大量的低精度或短數(shù)據(jù)類(lèi)型的形式出現(xiàn)，為了不浪費(fèi)數(shù)據(jù)通路寬度，充分高效的利用處理器上的多個(gè)計(jì)算單元，提高處理器性能和處理多媒體信息的效率，子字并行的處理方式應(yīng)運(yùn)而生.子字并行[1]是一種特殊的數(shù)據(jù)并行，在子字并行中，一個(gè)字就是一個(gè)數(shù)據(jù)集.子字是包含在字中的更低精度的數(shù)據(jù)單元.我們將若干個(gè)子字封裝到一個(gè)字中，然后對(duì)整個(gè)字進(jìn)行處理.子字并行允許在一個(gè)計(jì)算單元(字單元)內(nèi)對(duì)2個(gè)、4個(gè)或8個(gè)操作(子字)同時(shí)進(jìn)行.圖1(a)所示的是一個(gè)普通的32位操作與相應(yīng)的子字并行處理進(jìn)行比較，圖1(b)為展示的是在子字單元上如何進(jìn)行子字并行處理.顯然，與全字長(zhǎng)的處理相比，子字并行操作可以帶來(lái)更大的并行度.子字并行是處理多媒體類(lèi)型數(shù)據(jù)應(yīng)用的最自然的方式，它能夠充分利用多媒體算法數(shù)據(jù)精度小、內(nèi)部循環(huán)多的特點(diǎn).對(duì)于處理器設(shè)計(jì)來(lái)說(shuō)，子字并行大大提高了處理器的并行度，節(jié)省了數(shù)據(jù)通路和寄存器資源;多媒體指令的擴(kuò)展又提供了更高的處理速度;同時(shí)，對(duì)于嵌入式多媒體處理器來(lái)說(shuō)，為支持子字并行而組織數(shù)據(jù)通路，也可以獲得更低的并行開(kāi)銷(xiāo)和更少的控制重復(fù).有了子字并行的處理器方式，單一的一條LOAD/STORE指令就可以在存儲(chǔ)器和寄存器之間同時(shí)移動(dòng)若干個(gè)被封裝的子字，因而，存儲(chǔ)能力也得到了提高.因此，不論是通用微處理器還是多媒體微處理器或DSP，子字并行都是提高處理器性能、加速多媒體處理的有效方式.3相關(guān)研究子字并行的處理器方式雖然很有效，但圖像處理程序主要還是以串行程序方式編寫(xiě)(如:C)，結(jié)果卻需要以并行的方式執(zhí)行，因而對(duì)編譯器提出了很高的要求，需要編譯器來(lái)決定如何將子字?jǐn)?shù)據(jù)按照正確的順序封裝入源寄存器，進(jìn)行相應(yīng)子字對(duì)之間的運(yùn)算，運(yùn)算結(jié)束后，按照需求，將結(jié)果以正確的順序從目標(biāo)寄存器中提取出來(lái).因此，和子字并行在體系結(jié)構(gòu)研究上取得的成功相比，通用編譯器技術(shù)卻不能自動(dòng)的從應(yīng)用程序中提取這種并行性，進(jìn)而無(wú)法充分利用這類(lèi)特殊的指令集，編譯技術(shù)在自動(dòng)高效的識(shí)別、產(chǎn)生和處理子字并行指令方面，尚未取得令人滿意的結(jié)果.以MMX[2~4]為代表，借鑒SIMD陣列處理技術(shù)如向量處理來(lái)產(chǎn)生優(yōu)化代碼，采用向量處理編譯技術(shù)，能夠獲得1.5到6.5的加速比，這樣的結(jié)果已經(jīng)相當(dāng)不錯(cuò).因?yàn)閷?duì)于多媒體應(yīng)用這類(lèi)的計(jì)算密集型應(yīng)用，內(nèi)層循環(huán)是代碼中最關(guān)鍵的部分，也是體現(xiàn)最多并行的部分，所以向量處理的目的在于識(shí)別內(nèi)層循環(huán)，采用循環(huán)變換來(lái)得到向量操作，而這些操作就可以用子字并行指令實(shí)現(xiàn).向量處理包括:循環(huán)分析，循環(huán)正規(guī)化，依賴性分析，標(biāo)量擴(kuò)展，循環(huán)分布，向量化和循環(huán)分段.MIT的Larsen和Amarasinghe提出superword[5]的概念，認(rèn)為子字并行不僅僅是一種數(shù)據(jù)并行，還是一種指令級(jí)并行的方式，因此，對(duì)于一個(gè)基本塊中按相同順序執(zhí)行的相同的操作，都可以進(jìn)行并行處理.這種方法與傳統(tǒng)的向量編譯方法的不同在于它的向量化是對(duì)一個(gè)基本塊內(nèi)部指令的向量化.該方法基于SUIF[5]實(shí)現(xiàn)，并應(yīng)用于Motorola的AltiVec擴(kuò)展.這種方法解決了基本塊內(nèi)部的并行處理問(wèn)題，但是只適用于基本塊結(jié)構(gòu)簡(jiǎn)單的情況，對(duì)于帶條件轉(zhuǎn)移的基本塊如何處理，并沒(méi)有進(jìn)行深入研究，而且這種方法由于過(guò)于復(fù)雜，不具備很好的移植性，也難于實(shí)現(xiàn)，所以，只能作為一種啟發(fā)式方法進(jìn)行研究.與現(xiàn)有研究的不同在于，本文沿襲向量編譯的原理，根據(jù)圖像處理程序的特點(diǎn)，著重對(duì)關(guān)鍵部分———內(nèi)層循環(huán)進(jìn)行挖掘，提出了按位的數(shù)據(jù)流分析方法，為進(jìn)一步編譯優(yōu)化技術(shù)的使用奠定基礎(chǔ).4按位數(shù)據(jù)流分析數(shù)據(jù)流分析能夠幫助我們確定內(nèi)層循環(huán)，我們首先用循環(huán)正規(guī)化技術(shù)(loopnormalization)來(lái)保證循環(huán)的迭代空間的規(guī)則性和依賴性驗(yàn)證的簡(jiǎn)單.本文主要考察針對(duì)for循環(huán)的匹配，在開(kāi)始進(jìn)行子字并行規(guī)范之前，我們假設(shè)該循環(huán)中所有上下界都明確定義.對(duì)于C編譯器而言，我們假設(shè)其規(guī)約變量下界為0、變化步長(zhǎng)為1、且所有循環(huán)迭代都可以運(yùn)行，則舊的規(guī)約變量將為新規(guī)約變量的仿射函數(shù)代替，下標(biāo)表達(dá)式和下界也因此做相應(yīng)修改.下例所示為一個(gè)小的循環(huán)代碼段，其規(guī)約變量下界為2、步長(zhǎng)為1.shortinta[1000]，b[1000]，c[1000];for(i=2;i<1000;i++)a[i]=b[i]+c[i];通過(guò)循環(huán)正規(guī)化技術(shù)處理后，該循環(huán)可以變形為:shortinta[1000]，b[1000]，c[1000];for(i=1;i<999;i++)a[i+1]=b[i+1]+c[i+1];本文使用“格”作為數(shù)據(jù)流分析中對(duì)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的形式化表示方法.傳統(tǒng)的數(shù)據(jù)流分析[6]可以看作是沿著變量位寬的傳播進(jìn)行操作，或者為每個(gè)變量維持一個(gè)位向量.前者無(wú)法得到算術(shù)操作的精確的結(jié)果，因?yàn)閷?duì)一個(gè)8位數(shù)的位傳播往往導(dǎo)致一個(gè)9位的結(jié)果，盡管8位數(shù)就足夠了，或者一個(gè)變量中只有最重要的幾個(gè)位能夠進(jìn)行位消去.而后者不支持精確的算術(shù)分析，因?yàn)樗鶗?huì)保守的假設(shè)每個(gè)加法結(jié)果都產(chǎn)生進(jìn)位.所以，在進(jìn)行數(shù)據(jù)流分析的時(shí)候，我們使用“格”結(jié)構(gòu)來(lái)形式化表達(dá)內(nèi)部數(shù)據(jù)結(jié)構(gòu).一個(gè)數(shù)據(jù)范圍可以看作是從某個(gè)下界到某個(gè)上界變化的整數(shù)的子范圍的簡(jiǎn)單連接，因此，用數(shù)據(jù)范圍就能夠清楚的表達(dá)某個(gè)變量的下界和上界.因?yàn)槲覀冎恍枰靡粋€(gè)簡(jiǎn)單的范圍就可以表示變量的所有可能的值，因此，盡管該表示方法不允許消去低位的位，卻可以對(duì)算術(shù)表達(dá)式實(shí)現(xiàn)精確的計(jì)算.我們選擇格來(lái)表示數(shù)據(jù)范圍傳播基于以下三個(gè)方面的因素:首先，這種表示方法能夠?qū)⑽粚挿治鰬?yīng)用到更普遍的值范圍傳播問(wèn)題，這對(duì)于解決值預(yù)測(cè)、分支預(yù)測(cè)、常數(shù)傳播、過(guò)程復(fù)制和程序驗(yàn)證都非常有效.第二，該表示方法保證了精確性，這對(duì)于大多數(shù)算術(shù)應(yīng)用非常重要;第三也是最重要的，在我們的編譯算法中，用生存期(liferange)作為處理子字的標(biāo)準(zhǔn)，在該結(jié)構(gòu)中，我們將每個(gè)子字的生存期映射到值的范圍，從而獲得每個(gè)生存期的精確結(jié)果，所以，這種“格”的結(jié)構(gòu)也可視為對(duì)生存期傳播的表示.在格的表示中，值的生存期被分配到某個(gè)變量，格自下向上提升，如圖2所示值的定義和計(jì)算如下:(1)⊥DR⊥:未初始化時(shí)的子字生存期的值(2)TDR⊥:不能靜態(tài)決定的值，即子字集合的生存期的上界(3)∪:生存期的并集〈al，ah〉∩〈bl，bh〉=〈min(al，bl)，max(ah，bh)〉(4)∩:生存期的交集〈al，ah〉∩〈bl，bh〉=〈max(al，bl)，max(ah，bh)〉以如下所示的代碼段為例，這是取自MPEG-4算法中的一段簡(jiǎn)化的循環(huán)代碼，for(i=0;i<h;i++){C[i]=A[i]-B[i]/*1S*/D[i+1]=D[i]+C[i]/*2S*/}我們通過(guò)分析，得到代碼段中的真相關(guān)和輸出相關(guān)，圖3分別表示循環(huán)的數(shù)據(jù)相關(guān)以及循環(huán)分配后得到的強(qiáng)連通部件.相關(guān)圖的強(qiáng)連通部件表示帶有向邊的節(jié)點(diǎn)的最大集合，帶有多個(gè)節(jié)點(diǎn)的強(qiáng)連通部件表示相關(guān)循環(huán)中語(yǔ)句的最大集合.語(yǔ)句S1不帶自圈，所以它自己組成了一個(gè)單一的強(qiáng)連通部件，S1能夠按照子字并行方式處理.語(yǔ)句S2在循環(huán)中是自相關(guān)的，我們用循環(huán)展開(kāi)來(lái)消除這種相關(guān)，如下代碼所示.for(i=0;i<h;i+=2){C[i]=A[i]-B[i];C[i+1]=A[i+1]-B[i+1]}首先根據(jù)操作數(shù)的