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

王建花，陳朝暉

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

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

王建花，陳朝暉

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

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

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

0 引 言

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

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

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

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

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

1 研究背景

1.1 SCoP

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

圖1 SCoP的一個(gè)實(shí)例Fig.1 A case of SCoP

1.2 仿射表達(dá)式

仿射表達(dá)式: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.例如:對(duì)于循環(huán)loops(i，j)和參數(shù)(m，n)，所有仿射表達(dá)式的形式如下:

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

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

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

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

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

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

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

2.2 非仿射問(wèn)題

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

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

2.3 方法設(shè)計(jì)

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

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

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

2.4 代碼分析

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

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

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

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

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

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

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

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)指標(biāo)

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

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

(1)如果識(shí)別出的SCoP數(shù)目變多，就說(shuō)明本文的方法可以有效地?cái)U(kuò)展多面體模型的表示范圍.

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

3.2 實(shí)驗(yàn)內(nèi)容

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

4 結(jié) 論

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

［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—)，女，碩士研究生，研究方向?yàn)椴⑿杏?jì)算;陳朝暉(1969—)，男，研究員，碩士生導(dǎo)師，研究方向?yàn)楹教烨度胧杰浖夹g(shù).

*國(guó)家基礎(chǔ)科研資助項(xiàng)目(JCKY2016203B006)

2015-10-21