多面體編譯理論與深度學習實踐

目錄

第 1章體系結構發(fā)展對編譯技術的影響 1

1.1面向經典體系結構的性能優(yōu)化 .1

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

1.1.2存儲層次結構3

1.1.3領域專用架構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ù)學抽象 12

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

1.3.2多面體模型在編譯器中的應用 15

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

第 2章程序抽象表示基礎 .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調度樹 41

2.4.1調度的表示方式 41

2.4.2調度樹的結點44

2.4.3調度樹的操作47

2.4.4調度表示的比較 49

2.5抽象語法樹50

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

2.5.2上下文信息 .51

2.5.3結點和表達式52

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

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

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

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

第 3章依賴關系分析 61

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

3.2依賴及其性質 62

3.2.1依賴的分類 .65

3.2.2距離向量與方向向量66

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

3.2.4依賴與變換 .68

3.2.5依賴的復雜性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ù)據流分析91

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

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

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

3.7依賴與并行化 99

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

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

4.2預處理 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)變換的復雜性 . 109

4.3.3 Pluto調度算法 . 113

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

4.4.1循環(huán)交換 124

4.4.2循環(huá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ù)據并行 . 143

5.2復雜的分塊形狀 . 144

5.2.1交叉分塊 144

5.2.2分裂分塊 146

5.2.3鉆石分塊 149

5.2.4六角形分塊 . 151

5.3 Feautrier調度算法. 153

5.3.1一維時間表示的調度計算 . 153

5.3.2多維時間表示的調度計算 . 159

5.4開發(fā)向量化 164

5.4.1可向量化 Codelet 165

5.4.2利于向量化的調度算法 166

5.5面向分布式存儲結構的并行 172

5.5.1構造通信數(shù)據集 173

5.5.2通信優(yōu)化 176

第 6章挖掘局部性 .179

6.1金字塔形存儲層次結構之外的挑戰(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ù)據空間變換 195

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

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

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

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

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

6.6數(shù)組壓縮 . 213

6.6.1內存競爭關系 213

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

6.6.3代價模型 218

第 7章代碼生成.221

7.1一個比輸出指令序列更復雜的任務 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內存管理 . 240

7.5.1 CPU與 GPU間的傳輸 . 241

7.5.2內存提升 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設計理念 259

8.2.2 Halide調度樹 . 260

8.3 Tiramisu . 265

8.4 Tensor Comprehensions 270

8.5 AKG. 275

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

參考文獻 .285