自动SIMD向量化中基于混合并行的循环分段展开技术

自动SIMD向量化中基于混合并行的循环分段展开技术摘要：当前含有SIMD功能部件的计算机体系结构中，一般其向量部件与标量部件可并行工作，为了提高系统的硬件资源利用率，文章针对向量化循环，提出了基于混合并行的分段展开变换方法。

文章以处理器的硬件模型为基础，分析了开发混合并行的限制条件，设计了一种针对此模型的循环分段展开算法，可将原来完全向量化的循环，变换为向量与标量混合计算的循环。

通过此方法，可以提高系统的资源利用率，经对SPECCPU2000浮点测试表明，此向量化方法对一些向量化较好的例子，加速比有10%左右的提升。

关键词自动向量化，SIMD，混合并行，循环分段展开中图法分类号TP311文献标识码 ALoop section and unroll algorithm based on mix-parallel inSIMD Auto-VectorizationY ao Yuan Huang Lei Hou Y ong-sheng Wei Shuai( PLA Information Engineering University, Zhengzhou 450002, China) Abstract The current computer architecture with SIMD components, generally the vector components and scalar components can be parallel, in order to improve utilization of hardware resources, this article proposed a section and unroll mothord based on mix-parallel transformation for the loops which can vector. This article base on the processor hardware model, analysis of the development of hybrid parallel restrictions, designed to work for this model loop section and unroll algorithm, can be fully accountable to the quantification of the original loop is transformed into mixed vector and scalar computing loop. By this method, can improve system resource utilization, based on a floating-point test SPECCPU2000 show that this quantitative method to quantify some of the better examples, about 10% speedup improvement.. Keywords Auto-vectorization，SIMD，mix-parallel，Loop section and unroll1 背景介绍二十世纪末，家用电脑得到充分的发展，多媒体应用是家用电脑的主要用途之一。

而多媒体程序由于对大量数据采用相同的操作，因此适于进行向量化。

自从1996年Intel在奔腾处理器上集成了MMX后越来越多的通用处理器上集成了SIMD（Single Instruction Multiple Data，单指令多数据）扩展，很多的厂商在处理器中都集成了这一多媒体扩展应用。

如今数据的处理越来越庞大，如游戏机芯片、大规模并行处理机等，因此，SIMD技术不仅用在多媒体处理方面，而且用在各种有大量数据存取的应用中，为当前的海量数据存取以及高性能计算提供了一种有效方法。

使用SIMD技术的方法很多，其中的自动向量化技术是一个有效的方法，既能获得较好的性能也能为程序员节约较多的时间。

但是传统的自动向量化方法，只是尽量开发出程序的向量化能力，并没有考虑系统的硬件资源利用情况。

当前的SIMD计算机中，为了较高的性价比，体系结构中一般有标量功能部件和SIMD功能部件[1][2]，两种部件之间可以并行执行（类似于多指令多数据的执行结构MIMD）。

示意结构如下图所示：图1多部件指令执行示意结构本文提出采用混合并行的方法提高系统的硬件资源利用率，因此需要对程序进行一定的变换以开发程序的混合并行能力。

通过循环分段展开[3][4]技术改变循环内语句的执行方式，形成无依赖的向量语句与标量语句混合的循环，同时利用向量与标量部件，以提高系统的资源利用率。

一般SIMD功能部件和标量功能部件间的比例要根据处理机的用途来确定，理想的状况是能使这两类计算尽量在大多数应用中保持平衡，即向量计算用的时间和标量计算相等，这样才能最大限度的提高资源利用率。

但是，在实际应用中，向量代码与标量代码所占的比例不可能刚好满足硬件的要求。

即使比例相符合，但由于存在依赖和控制因素，向量代码和标量代码也不一定能同时在向量硬件和标量硬件上执行。

为了满足体系结构的这一特点，在自动向量化编译中提出了针对向量化循环语句的分段展开技术，通过分段展开变换后，使循环的每一次迭代中，一部分语句可以向量执行，另一部分语句同时可以标量执行，而要使这种混合的循环向量化需要用到超字并行[5]的向量化算法，本文对变换后的循环均使用此向量化算法，对此算法的研究较多，不再过多讨论。

利用循环变换开发SIMD向量化混合并行的研究相对较少，与体系结构关系较密切，Samuel Larsen提出了一种选择向量化的概念[6][7]，从指令的角度来出发的，将同一条语句的不同部分向量化，对比其效率，从而选择一种最有利的向量化方法，但此方法代价分析很困难，在自动向量化中实现也比较困难。

本文提出了基于混合并行的循环变换技术，较易实现，且在实际测试中取得了较好的效果。

2 开发混合并行的硬件计算模型模型假设：假设处理器体系结构中，包括一个SIMD功能扩展部件，两个标量执行单元，SIMD向量寄存器的宽度为128位，一次可以存取4个32位整型数据。

结构图如下：图 2 多功能部件计算模型结构假定向量操作是标量操作需要的机器周期数的2倍（实际情况可能不是这样的，不同的硬件结构间也会有差异，这里只是用一种简单的情况来说明），还假定不同的操作间机器周期数也是一样的（具体的情况要根据硬件结构来确定，只是一种简单的假设）。

先不考虑指令的发射及数据加载的时延，要想使部件运算平衡，需要向量化后的指令和标量指令的比例为：1/4，此模型中标量执行能力与向量执行能力相当，相同周期内标量部件与向量部件计算的数据量相同。

实际机器可能没有模型的这么简单，但向量部件与标量部件操作的机器周期数的比例一般来说是固定的，可以通过实验得到向量操作与标量操作平衡时的语句比例，在本章讨论的模型中执行一次向量操作，同时可以执行两次标量操作。

当标量部件与向量部件共同工作时，可以让向量部件的机器周期数掩盖标量部件的周期数，这也是将向量语句展开成标量语句的原因。

为了便于说明这个问题，机器硬件的功能如2中的模型假设一样，处理器中有两个标量部件，一个SIMD功能部件，执行一个SIMD指令需要的周期数是一个标量指令周期数的2倍。

先假设标量指令的机器周期为1，向量指令的机器周期为2，用下面的例子来说明这种语句展开的好处：: for(i=0;i<1024;i++)例1a[i]=c[i]+d[i];上例所示，若标量执行，需要的机器周期数为：1024个周期。

向量化后程序如下所示：2: for(i=0;i<256;i++)a[4*i:4*i+3]=c[4*i:4*i+3]+d[4*i:4*i+3];例向量化后的机器周期数为：256*2=512个周期，加速比为标量执行的2倍，若使用功能部件并行的方法，将循环中的向量循环分段展开为如下形式：3: for(i=0;i<128;i++){V 1: a[8*i:8*i+3]=c[8*i:8*i+3]+d[8*i:8*i+3];S1: a[8*i+4]=c[8*i+4]+d[8*i+4];S2: a[8*i+5]=c[8*i+5]+d[8*i+5];S3: 例a[8*i+6]=c[8*i+6]+d[8*i+6];S4: a[8*i+7]=c[8*i+7]+d[8*i+7];}上面的形式，V1可向量化执行，V1中使用的数据是4个连续的数据，且每次迭代语句首地址为8*i ，这种存储的数据符合向量化取数时地址对齐的要求（下节讨论），且语句V1、S1、S2、S3、S4之间均没有数据依赖性，这几条语句可并行执行。

执行到此循环时，向量部件执行V1，需2个周期，两个标量部件执行S1、S2需一个周期，S1、S2执行完后，向量部件还在执行V1，两个标量部件继续执行S3、S4，一个周期之后，三个执行部件均执行完毕，这样，循环的一次迭代就执行完了。

可用如下的图表来表示其执行过程：表 1功能部件并行的过程通过上面的分析可知，这种功能部件并行后，程序的执行周期数为：128*2 = 256，加速比为向量化之后的2倍。

原因就是，本模型中向量执行部件与标量执行部件的运算能力相同，并行操作，使向量的运算总量减少了一半3 利用循环分段展开开发混合并行的限制实际应用中，功能部件的并行限制条件很多，常规手工编写的代码一般是不会考虑到硬件的结构特点，并且还有控制依赖和数据依赖的限制，因此是不适合进行功能部件并行的。

向量化循环分段展开虽可以开发混合并行，但是对向量化的语句展开也不是完全没有限制的。

有时不正确的分段方法可能会导致向量化的语句地址不对齐，而混合的语句也不一定能在不同的功能部件上并行，具体情况还要看如何分段。

3.1 应用程序混合并行的限制循环变换针对的是应用程序，使应用程序更加符合目标机体系结构的特点。

下面就主要讨论一下应用程序中对并行操作的约束，约束条件是：(1)并行操作的语句要在同一个循环体内；(2)不存在语句间的控制依赖；(3)不存在语句间的数据依赖。

再对以上三条约束进行解释，首先，并行操作的语句要在同一个循环体内。

当前的商用编译器和科学研究编译器，由于要确保程序运行的正确，只保守的考虑循环体内部向量语句与标量语句的并行计算。

若语句在不同的循环体内，其语句间的相关性更加复杂，基础编译时，如果要判断这些语句间的关系，以确定其是否可并行操作的难度很大，从应用的角度来说，实现这种判断是非常困难的。