摘 要： 多媒體程式是資料密集型應用，其核心程式碼部分佔用了大部分的執行時間，因此，對多媒體應用程式的研究大多針對其核心程式碼部分。本文圍繞多媒體應用程式的核心內層迴圈，分析其子字並行特點，提出了1種新穎的按位資料流分析方法，能夠確定程式的內層迴圈，為進1步深入研究奠定基礎。
關鍵詞： 多媒體;子字並行;內層迴圈;資料流
1 引言
隨著多媒體技術和網路的迅猛發展，多媒體產業正在以驚人的速度擴充套件，卓越的多媒體處理能力成為對現代計算機的必然要求之1。
從體系結構研究方面，研究人員在通用處理器中增加新的多媒體功能處理部件以及相應的多媒體處理指令，或者設計專用的多媒體處理器（ASIP），都能夠完成對多媒體資訊的高效處理。但是，與多媒體處理器的發展相比，面向多媒體的編譯技術明顯滯後。出於多媒體應用程式與科學計算或其他通用應用程式的特殊性，開發人員往往還是會採用複雜低效且易出錯的手工編碼方式產生程式碼。
因此，我們認為，無論是從計算機體系結構、還是從編譯器等多方面來提高計算機的多媒體處理能力，首先必須要針對多媒體應用特點，對多媒體應用程式的特徵進行分析和研究。縱觀歷史，有許多面向程式特徵提高計算機效能的典範，證明了對程式特徵的分析和研究直接影響到計算機效能的優化和設計。例如，IBM公司與美國加利福尼亞大學通過對應用程式的統計和研究發現，CISC指令集80%的指令只在20%的執行時間內用到，因此簡化了計算機指令集結構，提出了RISC指令集結構，從而提高了機器效能，減輕設計人員負擔。迴圈是多媒體應用程式的核心，在程式的執行過程中幾乎佔了90%的時間，而核心迴圈體—內層迴圈又是迴圈的關鍵。有實驗資料表明，大多數多媒體應用在最內層迴圈花費了80%~90%的執行時間。因此，要挖掘多媒體應用的程式特徵，深入核心迴圈體的內層迴圈提取特徵是非常有必要的。本文圍繞多媒體應用程式的特點，對其核心程式碼———內層迴圈和並行性進行深入的分析，針對當前編譯技術的不足提出1種確定內層迴圈的資料流分析方法。本文第2部分介紹並分析多媒體應用程式的核心程式碼，以及其固有的子字並行性。第3部分介紹相關編譯技術的研究發展。第4部分介紹按位的資料流分析。第5部分給出結論。
2 多媒體應用程式核心分析
通過對多媒體應用程式定性研究分析，多媒體應用不同於科學計算和通用應用，它具有自身固有的特徵：
（1）內在的並行性
（2）資料型別的連續性
（3）實時響應性：如視訊會議和電子商務等，需要可靠迅捷的實時響應
（4）資料有序性：由於弱的空間區域性性，多媒體的很多資料與操作都具有強烈的有序性
（5）高網路頻寬性：隨著網路的發展，多媒體應用對網路頻寬的要求越來越高，如網路遊戲、網上視訊點播等
（6）高儲存頻寬性：因為多媒體應用程式處理的資料量往往很大、甚至海量，所以，對儲存頻寬的要求也很高。
多媒體應用程式往往包含1個或多個程式碼核心，代表了大部分的動態指令執行，在程式執行過程中幾乎佔據了90%的時間，所以，除開以上介紹的多媒體應用程式的這些特點，從編譯的角度，我們更關心其核心部分程式碼———內層迴圈。1般來說，這些核心部分執行的操作具有並行和計算密集的特點，且程式碼控制結構規則，需要對大量的、連續的、流的、可變精度的資料進行操作。首先，並行性的特徵源於多媒體應用程式對大量獨立的資料集合實現相同的操作，因此，這些操作能夠並行執行。第2，大量的計算密集型的操作和程式碼的控制結構並不複雜，與典型的整型程式相比，多媒體應用程式中通常幾乎不帶有分支，控制結構非常規則。第3，輸入輸出資料幾乎不存在時間區域性性，因此具有流特性，流資料即時操作即時丟棄，結果或者直接寫回記憶體或者傳送至網路作為輸出資料流，如流視訊幀、流音訊取樣。第4，根據不同的資料型別，資料元素的精度要求是可變的，如8位的影象畫素、16位的音訊取樣。1般來說，多媒體應用程式處理的資料大小為8位、16位、32位、64位整型，或32位單精度浮點、64位雙精度浮點。多媒體應用程式的每個資料以“子字”（subword）的形式進行操作，因此這種並行性稱為“子字並行”（subword paral—lelism）。
傳統的通用處理器是以字為單位進行處理的，1般是32位或64位，而影象資訊通常以大量的低精度或短資料型別的形式出現，為了不浪費資料通路寬度，充分高效的利用處理器上的多個計算單元，提高處理器效能和處理多媒體資訊的效率，子字並行的處理方式應運而生。子字並行[1]是1種特殊的資料並行，在子字並行中，1個字就是1個數據集。
子字是包含在字中的更低精度的資料單元。我們將若干個子字封裝到1個字中，然後對整個字進行處理。子字並行允許在1個計算單元（字單元）內對2個、4個或8個操作（子字）同時進行。圖1（a）所示的是1個普通的`32位操作與相應的子字並行處理進行比較，圖1（b）為展示的是在子字單元上如何進行子字並行處理。
顯然，與全字長的處理相比，子字並行操作可以帶來更大的並行度。子字並行是處理多媒體型別資料應用的最自然的方式，它能夠充分利用多媒體演算法資料精度小、內部迴圈多的特點。對於處理器設計來說，子字並行大大提高了處理器的並行度，節省了資料通路和暫存器資源;多媒體指令的擴充套件又提供了更高的處理速度;同時，對於嵌入式多媒體處理器來說，為支援子字並行而組織資料通路，也可以獲得更低的並行開銷和更少的控制重複。有了子字並行的處理器方式，單1的1條LOAD/STORE指令就可以在儲存器和暫存器之間同時移動若干個被封裝的子字，因而，儲存能力也得到了提高。因此，不論是通用微處理器還是多媒體微處理器或DSP，子字並行都是提高處理器效能、加速多媒體處理的有效方式。
3 相關研究
子字並行的處理器方式雖然很有效，但影象處理程式主要還是以序列程式方式編寫（如：C），結果卻需要以並行的方式執行，因而對編譯器提出了很高的要求，需要編譯器來決定如何將子字資料按照正確的順序封裝入源暫存器，進行相應子字對之間的運算，運算結束後，按照需求，將結果以正確的順序從目標暫存器中提取出來。因此，和子字並行在體系結構研究上取得的成功相比，通用編譯器技術卻不能自動的從應用程式中提取這種並行性，進而無法充分利用這類特殊的指令集，編譯技術在自動高效的識別、產生和處理子字並行指令方面，尚未取得令人滿意的結果。
以MMX[2~4]為代表，借鑑SIMD陣列處理技術如向量處理來產生優化程式碼，採用向量處理編譯技術，能夠獲得1。5到6。5的加速比，這樣的結果已經相當不錯。因為對於多媒體應用這類的計算密集型應用，內層迴圈是程式碼中最關鍵的部分，也是體現最多並行的部分，所以向量處理的目的在於識別內層迴圈，採用迴圈變換來得到向量操作，而這些操作就可以用子字並行指令實現。向量處理包括：迴圈分析，迴圈正規化，依賴性分析，純量擴充套件，迴圈分佈，向量化和迴圈分段。
MIT的Larsen和Amarasinghe提出superword[5]的概念，認為子字並行不僅僅是1種資料並行，還是1種指令級並行的方式，因此，對於1個基本塊中按相同順序執行的相同的操作，都可以進行並行處理。這種方法與傳統的向量編譯方法的不同在於它的向量化是對1個基本塊內部指令的向量化。該方法基於SUIF[5]實現，並應用於Motorola的AltiVec擴充套件。這種方法解決了基本塊內部的並行處理問題，但是隻適用於基本塊結構簡單的情況，對於帶條件轉移的基本塊如何處理，並沒有進行深入研究，而且這種方法由於過於複雜，不具備很好的移植性，也難於實現，所以，只能作為1種啟發式方法進行研究。
與現有研究的不同在於，本文沿襲向量編譯的原理，根據影象處理程式的特點，著重對關鍵部分———內層迴圈進行挖掘，提出了按位的資料流分析方法，為進1步編譯優化技術的使用奠定基礎。
4 按位資料流分析
資料流分析能夠幫助我們確定內層迴圈，我們首先用迴圈正規化技術（loop normalization）來保證迴圈的迭代空間的規則性和依賴性驗證的簡單。本文主要考察針對for迴圈的匹配，在開始進行子字並行規範之前，我們假設該迴圈中所有上下界都明確定義。
對於C編譯器而言，我們假設其規約變數下界為0、變化步長為1、且所有迴圈迭代都可以執行，則舊的規約變數將為新規約變數的仿射函式代替，下標表達式和下界也因此做相應修改。下例所示為1個小的迴圈程式碼段，其規約變數下界為2、步長為1。
short inta[1000]，b[1000]，c[1000];
for（i=2;i<1000;i++）
a[i]=b[i]+c[i];
通過迴圈正規化技術處理後，該迴圈可以變形為：
short inta[1000]，b[1000]，c[1000];
for（i=1;i<999;i++）
a[i+1]=b[i+1]+c[i+1];
本文使用“格”作為資料流分析中對內部資料結構的形式化表示方法。傳統的資料流分析[6]可以看作是沿著變數位寬的傳播進行操作，或者為每個變數維持1個位向量。前者無法得到算術操作的精確的結果，因為對1個8位數的位傳播往往導致1個9位的結果，儘管8位數就足夠了，或者1個變數中只有最重要的幾個位能夠進行位消去。而後者不支援精確的算術分析，因為它往往會保守的假設每個加法結果都產生進位。所以，在進行資料流分析的時候，我們使用“格”結構來形式化表達內部資料結構。1個數據範圍可以看作是從某個下界到某個上界變化的整數的子範圍的簡單連線，因此，用資料範圍就能夠清楚的表達某個變數的下界和上界。因為我們只需要用1個簡單的範圍就可以表示變數的所有可能的值，因此，儘管該表示方法不允許消去低位的位，卻可以對算術表示式實現精確的計算。
我們選擇格來表示資料範圍傳播基於以下3個方面的因素：首先，這種表示方法能夠將位寬分析應用到更普遍的值範圍傳播問題，這對於解決值預測、分支預測、常數傳播、過程複製和程式驗證都非常有效。第2，該表示方法保證了精確性，這對於大多數算術應用非常重要;第3也是最重要的，在我們的編譯演算法中，用生存期（life range）作為處理子字的標準，在該結構中，我們將每個子字的生存期對映到值的範圍，從而獲得每個生存期的精確結果，所以，這種“格”的結構也可視為對生存期傳播的表示。
在格的表示中，值的生存期被分配到某個變數，格自下向上提升，如圖2所示值的定義和計算如下：
（1）⊥DR⊥：未初始化時的子字生存期的值
（2）TDR⊥：不能靜態決定的值，即子字集合的生存期的上界
（3）∪：生存期的並集〈al，ah〉∩〈bl，bh〉=〈min（al，bl），max（ah，bh）〉
（4）∩：生存期的交集〈al，ah〉∩〈bl，bh〉=〈max（al，bl），max（ah，bh）〉
以如下所示的程式碼段為例，這是取自MPEG—4演算法中的1段簡化的迴圈程式碼，
for（i=0;i<h;i++）{
C[i]=A[i]—B[i] /*1S*/
D[i+1]=D[i]+C[i] /*2S*/
}
我們通過分析，得到程式碼段中的真相關和輸出相關，圖3分別表示迴圈的資料相關以及迴圈分配後得到的強連通部件。相關圖的強連通部件
表示帶有向邊的節點的最大集合，帶有多個節點的強連通部件表示相關迴圈中語句的
最大集合。語句S1不帶自圈，所以它自己組成了1個單1的強連通部件，S1能夠按照子字並行方式處理。語句S2在迴圈中是自相關的，我們用迴圈展開來消除這種相關，如下程式碼所示。
for（i=0;i<h;i+=2）{
C[i]=A[i]—B[i];
C[i+1]=A[i+1]—B[i+1]}
首先根據運算元的型別進行適當的展開，如暫存器為32位，那麼對於C語言中定義的short型別的int運算元，就要將迴圈展開2次，然後進行非迴圈指令排程，組合相同迴圈指令的所有例項，這樣，S2也可以按照子字並行方式執行了。
5 結論與展望
本文根據多媒體應用程式的特點，對其關鍵核心———內層迴圈進行分析研究，在現有向量編譯的基礎上，提出了挖掘內層迴圈的按位資料流分析演算法，方法簡單，容易執行，很好的挖掘了影象處理程式內在固有的子字並行。我們將在此工作基礎上，進1步融合多媒體編譯優化技術，在更復雜的迴圈結構上進行分析研究。
參考文獻：
[1] R B Lee。Subword parallelism with max—2[J]。IEEE Micro，1996，16（4）：51—59。
[2] A Krall，S Lelait。Compilation techniques for multimedia pro—cessors [J]。 International Journal of Parallel Programming，2000，28（4）：347—361。2577第 12A 期吳 丹：1種確定多媒體應用程式內層迴圈的子字並行編譯方法
[3]Intel Corporation。IA—32Intel Architecture Software Devel—oper’s Manual[Z]。Volume2A：Instruction Set Reference，A—M。2004。
[4] Intel Corporation。IA—32Intel Architecture Software Devel—oper’s Manual[Z]。Volume2B：Instruction Set Reference，N—Z。2004。
[5] Samuel Larsen，Saman Amarasinghe。Exploiting superword level parallelism with multimedia instruction sets[J]。 ACM SIG—PLAN Notices，2000，35（5）：145—156。
[6] Randy Allen，Ken Kennedy。Optimizing Compilers for Modern Architectures：A Dependence—Based Approach[M]。San Mateo，USA ：Morgan Kaufmann，2002