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

《计算机学报》2009年11期，2009，32（11）基于位宽控制提高SIMD架构并行度的优化算法张为华，朱嘉华，张宏江，臧斌宇（复旦大学并行处理研究所上海200433）摘要：随着SIMD功能单元做为多媒体加速部件的广泛应用，如何有效利用这一构架优化应用程序成为编译优化研究的热点。目前典型的SIMD结构为同一操作对不同的数据位宽提供了不同的指令版本，随着操作数位宽的增加，对应的SIMD指令可同时完成的操作个数也随之降低。因此，如何有效识别操作数的有效位宽，对提高优化过程中SIMD指令内操作的并行度将产生至关重要的影响。本文针对SIMD优化面临的并行度问题，提出了一种优化算法，该算法在对操作数的有效位进行分析的基础上，提出了一种进行溢出控制的算法，从而减少操作数对宽位宽数据类型的依赖。实验数据表明，该算法可以有效提高多媒体程序优化的并行度，对多媒体程序获得较好的加速效果。关键词：有效位控制，溢出处理，饱和算术，编译优化，并行度1引言随着人们生活水平的提高，各种多媒体应用逐渐成为各种运算平台的主要处理类型。这些应用在极大丰富人们生活的同时，对硬件环境的要求也越来越高。由于多媒体程序自身具有较好的数据并行性，在通用处理器内增加基于单指令流多数据流（SIMD）功能单元作为多媒体加速部件成为目前多媒体处理的主要解决方案[1]。随着SIMD功能架构的广泛应用，如何有效利用这一架构优化应用程序成为编译优化研究的热点之一。近年来，虽然针对SIMD架构的编译优化进行了大量的研究，但这些算法只对一些理想化的核心代码起到了优化作用，而对于真正的应用程序却很难达到预期的加速效果。造成这一性能差距的一个主要原因是SIMD优化过程中并行度利用不足。通常SIMD结构同一操作对不同的数据位宽提供了不同的指令版本，随着操作数位宽的增加，对应的SIMD指令可同时完成的操作个数也随之降低。以Intel公司的SSE2指令集为例：SSE2扩展指令集由一组基于128位SIMD寄存器的向量指令构成。通常每一种向量操作都对应了三条SSE2指令，这三条指令分别可同时完成4个标准整型（INT－32位)的操作，8个短整型（Short－16位)的操作或16个字符类型（Char－8位)的操作。利用SIMD指令优化相关程序时，在满足计算精度的要求下，选择并行度高的指令能得到更好的优化效果。然而，一方面,由于很多已有的多媒体程序是为通用处理器编写的，在编写过程中由于短数据类型（短整型或字符类型）被定义为标准整型不会对性能造成影响，因此程序员不会深入分析操作数的有效位宽，而把一些短数据类型定义为标准整型；另一方面，做为多媒体程序的主要开发语言，C语言中IntegerPromotion规则规定所有短数据类型的整数必须被扩充到标准整型以保留运算过程中的数据溢出部分。这些编程习惯和高级语言的规则极大阻碍了针对SIMD架构优化过程中高并行度指令的选择。本文针对SIMD优化面临的并行度问题，提出了一种优化算法，该算法首先对应用程序的进行有效位分析，使优化过程中更多的采用并行度高的指令成为可能；然后在此分析的基基金项目：国家自然科学资金（60273046）与博士点基金（20050246020）资助，作者简介:张为华博士，主要研究领域体系结构与编译优化，Email:[e-mail]；朱嘉华博士，主要研究领域体系结构与编译优化；张宏江硕士，主要研究领域编译优化；臧斌宇教授，博士生导师，主要研究领域体系结构与编译优化。《计算机学报》2009年11期，2009，32（11）础上，提出了一种溢出控制算法，控制短数据类型操作过程中可能出现的溢出。实验数据表明，该算法可以有效提高SIMD优化过程中的并行度，对多媒体程序可以获得较好的加速效果。本文剩余部分组织如下：第二章将介绍与本文相关的基础知识以及问题分析。第三章介绍了有效位分析算法。第四章介绍了溢出控制算法。第五章，给出了实验结果及对实验结果的分析。第六章给出了相关工作。第七章对全文进行了总结。2问题分析2.1背景知识2.1.1SIMD架构目前，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.2IntegerPromotion规则在C语言规范C99中，对整数计算有如下要求：当一个较短的有符号或无符号整型运算中可能出现溢出时，计算应该被扩展到标准整型。也就是说，在较短的整型计算中，如果出现数据溢出，这些溢出部分将被保留下来并参加以后的运算。当使用普通标量指令实现这些运算时，操作数将自动被扩展到标准整型，运算也完全按标准整型来进行，因此这一规范得到严格的遵守。这一规则被称作IntegerPromotion,在下文中我们简称这个规则为IP规则。2.2问题分析由于SIMD指令集合提供一系列并行度各异的向量指令，因此利用SIMD指令优化相关程序时，在满足计算精度的要求下，选择并行度高的指令能得到更好的优化效果。然而一些传统的编程习惯和高级语言的规则却对高并行度指令的选择造成了很大的限制。一方面，由于传统的多媒体程序主要运行在通用处理器上，短数据类型被定义为长数据《计算机学报》2009年11期，2009，32（11）类型并不会对性能造成影响。因此，传统的多媒体程序员并不会深入分析各个操作数所需要的有效位宽，而是把不确定宽度的整型数据类型直接定义为标准整型，这种情况造成的直接后果是在一些多媒体程序的许多计算过程中，有一些中间结果的部分数据位并不参与之后的计算，或是部分数据位虽然参与后续的计算，但它们的取值不影响最终的计算结果。我们将这样的数据位称为无效位，而将其他数据位称作有效位。虽然这种情况不会影响这些应用程序在传统通用处理器上的执行效率，但是却给针对SIMD架构的编译优化造成了极大的障碍。另一方面，基于寄存器的SIMD构架将若干个字符类型或者短整型数据紧密排列在一起进行统一的运算，这种构架充分利用了寄存器的宽度，但是并没为IP规则预留足够的空间。按照IP规则，所有短数据类型数据都应该被扩展到标准整型进行计算，在计算完毕后再根据目标变量长度进行剪裁。在SIMD构架上进行这样的操作会引入大量的额外开销，扩展数据用的指令和裁剪数据用的指令都需要较多的CPU周期才能完成；如果数据是带符号的整数，还需要通过一系列操作来获取每一个操作数的符号位（0或者－1）。这些额外开销，往往会抵消SIMD优化带来的性能提高，甚至导致负的加速效果。对于标准模式，由于存在短类型基于IP规则到32位的扩展，因此只要在计算中不出现右移，是否严格遵循IP规则对计算结果不会造成任何影响。然而，当标准模式中出现右移或处于饱和模式时，高位数据将在计算中发挥作用，是否严格遵循IP规则将影响最终结果。如果严格遵循IP规则，短数据类型的右移操作实际上都是标准整型的右移操作。也就是说，对于字符类型的运算来说，运算过程中的第9到32位数据将影响到最终的计算结果，而对短整型运算第17到32位数据将影响到最终的计算结果。但是，由于这些数据属于计算的溢出部分，在标准模式下，这些数据都会被处理器自动去掉从而导致最终结果的错误。为此，如果在计算中出现右移操作，不得不引入整数扩展，并且忍受随之而来额外开销。而在IP规则下，参与饱和算术运算的不仅仅是低位的数据，也包括了高位的数据。而高位数据及运算的高位结果对饱和运算的最终结果也起到了决定性的作用，在进行饱和计算之前就把溢出部分处理掉，不管使用的是标准模式还是饱和模式都会导致最终计算结果的错误。因此，为了得到正确的计算结果，必须保留数据和运算结果的高位部分。然而，通过整数扩展来保留数据和运算结果的高位部分，往往会使得饱和算术指令的操作数位数大于计算结果以及饱和算术本身的位数，而目前的SIMD架构并不支持这样的饱和算术指令。也就是说，即使进行了整数扩展，仍然无法从饱和算术指令中获得应有的性能提高。因此，在SIMD优化过程中，必须首先识别代码中变量的有效位，并在此基础上通过溢出控制算法来确保降低额外的开销和保证程序的正确性。3、有效位分析算法在多媒体程序中，通常有两种途径来对操作数的位宽进行压缩：1.高位压缩：由于多媒体应用所处理的数据多为8位或16位整数，因此在计算过程中高位部分往往对最终计算结果没有影响。2.低位压缩：多媒体应用有一个显著的特点，即对计算精度的要求较低。这一特点在代码中常常表现为低位计算往往对最终结果没有影响。因此在编译时通过有效位分析计算过程中高位/低位的作用，压缩不影响最终计算结果的高位/低位以提高SIMD计算的并行度。为了达到这样的目的，可以将变量与计算中间结果的数据位划分成高端无效位，有效位和低端无效位三个部分。为了便于在分析过程中描述，我们用有效区间来描述变量或计算中间结果的有效数据部分。有效区间下限为有效位中的最低位，而区间的上限为有效位中的最高位。图1给出了代码1中各变量与计算中间结果的数据位划分：《计算机学报》2009年11期，2009，32（11）代码1：charfoo(chara,shortb){intc，d，e；S1c=a7;S2d=b&0x3fffS3e=(c+d)8;returne;}图1代码1中各变量数据位的分类有效位分析与传统位宽分析一样，均属于双向的数据流分析。但除了能够象传统位宽分析那样预测正确实现代码所必须的计算精度外，还必须提供变量以及计算中间结果的各个数据位可能的取值范围以及对计算结果的影响。因此，有效位分析需要编译器在中间代码分析过程中传播变量以及中间结果的有效区间，基于[6]中的位宽分析算法，有效位分析方法可以通过以下四个步骤完成：1.将代码中的复合表达式分解成为一系列一元/二元表达式，并引入临时变量来存储复合表达式计算的中间结果。根据C语言标准的要求，这些临时变量将被申明成为标准整型。2.在开始传播有效位区间之前，为变量、常数和常数数组设定有效位区间的初始值。变量的有效位区间初值可以根据变量申明的数据类型来进行设定，表1给出了不同数据类型的有效区间的初始值。常数的有效位区间可以通过常数数值获取。与变量和常数不同，常数数组在代码中以数组变量的形式出现，然而这一数组的每一个元素都是一个确定的常数。在有效位区间传播过程中，我们将这样的常数数组当作特殊的常数，其有效位区间的上界为所有元素有效位区间上界的最大值，而下界为所有元素有效位区间下界的最小值。数据类型有效位区间初值Char[0,7]Short[0,15]Int[0,31]表1数据类型与有效位区间初值对照表3.设定变量有效位区间初值后，前向遍历静态单赋值语法树，在每一个赋值节点上依照[6]中的正向传播规则传播变量的有效位区间。4.完成有效位区间的前向传播后，逆向遍历静态单赋值语法树。并在每一个赋值节点上依照[6]中的逆向传播规则传播变量的有效位区间。图2给出了代码1广义有效位区间在这段代码的静态单赋值语