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

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

面向SLP 的多重循环向量化

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

Loop-Nest Auto-Vectorization Based on SLP

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

面向向量化的局部数据重组

目前,利用微处理器的多媒体扩展对非多媒体程序的向量化已成为提高程序性能的一个重要手段.然而,和多媒体程序相比,非多媒体程序存在大量的非连续和非对齐的数据引用方式,严重影响程序的向量化发掘和向量化性能.提出一种新的向量化方法-基于局部数据重组的向量化技术(.通过改变局部数据的布局,将循环中不连续的数据引用变为连续的数据引用,进而完成对循环的向量化;并对数据引用作对齐分析和对齐优化,从而提高程序的向量化性能.以SPEC CPU2000浮点测试集为例,该方法不仅可以向量化对于ICC编译器无法向量化的程序,而且对这些程序都有很好的性能提升,在当前的测试环境下某些程序性能最高可提高241.6%.     

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

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

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

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

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

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

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

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

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

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

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

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

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

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

基于Profile信息的连续性分析算法及其优化

在Open64编译框架基础上,提出一种基于Profile信息的循环内数据访问连续性分析算法及其向量化优化方法。采用反馈式编译优化技术,获取程序运行时的连续性Profile信息,通过结构体剥离和数据重组方法实现程序向量化。实验结果表明,该算法针对不规则程序代码,可提供更精确的向量化信息,提高程序的向量化程度。     

一种基于汇编代码的单重循环向量化方法

1 引言在微处理器设计中,开发指令级并行(ILP)以提高微处理器系统的性能受到了很大的限制。研究更大发射的超标量微处理器已经是一件极其复杂而没有意义的事。但是如果在开发指令级并行的同时,开发数据级并行,理论分析表明可以显著提高微处理器的性能,微处理器的等效IPC(每个时钟周期发射的指令条数)和超标量微处理器相比可以提高20～40多倍。因此,在微处理器系统设计中开发数据级并行具有重要的理论意义和实用价值。     

Vector optimization vs vectorization

This paper differentiates between vectorization and concurrentization and vector optimization. Vectorization (concurrentization) is the process of translating serial DO loops into vector code for a vector computer (concurrent code for a multiprocessor computer). Vector optimization uses vectorization (concurrentization) but adds some intelligence to decide which loop (s) to run in parallel. Vector optimization tools, such as loop interchanging and generation of multiple versions of a loop, are introduced and some decision mechanisms are discussed.     

向量化友好的循环分块因子选择算法

具有病态规模的嵌套循环程序在进行循环分块时容易忽略分块因子对向量化的影响,导致非对齐数据访问,降低分块后循环代码的性能。提出了一种向量化友好的循环分块因子选择算法VEC-TSS。该算法对可向量化循环层以向量化收益分析确定分块因子,对其他循环层通过以局部性收益和并行粒度确定分块因子。实验结果表明,针对具有病态规模的循环程序,VEC-TSS算法与另外两种分块因子选择算法相比可以获得更好的程序加速比,同时具有良好的可扩展性。