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

《多面體編譯理論與深度學習實踐》是2022年清華大學出版社出版的圖書，作者是趙捷、李寶亮。

基本介紹

• 中文名：多面體編譯理論與深度學習實踐
• 作者：趙捷、李寶亮
• 出版社：清華大學出版社
• 出版時間：2022年11月1日
• 定價：138 元
• ISBN：9787302616467

內容簡介

本書分十大章節和三章附錄章節，以現代體系結構特徵為目標，從理論、方法及套用等不同角度，詳細描述了各種提升程式並行性、數據局部性及適配目標架構特徵的高級編譯最佳化技術。本書還結合深度學習套用場景展開討論，介紹了如何在深度學習框架中使用高級編譯最佳化技術。

圖書目錄

第 1章體系結構發展對編譯技術的影響 .............................................................. 1

1.1面向經典體系結構的性能最佳化 ...................................................................1

1.1.1並行性發掘 ...................................................................................1

1.1.2存儲層次結構................................................................................3

1.1.3領域專用架構................................................................................4

1.2編譯器面臨的挑戰....................................................................................7

1.2.1並行性發掘 ...................................................................................8

1.2.2局部性發掘 .................................................................................10

1.2.3編程模型和抽象層次....................................................................11

1.3循環最佳化的數學抽象 ..............................................................................12

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

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

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

第 2章程式抽象表示基礎 .................................................................................25

2.1抽象表示在編譯器中發揮的作用..............................................................25

2.2整數集合與仿射函式 ..............................................................................28

2.2.1靜態仿射約束..............................................................................28

2.2.2整數集合....................................................................................29

2.2.3仿射函式....................................................................................32

2.2.4集合與映射的運算 .......................................................................34

2.3Fourier-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被執行關係 .................................................................................50

2.5.2上下文信息 .................................................................................51

2.5.3結點和表達式..............................................................................52

2.6各種抽象的工程實現 ..............................................................................53

2.6.1整數集合和仿射函式的實現..........................................................54

2.6.2調度樹的實現..............................................................................58

2.6.3抽象語法樹的實現 .......................................................................59

第 3章依賴關係分析 ........................................................................................61

3.1依賴關係分析在編譯最佳化中的作用 ..........................................................61

3.2依賴及其性質 ........................................................................................62

3.2.1依賴的分類 .................................................................................65

3.2.2距離向量與方向向量....................................................................66

3.2.3循環無關依賴和循環攜帶依賴 ......................................................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數據流分析............................................................................................91

3.6.1精確數據流分析 ..........................................................................93

3.6.2近似數據流分析 ..........................................................................96

3.6.3帶標記的數據流分析....................................................................98

3.7依賴與並行化 ........................................................................................99

第 4章循環變換.............................................................................................103

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

4.2預處理 ................................................................................................ 104

4.2.1循環正規化 ............................................................................... 104

4.2.2死代碼刪除 ............................................................................... 105

4.2.3別名分析 .................................................................................. 106

4.2.4疊代空間分裂............................................................................ 106

4.3多面體模型中的循環變換...................................................................... 107

4.3.1循環變換分類............................................................................ 108

4.3.2循環變換的複雜性 ..................................................................... 109

4.3.3 Pluto調度算法 ......................................................................... 113

4.4仿射循環變換 ...................................................................................... 124

4.4.1循環交換 .................................................................................. 124

4.4.2循環反轉 .................................................................................. 126

4.4.3循環延展 .................................................................................. 127

4.4.4循環傾斜 .................................................................................. 128

4.4.5循環合併 .................................................................................. 130

4.4.6循環分布 .................................................................................. 131

4.5近似仿射循環變換................................................................................ 133

4.5.1循環分塊 .................................................................................. 133

4.5.2循環分段 .................................................................................. 135

4.5.3循環展開壓緊............................................................................ 137

4.6代碼生成過程中的循環變換 .................................................................. 139

4.6.1分塊分離 .................................................................................. 139

4.6.2循環展開 .................................................................................. 140

4.6.3其他循環變換............................................................................ 141

4.7循環壓緊 ............................................................................................. 141

第 5章開發並行性 .........................................................................................143

5.1利用多面體模型發掘數據並行 ............................................................... 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開發向量化.......................................................................................... 164

5.4.1可向量化 Codelet...................................................................... 165

5.4.2利於向量化的調度算法 .............................................................. 166

5.5面向分散式存儲結構的並行 .................................................................. 172

5.5.1構造通信數據集 ........................................................................ 173

5.5.2通信最佳化 .................................................................................. 176

第 6章挖掘局部性 .........................................................................................179

6.1金字塔形存儲層次結構之外的挑戰 ........................................................ 179

6.2面向不同最佳化目標的循環合併策略 ........................................................ 180

6.2.1基於依賴圖的循環合併算法........................................................ 181

6.2.2拆分弱連通圖............................................................................ 183

6.2.3合併強連通分量 ........................................................................ 184

6.3循環合併與循環分塊的組合 .................................................................. 185

6.3.1先合併後分塊............................................................................ 186

6.3.2分塊後再合併............................................................................ 189

6.3.3提升高速快取的使用率 .............................................................. 192

6.4數據空間變換 ...................................................................................... 195

6.4.1間接數據空間變換 ..................................................................... 195

6.4.2顯式數據空間變換 ..................................................................... 198

6.5提升局部性的調度最佳化 ......................................................................... 202

6.5.1循環分塊後的重新調度 .............................................................. 202

6.5.2面向數據訪存連續性的調度最佳化 ................................................. 203

6.6數組壓縮 ............................................................................................. 213

6.6.1記憶體競爭關係............................................................................ 213

6.6.2劃分數據空間............................................................................ 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循環生成 ............................................................................. 228

7.3.2 if語句的生成位置 ..................................................................... 234

7.3.3循環展開 .................................................................................. 234

7.3.4分塊分離 ................................................................................. 236

7.3.5循環退化 .................................................................................. 237

7.3.6帶偏移的跨步循環 ..................................................................... 238

7.4 if控制流最佳化....................................................................................... 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