[正版新书] 多面体编译理论与深度学习实践 赵捷、李宝亮 清华大学出版社 编译技术;深度学习;芯片设计

赵捷，2009年于清华大学获得工学学士学位，2018年于法国巴黎高等师范学校获得工学博士学位，现就职于数学工程与先进计算国家重点实验室。赵捷博士长期从事编译器高级优化和代码生成方面的研究，目前主要从事深度学习编译器的研究。

李宝亮，2009年于清华大学获工学学士学位，2014年赴加拿大麦吉尔大学交流访问，2015年于国防科学技术大学获工学博士学位。李宝亮博士长期从事体系结构性能分析优化方面的研究，目前主要从事深度学习专用加速芯片的研制和相关系统软件和编程语言的开发。

本书利用多面体模型描述了如何实现不同阶段循环变换技术，是国内首个详细介绍该模型和循环优化技术的特殊编译参考书籍。

目录

第 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