基于数据级自动向量化的编译优化研究综述

贺婷

摘要： SIMD扩展部件是一种在多媒体程序和科学计算程序中提供指令并行的加速部件。本文首先介绍SIMD扩展部件的背景及行业现状，然后从挖掘方法、指针别名这2个角度介绍了SIMD现阶段发展情况，在此基础上并对SIMD编译优化方向进行了展望。

关键词： SIMD； 自动向量化； 数据级并行

中图分类号： TP393

文献标志码：A

文章编号： 2095-2163（2016）06-0068-04

0引言

为了提高多媒体业务的整体集成性能，当代处理器均已陆续采用了基于SIMD的指令集扩展，意图在一个时钟周期上操作多个同构数据，并且该方法已在专用处理器和通用处理器中得到了高效使用，较早如Texas C62XX（Texas Instruments，1998）、Intel IA32（Intel 2000）、AMD K6（Advanced Micro Devices，1999）等等。SIMD是single instruction and multiple data 的简写，主要用于实现同时处理相同数学运算的同构操作数[1]。

上世纪，Intel率先在奔腾处理器中加入MMX[2]，旨在提高有关图形、影像和声音等应用的处理速度，同时，支持的指令也较为清晰简单。随后即有SSE、SSE2、SSE3、SSE4.1的相继面世，其中的SSE[3]是MMX的超集。具体来说，SSE能够提供更高分辨率的图像浏览，获取高精优质的音视频，在指标效果愈加改进的语音识别方面却只需占取更少的CPU资源，当然，在功能方面，完善了之前非对齐访问相关的应用设计，增加了跨幅、插入、寻找等操作。在此之后应运而生的AVX、AVX2与IMCI，涉及的编译技术则从基于基本块对程序进行分析转到基于循环的分析，尤其对逻辑关系更加复杂的多重循环展开了向量化并行度的深入讨论；更进一步地，应用场景也由图形图像处理延伸到高性能计算中。与此同时，除了Intel积极行动之外，还有许多厂商纷纷进入SIMD的研发天地，重点包括VIS（Sun SPARK）]、MAX（HP PA-RISC处理器）、BlueGene/L[4]（IBM）、MVI-2（DEC Alpha）[5]、国产的SW-蓝光，以及龙芯[6]、魂心一号[7]等。综上可知，处理器的体系结构一直都在向着更高层次的并行而始终处于可持续、不间断的发展创新中。

如今，SIMD插件不仅在多媒体加速方面获得了成功应用，还已延拓到数字信号处理、图形图像、游戏加速等多个领域[8]。当然就优化实力而言，现阶段SIMD扩展在天然的数据并行、重复的访存模式、重复性的操作局部数据，FFT（快速傅里叶变换）、编解码方面的效果较为明显。并且，在后续的发展实践中，人们发现同样可以使用SIMD来加速科学计算程序，如在对DNA序列进行比对、求根运算和矩阵运算、以及加解密算法等的研发处理中，SIMD早已渗透到方方面面[9]。而指针的别名分析、复杂的数据依賴和控制依赖、以及不规则的访问模式等等，却都阻碍着向量指令的有效挖掘[10]。

本文第一节对比传统向量机和SIDM扩展部件的体系结构说明SIMD的优势，通过列举手写汇编和自动向量化引出自动编译。第2、3节探讨分析了发掘方法、数据布局和部分优化算法。第4节论述了编译优化的未来发展趋势，第5节则给出了全文总结。

[BT4]1SIMD研发概述

[BT5]1.1体系结构的对比

并行处理计算机在结构方面主要为以下几种：流水线结构、多功能部件结构、阵列结构、多处理机结构和数据流结构[11]。其中，流水线结构将指令执行过程分为若干段，每段执行指令的一部分。当本段指令执行后而即将进入下一段时，下条指令就会流入本段。因此，流水线计算机在整个流水线上可以对若干指令来设定并行处理。SIMD就是在一个控制器下对多个处理单元来选择提供控制[12]，对一队列数据中的所有元素进行同类操作，以此实现空间并行，相对于SIMD只是一个通用处理器的插件而言，传统向量机的存储系统和互联结构都展开了专门的设计。

[BT5]1.2使用途径

SIMD挖掘可划分为2类：手写汇编和自动向量化。具体来说，手写汇编即手工向量化[13]，这就对程序员提出了重点要求，也就是需要具备丰富的实战经验。以及对体系结构和指令集的丰厚知识。但在大规模并行的条件下，指令间数据、控制依赖关系较为复杂，手写汇编工作量甚大，出错概率增加，因而生成的代码很难具备普适性[14]，且不同的处理器，向量化指令集在配置上也各有不同，相应地也未能呈现良好可移植性。而自动向量化则是从编译器角度出发，通过对程序的控制流、数据流进行分析，自主实现标量代码向量化的方法。在此过程中，程序员已无需考虑应用程序的具体细节，更遑论对程序的单独设计修改，工作量由此将大大减少。不仅如此，编译器还可以对程序生成各种优化处理，这一切均已使得编译器自动向量化正日渐成为SIMD程序向量化的主要工作方式。

[BT5]1.3相关研究

目前，SIMD的研究已引起了广泛关注，关注焦点即是围绕关键技术的研究，例如对于相应编译器的研发设计。如VAST编译器对AtilVec[15]扩展指令集代码的定制融合，支持SSE/SSE2的PGI Workstation Fortran/C/C++编译器、以及支持SSE/MMV/AVX的Intel icc[16]、IBM的xlc、gcc、神威蓝光、龙芯[17]等。

目前，历经十余年的发展演变，SIMD的优化效果仍有待改进与提升，主要可从如下方面斟酌入手：指针别名和挖掘向量化的方法。向量化的挖掘就是如何识别可并行指令，生成向量指令，一般从循环、基本块和函数级进行分析。

[BT4]2向量化的挖掘

一般而言，并行处理可分为5个等级和2个粒度，如图1所示。层次越高，粒度越大；层次越低，粒度越小。对于粒度，可将其分为粗粒度和细粒度，SIMD属于细粒度[18]。目前，SIMD涉及的典型向量化方法主要有：基于循环的传统向量化方法、SLP（superword level parallelism）及模式匹配等。

2.1循环级向量化

循环级向量化在设计上包括着如下步骤：控制流分析、循环预处理、依赖分析、循环变换、向量化代码生成。其中，控制流分析，用于建立中间表示层的控制流分析，在此基础上，通过控制流图识别循环。预处理，用于实现对循环信息的记录，删除冗余代码和外提循环不变代码与规范指针。依赖分析，分析循环中的数据依赖，并以此构造数据流图。循环变换和向量化代码生成实现标量代码到向量代码的替代。经由研究得知，循环变换技术可进一步解析为标量扩张、循环分布、循环合并、分段和展开以及剥离技术[19-21]。在此，各分项技术的功能阐释可概述如下。

1）标量扩张。是用编译器生成的临时数组T-temp替代循环中的标量，主要使用场景为循环中标量和数组混用[22]。标量依赖产生的原因是使用相同的存储空间存储临时单元，在此使用标量依赖可以消除依赖，进行向量化。

2）循环分布。循环分布基于语句，将一个循环分解为多个，分解后的循环与原循环拥有相同的迭代空间，是原循环语句的子集。通常，循环分布适用于如下方面：

①可向量化循环的分解。②将原循环分解为较小的循环，改善Cache与TCB局部性。③紧嵌套循环的创建。④为减小寄存器压力，将原循环分解为较少变量引用的循环的集合[23]。

循环分布依赖于语句间的依赖关系，以强联通子图对语句依赖关系图进行分解，在循环分布之先，一般需前置语句重排，强联通分量的查找等操作，语句重排可参照tarjian算法[24-25]。

3）循环合并。循环分布的逆过程是循环合并[26]，循环合并是将2个及其以上的循环合并为一个大的循环，以此减小组织循环并行的开销，并提高数据局部性。一般，循环合并技术都是在开发并行程序时设计引入的，用于增加程序并行粒度，从而降低额外的同步开销。

4）循环分段和展开。循环分段[19，21]将一个循环划分为不同的段，每个循环中包含了多个原循环的迭代，主要用于将迭代次数较多的一层循环改写为外层并行化和内层向量化的循环。SIMD向量化指令的生成过程同时也是一种隐式循环分段，段长为向量寄存器可以一次处理的数据的个数，同时也是SIMD部件可以一次执行的标量操作数个数。

5）循环交换。循环交换[20-21，27]将紧嵌套循环中2个循环的顺序进行交换，在程序变换中呈现出最高执行效率。主要可在以下方面对性能提供设计改进：

①将内外层无依赖循环和有依赖循环进行交换，使得内层循环可向量化。②将范围较大的循环交换至外层，增加向量长度。循环交换在本质上是一种迭代空间重排序的方式，其合法性与数据依赖关系有关。

[BT5]2.2基本块级

指令级并行中SLP应用广泛，可追溯至2000年由Larsen和Amarasingle[10]首创提出，其设计侧重于在一段代码空间展开并行性的挖掘，最终，仍旧为循环的向量化服务，主要思路是在基本块内寻找相邻的内存访问，并将其配对、打包；同时通过定义使用链（DU）/使用定义链（UD）进行包扩展；而后，组合同构操作[22]，实现向量化代码的生成。在具体过程中，按照一定的迭代次数对循环依序处理展开，将地址连续的数据打包，再用向量指令替代同构语句。对迭代内和迭代间SIMD数据向量化，可以将不同循环块中的语句融合到一個基本块中。SLP并行算法流程如图2所示。

综合前述分析可知，超字级并行的优点可做如下基本概述[9]：

1）超字级并行是对基本块进行操作，这既适用于迭代内并行性的挖掘，又对迭代间也实际有效。

2）SLP从内存连续的数据访问出发，提供了对迭代内连续内存数据访问的机会。

3）通过DU和UD完成包扩展，减少寄存器重组等操作。

同样，SLP也存在一定的不足，可具体表述为：首先，SLP实现基本块内语句的并行性是通过循环合并和基本块展开来设计得到的，盲目的循环合并和基本块的展开有时可能会带来比收益更多的性能损耗；其次，三地址化、数据流优化等变换也可能会加大优化难度。

[BT5]2.3模式匹配的向量化方法

模式匹配是面向程序特性的一种方法，按照某种特定的模式，使用语句生成树的模式匹配，同时得到典型操作的扩展指令，如许多程序中大量出现的饱和运算、max/min、计算平均值、乘加运算等。这些运算通常处于程序中的功能热点，在执行时间中占据较大比重，但对高级语言来说，大多数却都不能支持这些典型操作，SIMD扩展通常为此提供一些特殊指令的设计，一般而言，使用这些特殊的指令可以显著降低执行时间[22，28]。

通常情况下，因为受限于SIMD扩展体系结构，模式识别则仅是作为传统向量化方法和SLP的补充，而这2种方法在高校等研究机构中则更为常见及普遍。

[BT4]3对齐分析及优化

一般来说，SIMD扩展支持展示的数据访问都是在向量寄存器宽度对齐的情况下指定发生的，对于不同的SIMD扩展，内存访问的对齐方式要求也各不相同，同时，无论何种结构，非对齐数据的访问必然引入额外的开销。对齐分析时，需全面分析数据访存与向量寄存器宽度[29]，从属于流分析的一种，主要包括过程间对齐分析和别名分析。

为此，展开针对性的研究指出：别名分析来源于c语言中对指针和引用并未设定限制的选择开发。当多于2个存储表达式在同一程序点引用相同存储位置就是指针别名。指针引入了2个基本的问题。一是指针变量在使用过程中可以指向的内存单元不同，预先对某时刻访问的内存单元进行定位将具备一定难度；二是内存单元因为可被多个指针定制访问而形成的内存单元的别名。即指针操作的灵活性使得在运行时期对其指向位置的定位成为一个难题，但其结果往往是其他程序分析、变换的基础，指针别名的精度严重影响着许多应用的性能，包括：自动向量化、安全性分析、bug的检测、硬件合成、以及多线程分析。而且，经过梳理20年的发展历程，已陆续提出了一些技术主要围绕提高别名分析的精度而各显其独特优势，诸如：考虑控制流的流敏感分析[30-31]，参考聚类数据类型成员指向关系的域敏感分析[32-33]，以及上下文敏感分析[34-35]和路径敏感等多维度静态分析。但是对于动态指针别名分析，还较少见到完备研究。现在，对于指针的别名分析大多就是通过动态插桩和试运行来最终获得[36]，将插桩得到的别名信息反馈到向量化阶段指导向量化代码的生成。设计实现框架如图3所示，主要可分为预分析、插桩试运行和反馈阶段。具体地，在预分析阶段，使用静态指针分析与向量化识别的方法构建候选的别名分析集合，而在后续的插桩试运行阶段，将重点研究预分析中确定的候选别名分析集，分析运行时的指针地址、循环迭代次数、上下文和应用点的跨步的长度信息；以此为基础，再依据profiling信息对向量化进行测试，依据测试结果控制运行时版本。

4未来的挑战

1）现有的向量化算法大多都预设在一种没有控制依赖的理想实现条件下，但在实际使用中，许多的循环内部都存在着严重的控制依赖，虽然已有一部分研究正在关注着应该如何向量化存在控制流的循环，但在处理上却并未臻至有效和成功，如何完善循环中存在着控制流依赖将是自动向量化面临的重大挑战[37]。

2）向量化条件严格。只有在无对齐问题和数据依赖问题均不存在的情况下，循环才可进行向量化，并且对于非对齐和非连续的访存，或者将不能获取向量化，即使能转入向量化也需要使用专门的指令展开设计处理，这就将显著降低向量化的进程效率。对此，有些研究尝试在向量化之前即对收益求取价值评估，以此避免向量化之后可能造成的性能下降的不利后果[23，29]。

3）虽然，基于编译指导的SIMD编译优化技术实现了一部分的向量化功能，但与目前比较主流的OpenMP并行化编程语言在种类和功能上都存在较大的差距，所以，需要针对基于编译指导的SIMD编译增加有效知识体系拓展，进一步丰富、强化其功能[27]。

5结束语

本文首先对SIMD扩展部件的起源和行业背景进行了描述，对传统向量机和SIMD扩展部件的工作原理提出了分析论述，同时又对比了两者体系结构。进一步地，则给出了手写汇编与自动向量化两者间的优缺点对照解析。在此基础上，第2、3节即对现阶段部分优化算法展开了全面研究，自动向量化的本质是如何挖掘出尽可能多的指令，实现大规模的并行，本文主要围绕自动向量化的挖掘部分，粒度上从基本块级和循环级进行分析，技术上从指针别名进行分析，详细整合评析了SIMD现阶段发展的相关算法，并于论文最终指出了未来需要应对的前景挑战。

参考文献：

DIPED B E， BSC K R. SIMD programming manual for Linux and Windows[M]. London： Springer-Verlag， 2004：23-47.

[2] PELEG A， WEISER U. MMX technology extension to the Intel architecture[J] . IEEE Micro， 1996， 16（ 4） ： 42-50.

[3] Intel Corporation. IA -32 Intel architecture software developers manual[EB/OL].[2006-06]. http： / / developer.intel.com.

[4] BACHEGA L ， CHATTERJEE S， DOCKSER K/. et al. A high-performance SIMD floating point unit for BlueGene/L： Architecture， compilation and algorithm design[C]//Proc. of 13th International Conference on Parallel Achitecture and Compilation Techniques. Washington， DC， USA：IEEE， 2004：85-96.

[5] CARLSON D A， CASTENLINO R W， MUELLER R O. Multimedia extensions for a 550 MHZ RISC microprocessor[J]. IEEE Journal of Solid-State Circuits， 1997， 32（11）： 1618-1624.

[6] PENG Fei， GU Naijie. SIMD compiler optimization and analysis based on Godson-3B processor[J]. Journal of Chinese Computer Systems， 2012， 33（12）：2733-2737.

[7] XIN Naijun， CHEN Xuchan. Extending the vector instruction set for highperformance DSP Matrix based on GCC[J]. Computer Engineering & Science， 2012，34（1）：57-63.

[8] NUZMAN D， ROSEN I， ZAKS A. Auto-vectorization of interleaved data for SIMD[C]//Acm Sigplan Notices. Ottawa， Canada：ACM， 2006， 41（6）：132-143.

[9] 高偉. 面向SIMD的自动向量化优化技术研究[D]. 郑州：信息工程大学， 2013：1-5.

[10]高伟，赵荣彩，韩林，等. SIMD自动向量化编译优化概述[J]. 软件学报，2015，26（6）：1265-1284.

[11] 360百科. 并行处理计算机系统[EB/OL]. [2013-06-23]. http：//baike.so.com/doc/6554956-6768705.html.

[12]王迪. SIMD编译优化技术研究[D]. 杭州：浙江大学，2008：2-12.

[13] BROWN D， LEVINE J， MASON T. Lex &YACC[M]. 2nd ed. Sebastopol： O Reilly Media，1992.

[14]姚远. SIMD自动向量识别及代码调优技术研究[D]. 郑州：解放军信息工程大学，2012：2-11.

[15] DIEFENDORFF K， DUBEY P K， HOCHSPRUNG R， et al. Altivec extension to Power PC accelerates media processing[J]. IEEE Micro， 2000， 20（2）：85-95.

[16]朱嘉华. SIMD编译优化研究[D]. 上海：复旦大学，2005：16-17.

[17]彭飞，顾乃杰，高翔，等. 龙芯3B的SIMD编译优化及分析[J].小型微型计算机系统，2012，33（12）：2733-2737.

[18]郑维民，汤志忠. 计算机系统结构[M]. 北京：清华大学出版社，2001：330-334.

[19] KENNEDY K ALLEN J R. Optimizing compilers for modern architectures： A dependence-based approach[M]. San Francisco， California：Morgan Kaufmann Publishers， 2002.

[20]陈火旺，刘春林，谭庆平，等著. 程序设计语言编译原理 [M]. 3 版. 北京：国防工业出版社，2000：369.

[21]沈志宇，胡子昂，廖湘科，等著. 并行编译方法 [M]. 北京：国防工业出版社，2000.

[22]黄磊. 循环变换技术在自动向量化中的应用研究[D]. 郑州：解放军信息工程大学，2011：2-10.

[23]张媛媛. 自动向量化的收益评估技术研究[D]. 郑州：解放军信息工程大学，2011：2-25.

[24]陈文光，杨博，王紫瑶，等. 一个交互式的 Fortran77 并行化系统[J]. 软件学报，1999，10（12）：1259-1267.

[25] TARJIAN R E . Depth first search and liner graph algorithms [J]. SIAM Journal of Computing， 1972，1（2）：146-160.

[26] MAYDAN D E， HENNESSY J L， LAM M S. Efficient and exact data dependence analysis [C]// Pldi 91： Acm Sigplan Conference on Programming Language Design & Implementation. Toronto， Ontario， Canada： ACM， 1991： 1-14.

[27] ALLEN J R， KENNEDY K. Automatic loop interchange[C]// 20 Years of the ACM/SIGPLAN Conference on Programming Language Design and Implementation （1979-1999）： A Selection. San Diego， California， USA：ACM，2003：75-90.

[28]朱嘉风. 面向SIMD的编译指导与条件分支的编译优化技术[D]. 郑州：解放军信息工程大学，2011.

[29]吴圣宁 ， 李思昆. 多媒体处理器的 SIMD 代码生成 [J]. 计算机科学 ，2007，34（7）：268-270.

[30] Rei T. Expression Data Flow Gragh： Precise FlowSensitive Pointer Analysis for C Programs[D]. Edmonton： University of Alberta，2011.

[31] YU Hongtao， XUE Jingling， HUO wei， et al. Level by level ：Making flowand contextsensitive pointer analysis scalable for millions of lines of code[C]//Proceeding of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization（CGO10）. Toronto， Ontario， Canada：ACM，2010：218-229.

[32] PEARCE D J， KELLY P H J， HANKIN C. Efficient filedsensitive pointer analysis of C[J]. ACM Transactions on Programming Languages and Systems（TOPLAYS），2007，30（1）：106-148.

[33]YU Hongtao， ZHANG Zhaoqing. An aggressively filedsensitive unificationbased pointer analysis[J]. Chinese Journal of Computers，2009，32（9）：1722.

[34]YAN Dacong ，XU Guoqing， ROUNTEV A. Demanddriven contextsensitive alias analysis for Java[C]//Providings of the 2011 International Symposium on Software Testing And Analysis（ISSTA11）. Toronto， Ontario， Canada：ACM，2011：155-165.

[35] CHRIS L， LENHARTH A， ADVE V.Making contextsensitive pointsto analysis with heap cloning practical for the real world[J]. ACM SIG，2007，42（6）：278-289.

[36]劉鹏，赵荣彩，李鹏远. 一种面向向量化的动态指针别名分析框架[J]. 计算机科学，2015，42（3）：26-30.

[37]MAYDAN D E， AMARASINGHE S P，LAM M S. Arraydata flow analysis and its use in array privatization[C]//Proceedings of the 20th ACM SIGPLANSIGACT symposium on Principles of programming languages. Charleston， South Carolina， USA：ACM，1993，94C（8）：2-15.

[38]魏帅. 面向SIMD向量化算法级重组技术研究[D]. 郑州： 解放军信息工程大学，2012：176-177.[ZK）]

[FL）]