面向SIMD的数组重组和对齐优化

随着多媒体应用的普及,越来越多的处理器集成了SIMD扩展,但是非连续或者非对齐访存会阻碍程序的向量化或者造成性能损失。针对实际应用中出现的数组引用不连续的情况,提出了一种数学模型,用以刻画数组的访存模式和数据重组方案,以判断这些数组引用是否可以通过数组转置的方法满足连续性要求;并采用过程间数组填充、循环剥离和基于SLP的向量化代码生成方法等进行对齐优化。最后基于SPEC2000测试集对该算法进行了测试,结果表明,该方法可以有效地提升向量化程序的执行效率。     

一种单指令多数据向量化归约方法

单指令多数据(SIMD)扩展部件旨在发掘多媒体程序和科学计算程序的数据级并行,归约操作引起的真依赖给发掘程序中的数据级并行带来了阻碍。但体系结构和指令集的差异,使得面向向量机的归约向量化方法并不适用于SIMD扩展部件。针对上述问题,提出一种面向SIMD扩展部件的归约向量代码生成方法,以及归约的识别方法,利用向量移位指令实现向量代码生成。基于SPEC2006标准测试集的测试结果表明,与未利用归约向量化技术前相比,利用该归约向量化方法后的向量化加速比提高34%,从而验证了该方法的有效性。     

SIMD自动向量化编译优化概述

SIMD扩展部件是集成到通用处理器中的加速部件,旨在发掘多媒体程序和科学计算程序的数据级并行.首先介绍SIMD扩展部件的背景和研究现状,然后从发掘方法、数据布局、多平台向量化这3个角度介绍了SIMD自动向量化的研究问题、困难和最新研究成果,最后展望了SIMD编译优化未来的研究方向.     

面向SIMD扩展部件的循环优化研究

高性能微处理器中普遍采用SIMD向量扩展作为计算加速部件。在深入研究SIMD扩展部件数据依赖关系约束条件的基础上,提出一种基于依赖关系逆向图的Tarjan扩展算法,提高了SIMD并行性识别率,并结合传统向量化方法,实现了面向SIMD扩展部件的循环优化技术,消除了不可向量化语句对可向量化语句在数据重组中不必要的开销。实际程序测试结果显示,其在基于依赖关系的SIMD并行性判定方面优于ICC编译器,经过循环优化后,最终生成的SIMD代码其执行效率平均提高了12%。     

一种面向SIMD扩展部件的向量化统一架构

随着多媒体应用的普及和高性能计算的需求,越来越多的处理器集成了SIMD扩展。为了针对不同SIMD扩展部件自动生成高效的向量化代码,设计了一套虚拟向量指令集,在此基础上构建了一种面向SIMD扩展部件的向量化统一架构。将输入程序通过向量识别等阶段转变为虚拟向量指令的中间表示,而后通过向量长度解虚拟化和指令集解虚拟化,将其转变为特定SIMD部件的向量指令集。在申威1600、DSP和Alpha上的实验结果表明:统一架构能够针对3种平台自动变换出高效的向量化代码,在DSP上的加速比要明显优于其它两种平台。     

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

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

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

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

GCC非满载SLP向量化

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

基于神威蓝光处理器的向量数学软件包

首先介绍了SIMD扩展技术,并分析了使用SIMD扩展的3种方式,认为通过调用特定目标平台优化的第三方库是应用领域软件开发者快速开发高效并行程序的较好的方式;其次,介绍了国产神威处理器SW-1600平台,并利用SIMD扩展和循环展开等技术开发了SW-VML(SW Vector Math Library),开发过程中提出了访存对界、简化向量条件分支的优化方法,解决了非对界访存、向量与标量数组转换影响性能的问题,并根据SW编译器对OpenMP的支持,开发了多线程OpenMp版;最后,在SW-1600平台上采用不同向量规模对SW-VML进行了测试,测试结果显示,SIMD向量化相对于串行程序加速比为2.08,4线程相对单线程平均加速比为2.26.SW-VML是在国产神威系列处理器上开发高效程序的向量函数软件包,也是在神威蓝光高性能计算平台单计算节点开发高性能程序的基础软件工具包.     

发掘函数级单指令多数据向量化的方法

当前面向单指令多数据（SIMD）扩展部件的两类向量化方法分别是循环级向量化方法和超字级并行（SLP）方法。针对当前编译器不能实现函数级向量化的问题,提出一种基于静态单赋值的函数级向量化方法。该方法首先分析程序的变量属性,然后利用一组包括向量函数子句、一致子句、线性子句等编译指示子句指导编译器实现函数级向量化,最后利用变量属性结果对向量化代码进行了优化。从多媒体和图像处理领域选择部分测试用例对所提的函数级向量化的功能和性能在国产申威平台上进行测试,与程序串行执行相比,采用函数级向量化后程序的执行效率更高。实验结果表明函数级向量化可以取得类似任务级并行的加速效果,该方法可以指导自动函数级向量化的实现。     

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

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

一种改进的控制流SIMD向量化方法

SIMD扩展部件是近年来集成到通用处理器中的加速部件,旨在发掘多媒体和科学计算等程序的数据级并行.控制依赖给发掘程序中的数据级并行带来了阻碍,当前不论基于loop-based还是SLP的控制流向量化方法都需要if转换,而没有考虑循环内蕴含的向量并行度,导致生成的向量代码效率较低.此外不精确的代价模型指导控制流向量化,同样导致生成的向量代码效率较低.为此提出了改进的控制流SIMD向量化方法,首先提出了含有控制依赖的循环分布算法,分离循环的可向量化部分和不可向量化部分,同时考虑分布时数据的局部性;其次提出了一种直接向量化控制流的方法,该方法考虑了基本块间的向量重用;最后利用精确的代价模型指导超字选择指令和超字条件分支指令的生成.实验结果表明,与现有的控制流向量化方法相比,本文提出的改进方法生成的向量代码性能提高24%.     

面向DSP的超字并行指令分析和冗余优化算法

如今单指令多数据流(SIMD)技术在数字信号处理器（DSP）上得到了广泛的应用,现有的向量化编译器大多都实现了自动向量化的功能,但是编译器并不适合支持DSP为特征的SIMD自动向量化,主要由于DSP复杂的指令集、特有的寻址模型,以及依赖关系或者数据非对齐等原因而导致向量化效率不高。为了解决此问题,在基于Open64的超字并行(SLP)自动向量化编译系统后端,对SLP自动向量化中的指令分析和冗余优化算法进行了添加和改进,生成更加高效的向量化源程序。实验结果表明,该优化方法能有效提高DSP性能并降低功耗。     

基于条件分类的控制流向量化

现代编译器越来越依赖SIMD指令来提高向量化性能,但控制流的复杂性严重阻碍了SIMD向量化的发掘。现有的控制流向量化方法对于单层控制流的向量化很有效,但对嵌套等复杂控制流无法取得令人满意的效果。因此,提出了一种基于条件分类的控制流向量化方法。该方法对条件为循环不变量的控制流,以层次遍历的顺序实施IF外提;对条件为循环变量的控制流,结合语句匹配和条件合并递归地进行IF转换,生成相应的SIMD指令,从而实现嵌套控制流的向量化。实验结果表明,该方法能够有效消除循环中的嵌套控制流,提高向量化发掘的能力, 有效提升 测试程序的性能。     

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

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

基于全局数据重组的循环倾斜优化

循环倾斜是程序优化中一种循环变换的手段,它改变空间迭代形式,将循环存在的跨迭代的并行用传统的并行标识出来,使得循环可以并行执行。但是循环倾斜后,并行执行的数据在内存中是离散的,而且每次迭代执行的次数是不一致的。为了更有效地利用SIMD,本文提出一种基于全局数据重组的循环倾斜优化方法。首先分析循环倾斜优化,针对数据离散的问题实现全局数据重组,改善数据局部性,循环易于向量化操作;针对迭代执行次数不一致问题,实现非满载向量操作,使尾循环得以向量执行。最后选择wavefront程序进行测试,优化后,程序计算可以获得平均10.73倍的加速效果。     

面向国产平台的LLVM自动向量化移植与优化

作为SIMD扩展部件向量化的重要手段,自动向量化已在LLVM编译器中得到实现,但向量长度以及指令集功能的差异,导致国产平台在自动向量化过程中容易错失向量化机会以及向量化后产生倒加速的问题。为使SIMD得到充分应用,结合国产平台的指令集特征完善指令代价信息以提高收益分析精准度,使其在自动向量化后生成后端支持且简洁高效的向量指令。在此基础上,提出一种改进的控制流向量化方法,通过添加指令代价信息提高自动向量化的适配能力,从而形成一套面向国产平台的LLVM自动向量化系统。实验结果表明,相比自动向量化移植前,通过该方法进行移植优化后,SPEC测试的整体性能提升10.8%,TSVC测试集中的加速比提升16%,精准代价指导下的加速比提升42%,控制流向量化下的加速比提升51%。