分段处理技术在向量化中的应用

本文针对内层DO 循环向量化处理,提出了利用分段处理技术把依赖关系对向量化的影响消除掉的简便方法。在内层DO 循环中,一些数组元素随着循环控制变量在执行区间上的变化而形成向量。这些向量可能交叉或部分重合,这种依赖关系有可能影响向量化。然而,在一台流水线型向量处理机上,向量寄存器的每组个数是有限的。当所有依赖距离大于该数目时,就可以忽略存在的依赖关系。否则,选出最小依赖距离,根据处理机的特点,决定向量化与否。分段处理有循环和展开两种方式。     

循环分布及依赖关系破除的优化问题

由于向量本身是一维的,一般只有内层循环才能向量化(当然这并不包括多重循环的单重化或循环交换所涉及的外层循环),因此,把非紧致型的多重循环变换成与之等价的多个紧致型多重循环,一般就可以增加内层循环向量化以及循环交换的机会,从而提高向量化的程度,这就是下面将要讨论的循环分布,我们将采用一种类似π图的表示方法,不妨就称之为h图。     

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

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

向量并行度指导的循环SIMD向量化方法

SIMD扩展部件是集成到通用处理器中的加速部件,旨在发掘多媒体和科学计算等领域程序的数据级并行.当前两种基本的向量发掘方法分别是发掘迭代间并行的Loop-based方法和发掘迭代内并行的SLP方法.Loop-aware方法是对SLP方法的改进,其思想是首先通过循环展开将迭代间并行转换为迭代内并行,使循环体内的同构语句条数足够多,再利用SLP方法进行向量发掘.但当循环展开不合法或者并行度低于向量化因子时,Loop-aware方法无法实现程序向量并行性的发掘.因此提出了向量并行度指导的循环向量化方法,依据迭代间并行度、迭代内并行度和向量化因子,构建循环向量化方法选择方案,同时提出不充分向量化方法发掘并行度低于向量化因子的循环向量并行性,最后依据向量并行度对生成的向量循环进行展开.经过标准测试集测试,向量并行度指导的循环SIMD向量化方法比Loop-aware方法识别率提升107.5%,性能提升12.1%.     

串行运算向量化

本文探讨用向量运算代替串行FORTRAN的DO循环的基本条件,提出了向量化判别定理以及实现向量化的算法。     

利用U模变换增加并行粒度与改善数据访问局部性的方法

提出了一种利用循环变换增加循环并行粒度，改善循环数据访问局部性的方法，该方法利用了给定二重循环的相关向量集的某些性质，将外层循环变量不同而内层循环变量相等的若干次迭代合并，成为折叠后迭代空间的一个结点，并且保持内层循环的并行性不变，从而达到增加循环并行粒度的目的。对于更普遍的情况，该文讨论了如何根据给定循环的循环向量集，确定一个U模变换对迭代空间进行变换，达到内层循环可并行和扩大循环粒度两个目的，针对循环变换中数据访问局部性可能变差的问题，该文提出了对内层循环先合并，根据合并后的相关向量集变换迭代空间，以及折叠迭代空间的方法，该文的方法是Wavefront循环并行化方法的一种扩展。     

SIMD向量指令的非满载使用方法研究

大规模SIMD体系结构提供了更强的向量并行硬件支持,但是,大量迭代次数不足的循环由于不能提供足够的并行性,难以用等价的向量方式实现。为了更有效地利用SIMD,提出了一种非满载地使用SIMD指令的向量化方法。研究了向量寄存器的使用方式,基于非满载的向量寄存器使用方式实现了非满载的向量操作和短循环的向量化,并将非满载的向量化方法用于一般循环的向量化。提供了收益分析方法来为本向量化方法作精确指导。实验结果表明了该方法的有效性,所选测试用例的目标循环被向量化,平均加速比达到1.2。     

简洁循环与冗余循环

本文从信息冗余的角度,把FQRTRAN DO循环分为简洁循环与冗余循环两大类,它们的时序层次相对而言,前者精炼,后者臃肿。本文证明了简洁循环集里的每一个简洁循环,对应着冗余循环集里的一族冗余循环,这族冗余循环跟相对应的那个简洁循环表现出同样的向量化性态,从而把数量庞大而结构臃肿的冗余循环集的向量化问题,归结为相对狭小而结构精炼的简洁循环集的向量化问题。     

Loop-Nest Auto-Vectorization Based on SLP

如今,越来越多的处理器集成了SIMD(single instruction multiple data)扩展,现有的编译器大多也实现了自动向量化的功能,但是一般都只针对最内层循环进行向量化,对于多重循环缺少一种通用、易行的向量化方法.为此,提出了一种面向SLP(supcrword level parallelism)的多重循环向量化方法,从外至内依次对各个循环层次进行分析,收集各层循环对应的一些影响向量化效果的属性值,主要包括能否对该循环进行直接循环展开和压紧、有多少数组引用相对于该循环索引连续以及该循环所包含的区域等,然后根据这些属性值决定在哪些循环层次进行直接循环展开和压紧,最后通过SLP对循环中的语句进行向量化.实验结果表明,该算法相对于内层循环向量化和简单的外层循环向量化平均加速比提升了2.13和1.41,对于一些常用的核心循环可以得到高达5.3的加速比.     

面向SLP 的多重循环向量化

如今,越来越多的处理器集成了SIMD(single instruction multiple data)扩展,现有的编译器大多也实现了自动向量化的功能,但是一般都只针对最内层循环进行向量化,对于多重循环缺少一种通用、易行的向量化方法.为此,提出了一种面向SLP(superword level parallelism)的多重循环向量化方法,从外至内依次对各个循环层次进行分析,收集各层循环对应的一些影响向量化效果的属性值,主要包括能否对该循环进行直接循环展开和压紧、有多少数组引用相对于该循环索引连续以及该循环所包含的区域等,然后根据这些属性值决定在哪些循环层次进行直接循环展开和压紧,最后通过SLP对循环中的语句进行向量化.实验结果表明,该算法相对于内层循环向量化和简单的外层循环向量化平均加速比提升了2.13和1.41,对于一些常用的核心循环可以得到高达5.3的加速比.     

三叉控制转移的向量化

本文运用文[1]的成果,研究 DO 循环中一般三叉控制转移的向量化问题。推导出来的向量化算法已经在银河计算机上模拟实现。     

充分发挥超级计算机性能的Fortran编译程序系统(上)

富士通公司开发向量化Fortran 编译程序的目的,在于应用高级语言充分发挥超级计算机的性能,其功能是针对IF 语句的性质使向量指令最优化,根据DO 循环的性质选择向量寄存器的结构。利用这些强化功能,使多重DO 循环和多重过程达到自动向量化,此外,借助循环展开功能,改善了执行性能。为充实向量化功能还备有会话形式的程序调谐软件。进一步支持向量扩充语言,以便对程序进行简洁描述。     

向量FORTRAN语言编译中的向量地址计算及循环优化

本文介绍了在FORTRAN ANSI X3.9-1978(也作为国际标准ISO 1539-1980)基础之上扩充了向量成份的语言系统中编译程序的循环优化。探讨了向量头、向量增量和向量长度的计算以及DO语句目标代码的向量化方法。     

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

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

向量化的区间分割技术

本文以相关分析方法为依据,深入研究了串行运算向量化的区间分割方法,在非整体向量化技术上取得了进展。 我们对变序点作了深入的剖析,把它划分为四类,并给出了变序点分割算法。在本文中首次提出了用分割DO循环执行区间的方法来消除递归依赖关系,使得某一类存在递归的DO循环能在子区间上向量化。     

使用代价分析的向量化循环分割技术

为了使循环在编译过程中更充分地被向量化,提出了一种基于代价分析的向量化循环分割技术。标记出了迭代依赖间隔中不存在依赖关系的循环片段,在此基础上建立一个简单有效的代价分析模型来评估这些循环片段向量化和未向量化的CPU时钟周期开销,最后从代价分析结果中确定是否需要将其向量化分割,从而把向量化特性应用到细短的循环片段。实验结果表明了该技术的有效性,对迭代依赖距离大的循环片段优化作用更明显。     

向量化的区间分割技术初探

本文以相关分析方法为依据,深入研究了串行运算向量化的区间分割方法,在非整体向量化技术上取得进展。我们对变序点作了深入的剖析,把它划分为四类,并给出了变序点分割算法。但本文的主要成果还在于:首次提出了用分割DO 循环执行区间的方法来消除递归依赖关系,使得某一类存在递归的DO 循环能在子区间上向量化。     

FORTRAN DO循环向量化的相关函数法

本文通过对FORTRAN DO循环中数组元素下标式的函数性态的分析研究,给出了一种新的向量化算法——这种算法作者称为“相关函数法”。FORTRAN DO循环向量化的相关函数法,对于循环中数组元素的下标式是循环控制变量的非线性函数时,给出了向量化的充分性准则;对于数组元素的下标式是循环控制变量的线性函数时,则给出了向量化的充分必要条件,本算法的特点是:由于对数组元素的下标式限制少,并且算法简便,所以适应面广,易于在机器上实现。     

DO循环的向量化—超平面方法

<正> 在理论上超平面法与坐标法一样,可以应用于任何深度n(注意,这里n≥2,在坐标法中n≥1)、任何大小的DO循环嵌套,以识别其中可以进行向量(数组)运算的并行成份,并改写原串行执行循环形式为具体的向量语言描述的并行执行循环形式。超平面法有效地应用于合有递归性的DO循环。根据工程实际情况,我们仅就两层DO循环嵌套讨论超平面法,这时它能使原串行执行N×M次减少到N+M-1次。本文沿用[1]中的概念及记号,设所讨沦的DO循环满足[1]中规定的条件。     

DO循环向量化的坐标方法

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