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

趙捷
2009年於清華大學獲得工學學士學位，2018年於法國巴黎高等師範學校獲得工學博士學位，
現就職於數學工程與先進計算國家重點實驗室。
趙捷博士長期從事編譯器高級優化和代碼生成方面的研究，目前主要從事深度學習編譯器的研究。

李寶亮
2009年於清華大學獲工學學士學位，2014年赴加拿大麥吉爾大學交流訪問，2015年於國防科學技術大學獲工學博士學位。
李寶亮博士長期從事體系結構性能分析優化方面的研究，
目前主要從事深度學習專用加速芯片的研製和相關係統軟件和編程語言的開發。

目錄

第1章體系結構發展對編譯技術的影響 1
1.1面向經典體系結構的性能優化.1
1.1.1並行性發掘.1
1.1.2存儲層次結構3
1.1.3領域專用架構4
1.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.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被執行關係.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