夏文博 胡偉方 郭浩然

1(鄭州大學(xué)信息工程學(xué)院 河南 鄭州 450000)2(北京空間信息中繼傳輸技術(shù)研究中心 北京 100094)

0 引 言

近年來，隨著以深度學(xué)習(xí)算法為代表的人工智能技術(shù)不斷應(yīng)用于各個(gè)領(lǐng)域，大量計(jì)算密集型程序?qū)τ?jì)算性能的要求逐步增高。為了利用程序中存在的并行性與數(shù)據(jù)局部性，確保程序快速執(zhí)行，降低設(shè)備功耗，通用CPU提供了多級緩存、多核、SIMD部件，甚至GPU等專用的計(jì)算加速器也用于提升程序的執(zhí)行效率[1]。更加復(fù)雜的并行層次及存儲(chǔ)器層次結(jié)構(gòu)給編譯優(yōu)化帶來了新的挑戰(zhàn)。

計(jì)算密集型程序中往往存在著大量的循環(huán)，例如在圖像處理程序中，計(jì)算核心耗時(shí)一般在圖像矩陣的運(yùn)算，對這些運(yùn)算進(jìn)行處理時(shí)，需要多層循環(huán)來表示運(yùn)算操作。將循環(huán)進(jìn)行適當(dāng)?shù)淖儞Q，并且映射到不同目標(biāo)平臺(tái)以充分發(fā)掘程序中的并行性和數(shù)據(jù)局部性則需要編譯優(yōu)化的支持[2]。目前，大多數(shù)工業(yè)級編譯器雖然支持基本循環(huán)變換、向量化、自動(dòng)并行代碼生成等功能，但是一旦涉及需要多種復(fù)雜轉(zhuǎn)換才能確保優(yōu)化所需的數(shù)據(jù)局部性及并行性的情況，常規(guī)編譯優(yōu)化過程是難以分析并進(jìn)行處理的，這嚴(yán)重限制了編譯器對程序性能的優(yōu)化能力。

多面體模型[3]是一種集成了靜態(tài)控制塊分析、依賴分析、循環(huán)調(diào)度變換于一體的數(shù)學(xué)表示方法。多面體模型比傳統(tǒng)抽象語法樹(Abstract Syntax Tree，AST)表示更準(zhǔn)確地描述了程序靜態(tài)信息與動(dòng)態(tài)特性。作為一種數(shù)學(xué)模型，多面體模型可以更抽象地描述循環(huán)嵌套，更加精確地計(jì)算語句實(shí)例之間的依賴關(guān)系。同時(shí)，多面體模型表示可以自然地表示多種循環(huán)變換方法，例如循環(huán)交換、循環(huán)傾斜等。利用多種循環(huán)變換方法，有利于發(fā)掘程序中的向量化機(jī)會(huì)，生成SIMD[4]代碼，也可以利用循環(huán)分塊等變換，幫助生成面向GPU體系結(jié)構(gòu)的SIMT(單指令多線程)代碼[5]。隨著GPU、AI芯片等多種全新體系結(jié)構(gòu)的出現(xiàn)，多面體編譯優(yōu)化已成為一種越來越流行的技術(shù)。

對程序應(yīng)用多面體優(yōu)化時(shí)，首先需要找到可以被轉(zhuǎn)換成多面體表示的相關(guān)代碼段，稱為靜態(tài)控制塊(Static Control Parts，SCoP)，并為它們創(chuàng)建一個(gè)多面體模型描述。然而，SCoP的構(gòu)成必須非常規(guī)范，實(shí)際程序中往往具有許多限制循環(huán)嵌套被識(shí)別為SCoP的非規(guī)則因素。在通過對SPEC2006[6]測試基準(zhǔn)的測試中發(fā)現(xiàn)許多測試用例程序中的相關(guān)循環(huán)代碼段存在諸多限制SCoP識(shí)別的問題。例如圖1中的代碼，在進(jìn)行SCoP檢測的過程中，由于大多數(shù)編譯器的別名分析相對保守，編譯器無法證明循環(huán)嵌套中所有數(shù)組訪問不會(huì)造成重疊，會(huì)將其識(shí)別為存在別名問題，多面體識(shí)別算法會(huì)判定該循環(huán)為非SCoP。

圖1 帶有可能別名的循環(huán)結(jié)構(gòu)

為了擴(kuò)展多面體編譯的實(shí)用性，目前已經(jīng)有一些學(xué)者對限制靜態(tài)控制塊識(shí)別的若干非規(guī)則因素進(jìn)行了研究。Benabderrahmane等[7]利用任意邊界建模循環(huán)結(jié)構(gòu)，解決了while循環(huán)的多面體建模處理。Strout等[8]研究了稀疏矩陣的多面體編譯優(yōu)化技術(shù)，并基于運(yùn)行時(shí)重排序轉(zhuǎn)換技術(shù)，擴(kuò)展了非仿射數(shù)組下標(biāo)在多面體模型中的應(yīng)用。另外也有開發(fā)人員選擇使用一些工具來緩解多面體建模不充分的問題，例如：SCoP的解析器Clan[9]，要求開發(fā)人員手工標(biāo)記每個(gè)SCoP來手動(dòng)幫助編譯器識(shí)別更多的SCoP，但是這種做法也給程序開發(fā)人員帶來了許多額外的負(fù)擔(dān)，需要進(jìn)行大量的人工分析來確定SCoP的位置及范圍。

本文首先使用SPEC2006測試集進(jìn)行多面體建模測試，分析并總結(jié)出實(shí)際應(yīng)用程序中阻礙SCoP識(shí)別的主要因素。針對多面體建模的多種主要限制因素，基于LLVM編譯框架提出了兩種提升多面體建模能力的解決方案：(1) 針對多面體模型的SCoP識(shí)別限制中的復(fù)雜循環(huán)格式問題，在編譯流程中添加循環(huán)規(guī)范化遍歷，對待分析的循環(huán)進(jìn)行規(guī)范化處理，消除部分不規(guī)范因素的影響。(2) 針對造成多面體建模失敗最多的非仿射數(shù)組訪問模式與循環(huán)邊界的問題，利用LLVM的靜態(tài)程序分析信息，提出了一種定值替換的方法來解決該問題。

1 SCoP識(shí)別限制分析

為了分析程序中限制SCoP識(shí)別的因素，對SPEC2006基準(zhǔn)測試中的C語言程序進(jìn)行了SCoP檢測測試與評估。在LLVM的多面體建模模塊中的SCoP識(shí)別功能函數(shù)中加入診斷信息輸出語句，統(tǒng)計(jì)導(dǎo)致SCoP識(shí)別失敗的原因，分析得出的主要原因如下：

(1) 非仿射的數(shù)組訪問表達(dá)式。在多面體模型中，要求所有的數(shù)組訪問表達(dá)式或條件表達(dá)式都必須是輸入?yún)?shù)或歸納變量的仿射表達(dá)式，否則SCoP的識(shí)別算法不會(huì)將該代碼所在的區(qū)域視為SCoP，從而阻礙了多面體模型對其進(jìn)行優(yōu)化。舉例如圖2所示。

圖2 非仿射表達(dá)式

此外，SCoP中所有循環(huán)迭代的上下限也必須是輸入?yún)?shù)或歸納變量的仿射表達(dá)式。

(2) 別名。當(dāng)編譯器對循環(huán)的分析結(jié)果無法證明兩個(gè)內(nèi)存訪問的基地址是否不相交時(shí)，特別是當(dāng)指針與參數(shù)值相關(guān)而不是全局變量或堆棧分配的內(nèi)存空間地址時(shí)，編譯器的別名分析就會(huì)保守地將其識(shí)別為指針別名，導(dǎo)致對該內(nèi)存訪問所在的程序段的多面體建模失敗。

(3) 函數(shù)調(diào)用。在多面體模型中，調(diào)度變換需要首先分析并嘗試消除程序中存在的依賴關(guān)系。然而，在具有外部函數(shù)調(diào)用或間接函數(shù)調(diào)用的循環(huán)中，依賴關(guān)系將變得非常復(fù)雜?；诙嗝骟w模型的依賴關(guān)系分析方法也不能給出程序中精確的數(shù)據(jù)依賴關(guān)系。所以，在SCoP的檢測過程中，往往會(huì)排除包含函數(shù)調(diào)用的相關(guān)代碼段。

(4) 非規(guī)范化的歸納變量。在多面體模型對循環(huán)嵌套的抽象表示中，循環(huán)嵌套中某個(gè)語句的迭代域會(huì)被表示成多維仿射空間中的有界凸多面體，該多面體中每個(gè)整數(shù)點(diǎn)都代表該語句的一個(gè)執(zhí)行實(shí)例。這使得在多面體建模過程中，對循環(huán)中的歸納變量具有一定的限制：在循環(huán)每次迭代中，迭代變量遞增或遞減幅度要求為1。編譯器在多面體模型建模之前，應(yīng)盡量將循環(huán)中的歸納變量等進(jìn)行規(guī)范化處理。

(5) 復(fù)雜的控制流。在多面體模型中，優(yōu)化需要得到代碼段中的循環(huán)的各個(gè)信息，如果程序代碼段中出現(xiàn)了比較復(fù)雜的終止符(例如：switch、goto等)或者具有復(fù)雜形式的控制流(通過while和for或者if結(jié)構(gòu)無法表示)，多面體模型將難以對程序的靜態(tài)信息與動(dòng)態(tài)特性進(jìn)行建模，不能識(shí)別為SCoP。

2 基于LLVM靜態(tài)分析的識(shí)別優(yōu)化

LLVM[10]是一組用于構(gòu)建編譯器的工具和庫。它圍繞一種和語言以及平臺(tái)無關(guān)的中間表示(LLVM-IR)構(gòu)建，提供了先進(jìn)的程序分析、優(yōu)化和目標(biāo)代碼生成等模塊功能。除了支持x86-32、x86-64和ARM等后端，還有針對大多數(shù)GPU加速器甚至硬件描述的目標(biāo)代碼生成。LLVM支持目前大部分常用的編程語言的靜態(tài)和即時(shí)編譯。LLVM模塊化的結(jié)構(gòu)、有良好可讀性的IR和一系列有用的工具，便于開發(fā)人員進(jìn)行基于LLVM的編譯模塊開發(fā)。基于LLVM的多面體工具的靜態(tài)控制塊檢測實(shí)現(xiàn)流程如圖3所示。

圖3 SCoP識(shí)別流程

2.1 復(fù)雜循環(huán)格式的優(yōu)化

LLVM-IR是LLVM編譯器的中間表示語言[11]。將源程序降級到LLVM-IR之后，源程序的復(fù)雜性就會(huì)顯著降低，并且生成的LLVM-IR沒有高級語言中的循環(huán)表示，只有跳轉(zhuǎn)語句和goto語句。源程序中的數(shù)組或仿射表達(dá)式也轉(zhuǎn)換為指針運(yùn)算和三地址格式的操作。在這種表示中，源程序中的所有必要信息都會(huì)通過LLVM提供的內(nèi)部分析Pass重新計(jì)算。所以，在LLVM-IR中，可以使用循環(huán)檢測或支配樹信息等簡單分析來驗(yàn)證待分析程序段是否只包含結(jié)構(gòu)化控制流，也可以使用更復(fù)雜的分析來檢查別名或提供關(guān)于函數(shù)調(diào)用副作用的信息。這里本文選擇運(yùn)行一組LLVM規(guī)范化Pass，進(jìn)一步規(guī)范化代碼，解決程序中不規(guī)范的循環(huán)格式。具體實(shí)現(xiàn)如圖4所示。

圖4 不規(guī)范循環(huán)格式處理流程

LLVM編譯框架具有非常完備的程序變換和規(guī)范化Pass集。其中包括基本別名分析、內(nèi)存到寄存器的提升、庫調(diào)用的簡化、指令簡化、尾部調(diào)用消除、循環(huán)簡化、閉環(huán)SSA表單計(jì)算和歸納變量規(guī)范化。表1中給出了一些限制SCoP識(shí)別的非規(guī)范因素相應(yīng)的解決方案，將這些方案加入到規(guī)范化Pass中，用以解決多面體的建模的一些限制。

表1 不同限制因素解決方案

2.2 非仿射問題的優(yōu)化

如圖5所示，多面體模型不支持維數(shù)是未知的數(shù)組。一種常用的做法是對數(shù)組進(jìn)行降維。使用一維數(shù)組并“手動(dòng)”執(zhí)行索引算法來實(shí)現(xiàn)n維數(shù)組。這樣就可以在一維數(shù)組上創(chuàng)建仿射下標(biāo)，使用靜態(tài)分析可以推斷出該一維數(shù)組是二維數(shù)組的映射訪問。但是，目前LLVM編譯器中并沒有相關(guān)的轉(zhuǎn)換實(shí)現(xiàn)。另外，這樣的轉(zhuǎn)換也會(huì)導(dǎo)致代碼的復(fù)雜度增加，可能會(huì)導(dǎo)致靜態(tài)分析失敗，對后續(xù)的分析造成影響。所以，非仿射表達(dá)式的主要問題是：雖然表達(dá)式的值是固定不變的，但是其表達(dá)式是非仿射的，并將其判定為不滿足多面體模型建模條件。

圖5 非仿射表達(dá)式

本文基于LLVM分析Pass得到的循環(huán)分析結(jié)果，對非仿射的表達(dá)式進(jìn)行結(jié)果判斷，通過保持恒定的參數(shù)值來消除上述形式的非仿射表達(dá)式對多面體建模的影響。具體所用的分析如下：

(1) 靜態(tài)單一賦值(SSA)：SSA表示的抽象視圖是一種聲明性語言[12]，通過插入額外的標(biāo)量變量，使每個(gè)定義都是唯一的。標(biāo)量變量的賦值可以是表達(dá)式的結(jié)果，也可以是位于目標(biāo)基本塊中控制流節(jié)點(diǎn)的phi節(jié)點(diǎn)的結(jié)果。例如，圖6中所示的程序代碼通過添加新的變量名和在控制流節(jié)點(diǎn)處合并值的phi節(jié)點(diǎn)，將其轉(zhuǎn)換為SSA。

圖6 SSA轉(zhuǎn)換

循環(huán)phi節(jié)點(diǎn)定義遞歸表達(dá)式：循環(huán)phi節(jié)點(diǎn)的第一個(gè)參數(shù)定義初始值，第二個(gè)參數(shù)使用自引用定義遞歸。例如：

a=loop_1-phi(0,a+1)

b=loop_1-phi(0,2×a)

a在第一次迭代時(shí)定義為0，并且對所有其他迭代使用自引用表達(dá)式a+1;b在第一次迭代中定義初始值0，接著是對于所有后續(xù)迭代引用另一個(gè)loop-phi節(jié)點(diǎn)2×a的表達(dá)式。

循環(huán)close-phi節(jié)點(diǎn)用來計(jì)算loop-phi節(jié)點(diǎn)在循環(huán)中定義的最后一個(gè)值：它們對應(yīng)于部分遞歸函數(shù)的min運(yùn)算符。例如：

c=loop_1-cloase-phi(b,a>10)

c被定義為當(dāng)a變?yōu)榇笥?0時(shí)第一次迭代的b的值：在示例中，c的值可以被靜態(tài)地計(jì)算為22。

(2) 標(biāo)量演化分析(SCEV)：從上述SSA表示的抽象開始，通過識(shí)別循環(huán)phi節(jié)點(diǎn)、循環(huán)閉合phi節(jié)點(diǎn)和派生的標(biāo)量聲明來分析標(biāo)量變量演化函數(shù)。循環(huán)phi節(jié)點(diǎn)由初始值和包含自引用的表達(dá)式來聲明，當(dāng)自引用與當(dāng)前循環(huán)中的標(biāo)量值或不變表達(dá)式一起出現(xiàn)在加法表達(dá)式中時(shí)，SCEV表示具有線性或仿射演化的遞歸函數(shù)。循環(huán)close-phi節(jié)點(diǎn)被聲明為一個(gè)由表達(dá)式計(jì)算的最后一個(gè)值，該表達(dá)式可能在循環(huán)中發(fā)生變化，然后SCEV表示一個(gè)部分遞歸函數(shù)。所有其他標(biāo)量聲明都可以表示為從其他遞歸和部分遞歸函數(shù)的聲明派生的SCEV。SCEV分析將為上述運(yùn)行示例提供以下表達(dá)式：

a={0,+,1}_1

b={0,+,2}_1

c=22

a的SCEV分析其初值為0，每次迭代值線性遞增加1。類似地，b的初值為0，每次迭代遞增加2。由于c的計(jì)算是在循環(huán)外，它的值并不隨循環(huán)的迭代而變化，所以，在這里可以通過SCEV的靜態(tài)分析得到表達(dá)式c的值為常量22。

(3) 迭代次數(shù)的分析：提供一個(gè)表示循環(huán)執(zhí)行的次數(shù)的SCEV分析。迭代的次數(shù)被計(jì)算為閉合phi節(jié)點(diǎn)(close-phi)的SCEV，或者SCEV的最后一個(gè)值，從0開始，在循環(huán)的每次迭代中增加1。在運(yùn)行的示例中，迭代數(shù)可以在退出循環(huán)時(shí)計(jì)算為a的值，并可以靜態(tài)地計(jì)算為11。

通過上述的分析可知，可以通過LLVM編譯器中的循環(huán)分析Pass得到程序中循環(huán)嵌套的中表達(dá)式的靜態(tài)分析值，再從中篩選出循環(huán)中重復(fù)出現(xiàn)的，可被定值為常量的參數(shù)值。然后，將其插入到非仿射參數(shù)或者表達(dá)式中，通過替換定值讓表達(dá)式保持恒定，并創(chuàng)建一個(gè)新的定值循環(huán)版本。最后將調(diào)度代碼插入到相應(yīng)的循環(huán)檢查基本塊中，以在運(yùn)行時(shí)確定實(shí)際參數(shù)值是否存在符合要求的版本。如果不符合，則使用原始版本。這樣可以將一些原本不能看成仿射的，但是循環(huán)上下界都是常數(shù)值的非仿射表達(dá)式表示成為仿射的，從而對更多的循環(huán)進(jìn)行多面體優(yōu)化。其具體實(shí)現(xiàn)如圖7所示。

圖7 定值版本循環(huán)生成流程

多面體模型代碼檢測階段，對循環(huán)代碼進(jìn)行分析時(shí)，如果發(fā)現(xiàn)循環(huán)中存在非仿射表達(dá)式，調(diào)整其判斷策略：將其進(jìn)行標(biāo)識(shí)為待分析的仿射表達(dá)式；再判斷是否存在專用的循環(huán)版本，如果存在則識(shí)別為SCoP，進(jìn)行多面體優(yōu)化，如果不存在，則判定為非SCoP，讓其按照原來的方案進(jìn)行處理。實(shí)現(xiàn)流程如圖8所示。

圖8 基于靜態(tài)分析的非仿射表達(dá)式處理流程

3 實(shí)驗(yàn)與分析

3.1 測試指標(biāo)與實(shí)驗(yàn)平臺(tái)

在多面體優(yōu)化過程中，SCoP的識(shí)別是優(yōu)化的基礎(chǔ)。本文進(jìn)行了如下兩個(gè)方面的測試：SCoP識(shí)別數(shù)目的優(yōu)化測試和優(yōu)化后的程序運(yùn)行加速比測試。

(1) SCoP識(shí)別數(shù)量測試：測試優(yōu)化前和優(yōu)化后，識(shí)別出來的符合多面體建模條件的靜態(tài)控制塊的平均數(shù)目，通過對比得出優(yōu)化的效果，驗(yàn)證本文提出的非規(guī)范因素消除方法的有效性。

(2) 程序運(yùn)行加速比測試：首先進(jìn)行不引入多面體優(yōu)化的基準(zhǔn)測試；之后分別測試初始多面體優(yōu)化工具和經(jīng)過本文優(yōu)化后的多面體優(yōu)化工具測試結(jié)果。通過對比兩次測試相對于基準(zhǔn)測試的加速比，來分析SCoP識(shí)別數(shù)目對多面體優(yōu)化的影響。

測試平臺(tái)采用處理器為Intel(R) Xeon(R) CPU E5- 2682 v4 @ 2.50 GHz，128 GB內(nèi)存，操作系統(tǒng)為CentOS7；編譯器版本為LLVM- 8.0.0。

3.2 測試內(nèi)容

為了對比測試優(yōu)化方案在實(shí)際應(yīng)用中對SCoP檢測能力的優(yōu)化效果，實(shí)驗(yàn)采用SPEC2006測試集來進(jìn)行測試。分別在LLVM中的多面體工具和經(jīng)過本文中設(shè)計(jì)的優(yōu)化后的LLVM多面體工具上進(jìn)行測試，得出識(shí)別到的SCoP數(shù)目的平均值。

LLVM編譯器可以使用OPT工具來手動(dòng)實(shí)施對LLVM-IR的單獨(dú)優(yōu)化，使用-polly-detect選項(xiàng)來直接測試識(shí)別出的SCoP，其中-polly選項(xiàng)代表引入多面體優(yōu)化。針對優(yōu)化后的版本，本文添加編譯選項(xiàng)-polly-canonicalize，利用LLVM標(biāo)準(zhǔn)化Pass來規(guī)范多面體檢測代碼，非仿射表達(dá)式的處理則使用-polly-opt-nonaff選項(xiàng)進(jìn)行控制。

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

3.3.1識(shí)別率分析

為了更確切地表示基于LLVM的靜態(tài)分析對消除多面體建模中SCoP識(shí)別的優(yōu)化能力，實(shí)驗(yàn)依然采用SPEC2006的C語言測試用例。實(shí)驗(yàn)結(jié)果如圖9所示，其中黑色部分表示優(yōu)化前識(shí)別出的SCoP數(shù)量，8個(gè)測試用例共識(shí)別出296個(gè)SCoP。白色表示經(jīng)過本文方法優(yōu)化后識(shí)別出的SCoP數(shù)目，8個(gè)測試用例共426個(gè)SCoP，平均識(shí)別數(shù)目增加了1.4倍。除mcf的識(shí)別出的循環(huán)個(gè)數(shù)沒有發(fā)生改變外，其余測試用例符合SCoP條件的循環(huán)個(gè)數(shù)都得到了提高。并且sjeng測試用例靜態(tài)控制塊數(shù)目提升最為明顯，提升了約4.3倍。實(shí)驗(yàn)結(jié)果表明，基于LLVM的靜態(tài)分析優(yōu)化以及規(guī)范化方法能夠有效提升SCoP的識(shí)別率。

圖9 動(dòng)態(tài)優(yōu)化前后靜態(tài)控制塊數(shù)量對比圖

3.3.2加速比分析

本文采用多面體模型編譯測試集PolyBench作為加速比測試的測試用例來測試SCoP識(shí)別數(shù)目對多面體優(yōu)化效果的提升效果。PolyBench[13]是一個(gè)具有30個(gè)數(shù)值計(jì)算的基準(zhǔn)測試套件，包含了線性代數(shù)計(jì)算、模板計(jì)算、圖像處理和數(shù)據(jù)挖掘的計(jì)算內(nèi)核。在計(jì)算加速比時(shí)，先使用經(jīng)過LLVM編譯器最優(yōu)選項(xiàng)-O3優(yōu)化后，獲取的程序運(yùn)行時(shí)間作為基準(zhǔn)時(shí)間，通過使用和不使用本文中的SCoP識(shí)別優(yōu)化方法，分別測試程序運(yùn)行的時(shí)間，通過與基準(zhǔn)時(shí)間相比較計(jì)算出各自的加速比。

測試結(jié)果如圖10所示，其中黑色部分表示在沒有進(jìn)行SCoP識(shí)別優(yōu)化情況下取得的加速比，白色部分表示在對SCoP識(shí)別方法進(jìn)行改進(jìn)后的情況下所取得的加速比。經(jīng)過優(yōu)化后，測試用例中的3 mm運(yùn)行速度最高相對于優(yōu)化前提升了2.3倍。大部分情況下，加速比有了相應(yīng)的提升，說明基于循環(huán)格式規(guī)范化和定值替換的方法可以避開多面體建模的一些限制，提升SCoP的識(shí)別率，發(fā)掘更多的多面體優(yōu)化機(jī)會(huì)以獲得性能提升。然而，也有一些測試用例出現(xiàn)了加速效果降低的現(xiàn)象，例如：mvt、symm。這種情況的出現(xiàn)，主要是因?yàn)樾略黾拥囊恍┭h(huán)代碼區(qū)域本身存在一些依賴或者其他原因，造成并行化優(yōu)化失敗。這樣就會(huì)出現(xiàn)優(yōu)化帶來的收益，不能抵消多面體建?；蛘逽CoP識(shí)別帶來的時(shí)間消耗的情況，從而導(dǎo)致程序運(yùn)行速度變慢。也有另外一種原因是SCoP識(shí)別數(shù)目增加后，并行處理這些靜態(tài)控制單元，需要更加頻繁地進(jìn)行線程開啟和同步，造成了線程開銷增加的問題，抵消了程序并行運(yùn)行帶來的收益。要解決這個(gè)問題，需要后續(xù)對SCoP的處理算法進(jìn)行改進(jìn)。

圖10 多面體優(yōu)化加速對比

4 結(jié) 語

本文針對多面體建模有諸多限制的問題，對阻礙程序代碼中實(shí)現(xiàn)多面體模型建立的因素進(jìn)行了全面分析。對不規(guī)則的循環(huán)代碼，在規(guī)范化處理Pass中整合了解決方案，對進(jìn)行多面體建模識(shí)別的區(qū)域進(jìn)行了規(guī)范化處理，解決了復(fù)雜的循環(huán)結(jié)構(gòu)的簡化和處理。針對限制多面體建模占比最多的非仿射表達(dá)式的問題，基于LLVM的靜態(tài)分析中的標(biāo)量演化，進(jìn)行了預(yù)分析優(yōu)化，將循環(huán)中不確定的變量參數(shù)，進(jìn)行了定值化處理，生成了定值版本的循環(huán)，從而對非仿射問題進(jìn)行了擴(kuò)展。最后經(jīng)過實(shí)驗(yàn)驗(yàn)證，本文所做的方法優(yōu)化，可以有效提升SCoP的識(shí)別數(shù)量，增強(qiáng)了多面體模型的優(yōu)化效果。