论文部分内容阅读
SIMD (Single Instruction Multiple Data)扩展部件已广泛应用于现代高性能计算的并行处理架构中,它使用宽位SIMD寄存器对多个字符型、整型、浮点型数据同时进行相同操作,实现一种细粒度的数据级并行。SIMD扩展部件以其实现成本低、部件功耗少、计算效率高等特点,逐渐成为高性能微处理器的必备计算加速部件,其应用领域也从最初的多媒体处理,扩展到科学计算、数字信号、密码破译等非多媒体应用领域。SIMD扩展部件作为体系结构层面的硬件设计,需要程序员显式参与才能充分发挥其计算潜能,这样大大增加了编程的工作负担和程序出错的概率,所以用户越来越多地希望编译器具备功能完备、性能高效的自动SIMD向量化能力,但现有自动SIMD向量化所获得的程序性能与用户所期望的理想性能之间还存在较大的差距,所以如何提高自动SIMD向量化的优化效果,成为SIMD优化技术亟待解决的重要问题之一。自动SIMD向量化技术是一种将串行代码自动转换成SIMD指令代码的程序变换技术,它最早起源于传统向量化技术,经过二、三十年的发展,积累了一批研究成果和实用技术,可以对规则循环产生高效的SIMD代码,但面对复杂多重循环时,无法产生令人满意的优化效果。本文以构建源到源自动SIMD向量化工具SW-VEC为研究背景,以国产通用高性能处理器SW1600为硬件平台,系统深入地讨论和研究了面向多重循环的向量化方法和性能优化技术,主要贡献和创新包括:1、现有SIMD扩展部件的并行性分析方法基本上沿用传统向量化中基于依赖环的分析技术,但向量计算机与SIMD扩展部件在体系结构上的差异,导致该分析方法无法反应出SIMD扩展部件的并行特性,造成SIMD并行性误判率较高的现象。针对该问题本文首先引入“受限并行”的概念来描述SIMD扩展部件并行本质;综合依赖距离、依赖方向和依赖性质,提出了适应SIMD扩展部件的并行性判定标准,并首次提出了基于依赖关系逆向图的Tarjan算法,在解决对非阻碍依赖关系的优化问题的同时,为面向依赖关系的循环预优化技术提供了必要的SIMD并行性判断信息,从而提高对多重循环SIMD并行性判定的准确率。测试结果表明所提出的SIMD扩展部件并行性判定标准以及循环预优化技术,可以为后端SIMD优化模块提供数量更多,依赖关系更友好的SIMD向量机会。2、非规则因素导致多重循环丧失基于多面体模型的SIMD优化机会,成为限制SIMD优化效果的另一重要原因。为了解决以上问题,本文通过采用动静结合的编译方式,在分析程序剖面信息的基础上,提出了基于动态检测条件的SIMD投机优化技术,以及SIMD投机并行混合代码框架。该混合代码框架可以根据动态检测条件结果,动态决定SIMD代码与串行代码的执行机会,从而为实现含有非规则因素多重循环的SIMD优化提供编译支持。3、多重循环在带来更佳优化机会的同时,也造成SIMD优化的许多困难,其中最主要的就是如何确定适合多重循环存取特性的SIMD向量化方案。为了解决该问题,本文首先针对循环置换、循环剥离和语句移动为主要内容的SIMD向量化方案提出了多面体建模方法,并在此基础上实现了SIMD向量化方案生成算法。结合生成的SIMD向量化方案,提出面向非连续对齐数组的SIMD向量化代价计算模型。通过将两者相结合,提出了基于最小SIMD向量化代价的SIMD向量化方案搜索算法,解决了多重循环SIMD向量化方案选择难题。测试结果表明,该方法所选择出的SIMD向量化方案与手工向量化方案基本一致,提升了多重循环的SIMD优化效果。4、SIMD扩展部件需要通过多级缓存实现向量数据的存取,故向量数据局部性成为影响SIMD优化效果的重要因素。为了提高Cache命中率,本文提出了一种基于应用环境的自适应循环分块方法。该方法综合考虑程序应用环境中的硬件因素和计算需求,将循环每次迭代所需数据量与高速缓存容量紧密结合,根据SIMD寄存器数据宽度、一级Cache、二级Cache容量以及程序数据需求,动态决定循环分块大小,提高向量数据的Cache命中率。测试结果表明,该优化技术能够针对不同硬件平台、不同应用程序取得较好的数据局部性,实现对SIMD优化效果的进一步提升。5、由于超子并行(Superword Level Parallelism, SLP)算法本身所固有的缺陷造成了所生成的SIMD代码中存在大量可以继续优化机会。为了利用这些优化机会,本文通过引入向量匹配度向量概念,使用与目标向量差异最小向量进行目标向量重组,降低重组指令的数目,提高SIMD代码的执行效率。测试结果表明,能够有效降低向量重组指令的个数,对测试用例取得了预期的优化效果。本文提出的优化技术已在SW-VEC工具中得到了实现,并在测试中验证了以上算法的正确性和有效性。