一种软件流水的反流水算法.doc-得力文库

资源描述

《一种软件流水的反流水算法.doc》由会员分享，可在线阅读，更多相关《一种软件流水的反流水算法.doc（7页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、汤志忠等:一种软件流水的反流水算法993一种软件流水的反流水算法*Supported by the National Natural Science Foundation of China under Grant No.60173010 (国家自然科学基金)作者简介: 汤志忠(1946),男,教授,博士生导师,主要研究领域为计算机系统结构,指令级并行算法,并行编译技术;李文龙(1977),男,博士生,主要研究领域为指令级并行算法;苏伯珙(1939),男,教授,主要研究领域为并行算法,优化编译技术.汤志忠1+, 李文龙1, 苏伯珙21(清华大学计算机科学与技术系,北京 100084)2(Wi

2、lliam Paterson大学计算机科学系,新泽西洲 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, U

3、SA)+ Corresponding author: Phn: +86-10-62772213, E-mail: tzz-, http:/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.http:/ pipelining is a loop optimization technique that has been widely implement

4、ed in modern 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 diffi

5、cult to understand, 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-pip

6、elined loop back 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摘要:软件流水是一种循环程序的优化技术,已经广泛应用于现代优化编译器中.为了充分利用VLIW DSP处理机的指

7、令级并行性,必须使用软件流水技术对DSP程序进行优化.然而,在串行源代码不存在的情况下,对软件流水后的原始代码进行变换、理解、测试和调试,并转换成其他处理机的代码是非常困难的.提出了一种反流水技术,它能够将软件流水后的优化汇编代码反向转换成语义等价的相应代码.通过20个程序的初步实验,验证了所提出的反流水算法的正确性.关键词:软件流水;反流水;指令级并行中图法分类号:TP338文献标识码: A在过去的几年中,数字信号处理机(digital signal processor,简称DSP)发展迅速1,由于对提高性能及解决大范围应用程序的持续需要,许多厂商推出了基于VLIW(very long in

8、struction word)的DSP处理机,为了充分利用这些VLIW DSP处理机的指令级并行性,DSP程序一般都要经过软件流水的优化.软件流水24通过重叠不同循环体的执行来加快循环程序在指令级并行处理机上的执行速度,这种技术已经研究多年,并在许多优化编译器中得以实现,例如Texas Instruments的TIC6X和StarCore的SC140等DSP处理机的编译器.研究反软件流水技术的动机是:首先,由于对原始串行代码的变换,软件流水后的代码很难理解、测试及调试.其次,由于处理机之间指令兼容性的问题,经过软件流水后的循环代码很难在其他处理机中移植和使用.第三,虽然软件流水后的循环程序、C

9、PU的执行时间效益很好,但在存储器使用上,它的空间效益可能很差.在应用软件流水对循环进行优化时,并没有考虑存储空间对性能的影响.对于某些存储空间有限的应用,软件流水不适合.最后,我们注意到,大量的DSP应用程序已被软件流水优化过,并且被测试过,但是这些应用程序的串行源代码已经不存在了.据我们所知,到目前为止,有关反软件流水算法的研究还很少,但是,这是一个应用前景非常好的研究领域,对于重新获取源代码和在不同处理机之间移植软件流水后的代码提供了可能.本文提出了一种反软件流水算法.首先使用严格的时序关系来识别循环程序的核心代码,然后利用循环展开技术,构造软件流水循环的数据相关性图(DDG).最后,利

10、用DDG来构造一个语义等价的串行循环程序.本文首先通过一个例子来说明什么是软件流水和反软件流水,然后,具体介绍我们提出的反软件流水算法,接下去是20个典型程序的实验结果,最后是结论.1 软件流水与反软件流水图1是点积函数中的循环经过软件流水后的代码,用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)

11、,A3LDH*+B7(4),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 B

12、6,B5,B5MPY B4,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汇编码表示的点积函数的软件流水循环结果反软件流水是软件流水的逆向操作,是把已经软件流水的循环代码转换成语义等价的串行代码.对于图1中的软件流水循环代码,反软件流水是把它转换成如图2所示的语义等价的串行循环代码.一般来说,一个软件流水后的循环程序由3部分组成:装入、核心和排空.与硬件流水线一样,软件流水的装入部分和排空部分

13、只执行一次,核心部分要重复执行.在图1中,从L1到L2是装入部分,L2到L3是核心部分,L3后面的指令属于排空部分.在装入部分和核心部分存在着严格的时序关系.例如,如果标号L1中的指令在时刻t发射,那么位于L1和L2之间的另外3条指令一定要在时刻t+1,t+2和t+3发射.任何阻塞和延迟执行都会破坏程序的语义,传统的控制相关和数据相关图都不能表示这种严格的时序关系.实际上,在反软件流水的结果出来之前,要理解软件流水循环的语义是非常困难的,连续循环体的折叠以及多个分支指令的延迟使得理解软件流水循环的控制流结构变得更加困难.如图1所示的软件流水循环经过反软件流水之后,生成如图2所示的语义等价的串行

14、代码,我们很容易理解图2的串行代码,关于代码的详细语义读者可以参照文献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 as

15、sembly code图2 TIC62汇编码表示的与点积软件流水循环语义等价的串行代码比较图1和图2这两段语义完全等价的代码,可以很容易看出,经过软件流水的循环,其时间效益更好,它的执行时间比串行代码要快5倍左右,而串行代码的空间效益好,它比软件流水循环节省了3倍的程序存储空间.另外,为了执行软件流水循环,必须有大量的功能部件和寄存器.因此,软件流水循环适合在类似于VLIW这种提供大量资源的处理机上运行.2 反软件流水算法下面结合图3的例子,解释我们所提出的反软件流水算法.图3给出的是点积函数中循环经过软件流水后的代码,采用TIC62处理机的汇编代码5表示.图中最左面一列是行号,符号“|”表明

16、当前行的指令可以与上一行上的指令并行执行.反软件流水算法的操作步骤如下:第1步.循环检测.从给定的代码中,识别出软件流水的循环体,这包括循环的入口和循环体的长度等,识别的准则如下:如果有一条向回跳转的分支指令,那么分支指令的目标地址就是循环的入口,循环体的长度等于向回跳转的分支指令与循环入口之间的距离再加上分支延迟槽的时间.如果在循环入口上面的,且代码长度等于分支延迟时间加1的区域内包含有向前跳转的分支指令,则分支指令的目标地址就是循环的入口,软件流水循环体的长度等于最近的分支指令和循环入口之间的距离.在图3中,L2是向回跳转的分支指令的目标地址,因此L2就是软件流水循环的入口,同时,软件流水

17、循环体的长度等于2.第2步.活变量分析.从一个给定的软件流水循环体中找出所有最后执行的指令.通常,活变量包含在最后执行的指令中.最后执行的指令一般分为下面两种类型:往活变量寄存器中写数据的指令和写存储器的指令.具体寻找活变量的方法是:在循环区域中自下往上搜索所有最后执行的指令.在图3中,Add B6,B5,B5和Add A5,A4,A4是最后执行的指令,因此活变量为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|L

19、B4,A3,A530|ADD 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步.数据相关性图的构造.构造软件流水循环的数据相关性图(DDG).首先,展开循环体k-1次,k等于循环体的指令组中最多指令的个数.指令组是指可以并行执

20、行的一组指令,在图3的代码段中,由|分隔的指令属于同一个指令组.其次,从第2步找到的最后执行的指令开始,使用高度优先的算法以自下向上的方式构造数据相关性.图4是重新构造的点积函数中软件流水循环的数据相关性图.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

21、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),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

22、 *+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 L2Fig.4 Data dependence graph (DDG) of running example图4 运行例子的数据相关性图第4步.软件流水循环的检查.检查一个循环是否经过软件流水.如果在循环体中存在两条

23、指令Ii和Ij,它们在循环体中的距离小于在数据相关性图中的距离,那么可以说这个循环体是经过软件流水处理的.比较图3和图4,可以确认,图3中所识别出的循环是经过软件流水的循环.第5步.找出装入和排空部分.在给定的代码段中找出软件流水循环的装入部分和排空部分.(1) 装入部分的查找:从循环的入口开始向上搜索,直到软件流水循环的上边界,在搜索过程中,找出所有包含循环体中指令的指令组,其中最上面的那个指令组是装入部分的上边界.(2) 排空部分的查找:从软件流水的循环体底部开始向下搜索,直到软件流水循环的下边界,在搜索的同时找出所有包含循环体中指令的指令组,其中最下面的指令组是排空部分的下边界.在图3中

24、,装入部分是编号613,排空部分是编号2540.第6步.重新调度.将DDG转换为串行代码.(1) 在从上述第(2)步找到的最后执行的指令中,自下而上利用列表调度法排列DDG上关键路径的偏序列表.为了满足所有指令的延迟时间,必要时可以插入NOP操作.(2) 将所有在非关键路径上的指令插入到关键路径中.(3) 删除装入和排空部分中所有包含在循环体中的指令.第7步.循环次数计算.计算出软件流水循环串行代码的执行次数.除了要考虑在给定的软件流水循环中所设置的执行次数初始值以外,还必须考虑其他诸多因素,如在装入部分所执行的循环次数,其值等于装入部分中包含的转移目标是循环入口的分支指令个数.另外,在排空部

25、分最后执行的指令条数以及在给定的软件流水循环体中,向回跳转的分支指令与修改循环执行次数指令的相关位置等都影响着串行代码的执行次数.从第(6)步第(7)步,我们得到了如图2所示的点积函数的串行代码,与图3中给定的循环在语义上是等价的.3 实验结果利用我们所提出的反软件流水算法进行了20个程序的实验,这些代码属于不同的应用程序,循环的长度各不相同,装入和排空部分也各不相同,这些程序均从TMS320C62x/C62x的用户编程手册中获取,感兴趣的读者可以参照文献5获取相关信息.实验中,我们使用TIC62编译器或者手工线性汇编器5生成代码段.首先,我们使用反流水技术将这些代码转换成串行代码,接着使用T

26、IC62的模拟器来运行原始的汇编代码和转换后的汇编代码.所有的计算结果表明,对于这些程序而言,我们的反流水算法是正确的.表1概括了这些软件流水循环的特点以及20个程序的反流水结果,其中Sub是指修改循环执行次数的指令,branch是指跳到循环入口的分支指令.注意,其中的“1”表示由编译器生成,“2”表示由线性汇编器生成.对于测试的每个程序,因为其软件流水循环的特点各不相同,经过反软件流水后,其执行次数、循环体长度都发生了变化,以第1个测试程序dot product_1为例,因为有显示的装入和排空,以及初始设置的循环执行次数,所以,反流水之后其执行次数为50,循环体长度为14.Table 1 E

27、xperimental result表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,

28、 no postlude511514Dot product_51Normal5015014FIR1No postlude3233215FIRnorld1No postlude1621615IIR2No postlude100410013Codebook2No postlude,conditional branch in loop body322329Vec_mpy1Normal7537516Latsynth1Normal200520025WVS2Normal4925016Add_test1No postlude5256Loop_test_11Branch in prelude only5025

29、06Loop_test_21Branch in prelude only10021007Loop_test_31Branch in prelude only10031007Loop_test_41Normal5055011Loop_test_81No prelude2092021Loop_test_121No prelude25232527Loop_test_161No prelude501750354 相关工作和结论在软件流水的研究领域,文献6,7给出的软件流水算法已经研究了多年,并且在很多的优化产品编译器中得以实现.而对于反编译循环软件流水的算法,目前反编译主要是将汇编代码或者二进制代码反

30、编译成源程序,比如在软件工程领域中8,将较低级的可执行代码转换成更容易理解的高级代码,以及在Java应用方面,将字节码转换成源程序9等.我们给出了反软件流水算法及其实验结果.对于DSP用户,我们的算法对于理解和调试经过软件流水后的代码是一个非常有用的工具.进一步地,我们提出的反软件流水算法可以进一步扩展用于解决代码兼容性问题,包括VLIW体系结构的软件流水循环.虽然可以使用动态重调度10来解决兼容性问题,但是它不能解决包含软件流水循环的代码.通过使用反软件流水技术,可以将软件流水循环的代码从一个源VLIW处理机转换为一系列语义等价的中间代码级的串行代码,然后这些中间代码可以送给目标VLIW处理

31、机的编译器.我们的代码适合于从一种VLIW DSP处理机到其他DSP处理机6汇编代码的转换.本文的方法主要针对不带分支的、最内层循环软件流水后的代码.如何扩展本文的方法用于处理带分支及多重循环软件流水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-L

32、evel parallel 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 pipeli

33、ning: A new 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. Iterat

34、ive modulo 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

35、of executable 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 empl

36、oying dynamic rescheduling. Journal of Parallel Programming, 1997,25(2):83112.11 Rong H, Tang Z, Gov Indarajan R, Alban D, Gao G. Single-Dimension software pipelining for multi-dimensional loops. In: Proc. of the Intl Symp. on Code Generation and Optimization with Special Emphasis on Feedback-Direct

37、ed and Runtime Optimization. IEEE Computer Society, 2004. 163174.*第13届全国信息存储技术学术会议征文通知为促进和加强存储技术的学术交流和产品展示，中国计算机学会信息存储技术专业委员会决定于2004年10月中旬在西安召开第13届全国信息存储技术学术会议。本次会议由中国计算机学会信息存储技术专业委员会主办，西北工业大学计算机学院承办。会议将通过学术报告、专题讨论、产品展示等多种形式，就信息存储的最新研究进展和发展趋势开展深入、广泛的学术交流，并特邀著名专家学者作专题报告。一、征文范围欢迎从事信息技术研究、开发、应用的各界人

38、士，就下列领域(但不限于)所涉及的信息存储技术方面的内容踊跃来稿：国内外存储技术的发展现状及趋势、信息存储理论研究与信息存储新技术研究；计算机主存体系结构研究及实现、海量信息存储技术、网络存储技术；存储领域中的核心技术及实现研究、存储相关芯片的设计与应用、智能存储技术；多媒体信息存储技术、数据仓库、数据挖掘；信息存储系统的安全性和可靠性;存储系统解决方案、存储技术及产品的标准。二、征文要求应征学术论文应是未正式发表过的研究成果，字数(含中英文摘要、关键字与参考文献)不超过8000字。请注明作者的通信地址、邮政编码、电话和E-mail地址。论文格式请参照计算机研究与发展格式。投稿方式：电子投稿

39、。稿件请采用Word、PDF文档格式。电子投稿的E-mail地址: 征文截止: 2004年07月15日录用通知: 2004年08月31日被本次会议录用的学术论文将收录在会议论文集内，优秀论文将在计算机研究与发展（增刊）上发表。有关会议的动态信息可通过拨打(029)8493772或通过E-mail询问。三、参展范围为了加强产业界、学术界和应用领域间的交流和联系，本次会议将举办信息存储技术交流会及产品展示会。凡与存储相关的产品和技术均欢迎参会参展，有意参展的单位请联系：联系人：张延园教授电话：(029)8493772 传真：(029) 8495772 E-mail: 四、中国计算机学会信息存储技术专业委员会联系方式联系人：方粮博士通讯地址： 410073 湖南长沙国防科技大学计算机学院电话： (0731)4575962-801 传真： (0731)4510109 E-mail: L

展开阅读全文