一種軟件流水的反流水算法

1、一種軟件流水的反流水算法*Supported by the National Natural Science Foundation of China under Grant No.60173010 (國家自然科學基金)作者簡介: 湯志忠(1946),男,教授,博士生導師,主要研究領域為計算機系統(tǒng)結構,指令級并行算法,并行編譯技術;李文龍(1977),男,博士生,主要研究領域為指令級并行算法;蘇伯珙(1939),男,教授,主要研究領域為并行算法,優(yōu)化編譯技術.湯志忠1+, 李文龍1, 蘇伯珙21(清華大學 計算機科學與技術系,北京 100084)2(William Paterson大學 計算機科

2、學系,新澤西洲 07470,美國)A De-Pipeline Algorithm for Software-PipelineTANG Zhi-Zhong1+, LI Wen-Long1, SU Bo-Gong21(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)2(Department of Computer Science, William Paterson University, New Jersey 07470, USA)+ Corresponding au

3、thor: Phn: +86-10-62772213, E-mail: tzz-dcs, Received 2003-09-24; Accepted 2004-03-02Tang ZZ, Li WL, Su BG. A de-pipeline algorithm for software-pipeline. Journal of Software, 2004,15(7): 987993.Abstract:Software pipelining is a loop optimization technique that has been widely implemented in modern

4、optimizing compilers. In order to fully utilize the instruction level parallelism of the recent VLIW DSP processors, DSP programs have to be optimized by software pipelining. However, because of the transformation of the original sequential code, a software-pipelined loop is often difficult to under

5、stand, test, and debug. It is also very difficult to reuse and port a software-pipelined loop to other processors, especially when the original sequential code is unavailable. In this paper we propose a de-pipelining algorithm which converts the optimized assembly code of a software-pipelined loop b

6、ack to a semantically equivalent sequential counterpart. Preliminary experiments on 20 programs verify the validity of the proposed de-pipelining algorithm.Key words:software pipelining; de-pipelining; instruction level parallelism摘 要:軟件流水是一種循環(huán)程序的優(yōu)化技術,已經廣泛應用于現(xiàn)代優(yōu)化編譯器中.為了充分利用VLIW DSP處理機的指令級并行性,必須使用軟件流

7、水技術對DSP程序進行優(yōu)化.然而,在串行源代碼不存在的情況下,對軟件流水后的原始代碼進行變換、理解、測試和調試,并轉換成其他處理機的代碼是非常困難的.提出了一種反流水技術,它能夠將軟件流水后的優(yōu)化匯編代碼反向轉換成語義等價的相應代碼.通過20個程序的初步實驗,驗證了所提出的反流水算法的正確性.關鍵詞:軟件流水;反流水;指令級并行中圖法分類號:TP338文獻標識碼: A在過去的幾年中,數(shù)字信號處理機(digital signal processor,簡稱DSP)發(fā)展迅速1,由于對提高性能及解決大范圍應用程序的持續(xù)需要,許多廠商推出了基于VLIW(very long instruction wor

8、d)的DSP處理機,為了充分利用這些VLIW DSP處理機的指令級并行性,DSP程序一般都要經過軟件流水的優(yōu)化.軟件流水24通過重疊不同循環(huán)體的執(zhí)行來加快循環(huán)程序在指令級并行處理機上的執(zhí)行速度,這種技術已經研究多年,并在許多優(yōu)化編譯器中得以實現(xiàn),例如Texas Instruments的TIC6X和StarCore的SC140等DSP處理機的編譯器.研究反軟件流水技術的動機是:首先,由于對原始串行代碼的變換,軟件流水后的代碼很難理解、測試及調試.其次,由于處理機之間指令兼容性的問題,經過軟件流水后的循環(huán)代碼很難在其他處理機中移植和使用.第三,雖然軟件流水后的循環(huán)程序、CPU的執(zhí)行時間效益很好,但

9、在存儲器使用上,它的空間效益可能很差.在應用軟件流水對循環(huán)進行優(yōu)化時,并沒有考慮存儲空間對性能的影響.對于某些存儲空間有限的應用,軟件流水不適合.最后,我們注意到,大量的DSP應用程序已被軟件流水優(yōu)化過,并且被測試過,但是這些應用程序的串行源代碼已經不存在了.據我們所知,到目前為止,有關反軟件流水算法的研究還很少,但是,這是一個應用前景非常好的研究領域,對于重新獲取源代碼和在不同處理機之間移植軟件流水后的代碼提供了可能.本文提出了一種反軟件流水算法.首先使用嚴格的時序關系來識別循環(huán)程序的核心代碼,然后利用循環(huán)展開技術,構造軟件流水循環(huán)的數(shù)據相關性圖(DDG).最后,利用DDG來構造一個語義等價

10、的串行循環(huán)程序.本文首先通過一個例子來說明什么是軟件流水和反軟件流水,然后,具體介紹我們提出的反軟件流水算法,接下去是20個典型程序的實驗結果,最后是結論.1 軟件流水與反軟件流水圖1是點積函數(shù)中的循環(huán)經過軟件流水后的代碼,用TIC62處理機的匯編語言5表示.MVK 0X32,B0MVC CSR,B8ZERO A4ZERO B5AND -2,B8,B4MVC B4,CSRSUB B0,5,B0MVK 0X2,A1L1:B0 B L2LDH*+A0(4),A3LDH*+B7(4),B4LDH*+A0(2),A3LDH*+B7(2),B4B0 B L2LDH*+A0(4),A3LDH*+B7(4)

11、,B4L2:LDH*+A0(2),A3LDH*+B7(2),B4B0 B L2MPY B4,A3,B6!A1ADD B6,B5,B5LDH*+A0(4),A3LDH*+B7(4),B4B0SUB B0,1,B0MPY B4,A3,A5!A1ADD A5,A4,A4A1SUB A1,1,A1L3:LDH*+A0(2),A3LDH*+B7(2),B4MPY B4,A3,B6ADD B6,B5,B5MPY B4,A3,A5ADD A5,A4,A4MPY B4,A3,B6ADD B6,B5,B5MPY B4,A3,A5ADD A5,A4,A4MPY B4,A3,B6ADD B6,B5,B5MPY B4

12、,A3,A5ADD A5,A4,A4ADD B6,B5,B5ADD A5,A4,A4Fig.1 Software pipelined loop of dot-product function in TIC62 assembly code圖1 TIC62匯編碼表示的點積函數(shù)的軟件流水循環(huán)結果反軟件流水是軟件流水的逆向操作,是把已經軟件流水的循環(huán)代碼轉換成語義等價的串行代碼.對于圖1中的軟件流水循環(huán)代碼,反軟件流水是把它轉換成如圖2所示的語義等價的串行循環(huán)代碼.一般來說,一個軟件流水后的循環(huán)程序由3部分組成:裝入、核心和排空.與硬件流水線一樣,軟件流水的裝入部分和排空部分只執(zhí)行一次,核心部分要重復

13、執(zhí)行.在圖1中,從L1到L2是裝入部分,L2到L3是核心部分,L3后面的指令屬于排空部分.在裝入部分和核心部分存在著嚴格的時序關系.例如,如果標號L1中的指令在時刻t發(fā)射,那么位于L1和L2之間的另外3條指令一定要在時刻t+1,t+2和t+3發(fā)射.任何阻塞和延遲執(zhí)行都會破壞程序的語義,傳統(tǒng)的控制相關和數(shù)據相關圖都不能表示這種嚴格的時序關系.實際上,在反軟件流水的結果出來之前,要理解軟件流水循環(huán)的語義是非常困難的,連續(xù)循環(huán)體的折疊以及多個分支指令的延遲使得理解軟件流水循環(huán)的控制流結構變得更加困難.如圖1所示的軟件流水循環(huán)經過反軟件流水之后,生成如圖2所示的語義等價的串行代碼,我們很容易理解圖2的

14、串行代碼,關于代碼的詳細語義讀者可以參照文獻5. MVK0X32, B0 ZEROA4 ZEROB5LE:LDH*+A0(4), A3 LDH*+B7(4), B4 LDH*+A0(2), A3 LDH*+B7(2), B4 B0SUBB0, 1, B0 B0BLE MPYB4, A3, B6 NOP MPYB4, A3, A5 ADDB6, B5, B5 ADDA5, A4, A4Fig.2 The semantically equivalent code of a software pipelined loop of dot product in TIC62 assembly code圖2

15、 TIC62匯編碼表示的與點積軟件流水循環(huán)語義等價的串行代碼比較圖1和圖2這兩段語義完全等價的代碼,可以很容易看出,經過軟件流水的循環(huán),其時間效益更好,它的執(zhí)行時間比串行代碼要快5倍左右,而串行代碼的空間效益好,它比軟件流水循環(huán)節(jié)省了3倍的程序存儲空間.另外,為了執(zhí)行軟件流水循環(huán),必須有大量的功能部件和寄存器.因此,軟件流水循環(huán)適合在類似于VLIW這種提供大量資源的處理機上運行.2 反軟件流水算法下面結合圖3的例子,解釋我們所提出的反軟件流水算法.圖3給出的是點積函數(shù)中循環(huán)經過軟件流水后的代碼,采用TIC62處理機的匯編代碼5表示.圖中最左面一列是行號,符號“|”表明當前行的指令可以與上一行上

16、的指令并行執(zhí)行.反軟件流水算法的操作步驟如下:第1步.循環(huán)檢測.從給定的代碼中,識別出軟件流水的循環(huán)體,這包括循環(huán)的入口和循環(huán)體的長度等,識別的準則如下:如果有一條向回跳轉的分支指令,那么分支指令的目標地址就是循環(huán)的入口,循環(huán)體的長度等于向回跳轉的分支指令與循環(huán)入口之間的距離再加上分支延遲槽的時間.如果在循環(huán)入口上面的,且代碼長度等于分支延遲時間加1的區(qū)域內包含有向前跳轉的分支指令,則分支指令的目標地址就是循環(huán)的入口,軟件流水循環(huán)體的長度等于最近的分支指令和循環(huán)入口之間的距離.在圖3中,L2是向回跳轉的分支指令的目標地址,因此L2就是軟件流水循環(huán)的入口,同時,軟件流水循環(huán)體的長度等于2.第2步

17、.活變量分析.從一個給定的軟件流水循環(huán)體中找出所有最后執(zhí)行的指令.通常,活變量包含在最后執(zhí)行的指令中.最后執(zhí)行的指令一般分為下面兩種類型:往活變量寄存器中寫數(shù)據的指令和寫存儲器的指令.具體尋找活變量的方法是:在循環(huán)區(qū)域中自下往上搜索所有最后執(zhí)行的指令.在圖3中,Add B6,B5,B5和Add A5,A4,A4是最后執(zhí)行的指令,因此活變量為B6和A5.1MVK 0X32,B02ZERO A43|ZERO B54SUB B0,5,B05|MVK 0X2,A16B0B L27LDH *+A0(4),A38|LDH *+B7(4),B49LDH *+A0(2),A310|LDH *+B7(2),B4

18、11|B0B L212LDH *+A0(4),A313|LDH *+B7(4),B414L2:LDH *+A0(2),A315|LDH *+B7(2),B416|B0B L217|MPY B4,A3,B618|!A1ADD B6,B5,B519LDH *+A0(4),A320|LDH *+B7(4),B421|B0SUB B0,1,B022|MPY B4,A3,A523|!A1ADD A5,A4,A424|A1SUB A1,1,A125LDH *+A0(2),A326|LDH *+B7(2),B427|MPY B4,A3,B628|ADD B6,B5,B529MPY B4,A3,A530|AD

19、D A5,A4,A431MPY B4,A3,B632|ADD B6,B5,B533MPY B4,A3,A534|ADD A5,A4,A435MPY B4,A3,B636|ADD B6,B5,B537MPY B4,A3,A538|ADD A5,A4,A439ADD B6,B5,B540ADD A5,A4,A4Fig.3 A segment of TIC62 assembly code圖3 TIC62處理機的匯編代碼片段第3步.數(shù)據相關性圖的構造.構造軟件流水循環(huán)的數(shù)據相關性圖(DDG).首先,展開循環(huán)體k-1次,k等于循環(huán)體的指令組中最多指令的個數(shù).指令組是指可以并行執(zhí)行的一組指令,在圖3的代碼

20、段中,由|分隔的指令屬于同一個指令組.其次,從第2步找到的最后執(zhí)行的指令開始,使用高度優(yōu)先的算法以自下向上的方式構造數(shù)據相關性.圖4是重新構造的點積函數(shù)中軟件流水循環(huán)的數(shù)據相關性圖.LDH *+A0(4),A3LDH *+B7(4),B4MPY B4,A3,A5ADD A5,A4,A4B0SUB B0,1,B0A1 SUB A1,1,A1LDH *+A0(2),A3LDH *+B7(2),B4MPY B4,A3,B6ADD B6,B5,B5B0 B L2LDH *+A0(4),A3LDH *+B7(4),B4MPY B4,A3,A5ADD A5,A4,A4B0SUB B0,1,B0A1 SUB

21、 A1,1,A1LDH *+A0(2),A3LDH *+B7(2),B4MPY B4,A3,B6ADD B6,B5,B5B0 B L2LDH *+A0(4),A3LDH *+B7(4),B4MPY B4,A3,A5ADD A5,A4,A4B0SUB B0,1,B0A1 SUB A1,1,A1LDH *+A0(2),A3LDH *+B7(2),B4MPY B4,A3,B6ADD B6,B5,B5B0 B L2LDH *+A0(4),A3LDH *+B7(4),B4MPY B4,A3,A5ADD A5,A4,A4B0SUB B0,1,B0A1 SUB A1,1,A1LDH *+A0(2),A3LD

22、H *+B7(2),B4MPY B4,A3,B6ADD B6,B5,B5B0 B L2LDH *+A0(4),A3LDH *+B7(4),B4MPY B4,A3,A5ADD A5,A4,A4B0SUB B0,1,B0A1 SUB A1,1,A1LDH *+A0(2),A3LDH *+B7(2),B4MPY B4,A3,B6ADD B6,B5,B5B0 B L2Fig.4 Data dependence graph (DDG) of running example圖4 運行例子的數(shù)據相關性圖第4步.軟件流水循環(huán)的檢查.檢查一個循環(huán)是否經過軟件流水.如果在循環(huán)體中存在兩條指令Ii和Ij,它們在循環(huán)

23、體中的距離小于在數(shù)據相關性圖中的距離,那么可以說這個循環(huán)體是經過軟件流水處理的.比較圖3和圖4,可以確認,圖3中所識別出的循環(huán)是經過軟件流水的循環(huán).第5步.找出裝入和排空部分.在給定的代碼段中找出軟件流水循環(huán)的裝入部分和排空部分.(1) 裝入部分的查找:從循環(huán)的入口開始向上搜索,直到軟件流水循環(huán)的上邊界,在搜索過程中,找出所有包含循環(huán)體中指令的指令組,其中最上面的那個指令組是裝入部分的上邊界.(2) 排空部分的查找:從軟件流水的循環(huán)體底部開始向下搜索,直到軟件流水循環(huán)的下邊界,在搜索的同時找出所有包含循環(huán)體中指令的指令組,其中最下面的指令組是排空部分的下邊界.在圖3中,裝入部分是編號613,排

24、空部分是編號2540.第6步.重新調度.將DDG轉換為串行代碼.(1) 在從上述第(2)步找到的最后執(zhí)行的指令中,自下而上利用列表調度法排列DDG上關鍵路徑的偏序列表.為了滿足所有指令的延遲時間,必要時可以插入NOP操作.(2) 將所有在非關鍵路徑上的指令插入到關鍵路徑中.(3) 刪除裝入和排空部分中所有包含在循環(huán)體中的指令.第7步.循環(huán)次數(shù)計算.計算出軟件流水循環(huán)串行代碼的執(zhí)行次數(shù).除了要考慮在給定的軟件流水循環(huán)中所設置的執(zhí)行次數(shù)初始值以外,還必須考慮其他諸多因素,如在裝入部分所執(zhí)行的循環(huán)次數(shù),其值等于裝入部分中包含的轉移目標是循環(huán)入口的分支指令個數(shù).另外,在排空部分最后執(zhí)行的指令條數(shù)以及在

25、給定的軟件流水循環(huán)體中,向回跳轉的分支指令與修改循環(huán)執(zhí)行次數(shù)指令的相關位置等都影響著串行代碼的執(zhí)行次數(shù).從第(6)步第(7)步,我們得到了如圖2所示的點積函數(shù)的串行代碼,與圖3中給定的循環(huán)在語義上是等價的.3 實驗結果利用我們所提出的反軟件流水算法進行了20個程序的實驗,這些代碼屬于不同的應用程序,循環(huán)的長度各不相同,裝入和排空部分也各不相同,這些程序均從TMS320C62x/C62x的用戶編程手冊中獲取,感興趣的讀者可以參照文獻5獲取相關信息.實驗中,我們使用TIC62編譯器或者手工線性匯編器5生成代碼段.首先,我們使用反流水技術將這些代碼轉換成串行代碼,接著使用TIC62的模擬器來運行原始

26、的匯編代碼和轉換后的匯編代碼.所有的計算結果表明,對于這些程序而言,我們的反流水算法是正確的.表1概括了這些軟件流水循環(huán)的特點以及20個程序的反流水結果,其中Sub是指修改循環(huán)執(zhí)行次數(shù)的指令,branch是指跳到循環(huán)入口的分支指令.注意,其中的“1”表示由編譯器生成,“2”表示由線性匯編器生成.對于測試的每個程序,因為其軟件流水循環(huán)的特點各不相同,經過反軟件流水后,其執(zhí)行次數(shù)、循環(huán)體長度都發(fā)生了變化,以第1個測試程序dot product_1為例,因為有顯示的裝入和排空,以及初始設置的循環(huán)執(zhí)行次數(shù),所以,反流水之后其執(zhí)行次數(shù)為50,循環(huán)體長度為14.Table 1 Experimental r

27、esult表1 實驗結果Assembly codeCharacteristicsSoftware-Pipelined loopDe-Pipelining resultInitial countBody lengthCount valueBody lengthDot product_12Normal4315014Dot product_22No postlude5015014Dot product_32Sub & branch in prelude only, no postlude5715014Dot product_42Branch in prelude only, no postl

28、ude511514Dot product_51Normal5015014FIR1No postlude3233215FIRnorld1No postlude1621615IIR2No postlude100410013Codebook2No postlude,conditional branch in loop body322329Vec_mpy1Normal7537516Latsynth1Normal200520025WVS2Normal4925016Add_test1No postlude5256Loop_test_11Branch in prelude only502506Loop_te

29、st_21Branch in prelude only10021007Loop_test_31Branch in prelude only10031007Loop_test_41Normal5055011Loop_test_81No prelude2092021Loop_test_121No prelude25232527Loop_test_161No prelude501750354 相關工作和結論在軟件流水的研究領域,文獻6,7給出的軟件流水算法已經研究了多年,并且在很多的優(yōu)化產品編譯器中得以實現(xiàn).而對于反編譯循環(huán)軟件流水的算法,目前反編譯主要是將匯編代碼或者二進制代碼反編譯成源程序,比如

30、在軟件工程領域中8,將較低級的可執(zhí)行代碼轉換成更容易理解的高級代碼,以及在Java應用方面,將字節(jié)碼轉換成源程序9等.我們給出了反軟件流水算法及其實驗結果.對于DSP用戶,我們的算法對于理解和調試經過軟件流水后的代碼是一個非常有用的工具.進一步地,我們提出的反軟件流水算法可以進一步擴展用于解決代碼兼容性問題,包括VLIW體系結構的軟件流水循環(huán).雖然可以使用動態(tài)重調度10來解決兼容性問題,但是它不能解決包含軟件流水循環(huán)的代碼.通過使用反軟件流水技術,可以將軟件流水循環(huán)的代碼從一個源VLIW處理機轉換為一系列語義等價的中間代碼級的串行代碼,然后這些中間代碼可以送給目標VLIW處理機的編譯器.我們的

31、代碼適合于從一種VLIW DSP處理機到其他DSP處理機6匯編代碼的轉換.本文的方法主要針對不帶分支的、最內層循環(huán)軟件流水后的代碼.如何擴展本文的方法用于處理帶分支及多重循環(huán)軟件流水11后的代碼是我們進一步的研究工作.References:1 Strauss W. Digital signal processing: The new semiconductor industry technology driver. IEEE Signal Processing Magazine, 2000,17(2):5256.2 Rau R, Fisher J. Instruction-Level para

32、llel processing: History, overview, perspective. Technical Report, HPL-92-132, HP Labs, 1992.3 Su B, Ding S, Xia J. URPRAn extension of URCR for software pipelining. In: Daniel D, ed. ACM SIGMICRO Newsletter. New York: ACM Press, 1986. 94103.4 Wang J, Eisenbeis C. Decomposed software pipelining: A n

33、ew approach to exploit instruction level parallelism for loop programs. In: Michael C, ed. Proc. of the Architectures and Compilation Techniques for Fine and Medium Grain Parallelism. 1993. 314.5 TMS320C62x/C67x Programmers guide. Texas Instrument Product Documentation, 1999.6 Rau B. Iterative modul

34、o scheduling: An algorithm for software pipelining loops. In: ACM SIGMICRO Newsletter. California: ACM Press, 1994. 6374.7 Richard AH. Lifetime-Sensitive modulo scheduling. In: Budd TA, ed. ACM SIGPLAN Notice. ACM Press, 1993. 258267.8 Cristina C. An environment for the reverse engineering of execut

35、able programs. In: Dennis W, ed. APSEC. Washington: IEEE Computer Society, 1995. 410.9 Jerome M, Laurie H. Decompiling Java using staged encapsulation. In: Thomas E, ed. WCRE. Washington: IEEE Computer Society, 2001. 368.10 Conte T, Sathaye S. Optimization of VLIW compatibility systems employing dynamic rescheduling. Journal of Parallel Programming, 1997,25(2):83112.11 Rong H, Tang Z, Gov Indarajan R, Alban D, Gao G. Single-