Trace Software Pipelining

Global software pipelining is a complex but efficient compilation technique to exploit instruction-level parallelism for loops with branches.This paper presents a novel global software pipelining technique,called Trace Software Pipelining,targeted to the instruction-level parallel processors such as Very Long Instruction Word (VLIW) and superscalar machines.Trace software pipelining applies a global code scheduling technique to compact the original loop body.The resulting loop is called a trace software pipelined (TSP) code.The trace softwrae pipelined code can be directly executed with special architectural support or can be transformed into a globally software pipelined loop for the current VLIW and superscalar processors.Thus,exploiting parallelism across all iterations of a loop can be completed through compacting the original loop body with any global code scheduling technique.This makes our new technique very promising in practical compilers.Finally,we also present the preliminary experimental results to support our new approach.     

摆动模调度中的寄存器溢出技术及其在GCC中的实现

软件流水是一种通过发掘循环的不同迭代的不同部分的指令间并行性,使这些指令并行执行,从而提高循环的执行效率的优化技术.但该技术在提高指令并行性的同时也增加了寄存器压力,而寄存器溢出技术正是解决寄存器压力的有效方法.摆动模调度是一种在进行近似最优化调度的同时尽力减小寄存器压力的软件流水算法,该算法已经作为一个新的优化遍出现在GCC的最新版本中.本文以GCC为平台,论述了摆动模调度中的寄存器溢出技术及其工程实现,从而使摆动模调度算法进一步增强了对寄存器压力的处理能力.     

Time Optimal Software Pipelining of Loops with Control Flows

Software pipelining is widely used as a compiler optimization technique to achieve high performance in machines that exploit instruction-level parallelism. However, surprisingly, there have been few theoretical or empirical results on time optimal software pipelining of loops with control flows. In this paper, we present three new theoretical and practical contributions for this underinvestigated problem. First, we propose a necessary and sufficient condition for a loop with control flows to have an optimally software-pipelined program. We also present a decision procedure to compute the condition. As part of the formal treatment of software pipelining, we propose a new formalization of software pipelining. Second, we present two software pipelining algorithms. The first algorithm computes an optimal solution for every loop satisfying the condition, but may run in exponential time. The second algorithm computes optimal solutions efficiently for most (but not all) loops satisfying the condition. The former one proves the sufficiency of the condition and the latter one suggests a practical optimal software pipelining algorithm. Third, we present experimental results which strongly indicate that achieving the time optimality in the software-pipelined programs is a viable goal in practice with reasonable hardware support.     

Loop Shifting for Loop Compaction

The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource constraints. In terms of loop transformation and code motion, the technique can be formulated as a combination of loop shifting and loop compaction. Loop shifting amounts to moving statements between iterations thereby changing some loop independent dependences into loop carried dependences and vice versa. Then, loop compaction schedules the body of the loop considering only loop independent dependences, but taking into account the details of the target architecture. In this paper, we show how loop shifting can be optimized so as to minimize both the length of the critical path and the number of dependences for loop compaction. The first problem is well-known and can be solved by an algorithm due to Leiserson and Saxe. We show that the second optimization (and the combination with the first one) is also polynomially solvable with a fast graph algorithm, variant of minimum-cost flow algorithms. Finally, we analyze the improvements obtained on loop compaction by experiments on random graphs.     

Circuit retiming applied to decomposed software pipelining

This paper elaborates on a new view on software pipelining, called decomposed software pipelining. The approach is to decouple the problem into resource constraints and dependence constraints. Resource constraints management amounts to scheduling an acyclic graph subject to resource constraints for which an efficiency bound is known, resulting in a bound for loop scheduling. The acyclic graph is obtained by cutting some particular edges of the (cyclic) dependence graph. In this paper, we cut edges in a different way, using circuit retiming algorithms, so as to minimize both the longest dependence path in the acyclic graph, and the number of edges in the acyclic graph. With this technique, we improve the efficiency bound given for Gasperoni and Schwlegelshohn algorithm, and we reduce the constraints that remain for the acyclic problem. We believe this framework to be of interest because it brings a new insight into the software problem by establishing its deep link with the circuit retiming problem     

模调度中的数据猜测方法

软件流水是一种重要的指令调度技术，通过重叠地执行不同的循环体来提高指令级并行性。模调度是一类重要的软件流水调度算法，保守的相关性分析可能会引入较多的模糊相关，这阻碍了模调度生成高效的调度结果。数据猜测能克服保守的相关性分析带来的调度限制，开发潜在的并行性。本文提出了模调度中的一种数据猜测方法，在开放源代码编译器ORC上实现了该方法，并用SPEC2000基准程序进行了测试，实验结果表明，该方法收到了较好的效果。     

基于路径分组与数据相关松弛的软件流水

软件流水是循环调度的重要方法.有分支循环的流水依然是个难题.现有算法可以分为4类:循环线性化、路径分离、整体调度和路径选择.它们都未能和谐地解决两个对立问题:转移时间最小化和最差约束问题.提出了基于路径分组和数据相关松弛的软件流水框架,试图无矛盾地解决上述问题.其主要思想是:(1)路径分组,即按照路径的执行概率和转移概率将路径分组,力求最小化转移时间;(2)数据相关松弛,力求避免最差约束,即当循环有多条路径时,有些相关在循环执行中并不一定有实例,理想的策略是仅当它有实例时才遵守.初步实验和定性分析表明,此     

Specification of software pipelining using petri nets

This paper presents a flexible model for software pipelining using the petri nets. Our technique, called the Petri Net Pacemaker (PNP), can create near optimal pipelines with less algorithmic effort than other techniques. The pacemaker is a novel idea which exploits the cyclic behavior of petri nets to model the problem of scheduling operations of a loop body for software pipelining. A way of improving the performance of loops containing predicates is given. The PNP technique also shows how nested loops can be pipelined. A comparison with some of the other techniques is presented. THis work was partially supported by the National Science Foundation under grants CDA-9100788 and CDA-9200371.     

弹性数据相关与软件流水

最差路径是有分支循环软件流水的一大障碍.对于有分支循环,某些数据相关(称为弹性相关)在循环的动态执行中可能产生、也可能不产生实例.据此,可将严重限制并行性的弹性相关用限制较松的虚构相关代替,再进行软件流水.若调度没有遵守原来的弹性相关,则使用下推变换修正.从而缓解或者完全解除了最差路径的限制.该方法与经典的控制猜测互补,特点是允许调度含错,然后纠错.     

一种软件流水的反流水算法

软件流水是一种循环程序的优化技术,已经广泛应用于现代优化编译器中.为了充分利用VLIW DSP处理机的指令级并行性,必须使用软件流水技术对DSP程序进行优化.然而,在串行源代码不存在的情况下,对软件流水后的原始代码进行变换、理解、测试和调试,并转换成其他处理机的代码是非常困难的.提出了一种反流水技术,它能够将软件流水后的优化汇编代码反向转换成语义等价的相应代码.通过20个程序的初步实验,验证了所提出的反流水算法的正确性.