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

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

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