自动向量化中基于数据依赖分析的循环分布算法

循环分布是开发向量化程序的一个有效的方法。但是由于程序中的数据相关性,当前的自动向量化编译器实现完全的循环分布非常困难。因此,当前的自动向量化编译器一般采用简单的循环分布方法。以数据依赖关系分析为基础,从有无依赖环的角度分析了程序中语句的向量化能力,提出了基于语句向量化识别的循环分布算法,并在自动向量化中加以实现。通过此方法,可以充分地分析语句或依赖环的向量化能力,最终采用循环分布,将可向量化的语句与不可向量化的语句分布在不同的循环中。该方法可以处理当前的自动向量化编译器无法向量化的循环,对一些语句间有依赖关系的循环可达到较好的效果。     

类型转换语句的SLP发掘方法

多媒体技术的迅速发展使得越来越多的处理器集成了SIMD扩展,当前的编译器大多数都已实现了自动向量化功能。为了发掘迭代内并行,一些编译器在自动向量化模块中引入了SLP向量化方法。多媒体数据的密集存储和规则运算使得在处理多媒体数据时需要进行频繁的数据类型转换,而目前的SLP向量化方法对数据类型转换的处理能力还不完善。为了在存在大量数据类型转换语句的程序中发掘更多的SLP向量化机会,提出了一种类型转换语句的SLP发掘方法,它能够在SLP向量化框架下利用数据重组实现具有相同向量化因子和不同向量化因子的数据类型之间的转换。实验结果表明,该方法能够有效地对类型转换语句进行SLP向量化发掘,提高了程序的向量化执行效率。     

一种支持跨幅访存的向量化代码生成方法

随着SIMD扩展部件的迅速发展,自动向量化工具已逐渐成熟.现阶段的工具能对连续访存程序进行较好的处理,然而,大部分非连续访存的多媒体程序并不能被转换为高效的向量化代码.提出并实现了一种支持跨幅访存的向量化代码生成方法,其利用目标系统已有的基本数据处理指令实现多个向量间的任意重组来解决含有非连续访存语句的向量化代码生成问题.经过实验分析和验证,提出的代码生成方法能够将含有跨幅访存的语句转化为面向目标系统的高效向量化代码,以提高程序执行效率.     

DO循环向量化的坐标方法

<正> 为了充分发挥巨型机的效率,有必要对标准FORTRAN语言进行向量化的研究。在此仅对具有一定限制条件的DO循环语句的向量化技术进行探讨。一、关于DO循环的限制条件为了便于工程上切实可行,拟讨论受下述条件限制的DO循环语句。 1.循环的嵌套层次只有二层,而且是紧嵌套形式(即二个DO语句之间不再含有其他语句); 2.(循环)指标变量的上、下界为整常量(或为在循环语句前已定值的整参量),且增量为1; 3.循环体中出现的变量为常量,A(aI+m,bJ+n)型数组变量(关于同名变量其α、     

出口分支语句的向量化方法

传统的向量化方法和超字并行方法依靠数据依赖关系分析确定程序中的并行性,而依赖关系分析无法处理非结构化控制流语句,现有的编译器对该类语句的向量化能力有限。为此,给出一种面向SIMD扩展体系结构的出口分支语句向量化方法,该方法针对一个向量因子内的出口分支语句,能够有效地进行自动向量化处理。测试结果表明,该方法既充分发掘了程序数据流中的并行性,又保证了控制流语义的正确性。     

渐进式智能回溯向量化代码调优方法

为了充分发挥高性能计算机的计算能力,缓解程序员设计和编写并行程序的压力,扩充可用软件集合,设计并实现了利用交互界面深入挖掘程序中的可向量化语句,优化生成代码中的向量化语句,提高生成代码的执行效率.该方法对充分发挥高性能计算机的计算能力,增强系统可用性和扩展应用范围具有重要的意义,同时能够提供有效的辅助手段和工具支持.渐进式智能回溯向量化代码调优架构通过对用户提交的串行程序进行程序分析和变换,采用串行程序分析、数据依赖分析、向量化分析等技术手段,根据分析结果对程序进行变换和优化,自动生成最终的向量化代码.该方法通过分析串行程序中潜在的并行性,将其自动变换为等价的向量化代码形式,大大简化了程序员的工作.     

面向部分向量化的循环分布及聚合优化

大量循环中都存在着少数无法向量化的语句以及许多可向量化语句,循环分布通常可以将这些语句分离到不同的循环中,进而实现循环的部分向量化。目前主流的优化编译器仅支持简单激进的循环分布方法,因而导致向量化后的循环开销过大,且不利于寄存器和cache的重用。针对上述问题,提出了面向部分向量化的循环分布及聚合方法。首先,分析了一般循环分布的两个关键问题:语句集的划分和循环执行顺序的确定;其次,提出了面向最大聚合的凝聚图结点排序方法来指导循环合并,在不影响并行性的前提下减小了循环开销;最后,通过实验对提出的方法进行了验证。实验结果表明,对于测试用例,提出的方法能够生成正确的向量化代码,并且能够显著提高向量化程序的执行效率。     

串行循环向量化的图论方法

本文讨论FORTRAN内层DO循环的向量化问题。对于满足给定条件的DO循环,根据文中导出的计算公式,可以精确地构造出与循环体相对应的时序依赖关系图。按照判别一个有向图是否存在有向回路的充要条件,采取逐个消去图中某些出度或入度为零的顶点的“消元法”,找出循环体中可以向量化的语句,并统一讨论了确定语句顺序和引进临时数组的算法。     

面向非多媒体程序的SIMD向量化算法的研究及改进

利用微处理器的多媒体扩展对非多媒体程序的向量化已成为提高程序性能的一个重要手段,然而目前几乎所有的商业编译器对非多媒体程序的向量化的结果,都无法说明其编译器有效的向量能力.本文通过分析典型的非多媒体程序——SPECCPU2000浮点程序,归纳出非多媒体程序的SIMD向量化特征,并依此提出局部数据重组的向量化方法、针对外层循环的向量化方法、部分语句SLP的向量化方法几种新的向量化方法和相关的向量化优化技术.通过对比Intel编译器对SPEC CPU2000的向量化性能测试,可以发现本文提出的改进方法有效的提高了程序的向量化.     

基于跨基本块变换和循环分布的SLP优化技术

现有的SLP优化算法无法处理内层循环中存在的依赖环和归约,并且在基本块边界产生大量的冗余拆包和赋值语句,从而导致向量化效率不高.针对该问题,提出了一种基于跨基本块变换和循环分布的SLP优化算法.该算法以控制流图为基础,根据基本块间各数组变量的Define-Use关系以及跨越基本块之间的数据依赖关系进行跨基本块的向量化变换,有序地采用跨基本块变换和循环分布,尽可能发掘最内层循环基本块内语句的并行性,使SLP自动向量化编译器生成具有更多SIMD指令的向量化代码.实验结果表明,该算法能够隐藏更多跨基本块冗余操作的开销,同时利用跨基本决的数据依较生成更优的SIMD指令,有效地提高了向量化程序的加速比.     

An introduction to a formal theory of dependence analysis

Dependence analysis is a very important part of any vectorizing or concurrentizing compiler. This paper is an introduction to a formal theory of dependence analysis. The emphasis here is on rigor —the subject matter is not new. The program model is a Fortran do loop consisting of loops and assignment statements. We carefully explain the key dependence concepts and indicate through examples how the dependence tests work. These ideas and methods can be readily extended to more general programs.     

基于值替代的错误定位方法

值替代方法通过查找能够影响失败运行错误输出的语句,并确定这类语句的IVMP(兴趣值映射对)。IVMP是由语句中原错误运行中的值映射集合和能产生正确输出的可替代值映射集合组成。这种方法应用于错误定位分析,对确定错误语句本身和与错误语句直接相关的语句非常有效。提出了一种同时考虑控制依赖和数据依赖的值替代算法,并加入了语句错误可能性分析,能全面分析程序中的错误。     

Optimal Fine and Medium Grain Parallelism Detection in Polyhedral Reduced Dependence Graphs

This paper presents an optimal algorithm for detecting line or medium grain parallelism in nested loops whose dependences are described by an approximation of distance vectors by polyhedra. In particular, this algorithm is optimal for the classical approximation by direction sectors. This result generalizes, to the case of several statements. Wolf and Lam's algorithm which is optimal for a single statement. Our algorithm relies on a dependence uniformization process and on parallelization techniques related to system of uniform recurrence equations. It can also be viewed as a combination of both Allen and Kennedy's algorithm and Wolf and Lam's algorithm.     

Loops skewing: The wavefront method revisited

Loop skewing is a new procedure to derive the wavefront method of execution of nested loops. The wavefront method is used to execute nested loops on parallel and vector computers when none of the loops can be done in vector mode. Loop skewing is a simple transformation of loop bounds and is combined with loop interchanging to generate the wavefront. This derivation is particularly suitable for implementation in compilers that already perform automatic detection of parallelism and generation of vector and parallel code, such as are available today. Loop normalization, a loop transformation used by several vectorizing translators, is related to loop skewing, and we show how loop normalization, applied blindly, can adversely affect the parallelism detected by these translators.     

弹性数据相关与软件流水

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

Compiling techniques for first-order linear recurrences on a vector computer

Linear recurrences are the most important class of nonvectorizable problems in typical scientific/engineering calculations. This work discusses high-performance methods for solving first-order linear recurrences on a vector computer, investigates automatic transformations, and develops compiling techniques for first-order linear recurrence problems. The results show that the improved vector code generated by the vectorizing compiler on the HITAC S-820 supercomputer runs at the rate of 150 MFLOPS (million floating operations per second) for moderate loop lengths (>1000) and over 200 MFLOPS for long loop lengths (> 10000). Also, overall performance improvements of 69% in the 14 Lawrence Livermore Loops and 25 % in the 24 Lawrence Livermore Loops, as measured by the harmonic mean, are attained.     

DBSC-Based Grayscale Line Image Vectorization

Vector graphics plays an important role in computer animation and imaging technologies. However present techniques and tools cannot fully replace traditional pencil and paper. Additionally, vector representation of an image is not always available. There is not yet a good solution for vectorizing a picture drawn on a paper. This work attempts to solve the problem of vectorizing grayscale line drawings. The solution proposed uses Disk B-Spline curves to represent strokes of an image in vector form. The algorithm builds a vector representation from a grayscale raster image, which can be a scanned picture for instance. The proposed method uses a Gaussian sliding window to calculate skeleton and perceptive width of a stroke. As a result of vectorization, the given image is represented by a set of Disk B-Spline curves.     

一种分析和理解程序的方法--程序切片

程序切片是一种分析和理解程序的技术,是通过对源程序中每个兴趣点分别计算切片来达到对程序的分析和理解。程序中某个兴趣点的程序切片不仅与该点定义和使用变量有关,而且与影响该变量的值的语名和谓词以及受该变量的值影响的语名的谓词有关。文中详细阐述了程序切片技术的研究与进展情况,并对目前存在各种程序切片方法和工具进行了比较;简单介绍了文中提出的面向对象的分层切片方法及其算法的思想;最后分析了程序切片技术目前     

KJ70煤矿安全监控分站的设计与研究

介绍了KJ70煤矿安全监控分站的设计思路,概述了KJ70煤矿安全监控系统的工作原理和结构框架;研究了监控分站的硬件和软件结构;详细分析了频率测量技术以及CAN总线通讯技术。以微控制器mcs-51为核心,在现有煤矿安全监控分站的基础上设计了与KJ70煤矿安全监控系统相配套的新型分站,经实践验证效果良好。     

Vectorizing the Monte Carlo algorithm for lattice gauge theory calculations on the CDC cyber 205

Lattice gauge theory is a technique for studying quantum field theory free of divergences. All the Monte Carlo computer calculations up to now have been performed on scalar machines. A technique has been developed for effectively vectorizing this class of Monte Carlo problems. The key for vectorizing is in finding groups in finding groups of points on the space-time lattice which are independent of each other. This requires a particular ordering of points along diagonals. A technique for matrix multiply is used which enables one to get the whole of the result matrix in one pass. The CDC CYBER 205 is most suitable for this class of problems using random “index-lists” (arising from the ordering algorithm and the use of random numbers) due to the hardware implementation of “GATHER” and “SCATTER” operations performing at a streaming-rate. A preliminary implementation of this method has executed 5 times faster than on the CDC 7600 system.