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

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

SMS软件流水调度算法的设计与实现

循环是程序中的热代码,对循环进行有效的优化可以显著缩短程序的执行时间。软件流水是一种开发循环体指令级并行的细粒度循环优化技术,它通过调度循环中连续迭代之间的指令使其并行执行,从而提高了循环的执行效率。实验数据表明,用Cerngoop程序包进行测试,循环优化效果明显。     

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

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

流水安全法--一个面向软件流水技术的新的数据相关性分析方法

软件流水是一种很有效的指令级并行优化技术,而能否进行尽可能精确的数据相关性分析是决定软件流水优化效果的一个非常重要的因素.本文通过分析软件流水技术本身的特点,从保障软件流水安全为出发点,导出了一组更严格有效的相关方程和限制不等式,大大提高了相关性判别的能力,最后与现有工作进行了比较,并用一个例子加以验证.     

一种支持多重循环软件流水的寄存器结构

寄存器结构及其分配是软件流水算法的关键之一.为支持多重循环的软件流水,该文提出一种新颖的寄存器结构：半共享跳跃式流水寄存器堆.它可以有效地解决多重循环软件流水下的特殊问题,即：同层次和跨层次的寄存器重命名问题以及断流问题;有效地消除外层循环的体间读写相关,提高程序的指令级并行度.它有3种分配方式可供灵活使用：单个寄存器、流水寄存器和寄存器组方式.流水寄存器方式对生存期确定的、局限于一个循环层次的寄存器重命名问题提供简单而有效的支持.寄存器组分配方式解决了多重循环软件流水时变量生存期不确定的情况.跳跃操作为     

分解式软件流水DESP：一种开发循环程序指令级并行性的新方法

本在软件流水方面提出一种新观点，把软件流水看作是一种指令级变形，是把一维指令向量变换成二维指令矩阵。这样，软流流水问题可以很自然地分解为两个子问题：一个是确定每个操作在指令矩阵中的行号，另一个是确定其在指令矩阵中的列号。其中这种观战我们开发出一种新的循环调度方法，叫做分解式软件流水－ＤＥＳＰ。     

多重循环的软件流水技术

为了解决多重循环的指令级并行编译问题，本文提出了反刍方法，以一种新的思维方式处理多重循环，将其视为一个程序流整体，有效地开发了多重循环的并行度．另外，本文还给出了实现反刍方法的基本步骤以及相应的硬件支持．最后，通过一些初步实验的结果验证了本算法的有效性，并讨论了其时间和空间效益，分析了其主要特点.     

循环体间相关问题及改进的URPR软件流水方法

本文首先在理论上分析了循环体间相关对软件流水的影响.提出了一个由循环本身性质决定的充分必要条件并证明了满足此条件的循环是可限制的,否则是不可限制的;其次我们证明了任意不可限制的循环展开K次后即可转换为可限制循环,K取决于循环本身的性质;最后给出了循环预处理算法和一个新的循环体压缩算法.实验结果表明,这两个算法可使URPR算法对任意循环都能得到最优时间效益并保持了良好的空间效益及低的计算复杂性.     

分解式软件流水DESP——一种开发循环程序指令级并行性的新方法*

本文在软件流水方面提出一种新观点，把软件流水看作是一种指令级变形，是把一维指令向量变换成二维指令矩阵．这样，软件流水问题可以很自然地分解为两个子问题：一个是确定每个操作在指令矩阵中的行号,另一个是确定其在指令矩阵中的列号．基于这种观点，我们开发出一种新的循环调度方法，叫做分解式软件流水——DESP．     

软件流水中的一种数据分配算法

数据元素的存储器分配是指令级并行优化编译过程中不可回避的一个关键性问题．该问题解决得好坏直接关系到编译优化的效率．本文第１节主要介绍ＩＬＳＰ（ｉｎｔｅｒｌａｃｅｄｉｎｎｅｒａｎｄｏｕｔｅｒｌｏｏｐｓｏｆｔｗａｒｅｐｉｐｅｌｉｎｉｎｇ）算法的基本思想．第２节以距阵乘法为例阐述了在ＩＬＳＰ算法下多重循环中数据元素的存取特点．第３节则从理论上对该特点进行了深入的分析研究，同时就一般多重循环给出了一个行之有效的ＩＬＳＰ算法下数据元素内存分配算法．第４节给出一个实验比较结果．最后是结论.     

软件流水领域多维数组数据相关性的测试

体差不等式测试为适用于软件流水领域的高维数组数据相关性分析算法,通过使用更严格的限制条件,该算法可以获得比传统数据相关性分析方法更精确的结果。文章展开该算法的实验研究。实验表明,虽然体差不等式测试算法只能针对实可行解域进行数据相关性分析,但所得到的结果仍然与实际情况相吻合。对于科学计算循环中出现的大多数数据相关性判定问题,使用体差不等式测试算法可以获得很好的效果。     

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.     

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.     

cache profiling信息指导的软件流水

软件流水是一种重要的指令调度技术,它通过同时执行来自不同循环迭代的指令来加快循环的执行时间.随着处理器速度和访存速度差距越拉越大,访存指令尤其是cache miss的访存指令日益成为系统性能提高的瓶颈.由于这些指令的延迟不是固定的,如何在软件流水中预测并掩盖这些访存指令的延迟是非常重要的.与前人预测访存延迟的方法不同,引入cache profiling技术,通过动态收集到profile信息来预测访存延迟,并进行适当的调度.当增加模调度循环中的访存指令的延迟时,启动间隔也会随之增大,导致性能不会随之上升.CSMS算法和FLMS算法在尽量不增大启动间隔的情况下,改变访存指令的延迟.改进了CSMS算法和FLMS算法,根据cache profiling的信息来改变访存延迟,所以比前人的方法更为准确.实验表明,新方法可以有效地提高程序性能,对SPEC2000测试程序平均性能提高1%左右,个别例子的性能改进高达11%.     

基于四阶段人工优化的软件流水技术

代码体积是优化存储资源有限的嵌入式系统的重要因素之一。针对该特点,使用oprofile性能分析工具,以EEMBC基准程序集作为工作负载,提出四阶段人工优化软件流水方法(FPMO)。电信类的自相关程序实验结果表明,FPMO以2.04%的代码增量为代价换来40.678%的性能提升,而单纯的编译器自动优化则以33.35%的体积膨胀换来38.33%的性能提升。     

Enhanced Co-Scheduling: A Software Pipelining Method Using Modulo-Scheduled Pipeline Theory

Instruction scheduling methods which use the concepts developed by the classical pipeline theory have been proposed for architectures involving deeply pipelined function units. These methods rely on the construction of state diagrams (or automatons) to (i) efficiently represent the complex resource usage pattern; and (ii) analyze legal initiation sequences, i.e., those which do not cause a structural hazard. In this paper, we propose a state-diagram based approach for modulo scheduling or software pipelining, an instruction scheduling method for loops. Our approach adapts the classical pipeline theory for modulo scheduling, and, hence, the resulting theory is called Modulo-Scheduled pipeline (MS-pipeline) theory. The state diagram, called the Modulo-Scheduled (MS) state diagram is helpful in identifying legal initiation or latency sequences, that improve the number of instructions initiated in a pipeline. An efficient method, called Co-scheduling, which uses the legal initiation sequences as guidelines for constructing software pipelined schedules has been proposed in this paper. However, the complexity of the constructed MS-state diagram limits the usefulness of our Co-scheduling method. Further analysis of the MS-pipeline theory, reveals that the space complexity of the MS-state diagram can be significantly reduced by identifying primary paths. We develop the underlying theory to establish that the reduced MS-state diagram consisting only of primary paths is complete; i.e., it retains all the useful information represented by the original state diagram as far as scheduling of operations is concerned. Our experiments show that the number of paths in the reduced state diagram is significantly lower—by 1 to 3 orders of magnitude—compared to the number of paths in the original state diagram. The reduction in the state diagram facilitate the Co-scheduling method to consider multiple initiations sequences, and hence obtain more efficient schedules. We call the resulting method, enhanced Co-scheduling. The enhanced Co-scheduling method produced efficient schedules when tested on a set of 1153 benchmark loops. Further the schedules produced by this method are significantly better than those produced by Huff's Slack Scheduling method, a competitive software pipelining method, in terms of both the initiation interval of the schedules and the time taken to construct them.     

Decomposed software pipelining: A new perspective and a new approach

Software pipelining is an efficient instruction-level loop scheduling technique, but existing software pipelining approaches have not been widely used in practical and commercial compilers. This is mainly because resource constraints and the cyclic data dependencies make software pipelining very complicated and difficult to apply. In this paper we present a new perspective on software pipelining in which it is decomposed into two subproblems—one is free from cyclic data dependencies and can be effectively solved by the list scheduling technique, and the other is free from resource constraints and can be easily solved by classical polynomial-time algorithms of graph theory. Based on this new perspective, we develop a new instruction-level loop scheduling approach, call DEcomposed Software Pipelining (DESP).