多面体编译理论与深度学习实践

第 1章体系结构发展对编译技术的影响 1

1

1面向经典体系结构的性能优化 1

1

11并行性发掘 1

1

12存储层次结构3

1

13领域专用架构4

1

2编译器面临的挑战7

1

21并行性发掘 8

1

22局部性发掘 10

1

23编程模型和抽象层次11

1

3循环优化的数学抽象 12

1

31多面体模型的基本概念 12

1

32多面体模型在编译器中的应用 15

1

33基于多面体模型的编译流程16

第 2章程序抽象表示基础 25

2

1抽象表示在编译器中发挥的作用25

2

2整数集合与仿射函数 28

2

21静态仿射约束28

222整数集合

29

223仿射函数

32

2

24集合与映射的运算 34

23

Fourier-Motzkin消去法38

24调度树

41

2

41调度的表示方式 41

2

42调度树的结点44

2

43调度树的操作47

2

44调度表示的比较 49

25抽象语法树

50

2

51被执行关系 50

2

52上下文信息 51

2

53结点和表达式52

2

6各种抽象的工程实现 53

261整数集合和仿射函数的实现54

262调度树的实现58

263抽象语法树的实现 59

第 3章依赖关系分析 61

31依赖关系分析在编译优化中的作用 61

32依赖及其性质 62

321依赖的分类 65

322距离向量与方向向量66

323循环无关依赖和循环携带依赖 67

324依赖与变换 68

325依赖的复杂性69

33依赖测试 72

331精确测试与保守测试73

332 ZIV测试 74

333 SIV测试 74

334 GCD测试 78

335 Banerjee测试 79

336 I测试80

34耦合下标依赖测试82

341扩展的 GCD测试 83

342 ζ测试 84

343 Delta测试 85

344 Omega测试86

35特殊的依赖测试 89

351 D测试 89

352 Range依赖测试 90

36数据流分析91

361精确数据流分析 93

362近似数据流分析 96

363带标记的数据流分析98

37依赖与并行化 99

第 4章循环变换103

41适配体系结构特征的关键技术 103

42预处理 104

421循环正规化 104

422死代码删除 105

423别名分析 106

424迭代空间分裂 106

43多面体模型中的循环变换 107

431循环变换分类 108

432循环变换的复杂性 109

433 Pluto调度算法 113

44仿射循环变换 124

441循环交换 124

442循环反转 126

443循环延展 127

444循环倾斜 128

445循环合并 130

446循环分布 131

45近似仿射循环变换 133

451循环分块 133

452循环分段 135

453循环展开压紧 137

46代码生成过程中的循环变换 139

461分块分离 139

462循环展开 140

463其他循环变换 141

47循环压紧 141

第 5章开发并行性 143

51利用多面体模型发掘数据并行 143

52复杂的分块形状 144

521交叉分块 144

522分裂分块 146

523钻石分块 149

524六角形分块 151

53 Feautrier调度算法 153

531一维时间表示的调度计算 153

532多维时间表示的调度计算 159

54开发向量化 164

541可向量化 Codelet 165

542利于向量化的调度算法 166

55面向分布式存储结构的并行 172

551构造通信数据集 173

552通信优化 176

第 6章挖掘局部性 179

61金字塔形存储层次结构之外的挑战 179

62面向不同优化目标的循环合并策略 180

621基于依赖图的循环合并算法 181

622拆分弱连通图 183

623合并强连通分量 184

63循环合并与循环分块的组合 185

631先合并后分块 186

632分块后再合并 189

633提升高速缓存的使用率 192

64数据空间变换 195

641间接数据空间变换 195

642显式数据空间变换 198

65提升局部性的调度优化 202

651循环分块后的重新调度 202

652面向数据访存连续性的调度优化 203

66数组压缩 213

661内存竞争关系 213

662划分数据空间 215

663代价模型 218

第 7章代码生成221

71一个比输出指令序列更复杂的任务 221

72代码生成方法 222

721凸包算法 222

722分割算法 224

73分割代码生成 227

731 for循环生成 228

732 if语句的生成位置 234

733循环展开 234

734分块分离 236

735循环退化 237

736带偏移的跨步循环 238

74 if控制流优化 239

75内存管理 240

751 CPU与 GPU间的传输 241

752内存提升 243

76同步指令 245

第 8章多面体编译理论的*新进展 247

81 MLIR 247

811 MLIR基本概念 249

812与多面体模型的集成 253

82 Halide 258

821 Halide设计理念 259

822 Halide调度树 260

83 Tiramisu 265

84 Tensor Comprehensions 270

85 AKG 275

86面向 Tensor Core的自动代码生成 280

参考文献 285