SIMD编译优化技术研究

摘要

多媒体应用是近年来计算机领域的研究热点。多媒体应用的代码往往具有较高的并行度。为了获得更高的性能，几乎所有的处理器厂商都为其处理器增加了多媒体扩展，以充分利用处理器的计算能力，并提供了具有单指令多数据特点的指令集，简称为SIMD指令。SIMD指令能够对一组数据执行向量形式的运算，每组数据被划分为几个子字，并对所有的子字都执行相同的操作。 SIMD指令能够带来较高的执行效果、较低的功耗和较好的资源利用率。充分利用SIMD指令可以有效提高应用程序的性能。但是目前编译器对SIMD指令的支持并没有达到足够令人满意的程度。程序员往往需要通过手写汇编代码、内嵌汇编、或者通过使用编译器认识的内部函数等手段在代码中显示的使用SIMD指令。这要求程序员对SIMD指令集有深入了解，提高了多媒体程序的开发难度。此外，由于不同处理器的SIMD指令集之间差异较大，从而使代码的可移植性降低。因此我们希望编译器能够自动的从高级语言生成SIMD指令。称为SIMD编译优化。 这种优化和传统的针对向量处理器的自动向量化非常类似，因此又称为SIMD向量化。但体系结构和主要应用领域的不同使多媒体扩展和向量处理器之间存在较大差异。两者在向量长度、指令集特点以及存储操作等方面存在着关键区别。妨碍SIMD编译优化的主要有以下几个问题：多媒体程序中复杂的代码形式影响了向量化效果，各种多媒体典型操作变化较多不易识别，存储操作功能较弱制约了优化性能的提升。 本文提出了一种面向由C语言编写的多媒体应用程序、与目标平台无关的SIMD向量化方法，是对原有的向量化方法的扩展与改进，解决了现有技术中含有指针形式的C程序难以向量化、多媒体典型操作无法有效识别、SIMD寄存器数据利用率不高等问题，能够有效生成SIMD指令。该方法主要在语法树中间表示上进行，不改变编译后端的结构，具有较好的可移植性和可扩展性。 该方法对传统向量化算法的主要改进之处在于：对多媒体C代码广泛存在的指针访问进行了分析处理；采用模式匹配方法有效识别复杂的多媒体典型操作；采用循环分布、循环交换等方法提高了循环中潜在的并行性；本文还提出了一种SIMD寄存器分配方法减少冗余存储操作，降低因体系结构限制而产生的数据存储操作开销。

目录

文摘

英文文摘

第一章绪论

1.1 SIMD技术的应用背景

1.1.1多媒体应用的特点

1.1.2媒体处理器的特点

1.1.3 SIMD技术

1.2编译器设计

1.2.1编译器的作用

1.2.2编译器的基本结构

1.2.3编译器的工作流程

1.2.4编译器的构造

1.3 SIMD编译优化

1.3.1 SIMD编译优化研究的意义

1.3.2 SIMD编译优化的要求

1.4相关工作与研究现状

1.4.1向量化方法

1.4.2超字并行

1.4.3对SIMD编译优化相关子问题的研究

1.5本文主要内容、创新点与结构安排

第二章中间表示与编译优化分析

2.1编译优化与中间表示

2.1.1线性中间表示

2.1.2图中间表示

2.1.3 LCC编译器的中间表示

2.2控制流分析

2.2.1控制流图

2.2.2必经结点(dominator)

2.2.3循环的识别

2.3数据流分析

2.3.1可达定义分析

2.3.2可用表达式分析

2.3.3活跃变量分析

2.4本章小结

第三章SIMD向量化技术

3.1多媒体扩展与向量化处理的区别

3.1.1向量长度差异

3.1.2寻址模式与存储操作差异

3.1.3指令集差异

3.2 SIMD编译优化框架

3.3循环预处理

3.3.1确定循环信息

3.3.2指针的分析与处理

3.4复合操作的识别与归约

3.5数据依赖分析

3.6循环变换

3.6.1循环代码分布

3.6.2循环层次交换

3.7 SIMD中间表示的生成

3.6本章小结

第四章SIMD寄存器分配

4.1寄存器分配概述

4.2向量间的数据重组

4.3线性扫描寄存器分配

4.3.1动态规划与树覆盖

4.3.2选择最优指令执行顺序

4.3.3生命期分析

4.3.4寄存器状态记录

4.3.5最小代价溢出

4.4本章小结

第五章实验与结论

全文总结

参考文献

致谢