目錄

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

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

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

1.1.2存儲(chǔ)層次結(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集合與映射的運(yùn)算 .34

2.3 Fourier-Motzkin消去法38

2.4調(diào)度樹 41

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

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

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

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

2.5抽象語(yǔ)法樹50

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

2.5.2上下文信息 .51

2.5.3結(jié)點(diǎn)和表達(dá)式52

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

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

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

2.6.3抽象語(yǔ)法樹的實(shí)現(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)無(wú)關(guān)依賴和循環(huán)攜帶依賴 67

3.2.4依賴與變換 .68

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

3.3依賴測(cè)試 .72

3.3.1精確測(cè)試與保守測(cè)試73

3.3.2 ZIV測(cè)試 74

3.3.3 SIV測(cè)試 74

3.3.4 GCD測(cè)試 78

3.3.5 Banerjee測(cè)試 .79

3.3.6 I測(cè)試.80

3.4耦合下標(biāo)依賴測(cè)試82

3.4.1擴(kuò)展的 GCD測(cè)試 .83

3.4.2 ζ測(cè)試 84

3.4.3 Delta測(cè)試 85

3.4.4 Omega測(cè)試86

3.5特殊的依賴測(cè)試 .89

3.5.1 D測(cè)試 .89

3.5.2 Range依賴測(cè)試 90

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

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

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

3.6.3帶標(biāo)記的數(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代碼生成過(guò)程中的循環(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一維時(shí)間表示的調(diào)度計(jì)算 . 153

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

5.4開發(fā)向量化 164

5.4.1可向量化 Codelet 165

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

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

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

5.5.2通信優(yōu)化 176

第 6章挖掘局部性 .179

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

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

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

6.2.2拆分弱連通圖 183

6.2.3合并強(qiáng)連通分量 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)存競(jìng)爭(zhēng)關(guān)系 213

6.6.2劃分?jǐn)?shù)據(jù)空間 215

6.6.3代價(jià)模型 218

第 7章代碼生成.221

7.1一個(gè)比輸出指令序列更復(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語(yǔ)句的生成位置 . 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章多面體編譯理論的最新進(jìn)展 247

8.1 MLIR . 247

8.1.1 MLIR基本概念 249

8.1.2與多面體模型的集成 253

8.2 Halide. 258

8.2.1 Halide設(shè)計(jì)理念 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的自動(dòng)代碼生成 280

參考文獻(xiàn) .285