面向SLP 的多重循环向量化

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

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

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

基于跨基本块变换和循环分布的SLP优化技术

现有的SLP优化算法无法处理内层循环中存在的依赖环和归约,并且在基本块边界产生大量的冗余拆包和赋值语句,从而导致向量化效率不高.针对该问题,提出了一种基于跨基本块变换和循环分布的SLP优化算法.该算法以控制流图为基础,根据基本块间各数组变量的Define-Use关系以及跨越基本块之间的数据依赖关系进行跨基本块的向量化变换,有序地采用跨基本块变换和循环分布,尽可能发掘最内层循环基本块内语句的并行性,使SLP自动向量化编译器生成具有更多SIMD指令的向量化代码.实验结果表明,该算法能够隐藏更多跨基本块冗余操作的开销,同时利用跨基本决的数据依较生成更优的SIMD指令,有效地提高了向量化程序的加速比.     

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

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

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

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

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

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

非正规化循环的单指令多数据向量化

针对非正规化循环的上下界、步长等循环信息不确定的问题,解决了循环条件为逻辑表达式、增量减量语句和do-while循环的正规化问题。对不能正规化的循环提出了一种展开压紧算法,并用超字并行向量化方法发掘展开压紧的结果。实验结果表明,与现有的非正规化循环的单指令多数据(SIMD)向量化方法相比,所提出的转换方法和展开压紧方法能够更好地发掘非正规化循环的向量化特性,生成代码的性能加速比提高了6%以上。     

新型超字级并行改进算法

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

滑动窗口应用循环展开及其数据通路生成

滑动窗口广泛应用于图像处理、模式识别和数字信号处理中,它具有数据量大、计算密集等特点.可重构硬件为滑动窗口应用提供了一个灵活高效的实现平台.文中基于一种存储、数据调度模型及其相应的数据通路生成技术,研究循环展开对滑动窗口应用的面积、时钟频率和吞吐率的影响.实验结果表明内层循环展开相对于外层循环展开将带来更大的控制复杂度,增加了对芯片面积的需求,然而外层循环展开需要更多的存储资源保存重用数据;当片内存储模块个数增加到一定规模时,时钟频率将随着循环展开不断降低;不同维度的应用,吞吐率随循环展开提升程度不同.     

基于执行频率的循环展开优化方法

本文提出一种面向嵌入式低功耗的基于执行频率的循环展开优化方法,根据循环的执行频率,积极展开一些频繁被执行的循环,不展开那些很少被执行的循环。所有这些都在GCC4.0.0上进行了实现,并在sim-panalyzer功耗模拟器上对12个Benchmarks进行了测试,结果表明,相对于传统的循环展开优化,新的优化方法可以有效的降低功耗,并且减少了代码量的增加。