基于數據級自動向量化的編譯優化研究綜述

賀婷

摘要： 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）]