基于多种同构化变换的SLP向量化方法

超字级并行(superword level parallelism,SLP)是一种面向处理器单指令多数据(single instruction multiple data,SIMD)扩展部件实现程序自动向量化的方法,这种方法被广泛应用于主流编译器中.SLP方法有赖于先找到同构指令序列再对之进行自动向量化.将非同构指令序列等价转为同构指令序列以扩展SLP方法的适用范围是当前研究趋势之一.提出SLP的一种扩展方法──SLP-M向量化方法,引入二元表达式替换同构转换方式,基于条件判断和收益计算的选择,利用多种指令序列同构化转换,将满足特定条件的非同构指令序列转换为同构指令序列,再进一步实施自动向量化,从而提升SLP的适用范围和收益.在LLVM中实现了SLP-M方法,并利用SPEC CPU 2017等标准测试集进行了测试评估.实验结果表明,SLPM方法相比于已有方法在核心函数测试中性能提升了21.8%,在基准测试程序整体测试中性能提升了4.1%.

面向SLP的多重循环向量化

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

一种基于剪切的SLP向量化方法

作为多媒体和科学计算等领域重要的程序加速器件之一,SIMD扩展部件现已广泛集成于各类处理器中。自动向量化方法是目前生成SIMD向量化程序的重要手段。超字并行SLP(superword level parallelism)方法现已广泛应用于编译器中,并成为实现基本块级代码向量化的主要手段。SLP在进行收益评估时仅考虑代码段整体向量化的收益,并没有考虑到向量化收益为负的片段会降低最终整体的向量化收益,从而导致SLP方法无法达到最好的向量化效果。基于此,提出了一种基于剪切的SLP向量化方法(throttling SLP,TSLP)。通过寻找最优的向量化子图,去除了向量化收益为负的代码段,从而可以获得更好的向量化效果。通过标准测试程序的实验结果表明,与原来的SLP方法相比,TSLP方法平均能够获得9%的性能提升。

GCC非满载SLP向量化

随着向量长度的不断增长, SIMD扩展部件得以处理更为庞大的数据级并行,但程序的并行阈值也随之提高.对于现有的自动向量化编译器,如果在分析阶段不能从串行代码中发掘出足够的数据级并行以完全填充向量寄存器,则不会进入相应的向量代码变换阶段,从而无法向量化.较长的向量长度使得某些并行性不足的程序失去了向量化的机会,造成了性能下降.为了更加充分的利用SIMD部件,介绍了一种面向基本块的非满载向量化方法ISLP.基于开源GCC编译器,从并行性检测、代码生成和代价模型3个方面详细阐述了ISLP的设计与实现.在标准测试集上的实验结果表明,该方法可以有效地对超字级并行性不足的程序进行向量化处理,提高程序执行效率.选取的测试用例在向量化后的平均加速比达到1.14,性能较常规SLP方法提升11.8%.

分段约束的超字并行向量发掘路径优化算法

超字并行(SLP)是一种针对基本块的向量并行发掘方法,结合循环展开可以发掘更多的并行性,但同时也会产生过多的发掘路径。针对上述问题,提出了一种分段约束的SLP发掘路径优化算法;采用分段的冗余删除方法,来保证冗余删除后段的同构性。采用段间的SLP发掘,来约束发掘路径;最后进行pack调整来处理访存重叠的情况。实验结果表明,该方法有效增强了SLP向量化功能,对于测试程序,向量化的平均加速比接近2。

软件流水向量化算法研究

描述了开源高性能编译器Open64及向量化框架,给出了多循环层进行依赖关系分析算法和收益分析方法。结合面向DSP架构的SLP向量化框架,给出了一种应用软件流水的向量化算法。实验结果表明软件流水向量化算法适用于某些计算密集的DSP应用,最高加速比达到14.2。

新型超字级并行改进算法

对于超字级并行(SLP)算法不能有效地处理大型程序中并行代码率较小,且可向量化的代码中可能存在对向量化不利的代码的问题,提出了一种新型的SLP改进算法NSLPO。首先,将程序中不能向量化的非同构语句进行同构化处理,定位SLP丢失的向量化机会;然后,通过冗余节点添加构建最大通用子图,通过冗余删除等优化过程得到同构化之后的补充SLP图,提高程序中代码的并行性;最后,运用节流法将对向量化有害的代码摒除在向量化之外,仅对它们进行标量处理,通过只向量化处理那些向量化有收益的代码以尽可能地提升程序效率。在一组广泛使用的内核测试集中进行实验,结果显示,与SLP算法相比,NSLPO算法性能更优,其执行时间比SLP平均减少9.1%。

基于有向图可达性的SLP向量化识别方法

SLP(superword level parallelism)是一种实现SIMD(single instruction multiple data)向量化的方法,当前的主流向量化编译器都实现了这种向量化方法.然而,当前算法在进行SLP向量化时,对应用程序中可向量化循环的分析过程过于保守,导致其识别SLP向量化的能力不足.为了提升该能力,本文提出了一种基于有向图可达性的SLP向量化识别方法.首先,基于数组依赖图构建包含数组和语句依赖信息的有向图,使同一条语句内的所有数组节点都在一个强连通分量内,并对强连通分量之间的依赖边进行剪枝;其次,分析不同强连通分量节点之间的可达性,根据节点的可达性获得识别SLP向量化所需的所有依赖信息,从而确定语句中的循环是否可以进行SLP向量化.将该方法在Open64-5.0编译器中实现后,SLP向量化效果得到大幅提升.对gcc-vect测试集中程序的实测结果表明,优化后的Open64-5.0编译器识别SLP向量化循环的能力优于GCC4.9,与Intel ICC14.0相当,生成的向量化代码性能优于当前最优算法.

一种新型自动向量化编译算法

SIMD(single instruction multiple data)体系结构在高性能计算与嵌入式多媒体计算中扮演着重要的角色,对于SIMD指令的自动向量化编译技术是当前编译领域的研究热点.本文基于超字并行(super-word level parallelism,SLP)算法提出了一种新的自动向量化算法GSLP(global super-word level parallelism),该算法分为两部分:语句分组和语句调度.语句分组从全局出发分析超字复用信息,在语句分组的过程中,充分挖掘基本块的直接或者间接的超字复用信息,提高基本块内语句并行操作的机会;语句调度对基本块内的所有语句进行调度并调整超字内部单字(Single-word)数据的组织顺序,使生成的代码中打包/解包(pack/unpack)操作的数量降到最低.使用16个测试程序对GSLP算法进行测试,试验结果表明该算法使打包/解包操作的数量平均减少了41.6%,与SLP算法所产生的加速相比平均提高了4.7%.