多面體編譯理論與深度學(xué)習(xí)實踐

目錄

第 1章體系結(jié)構(gòu)發(fā)展對編譯技術(shù)的影響 1

1.1面向經(jīng)典體系結(jié)構(gòu)的性能優(yōu)化 .1

1.1.1并行性發(fā)掘 .1

1.1.2存儲層次結(jié)構(gòu)3

1.1.3領(lǐng)域?qū)Ｓ眉軜?gòu)4

1.1.2編譯器面臨的挑戰(zhàn)7

1.2.1并行性發(fā)掘 .8

1.2.2局部性發(fā)掘 .10

1.2.3編程模型和抽象層次11

1.3循環(huán)優(yōu)化的數(shù)學(xué)抽象 12

1.3.1多面體模型的基本概念 12

1.3.2多面體模型在編譯器中的應(yīng)用 15

1.3.3基于多面體模型的編譯流程16

第 2章程序抽象表示基礎(chǔ) .25

2.1抽象表示在編譯器中發(fā)揮的作用25

2.2整數(shù)集合與仿射函數(shù) 28

2.2.1靜態(tài)仿射約束28

2.2.2整數(shù)集合 29

2.2.3仿射函數(shù) 32

2.2.4集合與映射的運算 .34

2.3 Fourier-Motzkin消去法38

2.4調(diào)度樹 41

2.4.1調(diào)度的表示方式 41

2.4.2調(diào)度樹的結(jié)點44

2.4.3調(diào)度樹的操作47

2.4.4調(diào)度表示的比較 49

2.5抽象語法樹50

2.5.1被執(zhí)行關(guān)系 .50

2.5.2上下文信息 .51

2.5.3結(jié)點和表達式52

2.6各種抽象的工程實現(xiàn) 53

2.6.1整數(shù)集合和仿射函數(shù)的實現(xiàn)54

2.6.2調(diào)度樹的實現(xiàn)58

2.6.3抽象語法樹的實現(xiàn) .59

第 3章依賴關(guān)系分析 61

3.1依賴關(guān)系分析在編譯優(yōu)化中的作用 61

3.2依賴及其性質(zhì) 62

3.2.1依賴的分類 .65

3.2.2距離向量與方向向量66

3.2.3循環(huán)無關(guān)依賴和循環(huán)攜帶依賴 67

3.2.4依賴與變換 .68

3.2.5依賴的復(fù)雜性69

3.3依賴測試 .72

3.3.1精確測試與保守測試73

3.3.2 ZIV測試 74

3.3.3 SIV測試 74

3.3.4 GCD測試 78

3.3.5 Banerjee測試 .79

3.3.6 I測試.80

3.4耦合下標依賴測試82

3.4.1擴展的 GCD測試 .83

3.4.2 ζ測試 84

3.4.3 Delta測試 85

3.4.4 Omega測試86

3.5特殊的依賴測試 .89

3.5.1 D測試 .89

3.5.2 Range依賴測試 90

3.6數(shù)據(jù)流分析91

3.6.1精確數(shù)據(jù)流分析 93

3.6.2近似數(shù)據(jù)流分析 96

3.6.3帶標記的數(shù)據(jù)流分析98

3.7依賴與并行化 99

第 4章循環(huán)變換.103

4.1適配體系結(jié)構(gòu)特征的關(guān)鍵技術(shù) . 103

4.2預(yù)處理 104

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

4.2.2死代碼刪除 . 105

4.2.3別名分析 106

4.2.4迭代空間分裂 106

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

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

4.3.2循環(huán)變換的復(fù)雜性 . 109

4.3.3 Pluto調(diào)度算法 . 113

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

4.4.1循環(huán)交換 124

4.4.2循環(huán)反轉(zhuǎn) 126

4.4.3循環(huán)延展 127

4.4.4循環(huán)傾斜 128

4.4.5循環(huán)合并 130

4.4.6循環(huán)分布 131

4.5近似仿射循環(huán)變換 133

4.5.1循環(huán)分塊 133

4.5.2循環(huán)分段 135

4.5.3循環(huán)展開壓緊 137

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

4.6.1分塊分離 139

4.6.2循環(huán)展開 140

4.6.3其他循環(huán)變換 141

4.7循環(huán)壓緊 . 141

第 5章開發(fā)并行性 .143

5.1利用多面體模型發(fā)掘數(shù)據(jù)并行 . 143

5.2復(fù)雜的分塊形狀 . 144

5.2.1交叉分塊 144

5.2.2分裂分塊 146

5.2.3鉆石分塊 149

5.2.4六角形分塊 . 151

5.3 Feautrier調(diào)度算法. 153

5.3.1一維時間表示的調(diào)度計算 . 153

5.3.2多維時間表示的調(diào)度計算 . 159

5.4開發(fā)向量化 164

5.4.1可向量化 Codelet 165

5.4.2利于向量化的調(diào)度算法 166

5.5面向分布式存儲結(jié)構(gòu)的并行 172

5.5.1構(gòu)造通信數(shù)據(jù)集 173

5.5.2通信優(yōu)化 176

第 6章挖掘局部性 .179

6.1金字塔形存儲層次結(jié)構(gòu)之外的挑戰(zhàn) 179

6.2面向不同優(yōu)化目標的循環(huán)合并策略 180

6.2.1基于依賴圖的循環(huán)合并算法 181

6.2.2拆分弱連通圖 183

6.2.3合并強連通分量 184

6.3循環(huán)合并與循環(huán)分塊的組合 185

6.3.1先合并后分塊 186

6.3.2分塊后再合并 189

6.3.3提升高速緩存的使用率 192

6.4數(shù)據(jù)空間變換 195

6.4.1間接數(shù)據(jù)空間變換 . 195

6.4.2顯式數(shù)據(jù)空間變換 . 198

6.5提升局部性的調(diào)度優(yōu)化 . 202

6.5.1循環(huán)分塊后的重新調(diào)度 202

6.5.2面向數(shù)據(jù)訪存連續(xù)性的調(diào)度優(yōu)化 . 203

6.6數(shù)組壓縮 . 213

6.6.1內(nèi)存競爭關(guān)系 213

6.6.2劃分數(shù)據(jù)空間 215

6.6.3代價模型 218

第 7章代碼生成.221

7.1一個比輸出指令序列更復(fù)雜的任務(wù) 221

7.2代碼生成方法 222

7.2.1凸包算法 222

7.2.2分割算法 224

7.3分割代碼生成 227

7.3.1 for循環(huán)生成 . 228

7.3.2 if語句的生成位置 . 234

7.3.3循環(huán)展開 234

7.3.4分塊分離 . 236

7.3.5循環(huán)退化 237

7.3.6帶偏移的跨步循環(huán) . 238

7.4 if控制流優(yōu)化. 239

7.5內(nèi)存管理 . 240

7.5.1 CPU與 GPU間的傳輸 . 241

7.5.2內(nèi)存提升 243

7.6同步指令 . 245

第 8章多面體編譯理論的最新進展 247

8.1 MLIR . 247

8.1.1 MLIR基本概念 249

8.1.2與多面體模型的集成 253

8.2 Halide. 258

8.2.1 Halide設(shè)計理念 259

8.2.2 Halide調(diào)度樹 . 260

8.3 Tiramisu . 265

8.4 Tensor Comprehensions 270

8.5 AKG. 275

8.6面向 Tensor Core的自動代碼生成 280

參考文獻 .285