4.1?適配體系結構特征的關鍵技術

由于高級語言隱藏了底層硬件體系結構的大量細節(jié)，如果不經(jīng)過優(yōu)化直接將高級程序設計語言編寫的程序部署在底層硬件上，往往無法充分利用底層硬件體系結構的處理能力。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

算子融合不僅可以提高計算密度，還可以避免相鄰算子之間通過GPU設備內存通信引入的數(shù)據(jù)訪問開銷。

循環(huán)變換和不同循環(huán)變換之間的組合是實現(xiàn)面向底層硬件體系結構的重要優(yōu)化手段。本章將基于多面體模型詳細介紹優(yōu)化編譯器實現(xiàn)循環(huán)變換及不同循環(huán)變換之間組合的方式，并介紹各種循環(huán)變換的應用場景，以及一些循環(huán)變換之間的關系。

4.2 預處理

只要維持程序的循環(huán)攜帶依賴，那么循環(huán)變換總是有效的。在開始分析依賴關系之前，優(yōu)化編譯器應該提供一些能夠對循環(huán)嵌套實現(xiàn)預處理的機制。一方面，預處理能夠簡化依賴測試或精確依賴分析的過程；另一方面，預處理也能夠消除一些復雜的循環(huán)攜帶依賴，為實現(xiàn)更多的循環(huán)變換創(chuàng)造環(huán)境。

4.2.1 循環(huán)正規(guī)化

循環(huán)正規(guī)化使得循環(huán)嵌套中每個循環(huán)下界從0開始運行到某個確定的上界，并且循環(huán)的步長為1.同時，使用新的循環(huán)索引變量替換的仿射函數(shù)表達式區(qū)替換原循環(huán)變量在循環(huán)內的所有引用。即循環(huán)的下界為0，上界為(U-L)/r，步長為1,。原循環(huán)索引變量為i，之后為r*i + L。注意r應該是一個具體的常數(shù)值而不是符號常亮，否則難以通過靜態(tài)分析來判定依賴是否存在。盡管可能通過引入謂詞條件的方式將非仿射表達式轉換為仿射表達式的形式，但這種向上近似的方法往往會導致冗余的循環(huán)跌打，程序的語義則通過引入的謂詞條件來保證。

4.2.2 死代碼刪除

在實際應用中，可能會存在一些不會被其他有用的語句引用結果的語句，即程序的死代碼。有用的語句是指用于輸出程序結果的代碼，或者那些再被優(yōu)化的程序中仍然需要執(zhí)行的代碼。

死代碼刪除可以在計算出程序的數(shù)據(jù)流信息之后，利用向下暴露集與程序迭代空間以及依賴關系之間的基本操作來完成，其基本思想是先根據(jù)近似數(shù)據(jù)流分析方法計算出被優(yōu)化的程序片段的向下暴露集，并依此計算出所有向下暴露集中語句實例的流依賴源點的集合，將二者集合求并，得到一個新的集合，向這些變量寫入數(shù)據(jù)的語句實例都不會是死代碼，重復該過程，直到求并之后的集合不再發(fā)生變化。由于死代碼可以與其他語句產生數(shù)據(jù)流關系，因此將所有死代碼語句導致的依賴從數(shù)據(jù)流關系和各種依賴關系中刪除，減少編譯器對程序實施循環(huán)變換的約束。

4.2.3 別名分析

別名分析阻礙優(yōu)化編譯器分析依賴關系最關鍵的因素之一，特別是對以多面體模型為基礎的優(yōu)化編譯器而言，因為多面體沒有辦法判定不同內存地址單元之間的別名關系，也就無法確定語句實例之間是否有依賴。

大多數(shù)基于多面體模型的優(yōu)化編譯器只是簡單地認為數(shù)組之間不再存在別名關系。

一種常用的方法是在程序設計語言級別引入輔助別名分析或者消除別名的語言特性。例如，C語言提供的restrict關鍵字。另一種方式是優(yōu)化編譯器在實施程序轉換時，對可能產生別名關系的數(shù)組進行標記，并依靠運行時技術確定別名關系是否存在。

4.2.4 迭代空間分裂

為了減少二維stencil中空間維度之間的長距離依賴在每個維度上的距離向量分量，可以采用一種稱為迭代空間分裂的方法。

對原迭代空間中非依賴方向進行切割，同一時間維度上的子空間可以通過折疊，將原來的依賴轉換。迭代空間分裂為子空間的折疊創(chuàng)造了條件，但子空間的折疊卻需要依靠多面體模型對循環(huán)迭代空間進行一維或多維反向的循環(huán)偏移或反轉變換才能獲得有利于循環(huán)變換的迭代空間。

4.3 多面體模型中的循環(huán)變換

與傳統(tǒng)的并行編譯器所采用的幺模矩陣相比，多面體模型具備以下幾個特點：
? ? ? ? 1. 應用范圍廣。幺模矩陣只能處理完美嵌套循環(huán)，而多面體模型對輸入程序的約束更少，不僅處理完美循環(huán)嵌套，而且對非完美循環(huán)也支持。
? ? ? ? 2. 表示能力強。幺模矩陣只能處理循環(huán)變換、切斜和反轉等變換。而多面體還能處理循環(huán)分塊、合并和分布等在內的幾乎所有循環(huán)變換。
? ? ? ? 3. 優(yōu)化空間大。多面體模型能處理更多的循環(huán)變換的組合。

除了面向通用體系結構的源到源優(yōu)化工具Pluto和PPCG外，GCC、LLVM、Opn64和IBM XL編譯器都集成了多面體優(yōu)化相關的模塊。也在深度神經(jīng)網(wǎng)絡和自動優(yōu)化和部署受到了廣泛的關注：MLIR, TensorComprehensions，Tiramisu, PlaidML/Stripe和Diesel等深度學習編譯器中發(fā)揮了不可替代的作用。

4.3.1 循環(huán)變換分類

根據(jù)循環(huán)變換對程序特征的改變，分為以下幾種：
? ? ? ? 1. 改變程序算法設計：是通過對算法的調整來降低時間或空間復雜度的。例如，在不考慮穩(wěn)定性的前提下，可以使用快排代替冒泡排序。
? ? ? ? 2. 改變程序計算順序：往往是為了提升程序的并行性或數(shù)據(jù)的局部性。例如循環(huán)合并就是為了縮短相鄰循環(huán)嵌套訪問數(shù)據(jù)之間的“生產-消費”距離、提升數(shù)據(jù)的時間局部性而實現(xiàn)的循環(huán)變換。
? ? ? ? 3. 僅改變循環(huán)結構、但不改變程序計算順序：主要是為了生成對目標體系結構友好的代碼而設計或實現(xiàn)的。例如循環(huán)展開就是一種為了充分利用細粒度指令流水并行而設計的循環(huán)變換。
? ? ? ? 4. 改變程序數(shù)據(jù)布局和被訪問內存地址單元：充分利用目標體系結構上的存儲層次結構。

編譯器很難實現(xiàn)第一種循環(huán)變換，基于多面體的編譯器能夠自動實現(xiàn)后三種的循環(huán)變換及其組合。后三種循環(huán)變換幾乎都需要考慮目標體系結構的特征，因此如何在多面體模型中實現(xiàn)對目標體系結構的抽象是實現(xiàn)循環(huán)變換的關鍵。

4.3.2 循環(huán)變換的復雜性

基于多面體模型的循環(huán)變化將循環(huán)的迭代空間表示成空間多面體，并通過多面體上的幾何操作達到分析和優(yōu)化程序的目的。多面體模型利用迭代空間、訪存映射、依賴關系和調度表示程序及其語義。其中，調度表示語句實例與其對應的字典序之間的仿射函數(shù)，多面體模型實現(xiàn)循環(huán)變換的方法就是在滿足依賴關系的前提下，將一種調度轉換成另一種調度的過程，該過程也被稱為調度變換。多面體模型首先將循環(huán)嵌套內的語句實例構成的集合表示為空間多面體的形式。從幾何角度來看，多面體模型上的調度變換實質上就是多維空間幾何的變基過程。

// CPU 一段可并行循環(huán)
for(t = 0; t < T; t+=1)for(i = 0; i < N; i+=1)A[t+1][i] = 0.25 * (A[t][i+1] -2*A[t][i] + A[t][i-1]);// GPU 二段可并行循環(huán)
for(t = 0; t < T; t+=1)for(it = 0; it < (N-2)/4; it+=1)for(ip = max(1, 4*ip); ip < min(N-1, 4*ip+4); ip+=1)A[t+1][ip] = 0.25 * (A[t][ip+1] -2*A[t][ip] + A[t][ip-1]);

只考慮并行性的前提下，循環(huán)變換的代碼在硬件上的部署似乎看起來沒有那么麻煩。然而，一個無法忽視的問題是現(xiàn)代體系結構上的存儲層次結構。盡管一些底層的編譯技術已經(jīng)充分考慮到如寄存器分配、指令流水線并行等細粒度策略，但是面向高速緩存的數(shù)據(jù)局部性優(yōu)化卻是循環(huán)變換不得不考慮的問題。

在基于多面體的編譯器中，代碼生成階段的輸入是表示程序迭代空間的集合和表示程序調度的映射。其中，表示程序調度的映射必須是從語句實例集合到字典序之間的仿射函數(shù)。

對迭代空間進行粗暴地矩形劃分是非法的，因為任意兩個水平相鄰的分塊之間存在依賴環(huán)，而多面體模型的代碼生成器限制循環(huán)只能延(t,i)坐標軸方向切割。細看之后發(fā)現(xiàn)，沿i軸獲得循環(huán)分塊是合法的。接下來解決t軸切割。t軸的切割方向與程序中的兩個依賴，即左上和右上方向的依賴都相交。如果沿著兩個依賴的其中一個方向進行切割并構造新的分塊形狀。不難發(fā)現(xiàn)，這兩種分塊形狀都不會導致任意方向相鄰兩個分塊之間的依賴環(huán)。

要構造上述分塊，i軸保持不變，另外一個坐標軸的指向左上或右上的依賴方向平行，需要編譯器自動實現(xiàn)對循環(huán)分塊友好的循環(huán)變換及這些循環(huán)變換的不同組合，這對編譯器很重要也很困難。

循環(huán)變換的目的有時候是互相沖突的，以程序并行性和數(shù)據(jù)局部性為例，上述分塊沒有實現(xiàn)最大化程序并行性的目的，盡管提高了數(shù)據(jù)局部性。

帶有OpenMP編譯指示的代碼在運行時有同步開銷，編譯指示在循環(huán)嵌套的層數(shù)越靠近，同步的開銷就越小。循環(huán)分塊增大了同步開銷，因此損失了程序并行性。

4.3.3 Pluto調度算法

Pluto算法以自動實現(xiàn)循環(huán)分塊為目的，在實施循環(huán)分塊之前試圖尋找能夠最大化循環(huán)分塊可能性的循環(huán)變化組合。

Pluto調度算法的核心是兼顧程序并行性和數(shù)據(jù)局部性的前提下，利用一種定義良好的代價模型，自動確定有利于實現(xiàn)循環(huán)分塊的順序關系，通過計算原始程序的順序關系和新的順序關系之間的映射函數(shù)，自動實現(xiàn)循環(huán)分塊友好的循環(huán)變換組合。

4.4 仿射循環(huán)變換

任何能用多維仿射變換表示的循環(huán)變換都成為仿射循環(huán)變換。Pluto調度算法先進行仿射變換，然后在循環(huán)分塊。

4.4.1 循環(huán)交換interchange

向量化：使用向量寄存器；并行化：無依賴；

循環(huán)交換將完美嵌套循環(huán)的兩個循環(huán)順序進行交換，通過這種技術既可以將可向量化的循環(huán)移動到循環(huán)嵌套的最內層以提高程序的向量化效果，也可以將可并行化的循環(huán)移動到循環(huán)嵌套最外層以增加程序的并行粒度，減少同步開銷。

Pluto調度算法的代價模型是面向多核架構設計的，所以Pluto算法在實現(xiàn)循環(huán)交換時，更傾向于將可并行化的循環(huán)移動到循環(huán)嵌套的外層，以提高并行的粒度，并降低同步開銷。

4.4.2 循環(huán)反轉reversal

循環(huán)反轉是一種將循環(huán)嵌套某一層循環(huán)的迭代方向進行反轉，并將循環(huán)步長設置為原始值的相反數(shù)。

for (int i = 1; i < M; i++)for (int j = 1; j < N; j++)for (int k = 0; k < K - 1; k++)A[i][j][k] = A[i][j-1][k+1] + A[i-1][j][k+1];// reverse loop
for (int k = K-2; k >= 0; k--)#pragema omp parallel forfor (int i = 1; i < M; i++)for (int j = 1; j < N; j++)A[i][j][-k] = A[i][j-1][-k+1] + A[i-1][j][-k+1];

4.4.3 循環(huán)延展scaling

循環(huán)延展通過延展循環(huán)索引變量的取值范圍和循環(huán)步長的技術，目的在于將程序中不規(guī)則的依賴轉換成災迭代空間上全局一致的依賴，從而使程序迭代之間的依賴距離向量分量能夠用整數(shù)表示，依此來為其他循環(huán)變換創(chuàng)造機會。

for (int i = 0; i < N; i++)f[i] = fin[i];
for (int i = 0; i < N/2; i++)g[i] = f[2*i+1] * f[2*i-1];
for (int i = 0; i < N; i++)h[i] = g[i/2+1] * g[i/2];

將g[i]循環(huán)以延展為2展開，所有循環(huán)迭代之間的依賴在整個迭代空間上全局一致，且3個循環(huán)還可以合并。

4.4.4 循環(huán)傾斜skewing

循環(huán)傾斜通過改變完美循環(huán)嵌套對應迭代空間形狀的循環(huán)變換技術，但并不會改變迭代之間的執(zhí)行順序。例如(t, i) --> (t, 2t+i)。

for(t = 0; t < T; t+=1)for(i = 0; i < N; i+=1)A[t+1][i] = 0.25 * (A[t][i+1] -2*A[t][i] + A[t][i-1]);

4.4.5 循環(huán)合并fussion

循環(huán)合并是一種通過將多個循環(huán)嵌套融合在一起形成一個統(tǒng)一的迭代空間，從而便于編譯器實現(xiàn)其他優(yōu)化的循環(huán)變換技術。循環(huán)合并本身是一個非常復雜的過程，合并后的循環(huán)可能會失去并行性或無法實現(xiàn)循環(huán)分塊，因為可能產生的依賴問題。循環(huán)合并通過循環(huán)的融合縮短程序數(shù)據(jù)之間的“生產--使用”距離，從而提高數(shù)據(jù)的局部性。

4.4.6 循環(huán)分裂fission

循環(huán)分裂是一種將一個循環(huán)嵌套在分裂成多個循環(huán)嵌套的循環(huán)變換技術。循環(huán)分裂通過將循環(huán)嵌套某層循環(huán)上的循環(huán)攜帶依賴轉換為循環(huán)無關依賴，來提升循環(huán)的并行性。

4.5 近似仿射變換

在仿射循環(huán)變換中，用于循環(huán)變換的表達式只包含加減法，乘法以及這些操作的組合，并且表示循環(huán)變換的仿射變換中不會涉及存在量詞。在一些循環(huán)變換中，除法、取模以及存在量詞是不可避免的，所以需要借助近似仿射表達式來表示循環(huán)變換。

4.5.1 循環(huán)分塊blocking

循環(huán)分塊將循環(huán)嵌套空間劃分成不同的分塊并改變循環(huán)迭代執(zhí)行順序的循環(huán)變換技術。如果在未經(jīng)循環(huán)傾斜的原始迭代空間上能夠實現(xiàn)正確的循環(huán)分塊，那么就稱為矩形分塊。在經(jīng)過一些仿射循環(huán)變換的組合之后才能進行循環(huán)分塊所得到形狀可能是平行四邊形后者其他形狀。

4.5.2 循環(huán)分段strip-mining

循環(huán)分段將一個循環(huán)的迭代空間分成多個子集，并將每個子集作為一個調度單元進行執(zhí)行的循環(huán)變換技術。在多核架構中，循環(huán)分段的實現(xiàn)往往是隱式地分配單個循環(huán)迭代空間的不同子集給不同線程。但是在多級并行硬件抽象的體系結構，例如GPU上的線程塊和線程，循環(huán)分段必須顯式執(zhí)行。

由編譯器顯式實現(xiàn)的循環(huán)分段往往會帶來額外的循環(huán)執(zhí)行開銷，因為引入了新的循環(huán)邊界判斷條件。除非能提升程序的并行性，否則并不鼓勵在優(yōu)化編譯器中顯示地實現(xiàn)循環(huán)分段。循環(huán)分段也可看做循環(huán)分塊在單層循環(huán)上的特殊情況。

4.5.3 循環(huán)展開壓緊unroll and jam

循環(huán)展開壓緊將某兩層的外層循環(huán)展開后再將內層循環(huán)進行合并的循環(huán)變換技術，壓緊效果在于減少了向量寄存器取數(shù)操作的次數(shù)，和展開效果在于增加不同計算功能部件之間的指令流水線并行效率。

4.6 代碼生成過程的循環(huán)變換

代碼生成過程中的循環(huán)變換包括分塊分離、循環(huán)展開和循環(huán)剝離。

4.6.1 分塊分離tile isolation

在迭代空間邊界上由于與迭代空間相交而被舍去部分區(qū)域的分塊被稱為半塊，其他沒有被舍去的分塊為整塊。分塊分離式一種將半塊和整塊分離，以消除循環(huán)嵌套中的重疊邊界條件限定條件（min、max）。

分開分離通過消除生成代碼中循環(huán)邊界的min和max等限定邊界操作，使得生成的代碼能夠對一些領域特定的加速芯片友好。

4.6.2 循環(huán)展開unrolling

循環(huán)展開是一種通過展開循環(huán)迭代來降低循環(huán)條件分支開銷的循環(huán)變換技術，提高指令間流水并行，并降低用于循環(huán)邊界判定的控制開銷，還為向量化創(chuàng)造條件，但注意寄存器溢出。

4.6.3 其他循環(huán)優(yōu)化

循環(huán)剝離peeling將循環(huán)某些迭代從循環(huán)主體中剝離出來的循環(huán)變換技術。循環(huán)中有時只有部分迭代會產生依賴，當這些循環(huán)迭代是循環(huán)的前幾個或后幾個迭代的時候，優(yōu)化編譯器就可以通過循環(huán)剝離的方法，將原來循環(huán)轉換為兩部分。

循環(huán)判斷外提unswitching將循環(huán)內與循環(huán)索引無關的條件謂詞外提到循環(huán)外的技術，降低分支開銷，減少代碼量。

4.7 循環(huán)壓緊

循環(huán)壓緊coalescing將多層循環(huán)嵌套壓縮成單層循環(huán)的技術。