武汉大学学报(理学版) 2016, Vol. Issue (5): 456-463
0

文章信息

吕鹏伟 , 刘从新 , 沈绪榜 . 2016
LV Pengwei, LIU Congxin, SHEN Xubang . 2016
一种新型自动向量化编译算法
A New Algorithm for Auto-Vectorization Compilation
武汉大学学报(理学版), 2016, (5): 456-463
Journal of Wuhan University(Natural Science Edition), 2016, (5): 456-463
http://dx.doi.org/10.14188/j.1671-8836.2016.05.009

文章历史

收稿日期：2015-10-28
Abstract              PDF              Figures              Tables
引用本文
吕鹏伟, 刘从新, 沈绪榜 . 一种新型自动向量化编译算法[J]. 武汉大学学报(理学版),2016, (5): 456-463.
LV Pengwei , LIU Congxin , SHEN Xubang . A New Algorithm for Auto-Vectorization Compilation[J]. Journal of Wuhan University(Natural Science Edition), 2016, (5): 456-463.
一种新型自动向量化编译算法
吕鹏伟, 刘从新, 沈绪榜    
西安微电子技术研究所, 陕西 西安, 710065
收稿日期: 2015-10-28
基金项目: 核高基重大专项（2014ZX01020-003）；国家自然科学基金项目资助（61136002）；国家863计划资助项目（2015AA7015028）
第一作者: 吕鹏伟, 男, 博士生, 主要从事编译优化技术、并行编译技术研究. E-mail:lvpwxidian@126.com
通信作者：E-mail:shenxubang@163.net
摘要: SIMD(single instruction multiple data)体系结构在高性能计算与嵌入式多媒体计算中扮演着重要的角色, 对于SIMD指令的自动向量化编译技术是当前编译领域的研究热点.本文基于超字并行 (super-word level parallelism, SLP)算法提出了一种新的自动向量化算法GSLP(global super-word level parallelism), 该算法分为两部分:语句分组和语句调度.语句分组从全局出发分析超字复用信息, 在语句分组的过程中, 充分挖掘基本块的直接或者间接的超字复用信息, 提高基本块内语句并行操作的机会；语句调度对基本块内的所有语句进行调度并调整超字内部单字(Single-word)数据的组织顺序, 使生成的代码中打包/解包(pack/unpack)操作的数量降到最低.使用16个测试程序对GSLP算法进行测试, 试验结果表明该算法使打包/解包操作的数量平均减少了41.6%, 与SLP算法所产生的加速相比平均提高了4.7%.
关键词: SIMD指令     编译技术     自动向量化     超字并行     超字复用    
A New Algorithm for Auto-Vectorization Compilation
LV Pengwei, LIU Congxin, SHEN Xubang    
Xi’an Institute of Microelectronics Technology, Xi’an 710065, Shaanxi, China
Abstract: The SIMD (single instruction multiple data) architecture plays an important role in high performance and embedded multi-media computing. Auto-vectorization compilation for SIMD instruction is the current hot research topic in the field of compilation. This paper proposed a new auto-vectorization algorithm GLSP (global super-word level parallelism). Our algorithm mainly consists of two parts, statement grouping and statement scheduling. Statement grouping analyzes the reuse information of super-word from the global situation, makes full use of the opportunities on direct or indirect super-word reuse for basic blocks, and improves the opportunities on parallel operation of statements in a basic block. Statement scheduling reduces the number of packing and unpacking operation to minimum in generated code by scheduling all statements in a basic block and adjusts the organization order of single word in a super-word. A test including 16 test benches has been applied on GLSP algorithm. The experimental result showed that, compared with SLP algorithm, it has an average 41.6% reduction on pack/unpack operations, and an average 4.7% improvement on speed-up.
Key words: SIMD(single instruction multiple data) instruction     compiling technique     auto-vectorization     SLP(super-word level parallelism)     super-word reuse    
0 引言

SIMD(single instruction multiple data)技术最初主要应用在大规模超级计算机中，但是随着应用领域的不断发展，今天的微处理器大都提供了SIMD指令，著名的商用SIMD指令架构有Intel的MMX/SSE/AVX，AMD的3DNow!，ARM的NEON以及IBM的VMX/Altivec.尽管大多数处理器都支持SIMD指令，但是如何编写高效的代码来充分挖掘SIMD指令的潜能仍旧困扰着应用开发人员.目前最普遍的解决方案是在编译器的后端中构建针对特定目标机架构的intrinsic函数，但这需要编程人员熟悉特定的目标机架构.使用intrinsic函数编写的应用程序可移植性非常差，一旦更换目标机平台几乎所有应用程序都要重写.因此，业界迫切需要一种自动生成SIMD指令的技术，为此科研人员开始研究如何通过编译技术自动生成特定目标机的SIMD指令.在这种需求的推动下，出现了多种自动向量化编译技术[1~5].

过去十几年，主流的自动向量化编译技术主要有两种：一种是基于传统向量机的针对循环的向量化编译技术；另一种是基于基本块的SLP算法.由于SIMD架构与传统的向量机架构存在一些差异，所以传统的向量化编译技术在应用于SIMD架构的时候有着诸多限制，并不能完全适用于SIMD架构.因此，为了更好地解决SIMD架构的编译问题，Larsen和Amarasinghe[6]提出了一种新的数据并行方法，称为超字并行(SLP,super-word level parallelism).与之前的向量化编译方法不同的是，SLP不是从循环嵌套中挖掘数据并行,而是在基本块内寻找数据并行机会.该算法按照一定的向量化尺寸，寻找基本块内访存地址相邻的操作，将其配对并打包成超字变量，然后将该超字变量作为种子，再根据DU链(define-use)和UD 链(use-define)将更多的超字变量纳入到超字语句中，然后按照SIMD指令的要求组合同构操作从而生成SIMD代码.目前，很多编译器开发了基于SLP算法的自动向量化编译方法，例如Opne64，LLVM，GCC编译器[7~9]，同时也有很多关于自动向量化编译方法的研究是基于SLP算法的，例如Tenllado等人针对现代编译器提出的提高SLP算法性能的方法[10].Shin等人使用一种策略把向量寄存器作为编译器控制的缓存来提高数据的局部性[11]，另外他们基于SLP算法针对控制流进行指令预处理获得了更高的数据并行性[12].魏帅等人提出了一种基于SLP的方法对多层循环进行自动向量化编译[13]，并在Open64编译器上实现了该方法.尽管很多研究都是基于SLP算法的，但是基于SLP算法的向量化编译技术仍然面临一个问题：SLP对于单字(Single-word)操作数在内存中的存放位置有比较严格的要求，通常SLP会查找在内存中地址连续的单字操作数，将其组合成超字操作数并将其加载到向量寄存器供SIMD操作使用，在此过程中，如果超字所包含的单字数据在内存中的存放位置是不连续的或者是交叉存放的，就要使用向量寄存器数据重排序指令(reshuffling/permutation)[14~16].对向量寄存器中的这些数据按照要求进行重新排序，该过程被称为打包(pack)，该过程开销较大，类似的开销同样会发生在将超字解包(unpack)的过程中.之前的研究显示，某些时候打包/解包所带来的开销会将SLP算法所取得的性能提高抵消掉，因此尽可能地减少打包/解包操作所带来的开销显得尤为重要[17].如果要使用的超字已经存在于向量寄存器中，那么访问它的代价就会大大降低，因为不需要进行访存以及任何的数据重排序指令，所以要减少打包/解包操作开销的关键是要尽量挖掘向量寄存器中的超字复用机会.SLP算法使用局部启发式算法来获得超字复用，该算法的主要问题在于每一步所作的语句分组决定都是基于已经确定的分组以及DU/UD链，忽略了其余的语句.换句话说，该方法没有从全局的角度出发，不能充分利用基本块内潜在的超字复用机会.为了解决该问题我们提出了一种GSLP算法(global super-word level parallelism)，该算法在构建超字语句的时候从全局出发，在基本块中基于更大范围来进行语句分组以提高超字的复用机会，通过有效地挖掘超字复用来减少打包/解包操作.

1 编译框架

整个编译框架如图 1所示，使用C/C++，Fortran等语言编写的源程序经过编译器前端(LLVM-GCC前端或者Clang)的处理生成一系列使用LLVM的中间代码IR表示的基本块.IR以基本块为单位首先经过通用优化算法的预优化处理，包括通用的SSA优化、常量传播、死代码消除、循环不变量外提、消除冗余指令、循环变换等；然后进入GSLP优化器中使用本文提出的GSLP算法对基本块进行处理；最后进入后端代码生成器中生成汇编代码.GSLP优化中主要包括分组和调度两个阶段，主要达到两个目标：

图 1 基于LLVM的向量化编译框架 Figure 1 Auto vectorization framework based on LLVM
图选项

1) 通过合理的语句分组，挖掘超字语句分组，并在语句分组之间产生尽可能多的超字复用；

2) 通过合理的语句调度，充分利用超字复用以减少pack/unpack操作的数量，从而减少这些指令所产生的开销.

2 语句分组

本节主要描述如何对基本块内的语句进行分组，该算法首先使用基本分组算法来寻找数据宽度为2的分组，然后将已经发现的分组作为原子语句，并以迭代的方式应用基本分组算法对基本块进行处理获得更大数据宽度的分组，直到目标机的SIMD数据通路被充分利用.通过使用分组算法，编译器可以识别所有可能的语句分组并对这些语句分组所包含的超字复用带来的收益进行评估，以此决定最佳的分组方案.需要注意的是在分组阶段的超字复用指的是有多个超字数据内部所包含的单字数据是相同的，但此时并不关心超字内部的单字是按照什么顺序组织到一起的.一个合理的语句分组方案，必须满足下面4个约束条件：

1) 超字语句内部的单字语句之间不存在数据依赖.

2) 如果基本块中的单字语句之间存在依赖关系，那么在分组后他们所属的超字语句之间这种依赖关系依然存在.

3) 超字语句中所包含的单字语句是同构的，即每个单字语句在其相同位置上以相同顺序进行相同的操作.

4) 超字语句中包含的超字的数据宽度不能超过底层架构所支持的最大数据宽度.

2.1 基本分组算法

为描述方便，我们在图 2(a)所示的例子上描述基本分组算法，该基本块只包含5条单字语句，并行数据宽度设置为2.基本算法描述如下：

第一步，选取候选语句分组(candidate statement groups).根据前面所述的4个约束条件，将图 2(a)所示代码的候选语句分组为G={{S1，S2}，{S1，S3}，{S4，S5}}，即G={G1，G2，G3}，G1={S1，S2}，G2={S1，S3}，G3={S4，S5}.需要注意，如果两个不同的候选分组具有公共的单字语句或者两个分组之间有依赖环存在，即存在G1={Si，Sj}，G2={Sj，Sk}或者G1δG2和G2δG1同时存在，δ表示依赖关系，则可以认为他们是相互冲突的，任何情况下相互冲突的候选分组在最终确定的分组集合中是不能共存的，否则就会导致错误的执行结果.

第二步，根据候选语句分组构建超字变量冲突图(super-word variable conflicting graph)，简写为SVCG=(V，E)，图中的结点V表示超字变量，边E表示超字变量之间的冲突关系.超字变量指的是一个候选分组中处于同构语句的相同位置上的单字变量所组成的集合，如图 2中的候选组G1={S1，S2}对应的超字变量为：{V1，V2}-G1和{V3，V5}-G1.SVCG的构建描述如下：遍历所有的候选分组，为每一个分组Gi所产生的超字变量建立一个结点，如果新建结点对应的候选语句分组与图中已经存在的结点所对应的候选语句分组之间存在冲突那么就在这两个结点之间插入一条边，如图 2(b)是基于图 2(a)的候选语句分组构建的超字变量冲突图.

图 2 基本分组算法示例图 Figure 2 An example for grouping algorithm
图选项

第三步，基于第二步获得的候选语句分组和超字变量冲突图SVCG来建立加权语句分组图(weighted statement grouping graph)，WSGG =(V，E).结点V表示一个候选语句分组，边E表示两个候选语句分组之间有冲突.同时，WSGG图还是一个加权图，每一个结点的权值代表了该候选语句分组Gi所包含的超字变量的复用比例.为计算候选语句分组Gi的权值，查找SVCG(图 2(b)所示)中与Gi具有相同的超字变量并且对应的候选语句分组与Gi不冲突的结点，并以这些结点建立一个权值计算辅助图(auxiliary graph for weight calculating)，简称AG.例如要计算图 2(c)中G3的权值，找到图 2(b)中的结点{V1，V2}-G1，{V3，V5}-G1和{V1，V5}-G2，这三个结点与分组G3具有相同的超字变量并且不存在冲突，这三个结点建立的AG图如图 2(d)所示.AG图中的边表示这些超字语句在调度阶段不能同时使用，可以用一种简单的算法来消除这些冲突：在AG选择度最高的结点(即连接边最多的结点)并删除该结点以及所有与它连接的边，重复该过程直到AG中没有任何的边剩下，如图 2(e)所示.现在将AG中剩余的结点与SVCG中包含相同超字变量的结点进行匹配，并计算匹配的次数.对于G3来说，它所对应的3个超字变量，有2个可以与AG中的超字变量匹配，这说明3个超字变量中有2个可以被复用，所以结点G3的权值是2/3.然后使用相同的方法继续对分组G1和G2的权值进行计算，可以获得如图 2(c)所示的语句分组图.

第四步，基于第三步构建的加权语句分组图WSGG来确定最终的语句分组.具体方法是：将WSGG图中的所有结点按照其权值的大小进行降序排序，权值最高的结点将作为第一个被确定的语句分组，例如图 2(c)中的G1.如果出现权值相同的结点，那么就随机选择其中一个确定为语句分组.一旦确定了一个语句分组，就需要对WSGG和SVCG两个图进行更新，例如，在WSGG图中，删掉图 2(c)的结点G1以及所有与之相连的结点(如结点G2)，便可以得到图 2(f)；类似地在SVCG图中，要删除所有确定为语句分组的候选分组所对应的超字变量结点，以及与之相连的所有结点(即与之冲突的超字变量)，如将图 2(b)中G1对应的变量包结点{V1，V2}-G1，{V3，V5}-G1，以及与这两个结点相连的所有结点都删除，便可以得到图 2(g).如果WSGG不为空，在对SVCG和WSGG更新后回到第三步重新计算WSGG中剩余的结点所携带的权值，然后执行第四步，直到WSGG为空，最后可以确定全部的语句分组.

基于图 2中的例子，在确定分组G1之后，使用基本分组算法可以得到G3的权值为0，但是由于此时WSGG图中只剩下G3，所以G3被确定为第二个分组，最终可以得到的分组是{G1，G3}，此时基本块为B={G1，S3，G3}，G1和G3表示候选的超字语句，S3表示单字语句.

2.2 迭代分组算法

前一节描述的是基本分组算法，生成的SIMD指令的并行度为2.如果仅仅使用上述基本分组算法生成最终的语句分组，那么底层硬件支持的SIMD指令的最大数据宽度将无法被充分利用，为了解决该问题，在基本分组算法的基础上，使用迭代处理的方法获得并行度更大的超字语句，该算法就是迭代分组算法.基本思想是，在一遍语句分组结束之后，将每一个语句分组{Si，Sj}作为一个新的原子语句，并且每一个变量包作为一个新的原子变量，此时基本块内的程序语句已经发生了变化，即基本块既包含原始的单字语句，又包含刚刚经过基本分组算法确定的候选超字语句，同时基本块内的变量也随之发生变化，既有单字变量，又有超字变量；然后，再次使用基本分组算法对基本块进行处理并确定新语句分组.如果某些分组已经达到SIMD支持的最大数据宽度，那么将不再对这些分组进行处理.迭代地使用该策略直到最终生成的超字数据达到SIMD架构所支持的最大数据宽度并且所有的语句分组都被处理完毕.

迭代分组算法的伪代码如算法1所示，算法的输入是原始的基本块，输出的是经过分组算法处理之后确定的超字语句分组.第3行到第10行是构建SVCG图；第12行到第15行是构建WSGG图；第17行到第30行是确定最终的分组，而这中间的18行到26行是关键部分，该部分代码用来计算候选分组的权值.

算法1 迭代分组算法
输入：原始基本块内的语句序列S
输出：最终确定的超字语句集合D
1.识别候选语句分组集合G={G1，G2，……，Gn};
2.初始化超字变量冲突图SVCG；
3. for 语句分组集合G中的所有分组Gmdo
4. for Gm包含的超字变量{Vi，Vj} do
5. 在SVCG中添加结点{Vi，Vj}-Gm；
6. if SVCG中存在与{Vi，Vj}-Gm冲突的结点{Vq，Vr}-Gn
7. then 添加边〈{Vi，Vj}-Gm，{Vq，Vr}-Gn〉；
8. end for
9.end for
10.初始化加权语句分组图WSGG；
11.for 语句分组集合G中的所有分组Gm do
12. 在WSGG图中添加结点Gm；
13. if WSGG图中存在与Gm冲突的结点Gn，
14. then添加边〈Gm，Gn〉;
15.end for；
16.D←Φ；
17.while WSGG.V ≠ Φ do
18. for Gm∈WSGG.V do //下面开始构建AG图
19.初始化AG;//AG：辅助权值计算图
20.抽取与Gm不冲突的结点作为AG图中的结点；
21.如果AG中存在冲突的结点之间添加一条边;
22.消除AG图中存在的冲突;
23.计算Gm的复用次数Reuse;
24.计算Gm的权值Wm=Reuse/Nm;
25. WSGG.W←WSGG.W∪{Wm};//添加结点的权值
26. end for
27. 查找WSGG中权值最大的结点Gmax，D∪Gmax;
28. 更新SVCG和WSGG;
29. 初始化WSGG图中剩余结点的权值，WSGG.W←Φ;
30.end while
表选项
3 语句调度

语句分组算法虽然确定了基本块内的语句分组，但是此时基本块内的所有语句的执行顺序仍然没有确定，需要对指令进行调度.指令调度解决如下两个问题：

1) 获得基本块内所有语句(包含单字语句和超字语句)的一个最佳执行顺序；

2) 调整超字语句内部单字语句的顺序.

详细的语句调度算法描述如下：

第一步，基于基本块内的所有语句(包括超字语句和单字语句)构建一个数据依赖图DDG(data dependence graph).在该图中，每一个结点表示一个语句，结点之间的边表示结点之间的数据依赖关系.如果存在超字语句依赖于数个单字语句的情况，那么就需要在DDG中添加一个pack结点表示数据打包指令；如果存在单字语句依赖于超字语句的情况，那么就需要在DDG中添加一个unpack结点表示数据解包指令.如图 3所示，假设图 2(a)中的V3，V5，V7的值已知，那么可以构建基于{G1，S3，G3}的数据依赖图，由于G3={S4，S5}，它们分别依赖于G1的运算结果中的V1，以及S3的运算结果V5，所以需要增加pack和unpack结点.

图 3 {G1，S3，G3}的数据依赖图 Figure 3 DDG of {G1，S3，G3}
图选项

第二步，从DDG中选择已就绪的(数据依赖关系已消除的，如图 3中的G1和S3)语句加入到候选执行队列中.执行队列中的单字语句由于互相没有依赖性，所以单字语句之间的执行顺序不需要调整，而超字语句执行的先后顺序会影响超字复用，所以当执行队列中包含多条超字语句的时候，就需要对超字之间的执行顺序进行处理并对超字语句内部的单字语句进行排序.定义一个Live Super-word 集合(简称LS集合)来模拟处理器运行时向量寄存器的状态，集合中的元素就是当前存在于向量寄存器中的超字变量.在确定超字语句的调度方案的过程中，需要计算每条超字语句中处于向量寄存器中的超字的数目，称之为“可复用的超字数目”，使用N表示.需要注意的是：在计算N的过程中，仍然只关注可复用的超字之间是否包含了相同的单字变量，而不关注超字内部单字之间的顺序.我们假设初始状态下LS为空集合，这是因为程序在刚开始执行的时候，超字语句中的没有任何超字可以在向量寄存器中被复用，所以计算得出的每一个超字语句对应的N也为零，此时各个超字语句之间可以是任意的执行顺序，而后随着不断有超字语句被调度就会不断地产生新的超字并插入LS集合中.具体的调度方法描述如下：

第一步，计算候选执行队列中每一个超字语句对应的N，按照N的大小对超字语句进行降序排序，将N最大的超字语句放在本次被调度的超字语句队列的最前面，如果存在N相同的超字语句，就任选其中一个超字语句作为最先被调度的超字语句.对已经被调度的超字语句做标记，下次调度的时候将不会再对其进行调度.

第二步，对刚被调度的超字语句内部的单字语句进行排序确定一个最佳的组织顺序(产生的向量寄存器数据重排序指令的数目最少的顺序).如果排序过程会产生新的超字，那么将新的超字插入到LS中，并移除LS中与新超字包含相同单字数据但组织顺序不同的超字.

第三步，判断依赖图是否为空，若非空则返回第二步继续执行直到依赖图中所有的结点都被处理.

调度算法的伪代码如算法2所示，第1行表示构建数据依赖图DDG，该算法的输入是语句分组确定的基本块，输出的是经过调度算法处理基本块.第6到第19行是调度算法的关键，第7到第9行计算每个超字语句的可复用超字数目；第10行选出可复用次数最大的超字语句；第11行调整候选执行队列q中超字语句之间顺序；第12行确定超字语句内部的单字语句的顺序，并选出最佳组织顺序.

算法2 语句调度算法
输入：经过分组阶段处理的基本块B
输出：经过调度阶段处理的基本块B′
1.基于基本块B构建数据依赖图DDG并初始化Q=Φ;
2. for DDG图中所有的结点 do
3. 选择就绪状态的结点加入到候选执行队列q中;
4. 从候选队列中选择超字语句加入到RS中;
5. 初始化LS集合;
6. while RS≠Φ；
7. for RS中的所有超字语句S do
8.计算S中包含的超字变量存在于LS中的数目N;
9. end for
10. 选择最大的Nmax所对应的超字语句Smax;
11. 将Smax调度为q中最先执行的超字语句;
12. 确定Smax内部的单字语句的顺序，选出最佳排序;
13. if 排序后产生了新的超字Wnew then
14.LS←LS∪{Wnew};
15.if 存在Wold与Wnew包含相同的单字变量 then
16. LS←LS-{Wold};
17.end if
18. end if
19. end while
20. Q←Q∪q;
21. 更新DDG;
22. 更新RS;
23.end for
24.输出最终的执行队列Q;
表选项
4 实验结果及分析

实验平台为Intel酷睿i5处理器，内存4GB，支持SSE/SSE2/SSE4指令集，使用32位Debian7.8操作系统.处理器的向量寄存器宽度为128bit，可以同时处理2个64bit，4个32bit，8个16bit或者16个8bit的数据.我们基于开源编译器LLVM实现了本文所描述的GSLP算法，并使用了16个测试程序对其进行了评估，其中10个测试程序分别来源于SPEC2006中的浮点测试程序，另外6个来源于NAS测试程序.

根据前几节的描述，我们知道在使用SLP算法进行自动向量化编译的时候，由于其在利用超字复用信息方面的局限性导致在生成超字语句的过程中并没有考虑到生成的pack/unpack类操作对程序性能的影响，尤其是在超字第一次出现的时候必须依靠pack操作将其打包并加载到向量寄存器中，在此过程中如果超字所包含的单字在内存中的地址不连续或者超字内的单字之间的顺序需要调整，就需要使用数据重排序指令进行处理，这时打包过程的开销就会很高.与此类似，在SIMD指令运算结束之后，如果超字内包含的单字又作为数据被单字操作使用，这时候又需要使用unpack指令将超字解包，如果不能有效的利用超字复用，那么生成的代码中将有大量的操作是为pack/unpack过程服务的，这会严重影响程序性能.

第一组实验结果是相对于原始的测试程序，分别使用GSLP算法和SLP算法的时候在程序执行效率方面的提高，主要测试标准是程序执行时间的减少，反映了程序执行的加速效果. 编译器未使用任何自动向量化编译优化仅开启O3优化选项时，程序的执行时间为TO.在开启O3的基础上仅开启SLP优化时的执行时间为TSLP，而在开启O3的基础上仅开启SLP优化时的执行时间为TSLP，那么二者相对于只开启O3优化选项时，产生的性能提升百分比分别为：SSLP=(TO-TSLP)/TO和SSLP=(TO-TGSLP)/TO，如图 4所示，坐标横轴是测试程序的名字，按照使用GSLP算法所带来执行效率提升的升序排列.使用GSLP算法与SLP算法相比，在加速比上平均提高了4.7%.可以发现，针对个别测试程序，GSLP算法和SLP算法取得的加速效果很接近，例如ft，soplex和gromacs.而对于另一些应用GSLP取得的加速效果要明显好于SLP算法，例如lbm，milc，calculix，wrf，namd，mg和cg.这是因为针对与ft，soplex和gromacs等程序所包含的单字操作所对应的数据之间包含很多内存地址非连续的数据，即便使用GSLP算法也不易挖掘超字复用信息，依然会产生大量的pack/unpack操作.

第二组实验结果给出的是GSLP算法对pack/unpack操作的影响. SLP算法产生的packing/unpacking操作的数量为ISLP，GSLP算法产生的packing/unpacking指令的数量为IGSLP，那么GSLP算法相对于SLP算法产生的packing/unpacking操作数量的减少百分比为：R=(ISLP-IGSLP)/ ISLP，图 5给出的是使用GSLP算法时相比使用SLP算法时，产生的pack/unpack操作在数量上的减少.可以看到，对于大部分测试程序来说GSLP算法的效果是很明显的，pack/unpack操作的使用数量有着明显的降低，与SLP算法相比，平均减少了41.6%，但对于某些程序却不明显，这是因为这些程序中的超字复用信息即使在使用GSLP算法的时候仍然不容易被挖掘出来.观察图 4和图 5可以发现，图 5中pack/unpack操作数量减少不明显的测试程序在图 4中GSLP相比SLP所取得的性能提升也不明显，例如图 5中soplex，sp，gromacs他们的pack/unpack操作的数量几乎没有减少，而在图 4中的对应的相对于SLP算法的性能提升也微乎其微，这充分说明了pack/unpack操作对于程序自动向量化性能的影响.

图 4 GSLP和SLP算法分别对于程序性能的提高 Figure 4 Two algorithms for the improvement of the performance of the program
图选项
图 5 使用GSLP时packing/unpacking操作的减少 Figure 5 The reduce of packing/unpacking operation when using GSLP algorithm
图选项

所以在使用自动向量化编译的时候，尽可能的减少pack/unpack的生成会提高程序性能.而GSLP算法的根本出发点就是在整个基本块内部以一种全局的视角来挖掘基本块内部的所有直接的或者间接的超字复用，尽管仍然会产生pack/unpack操作，但是GSLP算法可以将pack/unpack操作的开销降到最低.

5 结论

本文针对SLP算法的不足，提出了GSLP算法来挖掘基本块内的数据并行，该算法从全局的视角出发，在语句分组阶段充分挖掘超字变量的复用信息，然后以此来评估分组收益，根据分组收益对基本块内的单字语句进行分组形成候选的超字语句；在语句调度阶段充分利用超字变量的复用信息对基本块内的语句进行调度减少pack/unpack操作的开销.最后基于测试程序对GSLP算法进行测试，结果表明该方法可以解决SLP的不足，并且与SLP算法所产生的加速比相比有着明显的提高.

参考文献
[1] FRANCHETTI F, KRAL S, LORENZ J, et al. Efficient utilization of SIMD extensions[J]. Proceedings of the IEEE , 2005, 93 (2) : 409–425 DOI:10.1109/JPROC.2004.840491
[2] WU P, EICHENBERGERA E, WANG A. Efficient SIMD code generation for runtime alignment and length conversion[C]//CGO’05 Proceedings of the International Symposium on Code Generation and Optimization. Washington: IEEE Computer Society, 2005: 153-164.
[3] NUZMAN D, DYSHEL S, ROHOU E, et al. Vapor SIMD: Auto-vectorize once, run everywhere[C]//CGO'11 Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization. Washington D C: IEEE Computer Society, 2011: 151-160.
[4] PHARR M, MARK W R. ISPC: A SPMD compiler for high performance CPU programming[DB/OL].[2015-11-12]. http://pl887.pairlitesite.com/papers/ispc/ispc_inpar_2012.pdf.
[5] KONG M, VERAS R, STOCK K, et al. When polyhedral transformations meet SIMD code generation[C]//PLDI’13Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM, 2013:127-138.
[6] LARSEN S, AMARASINGHE S. Exploiting superword level parallelism with multimedia instruction sets[C]//PLDI’00 Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation. New York: ACM, 2000: 145-156.
[7] NUZMAN D. Multi-platform Auto-vectorization[C]// CGO’06 Proceedings of the International Symposium on Code Generation and Optimization.Washington D C: IEEE Computer Society, 2006:281-294.
[8] NUZMAN D, ZAKS A. Autovectorization in GCC----Two Years Later[DB/OL].[2015-11-12]. https://www.researchgate.net/publication/255608628_Autovectorization_in_GCC-two_years_later.
[9] ROSEN I, NUZMAN D, ZAKS A. Loop-Aware SLP in GCC[DB/OL].[2015-11-12]. https://ols.fedoraproject.org/GCC/Reprints-2007/rosen-reprint.pdf.
[10] TENLLADO C, PIUEL L, PRIETO M. Improving superword level parallelism support in modern compilers[C]// CODES+ISSS’05 Proceedings of the 3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System synthesis.New York: ACM, 2005: 303-308.
[11] SHIN J, CHAME J, HALL M. Compiler-controlled caching in superword register files for multimedia extension architectures [C]//PACT’02 Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques. Washington D C: IEEE Computer Society, 2002:45-55.
[12] SHIN J, HALL M, CHAME J.Super-word level parallelism in the presence of control flow[C]//CGO’05 Proceedings of the Iinternational Symposium on Code Generation and Optimization. Washington D C: IEEE Computer Society, 2005: 165-175.
[13] 魏帅, 赵荣彩, 姚远. 面向 SLP 的多重循环向量化[J]. 软件学报 , 2012, 23 (7) : 1717–1728 DOI:10.3724/SP.J.1001.2012.04106 WEI S, ZHAO R C, YAO Y. Loop-nest auto-vectorization based on SLP[J]. Journal of Software , 2012, 23 (7) : 1717–1728
[14] REN G, WU P, PADUA D. Optimizing data permutation for SIMD devices[C]//PLDI’06 Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM,2006:118-131.
[15] NUZMAN D, ROSEN I, ZAKS A. Auto-vectorization of interleaved data for SIMD[C]//PLDI’06 Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and implementation. New York: ACM , 2006:132-143.
[16] 高伟, 赵荣彩, 韩林, 等. SIMD自动向量化编译优化概述[J]. 软件学报 , 2015, 26 (6) : 1265–1284 GAO W, ZHAO R C, HAN L, et al. Research on SIMD auto-vectorization compiling optimization[J]. Journal of Software , 2015, 26 (6) : 1265–1284
[17] 徐金龙, 赵荣彩, 韩林. 分段约束的超字并行向量化发掘路径优化算法[J]. 计算机应用 , 2015, 35 (4) : 950–955 XU J L, ZHAO R C, HAN L. Vector exploring path optimization algorithm of superword level parallelism with subsection constraints[J]. Journal of Computer Applications , 2015, 35 (4) : 950–955