王建花，陳朝暉

(北京控制工程研究所，北京100190)

基于動態(tài)分析的多面體模型非仿射擴展方法*

王建花，陳朝暉

(北京控制工程研究所，北京100190)

多面體模型只能表示循環(huán)中訪存數(shù)組下標可以用仿射表達式表示的循環(huán)，針對這個限制設(shè)計一種基于動態(tài)分析的方法對多面體模型的表示范圍進行擴展.該方法利用程序運行時的動態(tài)信息，將循環(huán)非仿射表達式中的循環(huán)全局參數(shù)用定值替換，推測生成非仿射循環(huán)的參數(shù)定值化版本，使之可以被多面體模型表示.該方法擴展了多面體模型的表示范圍，使更多的代碼區(qū)域可以被并行優(yōu)化，提高了程序中SCoP的覆蓋率，提高了程序運行的加速比.實驗證明了該方法的有效性.

并行編譯;多面體模型;SCoP;仿射;動態(tài)分析

0 引 言

多面體模型優(yōu)化方法是一種針對嵌套循環(huán)進行并行優(yōu)化的編譯技術(shù).多面體模型將程序中的循環(huán)映射到數(shù)學(xué)上的多面體模型中，利用已經(jīng)非常完備和正確的多面體理論做各種形式的變換，再將其重新映射回程序中的循環(huán).它幾乎覆蓋了所有傳統(tǒng)循環(huán)變換方法，并進一步完成一系列比較復(fù)雜的循環(huán)體優(yōu)化，給出綜合性的代碼優(yōu)化、并行化方案［1］.

程序中可以被多面體模型表示的代碼區(qū)域稱為靜態(tài)控制體(static control part，SCoP)［2］，多面體模型從程序的控制流圖中提取出SCoP，為它構(gòu)建多面體模型表示，并在多面體模型上進行相應(yīng)的轉(zhuǎn)換.然而，一些代碼區(qū)域由于不能滿足SCoP的限制條件，從而無法被多面體模型表示優(yōu)化.其中一個主要的限制條件是SCoP要求循環(huán)界限和訪存數(shù)組下標必須可以用仿射表達式表示.靜態(tài)分析時，程序中存在一些無法判斷的代碼情況，為了保證優(yōu)化的正確性，靜態(tài)優(yōu)化技術(shù)對其保守估計［3］，不對其表示和優(yōu)化，大大降低了可優(yōu)化代碼(SCoP)的覆蓋率.

對多面體模型表示的進行了擴展非仿射限制，大致可以分為3類:第一類是對非仿射表達式分析，為其提供常規(guī)的表示，進而對其優(yōu)化處理;第二類是將新的代數(shù)方法應(yīng)用于多面體模型，使多面體模型可以表示非仿射表達式;第三類是使用動態(tài)分析技術(shù)，將在運行時間檢測到的動態(tài)信息應(yīng)用于對非仿射表達式的并行化優(yōu)化.

文獻［3］使用第一類方法擴大了多面體的表示范圍，為每個非仿射的條件語句提供一個控制預(yù)判句.然而這個方法引入了條件變量對控制預(yù)判語句的依賴關(guān)系，降低了依賴分析的準確性.文獻［4］和［5］使用量詞消除方法處理代碼轉(zhuǎn)換過程和代碼生成過程中的乘法參數(shù).然而，該方法需要復(fù)雜的建模和轉(zhuǎn)換階段，可能使程序性能降低.Baghdal等［6］揭示了推測優(yōu)化技術(shù)的巨大潛力，Jimborean等［7-8］將推測并行技術(shù)應(yīng)用到多面體模型上.編譯時間時假設(shè)循環(huán)界和數(shù)組下標是仿射的，生成程序靜態(tài)并行化版本框架.運行時間時，若假設(shè)成立，則利用動態(tài)信息實例化靜態(tài)并行版本，反之則回退執(zhí)行原始的順序版本.然而，該方法在多面體轉(zhuǎn)換過程中不能改變程序語句的順序，也不能改變循環(huán)的結(jié)構(gòu)，大大限制了多面體的并行轉(zhuǎn)換方式.文獻［9］將檢查/執(zhí)行策略應(yīng)用到多面體模型中，提出了一個循環(huán)轉(zhuǎn)換架構(gòu).這個架構(gòu)使用無解釋函數(shù)(uninterpreted function)表示數(shù)組下標，結(jié)合程序運行時的具體數(shù)值建立函數(shù)映射關(guān)系.然而該方法僅能對只讀的非仿射數(shù)組下標處理.

一個嵌套循環(huán)中值不被改變的量叫做循環(huán)的全局參數(shù)，一些循環(huán)的全局參數(shù)使下標表達式和循環(huán)界只能被非仿射表達式表示.本文設(shè)計一種基于動態(tài)分析的多面體模型擴展方法，獲取程序運行時間時的動態(tài)信息，得到導(dǎo)致表達式非仿射的循環(huán)的全局參數(shù)的具體數(shù)值，用定值替代對應(yīng)的參數(shù)，生成循環(huán)的全局參數(shù)定值化的循環(huán)版本，這個循環(huán)版本消除了由循環(huán)的全局參數(shù)引起的非仿射表達式，因而可以形成有效的SCoP.相較于其他的多面體模型非仿射擴展方法，本文的方法識別循環(huán)中值不變的全局參數(shù)，適用于值特定的循環(huán).

1 研究背景

1.1 SCoP

SCoP的特點是函數(shù)體中最大的連續(xù)語句集，是步長為常數(shù)、循環(huán)邊界和訪存數(shù)組下標可以用仿射表達式表示的循環(huán)嵌套序列.SCoP中不包含帶有副作用的函數(shù)調(diào)用［3］，即只允許純函數(shù)和常量函數(shù)的調(diào)用.程序中一個典型的SCoP如圖1所示.

圖1 SCoP的一個實例Fig.1 A case of SCoP

1.2 仿射表達式

仿射表達式:Ax+Bn.其中，x表示循環(huán)的迭代向量，x=(i1，i2，…，in)T，A，B表示整數(shù)向量，A= (x1，x2，…，xn)，B=(xn+1，xn+2，…，xn+k+1)，n表示循環(huán)的全局參數(shù)向量，n=(n1，n2，…，nk，1)T.例如:對于循環(huán)loops(i，j)和參數(shù)(m，n)，所有仿射表達式的形式如下:

式中，x1，…，x5是整數(shù)，形如i*n或者n*m的表達式不允許出現(xiàn).

2 非仿射的動態(tài)擴展方法

2.1 動態(tài)優(yōu)化

動態(tài)優(yōu)化是指分析優(yōu)化工作要結(jié)合程序運行時間時的動態(tài)信息進行或者是在程序的運行時間內(nèi)進行分析優(yōu)化.在編譯時間時，程序中存在一些無法判斷是否違反SCoP限制條件的代碼區(qū)域，為了保證優(yōu)化的正確性，靜態(tài)優(yōu)化技術(shù)對其保守估計，不對其進行優(yōu)化，因此大大降低了可優(yōu)化代碼的覆蓋率［3］.在運行時間時，可以獲取到程序更多、更準確的信息，因此能對當前區(qū)域是否滿足SCoP條件做出更準確的判斷.很多編譯時間時無法判斷的代碼情況在程序運行中是滿足SCoP的限制條件的.因此，在運行時間時檢測并記錄代碼信息，在編譯時間時將這些動態(tài)信息用于對非仿射的循環(huán)界、訪存數(shù)組下標等代碼的并行優(yōu)化，可以使更多的循環(huán)體被優(yōu)化.

GCC(GNU compiler collection)實現(xiàn)動態(tài)優(yōu)化的方式是在程序第一次運行的編譯時間時進行程序插樁，運行時間時插樁程序執(zhí)行，記錄程序運行時的動態(tài)信息并反饋給編譯器，這些記錄的動態(tài)信息被稱為profile信息.在對程序進行再次編譯時，利用收集的動態(tài)profile信息，對程序優(yōu)化，生成優(yōu)化后的可執(zhí)行文件.記錄profile信息并利用該信息進行優(yōu)化的過程被稱為profile優(yōu)化過程.

GCC中的value profile優(yōu)化方法在程序運行時記錄變量的值，并統(tǒng)計它每個值的出現(xiàn)次數(shù)，如果一個值出現(xiàn)的次數(shù)在總次數(shù)的一半以上，那么就判定該值可以進行value profile優(yōu)化，例如將除法運算的除數(shù)替換成為一個定值.總得來說，value profile優(yōu)化基于某個出現(xiàn)概率大的定值增加了一條執(zhí)行得更快的路徑，代價是增大了代碼規(guī)模.

本文設(shè)計的多面體模型表示范圍的擴展方法，是基于GCC中的value profile動態(tài)優(yōu)化框架完成的.

2.2 非仿射問題

許多程序的代碼存在如圖2所示的情況，循環(huán)中的循環(huán)界或者訪存數(shù)組下標存在由循環(huán)的全局參數(shù)引起的非仿射項，使得循環(huán)界或者數(shù)組下標只能用非仿射表達式表示.例如，C語言不能定義維度大小未知的多維數(shù)組，因此經(jīng)常會使用一維數(shù)組來代替多維數(shù)組，通過下標的映射公式實現(xiàn)一維數(shù)組到多維數(shù)組的映射.然而，這種方式產(chǎn)生了非仿射的數(shù)組下標.如圖2，在編譯時間時靜態(tài)分析，j*N+i被識別為非仿射表達式，因此該循環(huán)不能被多面體模型表示，該代碼區(qū)域無法被并行優(yōu)化.而在實際的執(zhí)行過程中，循環(huán)的全局參數(shù)N往往是一個給定的常數(shù)，這樣的話j*N+i就可以被轉(zhuǎn)換成可以被多面體模型表示的仿射表達式.

圖2 非仿射的數(shù)組下標Fig.2 Non-affine array index

2.3 方法設(shè)計

本文設(shè)計一種方法，基于GCC的value profile動態(tài)優(yōu)化框架，結(jié)合在運行時間時循環(huán)全局參數(shù)的值的信息對多面體模型的表示范圍進行非仿射擴展.如圖3所示，本文設(shè)計的動態(tài)非仿射擴展方法主要分為7個步驟來執(zhí)行.1)代碼分析;程序第一次運行時，在編譯時間時分析程序，尋找引起非仿射表達式的循環(huán)的全局參數(shù)，準備記錄該變量的profile信息.2)代碼插樁;在編譯時間時插入代碼以在程序運行時間時收集變量的值和出現(xiàn)次數(shù)等profile信息.3)收集profile信息;程序第一次運行的運行時間時，記錄變量的profile信息.4)分析N值的信息;程序第二次運行時，在編譯時間時對變量的profile信息分析，判斷該循環(huán)全局參數(shù)的值是否在大多數(shù)執(zhí)行情況中是定值.5)生成參數(shù)定值化的循環(huán)版本;經(jīng)過步驟(4)的分析，如果變量在大多數(shù)情況時取同一定值，則用該定值替換變量，生成對應(yīng)該值的參數(shù)定值化的循環(huán)版本，在這個循環(huán)版本中，由該循環(huán)全局參數(shù)引起的非仿射情況被去除.6)多面體模型并行優(yōu)化;GCC編譯器中的多面體模型框架識別優(yōu)化代碼區(qū)域的SCoP，并對SCoP進行并行優(yōu)化.由于參數(shù)定值化的循環(huán)版本去除了原循環(huán)中的非仿射表達式，若該循環(huán)同時滿足SCoP的其他限制條件，則此循環(huán)版本可被多面體模型表示優(yōu)化.7)運行優(yōu)化程序;經(jīng)過優(yōu)化的程序在運行時，即時判斷正在運行的函數(shù)中循環(huán)的全局參數(shù)的值是否與編譯生成的參數(shù)定值化的循環(huán)版本匹配，若匹配，則運行優(yōu)化(并行)版本;若不匹配，則運行原串行版本.

圖3 非仿射擴展的執(zhí)行流程Fig.3 Implementation of the non-affine extensions

本文主要實現(xiàn)第(1)和第(5)步驟，其他幾個步驟在value profile框架中已經(jīng)實現(xiàn).步驟(1)是對程序進行分析，尋找程序中需要進行value profile的變量，步驟(5)就是對程序進行SCoP的動態(tài)非仿射擴展部分的代碼優(yōu)化.

2.4 代碼分析

分析當前函數(shù)，提取每條語句中的數(shù)據(jù)引用，分析每個數(shù)據(jù)引用的下標，分析過程如圖4所示.若當前處理的數(shù)組下標中存在非仿射乘法項，則對當前乘法項的兩個操作數(shù)分析，若操作數(shù)中存在循環(huán)的全局參數(shù)，則將該參數(shù)放入profile容器中，以待進行后續(xù)的處理.

圖4 尋找profile值的執(zhí)行流程Fig.4 Implementation of profiling

2.5 生成優(yōu)化版本

程序第二次編譯時間時對循環(huán)進行轉(zhuǎn)換，生成參數(shù)定值化的循環(huán)版本.它復(fù)制當前循環(huán)，將進行了profile優(yōu)化的循環(huán)的全局參數(shù)替代為定值，生成新的循環(huán)版本.并生成條件語句以在程序運行時間時判定執(zhí)行哪個循環(huán)版本.

圖5(a)所示為原程序，圖5(b)所示為優(yōu)化后的程序.其中bb1end是指新生成的條件語句，判斷在運行時間時真實的循環(huán)全局參數(shù)的值是否與優(yōu)化的循環(huán)版本中的值匹配，loop_specific_version是指將循環(huán)的全局參數(shù)用定值替換后的循環(huán)版本.

圖5 代碼轉(zhuǎn)換Fig.5 Code transformation

完成代碼轉(zhuǎn)換后，對當前函數(shù)的控制流程圖進行修改，分離原來的bb塊，向流程圖中添加新的邊.控制流程圖的修改過程如圖6所示.

3 實 驗

3.1 實驗指標

實驗將通過對比優(yōu)化前后GCC-4.8.3編譯器識別出的SCoP的數(shù)目和程序運行的加速比來驗證本文方法的有效性.

圖6 修改函數(shù)流程圖Fig.6 Modification of the CFG

(1)如果識別出的SCoP數(shù)目變多，就說明本文的方法可以有效地擴展多面體模型的表示范圍.

(2)加速比是測試程序的基準運行時間與使用多面體模型編譯后程序運行時間的比值.基準時間是指不對程序使用多面體模型優(yōu)化編譯所得程序的運行時間.如果加速比提升，就說明本文的方法可以有效地提高程序的運行速度.

3.2 實驗內(nèi)容

本實驗使用GCC-4.8.3編譯，使用PolyBench (the Poyhedral Benchmark suite)測試集進行實驗，該測試集被廣泛應(yīng)用于多面體模型優(yōu)化方法的測試中.在處理器為4核，主頻為1.8 GHz，內(nèi)存為1 GB，操作系統(tǒng)為Linux的虛擬機上運行所有的測試集.

分別在GCC-4.8.3和使用本文設(shè)計的多面體非仿射擴展方法優(yōu)化后的GCC-4.8.3上運行該標準測試程序集合，對比實驗指標，對實驗結(jié)果進行分析.每個程序共運行四次，

圖7為每次運行的編譯選項.圖7(a)所示選項為編譯器編譯程序時，僅使用-O2選項編譯，編譯所得程序的運行時間作為基準時間;圖7(b)所示為使用未經(jīng)過優(yōu)化的編譯器使用多面體模型編譯程序時的選項;圖7(c)、(d)為優(yōu)化后的編譯器編譯程序時兩次運行的選項.其中，-fgraphite選項表示用多面體模型對循環(huán)優(yōu)化，-floop-parallelize-all-ftree-parallelize-loops=4選項表示將可并行化的循環(huán)分為4個線程執(zhí)行.程序第一次運行時，增加-fprofile-generate選項，用以分析程序，找到需要profile的變量，并在程序運行時輸出變量的profile信息;程序第二次運行時，增加選項-fprofile-use，利用收集的動態(tài)profile信息使用本文設(shè)計的方法對程序進行優(yōu)化.

圖7 編譯參數(shù)Fig.7 Program parameters

3.3 實驗結(jié)果及分析

對GCC-4.8.3的多面體進行非仿射擴展，優(yōu)化前后識別出的SCoP數(shù)目進行對比，結(jié)果如圖8所示.可以看出，對于大多數(shù)程序，用本文方法優(yōu)化后的編譯器可以識別出更多的SCoP，即有更多的代碼區(qū)域可以被多面體模型表示.由此說明了本文的方法可以有效地擴展多面體模型的表示范圍.

圖8 優(yōu)化前后編譯器識別出的SCoP數(shù)目比較Fig.8 Comparison of the number of recognized SCoPs

圖9顯示了編譯器在多面體優(yōu)化前后編譯各個測試程序的加速比對比.從圖中可見，由于優(yōu)化后的編譯器可以識別出更多的SCoP，多面體可以表示和優(yōu)化更多的代碼區(qū)域，在特定的情況下加速比也有了相應(yīng)的提高.可以看到，程序bicg，gemm，mvt，trisolv適用于本文設(shè)計的多面體擴展方法，將這些表達式中的循環(huán)參數(shù)用定值替換后，可以被多面體模型表示優(yōu)化，加速比有了明顯的提升，gemm的加速比達到了5.7倍，這是因為將循環(huán)參數(shù)替換為定值后，不僅可以使并行優(yōu)化應(yīng)用到更多的代碼區(qū)域上，同時也可以使一些其他優(yōu)化有更好的應(yīng)用.而2mm、3mm等程序，雖然該擴展方法可以識別出更多的SCoP，然而由于這些程序代碼中自身存在的依賴關(guān)系使得這些程序代碼無法被轉(zhuǎn)換成并行代碼并行執(zhí)行，因此加速比并沒有提升.對于symm等程序，優(yōu)化后的編譯器可以識別出更多的SCoP，然而它們的加速比卻下降了，這并不是由于本文設(shè)計的方法增加了選擇執(zhí)行哪個程序版本的路徑引起的，因為選擇路徑的時間耗費非常少，可以忽略不計.這種情況產(chǎn)生的原因是，進行了循環(huán)參數(shù)定值化轉(zhuǎn)換的循環(huán)版本的運行速度確實比原循環(huán)版本運行速度慢.

圖9 優(yōu)化前后測試程序執(zhí)行時間加速比Fig.9 Comparison of the number of speedup

4 結(jié) 論

針對代碼區(qū)域存在由循環(huán)參數(shù)引起的非仿射的循環(huán)界和訪存數(shù)組下標時不能被并行優(yōu)化的情況，本文基于動態(tài)分析設(shè)計了一種針對多面體模型非仿射問題的擴展方法.在程序的運行時間時收集循環(huán)參數(shù)的動態(tài)信息，在編譯優(yōu)化時對這些動態(tài)信息進行分析，如果滿足條件，則將該循環(huán)參數(shù)替換為定值，生成非仿射循環(huán)的參數(shù)定值化的循環(huán)版本.通過實驗驗證，本方法擴展了多面體模型的表示范圍，使更多的代碼區(qū)域可以被優(yōu)化.本文的方法識別循環(huán)中重復(fù)出現(xiàn)的循環(huán)參數(shù)，適用于由循環(huán)參數(shù)引起的非仿射表達式的情況.

［1］李川，陳朝暉.基于多面體模型的數(shù)據(jù)依賴分析方法［J］.空間控制技術(shù)與應(yīng)用，2015，41(5):43-47.LI C，CHEN Z H.Data-dependence analysis method based on polyhedral model［J］.Aerospace Control and Application，2015，41(5):43-47.

［2］POP S，COHEN A，BASTOUL C，et al.GRAPHITE: Polyhedral analyses and optimizations for GCC［C］// Proceedings of the 2006 GCC Developers Summit.Ottawa;GCC，2006:179-197

［3］BENABDERRAHMANE M W，P L N，COHEN A，et al.The polyhedral model is more widely applicable than you think［J］.Lecture Notes in Computer Science，2010:283-303.

［4］GR??LINGER A.The challenges of non-linear parameters and variables in automatic loop parallelisation［D］.University of Passau，Department of Informatics and Mathematics，2009.

［5］GR??LINGER A.Extending the polyhedron model to inequality systems with non-linear parameters using quantifier elimination［D］.University of Passau，Department of Informatics and Mathematics，2003.

［6］BAGHDADI R，COHEN A，BASTOUL C，et al.The potential of synergistic static，dynamic and speculative loop nestoptimizationsforautomatic parallelization［C］//Workshop on Parallel Execution of Sequential Programs on Multi-core Architectures(PESPMA'10)，2010.

［7］JIMBOREAN A，L M，et al.VMAD:an advanced dynamic program analysis＆ instrumentation framework［C］//CC-21st International Conference on Compiler Construction.2012:220-237.

［8］ALEXANDRA J，F(xiàn) D J，JUAN M M C.Dynamic and speculative polyhedral parallelization using compilergenerated skeletons［J］.Springer Science，2013，42 (4):529-545.

［9］ANAND V，M S，MARY H.Non-affine extensions to polyhedral code generation［C］//ACM CGO:Orlando，F(xiàn)L，2014.

A Non-Affine Extension Method of Polyhedral Model Based on Dynamic Analysis

WANG Jianhua，CHEN Zhaohui
(Beijing Institute of Control Engineering，Beijing 100190，China)

The polyhedral model is now only applied in code regions with affine expressions in arrays’indexes.A method is presented that extending polyhedral model to non-affine expression.With the information acknowledged in runtime，non-affine expressions can be transformed to affine expressions，which are led by parameters that do not change in the loop nest.Then a specialized version of the original loop is generated，which makes polyhedral techniques applicable.This method enables the polyhedral model to be applicable in more code regions.More SCoPs in the code regions are recognized and higher speedup is achieved，therefore the performance of the program is improved.The validity and efficiency of the presented method are demonstrated by a series of experiments.

parallel compiling;polyhedral model;SCoP;affine;dynamic analysis

TP31

:A

:1674-1579(2016)02-0057-06

10.3969/j.issn.1674-1579.2016.02.011

王建花(1989—)，女，碩士研究生，研究方向為并行計算;陳朝暉(1969—)，男，研究員，碩士生導(dǎo)師，研究方向為航天嵌入式軟件技術(shù).

*國家基礎(chǔ)科研資助項目(JCKY2016203B006)

2015-10-21