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

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

弹性数据相关与软件流水

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

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

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

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

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

多重循环的软件流水技术

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

多重循环的软件流水：比较和提高

循环并行化是并行编译的核心问题之一。许多科学计算程序的大部分执行时间花费在循环上,有效开发循环中的并行性将提高整个程序的执行效率。多重循环最为常见,因此并行化多重循环具有重要的理论和现实意义。现代处理器中硬件资源迅速增长,也使得在整个多维循环空间中开发并行性成为必要。目前大多数软件流水算法只对最内层循环,仅有少数的算法对多重循环进行软件流水,本文介绍几种多重循环的软件流水算法,比较它们之间的相似与不同之处,为编译器实现中算法的选择提供了指导。     

支持多重循环软件流水的循环控制机制

ＩＬＳＰ－内外层交替执行的多重循环的软件流水算法是对多重循环进行优化的有效方法。为了保证ＩＬＳＰ算法具有良好的时间效益和空间效益，就必须有一套支持这个算法的行之有效的多重循环软件流水机制。文中将比较详细地介绍一套控制机制。它与多重循环优化编译器相配合，可以有效地支持多重循环的软件流水，并且可以保证ＩＬＳＰ算法具有较高的加速比和较低的空间代价。     

IA-64中软件流水的寄存器需求研究

软件流水是开发循环程序指令级并行性的重要方法之一,IA-64是支持软件流水的EPIC体系结构,通过对NAS Benchmarks中可软件流水循环所需的寄存器进行量化分析,提出了一种限制循环展开因子的启发式算法,有效地解决了因可用寄存器不足而导致软件流水失败的问题,并提高了应用程序的执行速度。     

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

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

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

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

一个基于软件流水技术的VLIW体系结构

本文叙述一个正在开发的VLIW多处理单元单片机,这个机器的体系结构基于URPR软件流水技术,采用了流水寄存器堆来减少体间相关距离,因此,细粒度并行性可得到充分开发,从而提高了循环体重叠程度,使得优化后的循环体的长度可大大缩短.模拟实验结果表明,这个体系结构在优化编译器的配合下可达到很高的性能。     

一个VLIW体系结构的单片多处理机

本介绍一个采用ＶＬＩＷ超长指令字体系结构的高性能单片多处理机，在这个体系结构中采用流水寄存器堆来消除循环程序内的数据相关，从而使程序能够在指令级以极高的并行度并行运行。模拟实验结果表明这个体系结构具有很高的运算速度和很好的性能价格比。     

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.     

VelociTI结构浮点DSPs寄存器堆读写的流水线设计

研究了VelociTI结构浮点数字信号处理器寄存器堆的流水线读写原理并提出了一种设计方法。该方法对单操作数双精度浮点指令采用2个32位数据通路用1个流水线周期读取源操作数,双操作数双精度浮点指令采用锁定译码单元,利用若干流水线周期读取源操作数。采用写控制向量的方法实现了流水线多个周期执行写操作。该方法正确实现了基于IEEE754标准的双精度浮点数据在寄存器堆与功能单元之间的32位数据通路上的传输,仿真结果验证了其正确性。     

依赖距离主导的向量化方法研究*

向量寄存器的非满载使用方式为大量迭代次数不足的循环提供了向量化的机会,但也导致向量化的并行宽度不固定,传统的向量因子主导的依赖测试方法不再适用。本文提出了一种依赖距离主导的依赖测试方法,通过分析依赖图中所有依赖环的破环关键边所携带的依赖距离,选择其中最小的依赖距离来决定并行宽度,破除依赖环,实现基于向量寄存器非满载使用方式的向量化。实验结果表明,该方法能够有效增加循环向量化的机会和提高向量寄存器的使用率,测试用例的向量化加速比平均提高14.6%。     

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).