基于剖析信息和关键路径长度的软件扇出树生成算法  

Profile Information and Critical Path Length Based Software Fanout Tree Generation Algorithm

作　　者：曾斌[1] 安虹[1,2] 王莉[1] 

机构地区：[1]中国科学技术大学,合肥230027 [2]中国科学院计算机体系结构重点实验室,北京100080

出　　处：《计算机科学》2010年第3期248-252,共5页Computer Science

基　　金：国家自然科学基金重点项目(60633040);国家973计划项目(2005CB321601);国家863重大项目(2006AA01A102-5-2);教育部-英特尔信息技术专项科研基金项目(MOE-INTEL-08-07)资助

摘　　要：开发利用ILP(Inst ruction-level Parallelism)是现代高性能处理器取得高性能的关键要素之一。宽发射的超标量处理器、超长指令字处理器和数据流处理器只有在并行执行多条相邻的指令时才能获得较高的性能。数据流处理器的一个关键问题是如何把指令的计算结果高效地播送给目标指令而不用读写集中式寄存器文件。对于每条目标数大于指令所能编码的目标数的指令,编译程序都要插入一棵由MOV指令构成的软件扇出树来把计算结果播送给多条目标指令。为了暴露更多的ILP给硬件执行基底,提出了一种改进的软件扇出树生成算法,本算法根据目标指令的执行概率大小以及目标指令到该指令所在块的出口的关键路径长度来计算目标指令的权值,然后对各个叶子的优先权值进行排序,再根据优先权值的顺序来构造一棵软件扇出树,以便把指令的计算结果播送给多条目标指令。实验结果发现,本算法相对于传统的软件扇出树生成算法其性能有较大的提高。Exposing and exploiting instruction-level parallelism （ILP） is one of the most critical components of high performance for modern processors. Wide-issue superscalar, very long instruction word （VLIW） and dataflow processors can only achieve high performance when they execute nearby instructions in parallel. In order to expose more instruction-level parallelism to hardware execution substrate, this paper proposed an improved fanout tree generation algorithm. This algorithm first calculates the priority value of every target instruction based on its execution probability and the critical path length from the target instruction to an exit of its block, and then sorts the priority values in ascending order and generates a software fanout tree. Experimental results show that the algorithm proposed in this paper improves the performance over the prior work modestly.

关 键 词：软件扇出树 执行概率 关键路径 优先权 

分 类 号：TP302.1[自动化与计算机技术—计算机系统结构]