I基于位宽控制提高SIMD架构并行度的优化算法.docVIP

基于位宽控制提高SIMD架构并行度的优化算法 张为华，朱嘉华，张宏江，臧斌宇 （复旦大学并行处理研究所 上海 200433） 摘要：随着SIMD功能单元做为多媒体加速部件的广泛应用，如何有效利用这一构架优化应用程序成为编译优化研究的热点。目前典型的SIMD结构为同一操作对不同的数据位宽提供了不同的指令版本，随着操作数位宽的增加，对应的SIMD指令可同时完成的操作个数也随之降低。因此，如何有效识别操作数的有效位宽，对提高优化过程中SIMD指令内操作的并行度将产生至关重要的影响。本文针对SIMD优化面临的并行度问题，提出了一种优化算法，该算法在对操作数的有效位进行分析的基础上，提出了一种进行溢出控制的算法，从而减少操作数对宽位宽数据类型的依赖。实验数据表明，该算法可以有效提高多媒体程序优化的并行度，对多媒体程序获得较好的加速效果。 关键词：有效位控制，溢出处理，饱和算术，编译优化，并行度 1 引言 随着人们生活水平的提高，各种多媒体应用逐渐成为各种运算平台的主要处理类型。这些应用环境的要求越来越高在通用处理器内增加基于SIMD）功能单元作为多媒体加速部件。SIMD架构的编译优化进行了大量的研究，但这些算法只对一些理想化的核心代码起到了优化作用，而对于真正的应用程序却很难达到预期的加速效果。造成这一性能差距的一个主要原因是SIMD优化过程中并行度利用不足。通常SIMD结构同一操作对不同的数据位宽提供了不同的指令版本，随着操作数位宽的增加，对应的SIMD指令可同时完成的操作个数也随之降低。以Intel公司的SSE2指令集为例：SSE2扩展指令集由一组基于128位SIMD寄存器的向量指令构成。通常每一种向量操作都对应了三条SSE2指令，这三条指令分别可同时完成4个标准整型（INT－32位)的操作，8个短整型（Short－16位)的操作或16个字符类型（Char－8位)的操作。利用SIMD指令优化相关程序时，在满足计算精度的要求下，选择并行度高的指令能得到更好的优化效果。然而，一方面,由于很多已有的多媒体程序是为通用处理器编写的，在编写过程中由于短数据类型（短整型或字符类型）被定义为标准整型不会对性能造成影响，因此程序员不会深入分析操作数的有效位宽，而把一些短数据类型定义为标准整型；另一方面，做为多媒体程序的主要开发语言，C语言中Integer Promotion规则规定所有短数据类型的整数必须被扩充到标准整型以保留运算过程中的数据溢出部分。这些编程习惯和高级语言的规则极大阻碍了针对SIMD架构优化过程中高并行度指令的选择。 本文针对SIMD优化面临的并行度问题，提出了一种优化算法，该算法首先对应用程序的进行有效位分析，使优化过程中更多的采用并行度高的指令成为可能；然后在此分析的基础上，提出了一种溢出控制算法，控制短数据类型操作过程中可能出现的溢出。实验数据表明，该算法可以有效提高SIMD优化过程中的并行度，对多媒体程序可以获得较好的加速效果。 本文剩余部分组织如下：第二章将介绍与本文相关的基础知识以及问题分析。第三章介绍了有效位分析算法。第四章介绍了溢出控制算法。第五章，给出了实验结果及对实验结果的分析。第六章给出了相关工作。第七章对全文进行了总结。 2 问题分析 2.1 背景知识 2.1.1 SIMD架构 目前，SIMD功能单元做为多媒体加速部件越来越广泛的应用到各种处理器中。在典型的SIMD架构中，同一操作对不同的数据位宽提供了不同的指令版本。随着操作数位宽的增加，对应的SIMD指令可同时完成的操作个数也随之降低。以Intel公司集成于奔腾处理器芯片中的SSE2指令集为例：SSE2扩展指令集由一组基于128位SIMD寄存器的向量指令构成。通常每一种向量操作都对应了三条SSE2指令，这三条指令分别可同时完成4个标准整型（INT－32位)的操作，8个短整型（Short－16位)的操作或16个字符类型（Char－8位)的操作。 同时，在SIMD架构中，每一个SIMD算术指令都有两种模式：标准模式和饱和模式。在标准模式下，当计算结果发生溢出时处理器会自动去掉溢出部分，计算结果取与该数据类型相应的低位。在饱和模式下，当计算结果发生溢出（上溢或下溢）时，处理器会自动去掉溢出的部分，使计算结果取该数据类型表示数值的上限值（如果上溢）或下限值（如果下溢）。比如，对于一个值为255的字符类型变量，将其值加1，在标准模式下，相加结果为0（去掉进位）；在饱和模式下，结果为255。饱和模式用类似的方法来处理下溢出，比如对于一个字节数据类型的数在饱和模式下，1减2的结果为0（而不是-1）。 2.1.2 Integer Promotion规则 在C语言规范C99中，对整数计算有如下要求：当一个较短的有符号或无符号整型运算中可能出现溢出时，计算应该被扩展到