循环变换技术在自动向量化中的应用研究

论文摘要

近年来,随着多媒体应用的迅速发展,很多高性能微处理器都采用了SIMD扩展技术。SIMD扩展技术缺少统一的指令描述规范,程序员不仅需要对程序的结构有较为深刻的认识,而且要掌握目标平台支持的扩展体系结构和指令集的特点,对程序员来说编写SIMD程序是具有挑战性的工作,因此当前编译技术中的自动向量化就是解决这个问题的一个重要方法。自动向量化需要编译器能够充分分析原程序的特点,将其中可向量化的循环或语句块转换成语义等价的SIMD指令。本文针对当前的主流编译器在自动向量化方面的缺点,结合传统的循环变换方法,深入研究了可以提升自动向量化效率的循环变换技术。首先,以数据依赖关系分析为基础,分析了程序中语句向量化的合法性,设计实现了语句向量化识别算法及基于语句向量化识别的循环分布算法。第二,针对SIMD体系结构中标量部件与向量部件可并行工作的特点,研究了基于混合并行的循环变换技术,设计实现了一种简单通用的循环选择合并算法,并针对合并不成功或性能不能达到预期效果的情况,提出了相应的分段展开变换策略,提高了系统的硬件资源利用率。第三,针对自动向量化变换在处理复杂应用程序所存在的不足,研究了基于信息识别的交互式变换方法,设计实现了一种交互式的循环变换调优框架。在该框架结构内,通过分析应用程序的特点,采用可视化动静态编译信息的方法,为用户提供一个高效的渐近式SIMD交互调优环境。本文研究的循环变换方法在自动向量化项目SW-VEC中进行实现,测试结果表明,使用本文的自动变换方法对SPEC CPU2000浮点测试集中几个向量化较好的测试程序性能平均有10%左右的提升,从而验证了本文提出的方法可以提升向量化识别率并能够得到较高的加速比。同时,测试结果表明,通过交互式的循环变换方法,可以弥补自动向量化中难以处理的复杂情况,进一步提高编译器的向量化能力。

论文目录

• 表目录
• 图目录
• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究的背景
• 1.1.1 使用SIMD 技术的主要途径
• 1.1.2 自动向量化方法介绍
• 1.1.3 循环变换技术介绍
• 1.1.4 自动向量化中研究循环变换的意义
• 1.2 课题研究的内容
• 1.2.1 课题来源
• 1.2.2 论文的主要工作及创新点
• 1.3 国内外发展现状
• 1.4 论文的结构安排
• 第二章 基于数据依赖分析的循环分布技术
• 2.1 问题概述
• 2.2 SIMD 中的依赖关系分析
• 2.2.1 语句依赖未形成依赖环时的分析
• 2.2.2 语句依赖形成依赖环时的分析
• 2.3 基于向量化识别的循环分布算法
• 2.3.1 基于依赖关系的语句向量化能力分析
• 2.3.2 基于语句向量化识别的循环分布
• 2.4 本章小结
• 第三章 基于混合并行的循环合并与分段技术
• 3.1 问题概述
• 3.2 开发混合并行的约束
• 3.2.1 多功能部件并行操作的约束
• 3.2.2 应用程序并行操作的约束
• 3.2.3 处理器体系结构对混合并行的约束
• 3.3 基于混合并行的循环选择合并变换
• 3.3.1 循环合并变换的约束分析
• 3.3.2 多功能部件计算模型
• 3.3.3 简单的循环选择合并变换
• 3.4 针对向量化循环的分段展开变换
• 3.4.1 循环分段展开的基本思想
• 3.4.2 向量化循环分段并行的限制
• 3.4.3 向量化循环分段展开算法
• 3.5 本章小结
• 第四章 基于信息识别的交互式循环变换技术
• 4.1 问题概述
• 4.2 向量化交互的流程
• 4.3 向量化交互调优信息
• 4.3.1 交互信息分类
• 4.3.2 交互信息提取
• 4.3.3 交互信息的使用
• 4.4 向量化交互式变换的方法
• 4.4.1 基于控制流信息的交互
• 4.4.2 基于数据连续信息的交互
• 4.4.3 基于数据对齐信息的交互
• 4.4.4 基于数据依赖信息的交互
• 4.4.5 基于混合并行的交互
• 4.4.6 基于局部数据存储信息的交互
• 4.5 本章小结
• 第五章 实验测试与结果分析
• 5.1 实验环境
• 5.2 测试集说明
• 5.3 对自动变换的测试
• 5.4 交互式变换的实现与测试
• 5.4.1 交互式变换的实现
• 5.4.2 交互式变换的信息提取
• 5.4.3 交互式变换的测试
• 5.5 本章小结
• 结束语
• 一、工作总结
• 二、未来研究展望
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢