摘 要： 多媒體程序是數據密集型應用，其核心代碼部分佔用了大部分的執行時間，因此，對多媒體應用程序的研究大多針對其核心代碼部分。本文圍繞多媒體應用程序的核心內層循環，分析其子字並行特點，提出了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