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

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

面向多簇超长指令字DSP的向量化优化算法

BWDSP是一款针对高性能计算领域设计的处理器,采用多簇超长指令字（VLIW）体系结构和SIMD架构,同时也提供了很多向量化指令．然而现有的编译框架无法对这些向量化指令提供支持,因此本文提出了一种向量化优化算法,可以显著提高一些在DSP领域有着广泛应用的计算密集型程序的性能．最终实验结果表明,该优化算法能够平均取得6．60倍的加速比．     

基于数据对齐属性指导的GCC自动向量化优化

主流通用处理器都已经实现了多核并行以及处理器核内的SIMD并行。虽然GCC编译器实现了面向SIMD并行的自动向量化,但是编译器针对OpenMP并行程序的自动向量化效果仍很不理想。针对多线程并行的OpenMP程序,基于GCC的OpenMP编译实现,扩展了数据对齐属性指导语句,使编译器在自动向量化时能够进行更准确的数据对齐与否的判断,优化了GCC编译器的自动向量化。     

一种多倍数据供应的编译优化方法

数据的快速及时供应对访存密集型程序的性能有着直接的影响.提出一种多倍数据供应MDS(Multiple Data Supply)的编译优化方法,在不增加处理器设计复杂度的前提下,利用现有处理器的高带宽,一次对内存进行多个数据的读写,减少访存次数,提高应用程序效率.在编译优化阶段,利用自动向量化技术,生成向量形式的树结构,增加一条新的扩展路径来处理从向量化的树结构到底层结构的扩展.针对向量化后树结构的多样性问题,设计新的优化遍以及RAC(Register Assignment Chain)替换算法进行专门处理.在龙芯3A处理器平台上,对SPEC-CPU2000的测试,CINT程序平均性能提升11.6％,CFP程序平均性能提升14.4％.     

基于编译指示的向量化方法

编译器由于程序分析能力不足,无法自动实现循环向量化或者会造成盲目自动向量化。为此,提出一种基于编译指示的向量化方法。通过在代码中插入向量化编译指示语句,指导自动向量化编译工具的处理过程,自动生成高效的向量化代码。测试结果表明,该方法能够有效提高目标代码的运行性能。     

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

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

一种基于增量式实例学习的迭代编译方法

为提高编译器的自适应性,以应对复杂的体系结构,提出一个结合迭代编译和机器学习的编译框架。编译器可将在优化空间中搜索到的最佳编译选项信息保存到知识库中,并能从知识库中学习获得适合当前程序的最佳编译选项。实例学习算法具有增量式的特点,可有效利用编译过程中积累的数据。通过避免冗余实例入库以及从库中剔除噪声实例,保证学习的精度与效率。     

一种针对多媒体扩展指令集和实际多媒体程序的自动向量化方法

自动向量化编译是利用处理器的多媒体扩展指令集提升多媒体程序性能的理想工具．但目前的研究不能有效加速实际程序．其主要原因是：普通算术操作的向量化不一定有性能提升;而多媒体典型操作因为其在源代码中表现形式多样而不能充分向量化．为了解决这一问题,文章对经典向量化算法进行改进以灵活统一地向量化这两类操作．主要的改进是增加了两个步骤：统一操作的不同表现形式和识别有价值的向量化操作．改进后的算法可以充分利用指令集生成高效代码,从而对实际多媒体程序拥有良好效果．此外,该算法可扩展性也很强．     

分簇VLIW DSP上支持单双字模式选择的SIMD编译优化

BWDSP100是一款采用超长指令字(VLIW)和单指令多数据流(SIMD)架构的针对高性能计算领域而设计的32位静态标量数字信号处理器,其指令级并行(ILP)主要是通过其特殊的分簇体系结构和SIMD指令来实现,然而现有的编译框架无法对这些特殊的SIMD指令提供支持。由于BWDSP100拥有丰富的SIMD向量化资源,且其所运用的雷达数字信号处理领域对程序的性能要求极高,因此针对BWDSP100结构的特点,在传统Open64编译器中SIMD编译优化框架的基础上提出并实现了一种支持单双字模式选择的SIMD编译优化算法,通过该算法可以显著提高一些在DSP上有着广泛运用计算密集型程序的性能。实验结果表明,与优化前相比,该算法方案在BWDSP编译器上的实现能够平均取得5.66的加速比。     

监督学习模型指导的函数级编译优化参数选择方法研究

基于机器学习的迭代编译方法可以在对新程序进行迭代编译时,有效预测新程序的最佳优化参数组合。现有方法在模型训练过程中存在优化参数组合搜索效率较低、程序特征表示不恰当、预测精度不高的问题。因此,基于机器学习的迭代编译方法是当前迭代编译领域内的一个研究热点,其研究挑战在于学习算法选择、优化参数搜索以及程序特征表示等问题。基于监督学习技术,提出了一种程序优化参数预测方法。该方法首先通过约束多目标粒子群算法对优化参数空间进行搜索,找到样本函数的最佳优化参数;然后,通过动静结合的程序特征表示技术,对函数特征进行抽取;最后,通过由函数特征和优化参数形成的样本构建监督学习模型,对新程序的优化参数进行预测。分别采用k近邻法和softmax回归建立统计模型,实验结果表明,新方法在NPB测试集和大型科学计算程序上实现了较好的预测性能。     

一种面向向量化的动态指针别名分析框架

指针别名分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础.在向量化方法和动态指针别名分析相关研究的基础上,设计了一种面向向量化的动态指针别名分析框架.该框架通过动态插桩和试运行提取指针别名信息,并反馈到向量化阶段指导向量化代码生成.从提取候选别名分析集、插桩及试运行和反馈优化3个方面对整体框架进行分析和研究.该框架基于Open64实现,并以通用测试集GCC-VECT和典型应用进行了实验评估,结果表明,该框架相比静态指针别名分析具有更精确的别名分析结果,该结果能够有效改进向量化程序的加速比.     

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

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

SINOF: A dynamic-static combined framework for dynamic binary translation

Dynamic binary translation (DBT) is an important technique in virtualization, and in migrating legacy binaries to platforms based on a new architecture. However, poor profile information limits the process of optimization at runtime, so the DBT system may suffer from substantial overhead. In this paper, we design and implement a static-integrated optimization framework (SINOF) to improve the runtime performance for DBT. Combining static and dynamic approaches can greatly reduce the overhead of optimizing, profiling and translating for any program that runs repeatedly. Under this framework, once the source image has been executed, the profile information and target code will be saved in a software cache, and will be available for future runs. In the static phase, the saved code is analyzed and optimized based on the information collected in the previous run. Especially, we reorganize the code layout of the software cache. Experimental results show that the proposed framework can reduce run time by more than 30% on average compared to the original versions of DBT that the framework is based on.     

Vectorization and multitasking of dynamic programming in control: Experiments on a CRAY-2

Parallelism in dynamic programming is considered within the specificity of optimal control. We present the program PDVP developed for solving a general deterministic discrete-time optimization problem by means of a parallel dynamic programming algorithm on the state variables. Multitasking and vectorization are considered from the viewpoint to implement PDVP on a CRAY-2. The performances are analysed through a significant application to the optimization of satellite trajectories. Promising results are obtained.     

基于BDD的谓词分析与优化

为对带谓词的数据流进行准确而有效的分析,首先介绍了John W.Sias等人提出的一种基于二进制决策图(BDD)的谓词分析系统(PAS);然后在其基础上,提出了结合芯片自身体系结构特点的谓词优化算法。将PAS及优化算法在学院研制的FT_D4芯片的编译器上实现,实验结果表明,这种基于BDD的谓词分析与优化方法简化了程序控制结构,减少了对谓词寄存器的使用,缩短了代码执行时间,性能获得了较大的提高。     

快速多极子方法在申威众核处理器上的实现和优化

快速多极子方法(FMM)是一种求解N体问题的快速高效数值算法,在宇宙学和分子动力学等模拟中具有广泛的应用。申威SW26010是一款国产众核异构处理器,含260核心(4核组)。基于申威SW26010的众核架构设计和实现了快速多极子方法,并对核心函数(尤其是最耗时的粒子对相互作用)系统地进行了性能优化,包括异步DMA、SIMD向量化、循环展开、内联汇编指令调整等。以粒子对相互作用为例,优化后代码的计算速度约为主核上运行的原始代码的400倍,每个核组上的浮点性能达到250 GFLOPS,即理论峰值性能的32.5%。     

面向SLP 的多重循环向量化

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

程序自动并行化中的数组终写关系分析

在程序自动并行化中过程中,数据收集阶段可能产生冗余通信,该文利用数组终写关系分析的方法来消除冗余通信,实现嵌套循环中数组数据最后写关系的快速求解,并将结果提供给编译器后端,生成精确数据收集代码。描述数组终写关系的研究目的和内容,将所处理的嵌套循环根据其结构特征进行分类,给出实现算法的过程。测试结果证明了该算法的正确性和高效性,所产生的精确数据收集代码能够有效地消除部分冗余通信,从而优化和提高了并行化程序的性能。     

面向多簇架构DSP的树匹配向量化算法

BWDSP是针对高性能计算设计的一款新型的处理器, 采用多簇超长指令字体系结构和SIMD架构, 有丰富的指令集. 为充分利用BWDSP提供的向量化资源, 迫切需要提出一种向量化算法. 本文在open64基础上研究并实现了面向多簇超长指令字(VLIW)DSP的SIMD编译优化算法. 算法基于OPEN64的中间语言WHIRL, 能够充分地利用BWDSP丰富的硬件资源和向量化指令. 最终实验结果表明, 对于能够合成双字和单字的循环程序, 该优化算法能够平均取得6倍和4倍的加速比.