目录
第 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.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
