编译原理 依赖于机器的优化10

1、第十章第十章 依赖于机器的优化依赖于机器的优化 在指令级并行的机器上，程序的运行速度依在指令级并行的机器上，程序的运行速度依 赖于下面几个因素赖于下面几个因素 程序中潜在的并行程序中潜在的并行 处理器上可用的并行处理器上可用的并行 从串行程序提取并行的能力从串行程序提取并行的能力 在给定的调度约束下发现最佳并行调度的能力在给定的调度约束下发现最佳并行调度的能力 并行的提取和并行执行的调度都可以静态地并行的提取和并行执行的调度都可以静态地 在软件中或动态地在硬件中完成在软件中或动态地在硬件中完成 第十章第十章 依赖于机器的优化依赖于机器的优化 本章内容本章内容 使用使用指令级并行指令级并行的基础

2、问题的基础问题 提取并行的数据相关性分析提取并行的数据相关性分析 代码调度的基本概念代码调度的基本概念 基本块调度的技术、发现通用程序中的高度数据基本块调度的技术、发现通用程序中的高度数据 相关控制流的方法、调度数值程序的软件流水线相关控制流的方法、调度数值程序的软件流水线 技术技术 在在多处理器系统多处理器系统上，使用数组的计算密集型程序上，使用数组的计算密集型程序 的并行化和数据局部性优化的概念和方法的并行化和数据局部性优化的概念和方法 10.1 处理器体系结构处理器体系结构 在考虑指令级并行时，通常想象成一个处理在考虑指令级并行时，通常想象成一个处理 器在单个时钟周期内发射几个操作器在单

3、个时钟周期内发射几个操作 事实上，在每周期内发射一个操作是可能的事实上，在每周期内发射一个操作是可能的, 而指令级并行的获得是通过使用流水线技术而指令级并行的获得是通过使用流水线技术 本节先解释流水线，然后讨论多指令发射本节先解释流水线，然后讨论多指令发射 10.1 处理器体系结构处理器体系结构 10.1.1 指令流水线和分支延迟指令流水线和分支延迟 ii + 1i + 2i + 3i + 4 1. if 2. idif 3. exidif 4. memexidif 5. wbmemexidif 6.wbmemexid 7.wbmemex 8.wbmem 9.wb 取指令取指令if, 译码译码

4、id, 执行操作执行操作ex, 访问内存访问内存mem, 回写结果回写结果wb 5级指令流水线中级指令流水线中 的的5条连续指令条连续指令 10.1 处理器体系结构处理器体系结构 10.1.1 指令流水线和分支延迟指令流水线和分支延迟 分支延迟分支延迟 发现应该执行一个分支而不是直接后继发现应该执行一个分支而不是直接后继 转向一个分支时会引起取分支目的地址指令的延转向一个分支时会引起取分支目的地址指令的延 迟并引起指令流水线迟并引起指令流水线“打嗝打嗝” 可以通过使用硬件，根据分支的执行历史来预测可以通过使用硬件，根据分支的执行历史来预测 分支结果并从预测的目的地址预取指令分支结果并从预测的目

5、的地址预取指令 分支延迟不可避免，因为分支预测会发生偏差分支延迟不可避免，因为分支预测会发生偏差 10.1 处理器体系结构处理器体系结构 10.1.2 流水化的执行流水化的执行 如果不依赖一条指令结果的随后指令在该结如果不依赖一条指令结果的随后指令在该结 果产生前就被允许执行果产生前就被允许执行 有些指令的执行需要几个周期，几个操作同时出有些指令的执行需要几个周期，几个操作同时出 现在它们的执行级上可能的现在它们的执行级上可能的 如果最长的执行流水线是如果最长的执行流水线是n级，级，n个操作同时进行个操作同时进行 的可能性是存在的的可能性是存在的 并非所有的指令都能被完全流水化，例如浮点除并非

6、所有的指令都能被完全流水化，例如浮点除 通用处理器大都动态察觉相继指令之间的依赖性通用处理器大都动态察觉相继指令之间的依赖性 嵌入式系统把数据相关性的检查交给软件嵌入式系统把数据相关性的检查交给软件 10.1 处理器体系结构处理器体系结构 10.1.3 多指令发射多指令发射 每周期发射几个操作，让更多操作同时进行每周期发射几个操作，让更多操作同时进行 超长指令字机器超长指令字机器 将若干个操作编码在单周期中发射将若干个操作编码在单周期中发射 编译器需要确定哪些操作可以并行发射编译器需要确定哪些操作可以并行发射 超标量机器超标量机器 超标量机器有按普通顺序执行语义的正规指令集超标量机器有按普通顺

7、序执行语义的正规指令集 硬件自动察觉指令之间的相关性，并且在它们的硬件自动察觉指令之间的相关性，并且在它们的 操作数可用时就发射它们操作数可用时就发射它们 更复杂的调度器能够更复杂的调度器能够“乱序乱序”执行指令执行指令 10.2 代码调度的约束代码调度的约束 代码调度代码调度 用在代码生成器产生的机器代码上的优化技术用在代码生成器产生的机器代码上的优化技术 本节讨论代码调度的约束本节讨论代码调度的约束 控制相关约束控制相关约束 在原程序中执行的所有操作都在原程序中执行的所有操作都 必须在优化代码中执行必须在优化代码中执行 数据相关约束数据相关约束 优化程序中的操作产生的结果优化程序中的操作产

8、生的结果 必须同原程序对应操作的结果一样必须同原程序对应操作的结果一样 资源约束资源约束 调度不能过分占用机器的资源调度不能过分占用机器的资源 优化程序很难调试优化程序很难调试 内存状态可能和顺序执行的任何内存状态不匹配内存状态可能和顺序执行的任何内存状态不匹配 10.2 代码调度的约束代码调度的约束 10.2.1 数据相关数据相关 真相关真相关 如果对同一个单元先写后读，那么如果对同一个单元先写后读，那么 读依赖于所写的值读依赖于所写的值 反相关反相关 如果对同一个单元先读后写。可以如果对同一个单元先读后写。可以 通过把值存在不同的单元来删除反相关通过把值存在不同的单元来删除反相关 输出相关

9、输出相关 如果对同一个单元先后写两次。也如果对同一个单元先后写两次。也 可删除可删除 数据相关概念可同时用于内存访问和寄存器数据相关概念可同时用于内存访问和寄存器 访问访问 10.2 代码调度的约束代码调度的约束 10.2.2 发现内存访问中的相关性发现内存访问中的相关性 例例 (1) a = 1 (2) p = 2 (3) x = a 语句语句(1)和和(2)可能构成输出相关可能构成输出相关 语句语句(1)和和(3)可能构成真相关可能构成真相关 语句语句(2)和和(3)可能构成真相关可能构成真相关 除非编译器知道除非编译器知道p不可能指向不可能指向a，否则，否则3个操作必个操作必 须串行执行

10、须串行执行 10.2 代码调度的约束代码调度的约束 10.2.2 发现内存访问中的相关性发现内存访问中的相关性 发现数据相关需要不同形式的分析发现数据相关需要不同形式的分析 数组元素间的别名分析数组元素间的别名分析 ai和和aj是否互为别名是否互为别名 指针别名分析指针别名分析 若若p和和q相等，则相等，则 p和和 q、p-next和和q-next、 p-data和和q-data等都分别互为别名等都分别互为别名 过程间分析过程间分析 引用调用场合：形参和形参之间、形参和全局变引用调用场合：形参和形参之间、形参和全局变 量之间因实参而引起互为别名量之间因实参而引起互为别名 10.2 代码调度的约

11、束代码调度的约束 10.2.3 寄存器使用和并行执行之间的折衷寄存器使用和并行执行之间的折衷 例：例：(a + b) + c + (d + e) ld r1, a ld r2, b add r1, r1, r2 ld r2, c add r1, r1, r2 ld r2, d ld r3, e add r2, r2, r3 add r1, r1, r2 + e + c + ab + d 若瞄准极小化寄存器若瞄准极小化寄存器 的使用个数，则只需的使用个数，则只需 使用使用3个寄存器个寄存器 10.2 代码调度的约束代码调度的约束 10.2.3 寄存器使用和并行执行之间的折衷寄存器使用和并行执行之

12、间的折衷 例：例：(a + b) + c + (d + e) ld r1, a ld r2, b add r1, r1, r2 ld r2, c add r1, r1, r2 ld r2, d ld r3, e add r2, r2, r3 add r1, r1, r2 + e + c + ab + d 完成整个计算需要完成整个计算需要7步步 10.2 代码调度的约束代码调度的约束 10.2.3 寄存器使用和并行执行之间的折衷寄存器使用和并行执行之间的折衷 例：例：(a + b) + c + (d + e) + e + c + ab + d 如果对每个中间结果如果对每个中间结果 使用不同寄存器

13、，则使用不同寄存器，则 完成计算只需要完成计算只需要4步步 r1 = a r6 = r1+r2 r8 = r6+r3 r9 = r8+r7 r2 = b r7 = r4+r5 r3 = cr4 = d r5 = e 10.2 代码调度的约束代码调度的约束 10.2.4 寄存器分配和代码调度的次序安排寄存器分配和代码调度的次序安排 先寄存器分配先寄存器分配 结果代码中会有很多存储相关结果代码中会有很多存储相关 非数值应用本质上没有多少并行，采用这种方式非数值应用本质上没有多少并行，采用这种方式 先代码调度先代码调度 导致寄存器溢出，抵消指令级并行的优点导致寄存器溢出，抵消指令级并行的优点 适用于

14、有许多大表达式的数值应用适用于有许多大表达式的数值应用 在假定伪寄存器就是物理寄存器情况下，先调度在假定伪寄存器就是物理寄存器情况下，先调度 指令，然后寄存器分配，把处理寄存器溢出的代指令，然后寄存器分配，把处理寄存器溢出的代 码附加在必要的地方，并再次进行代码调度码附加在必要的地方，并再次进行代码调度 10.2 代码调度的约束代码调度的约束 10.2.5 控制相关控制相关 在非数值计算中，基本块非常小，其中的操作通在非数值计算中，基本块非常小，其中的操作通 常高度相关，几乎不能并行常高度相关，几乎不能并行 调查跨基本块的并行是至关重要的调查跨基本块的并行是至关重要的 若一条指令很可能被执行且

15、有空闲的资源可若一条指令很可能被执行且有空闲的资源可“免免 费费”用于完成该指令的操作，则可以投机地执行用于完成该指令的操作，则可以投机地执行 该指令；若投机成功，则程序运行得快一些该指令；若投机成功，则程序运行得快一些 例例 if (a t) b = a a依赖于比较依赖于比较a t的结果的结果 b = a a; 若若a a不会产生副作用，则不会产生副作用，则 d = a + c; a a可以投机地执行可以投机地执行 10.2 代码调度的约束代码调度的约束 10.2.6 投机执行的支持投机执行的支持 内存读取是一类使用频繁，且能从投机执行大大内存读取是一类使用频繁，且能从投机执行大大 获益的

16、指令获益的指令 但在但在 if (p != null) q = p 中，投机地对中，投机地对p脱引用将引起该程序因脱引用将引起该程序因p等于等于null 而错误地停止而错误地停止 许多高性能处理器提供专门的特性来支持投机地许多高性能处理器提供专门的特性来支持投机地 内存访问内存访问 10.2 代码调度的约束代码调度的约束 10.2.6 投机执行的支持投机执行的支持 预取指令预取指令在数据使用前将其从内存取到缓存在数据使用前将其从内存取到缓存, 若该单元无效或访问它会引起缺页，则忽略若该单元无效或访问它会引起缺页，则忽略 抑制位抑制位允许投机地从内存将数据读取到寄允许投机地从内存将数据读取到寄

17、存器堆，若出现非法内存访问或缺页，则设置目存器堆，若出现非法内存访问或缺页，则设置目 标寄存器的抑制位标寄存器的抑制位 判定指令判定指令在判定条件为真时才执行的指令在判定条件为真时才执行的指令 例例 if (a = 0)翻译成翻译成 add r3, r4, r5 b = c + d; cmovz r2, r3, r1 假定假定a、b、c和和d分别被分配了分别被分配了r1、r2、r4和和r5 可用来将相邻基本块组合成一个更大基本块可用来将相邻基本块组合成一个更大基本块 10.2 代码调度的约束代码调度的约束 10.2.7 一个基本的机器模型一个基本的机器模型 机器模型机器模型m = (r, t)

18、 t：操作类型集，如读取、存储和算术运算等：操作类型集，如读取、存储和算术运算等 r = r1, r2, ：硬件资源向量集，如内存访问部：硬件资源向量集，如内存访问部 件、算术运算部件和浮点功能部件件、算术运算部件和浮点功能部件 ri代表第代表第i类资源中可用的部件数类资源中可用的部件数 每个操作有一组输入操作数、一组输出操作数和每个操作有一组输入操作数、一组输出操作数和 一个资源需求一个资源需求 和每个输入操作数相关的是一个输入延迟和每个输入操作数相关的是一个输入延迟 和每个输出操作数相关的是一个输出延迟和每个输出操作数相关的是一个输出延迟 10.2 代码调度的约束代码调度的约束 10.2.

19、7 一个基本的机器模型一个基本的机器模型 机器模型机器模型m = (r, t) 对每种操作类型对每种操作类型t，资源使用由一张二维资源预留，资源使用由一张二维资源预留 表表rtt来建模来建模 条目条目rtti, j是是t类型的一个操作在它被发射类型的一个操作在它被发射i时钟时钟 周期后，使用第周期后，使用第j种资源的部件数种资源的部件数 对任何对任何t、i和和j，rtti, j必须小于或等于必须小于或等于rj 10.3 基基 本本 块块 调调 度度 10.3.1 数据依赖图数据依赖图 基本块由数据依赖图基本块由数据依赖图g = (n, e)来表示来表示 结点集合结点集合n表示该块的机器指令中的

20、操作集合表示该块的机器指令中的操作集合 有向边集合有向边集合e表示这些操作之间的数据相关约束表示这些操作之间的数据相关约束 g的结点集的结点集n和边集和边集e按如下两步构造按如下两步构造 n中的每个操作中的每个操作n有一张资源预留表有一张资源预留表rtn，其值直，其值直 接就是接就是n的操作类型的资源预留表的操作类型的资源预留表 每条边每条边e都标示有延迟都标示有延迟de，表示，表示e的目的结点必须的目的结点必须 在它源结点发射在它源结点发射de个时钟周期之后才可以发射个时钟周期之后才可以发射 10.3 基基 本本 块块 调调 度度 数据依赖图数据依赖图资源预留表资源预留表 alu men l

21、d r2, 0(r1) st 4(r1), r2 ld r3, 8(r1) add r3, r3, r2 add r3, r3, r4 st 0(r7), r7 st 12(r1), r3 2 2 2 111 1 1 1 i1 i2 i3 i4 i5 i6 i7 灰色表灰色表 示示1 白色表白色表 示示0 操作是全流水操作是全流水 的，只需显示的，只需显示 在第在第1行使用行使用 的资源的资源 10.3 基基 本本 块块 调调 度度 10.3.2 基本块的表调度基本块的表调度 关键路径包括最后关键路径包括最后5个结点，故第个结点，故第3条指令先调度条指令先调度 再调度第再调度第1条指令，因为第

22、条指令，因为第4条指令还需等条指令还需等1周期周期 第第4周期调度周期调度2条条 资源预留表资源预留表 alu men 调度表调度表 ld r3, 8(r1) add r3, r3, r2 add r3, r3, r4 st 0(r7), r7 st 12(r1), r3 st 4(r1), r2 ld r2, 0(r1) 10.3 基基 本本 块块 调调 度度 10.3.2 基本块的表调度基本块的表调度 根据每个结点同先前已经被调度的各结点之间的根据每个结点同先前已经被调度的各结点之间的 数据相关约束，来计算一个结点可以执行的最早数据相关约束，来计算一个结点可以执行的最早 时间槽时间槽 这个

23、结点所需资源根据一张资源预留表来进行检这个结点所需资源根据一张资源预留表来进行检 查，该资源预留表收集了所有到目前为止被占用查，该资源预留表收集了所有到目前为止被占用 资源。这个结点的调度按有足够资源的最早时间资源。这个结点的调度按有足够资源的最早时间 槽来安排槽来安排 10.4 全局代码调度全局代码调度 对于有适度指令级并行的机器，仅对每个基对于有适度指令级并行的机器，仅对每个基 本块进行紧凑调度会引起许多资源空闲本块进行紧凑调度会引起许多资源空闲 全局调度：为了更好地利用机器资源，需要全局调度：为了更好地利用机器资源，需要 考虑把指令从一个基本块移到另一个基本块考虑把指令从一个基本块移到另

24、一个基本块 的代码生成策略的代码生成策略 必须保证必须保证 原来程序中所有指令在优化程序中都被执行原来程序中所有指令在优化程序中都被执行 当优化程序可以投机地执行额外指令时，这些指当优化程序可以投机地执行额外指令时，这些指 令肯定不能有任何多余的副作用令肯定不能有任何多余的副作用 10.4 全局代码调度全局代码调度 10.4.1 简单的代码移动简单的代码移动 先用例子展示操作在基本块之间移动涉及的问题先用例子展示操作在基本块之间移动涉及的问题 l: if (a = 0) goto l c = b e = d + d (a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码 ld r6,

25、 0(r1) nop beqz r6, l ld r7, 0(r2) nop st 0(r3), r7 ld r8, 0(r4) nop add r8, r8, r8 st 0(r5), r8 b2 b1 b3 l: 10.4 全局代码调度全局代码调度 假定假定a, b, c, d和和e的地址不同，分别保存在的地址不同，分别保存在r1到到r5 由于数据相关，块内的指令必须串行执行，且插由于数据相关，块内的指令必须串行执行，且插 入入 nop l: if (a = 0) goto l c = b e = d + d (a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码 ld r6,

26、0(r1) nop beqz r6, l ld r7, 0(r2) nop st 0(r3), r7 ld r8, 0(r4) nop add r8, r8, r8 st 0(r5), r8 b2 b1 b3 l: 10.4 全局代码调度全局代码调度 假定机器在一个时钟周期执行任意的两个操作假定机器在一个时钟周期执行任意的两个操作 读取操作有读取操作有2周期的延迟，其他指令周期的延迟，其他指令1周期的延迟周期的延迟 l: if (a = 0) goto l c = b e = d + d (a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码 ld r6, 0(r1) nop beq

27、z r6, l ld r7, 0(r2) nop st 0(r3), r7 ld r8, 0(r4) nop add r8, r8, r8 st 0(r5), r8 b2 b1 b3 l: 10.4 全局代码调度全局代码调度 b3肯定要执行，因而可以和肯定要执行，因而可以和b1并行执行并行执行 b2的读取操作在执行的读取操作在执行b1时投机地完成时投机地完成 b2的存储操作放到的存储操作放到b3的的 一份拷贝中一份拷贝中 l: if (a = 0) goto l c = b e = d + d (a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码 ld r6, 0(r1) nop

28、beqz r6, l ld r7, 0(r2) nop st 0(r3), r7 ld r8, 0(r4) nop add r8, r8, r8 st 0(r5), r8 b2 b1 b3 l: 10.4 全局代码调度全局代码调度 l: 全局调度前后的流图全局调度前后的流图 if (a = 0) goto l c = b e = d + d (a) 源代码源代码 st 0(r5), r8 (b) 局部调度的机器代码局部调度的机器代码 ld r6, 0(r1), ld r8, 0(r4) ld r7, 0(r2) add r8, r8, r8, beqz r6, l st 0(r5), r8,

29、st 0(r3), r7 l: (c) 全局调度的机器代码全局调度的机器代码 b1 b3 b3 ld r6, 0(r1) nop beqz r6, l ld r7, 0(r2) nop st 0(r3), r7 ld r8, 0(r4) nop add r8, r8, r8 st 0(r5), r8 b2 b1 b3 l: 10.4 全局代码调度全局代码调度 基本块之间的基本块之间的支配关系支配关系 指令在基本块之间的移动因支配关系不同而不同指令在基本块之间的移动因支配关系不同而不同 b1和和b3控制等价：控制等价：b1支配支配b3， b3后支配后支配b1 b1支配支配b2， 但是但是b2并非

30、后支配并非后支配b1 b2不支配不支配b3， 但是但是b3后支配后支配b2 ld r6, 0(r1) nop beqz r6, l ld r7, 0(r2) nop st 0(r3), r7 ld r8, 0(r4) nop add r8, r8, r8 st 0(r5), r8 b2 b1 b3 l: 10.4 全局代码调度全局代码调度 10.4.2 向上的代码移动向上的代码移动 从块从块src向上移动到块向上移动到块dst，假定移动未违反数据相，假定移动未违反数据相 关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快 若若dst和和src等价，则被移动操作应该被执

31、行时，它等价，则被移动操作应该被执行时，它 正好仅被执行一次正好仅被执行一次 dst src 10.4 全局代码调度全局代码调度 10.4.2 向上的代码移动向上的代码移动 从块从块src向上移动到块向上移动到块dst，假定移动未违反数据相，假定移动未违反数据相 关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快 若若dst和和src等价，则被移动操作应该被执行时，它等价，则被移动操作应该被执行时，它 正好仅被执行一次正好仅被执行一次 若若src未后支配未后支配dst，被移动操作可利用空闲资源免，被移动操作可利用空闲资源免 费执行，在控制流到达费执行，在控制流到达sr

32、c时获益时获益 dst src 10.4 全局代码调度全局代码调度 10.4.2 向上的代码移动向上的代码移动 从块从块src向上移动到块向上移动到块dst，假定移动未违反数据相，假定移动未违反数据相 关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快 若若dst和和src等价，则被移动操作应该被执行时，它等价，则被移动操作应该被执行时，它 正好仅被执行一次正好仅被执行一次 若若src未后支配未后支配dst，被移动操作可利用空闲资源免，被移动操作可利用空闲资源免 费执行，在控制流到达费执行，在控制流到达src时获益时获益 若若dst不支配不支配src， 需要插入被移动

33、操作的拷贝需要插入被移动操作的拷贝 dst src 10.4 全局代码调度全局代码调度 10.4.3 向下的代码移动向下的代码移动 从块从块src向下移动到块向下移动到块dst，假定移动未违反数据相，假定移动未违反数据相 关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快 若若dst和和src等价，则被移动操作应该被执行时，它等价，则被移动操作应该被执行时，它 正好仅被执行一次正好仅被执行一次 src dst 10.4 全局代码调度全局代码调度 10.4.3 向下的代码移动向下的代码移动 从块从块src向下移动到块向下移动到块dst，假定移动未违反数据相，假定移动未违

34、反数据相 关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快 若若dst和和src等价，则被移动操作应该被执行时，它等价，则被移动操作应该被执行时，它 正好仅被执行一次正好仅被执行一次 src未后支配未后支配dst, 向下移动的代码经常是存储操作向下移动的代码经常是存储操作, 复制从复制从src到到dst路径上的各块，并把路径上的各块，并把 被移动操作仅放置在被移动操作仅放置在dst的新拷贝中的新拷贝中 src dst 10.4 全局代码调度全局代码调度 9.5节的例子可作为参考节的例子可作为参考 b1 b2b3 b4 a = b + c b5b6 b7 d = b

35、+ c b1 b2b3 b4 t = b + c a = t b4 b5 d = t d = b + c b6b6 b7 10.4 全局代码调度全局代码调度 10.4.3 向下的代码移动向下的代码移动 从块从块src向下移动到块向下移动到块dst，假定移动未违反数据相，假定移动未违反数据相 关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快 若若dst和和src等价，则被移动操作应该被执行时，它等价，则被移动操作应该被执行时，它 正好仅被执行一次正好仅被执行一次 src未后支配未后支配dst, 向下移动的代码经常是存储操作向下移动的代码经常是存储操作, 复制从复制从s

36、rc到到dst路径上的各块，并把路径上的各块，并把 被移动操作仅放置在被移动操作仅放置在dst的新拷贝中的新拷贝中 dst没有后支配没有后支配src，插入补偿代码以，插入补偿代码以 保证被移动操作在不经保证被移动操作在不经dst路径上也执行路径上也执行 src dst 10.4 全局代码调度全局代码调度 10.4.4 更新数据相关更新数据相关 代码移动会改变操作之间的数据相关关系代码移动会改变操作之间的数据相关关系 两个对两个对x的赋值之一可以移动到最上面的基本块的赋值之一可以移动到最上面的基本块 ，该变换能维持原来程序中的所有相关性，该变换能维持原来程序中的所有相关性 一旦一个对一旦一个对x

37、的赋值被上移，另一个就不能移动的赋值被上移，另一个就不能移动 了了 移动使得移动使得x在最上面块的出口在最上面块的出口 由不活跃变成活跃由不活跃变成活跃 一个变量在某个程序点一个变量在某个程序点 活跃，则就不能把对它的投机活跃，则就不能把对它的投机 定值移到该点的上面定值移到该点的上面 x = 1x = 2 10.4 全局代码调度全局代码调度 10.4.5 全局调度的其他问题全局调度的其他问题 程序调度应该使经常执行的路径运行得快一些，程序调度应该使经常执行的路径运行得快一些， 不经常执行的路径可能会因调度变得慢一些不经常执行的路径可能会因调度变得慢一些 编译器可用来估计执行频率的技术有若干种

38、编译器可用来估计执行频率的技术有若干种 (1) 内循环比外循环执行得更频繁内循环比外循环执行得更频繁 (2) 分支指令往回跳转比不跳转要更经常分支指令往回跳转比不跳转要更经常 (3)看守程序出口或异常处理例程的分支语句很看守程序出口或异常处理例程的分支语句很 少被执行少被执行 最好的频率估计来自动态剖析，程序被静态插桩最好的频率估计来自动态剖析，程序被静态插桩 以用来运行时记录条件分支每次的走向以用来运行时记录条件分支每次的走向 10.4 全局代码调度全局代码调度 10.4.5 全局调度的其他问题全局调度的其他问题 最简单的全局调度算法也相当复杂，不介绍最简单的全局调度算法也相当复杂，不介绍

39、在一些全局调度算法中，循环迭代的边界是代码移在一些全局调度算法中，循环迭代的边界是代码移 动的一种屏障，需循环展开动的一种屏障，需循环展开 for(i = 0; i n; i +) for ( i = 0; i + 4 n; i += 4) s(i);s(i); s(i +1); s(i +2); s(i +3); for ( ; i n; i +) s(i); 10.4 全局代码调度全局代码调度 10.4.6 静态调度器和动态调度器的相互影响静态调度器和动态调度器的相互影响 动态调度器的优点是可以根据运行时的情况建立新动态调度器的优点是可以根据运行时的情况建立新 的调度表，无需事先编码所有可

40、能的调度表的调度表，无需事先编码所有可能的调度表 10.4 全局代码调度全局代码调度 10.4.6 静态调度器和动态调度器的相互影响静态调度器和动态调度器的相互影响 存在动态调度情况下，静态调度器的作用存在动态调度情况下，静态调度器的作用 保证尽早地取高延迟的指令，使得动态调度器能保证尽早地取高延迟的指令，使得动态调度器能 够尽早发射它们够尽早发射它们 尽早安排预取指令，使数据到要用时已经在缓存尽早安排预取指令，使数据到要用时已经在缓存, 或尽早安排可能不命中缓存的操作或尽早安排可能不命中缓存的操作 只需要给数据相关的操作安排正确的次序，无需只需要给数据相关的操作安排正确的次序，无需 通过极小

41、化延迟来分离每一对数据相关的操作通过极小化延迟来分离每一对数据相关的操作 给分支预测指令较高优先级，以减少预测错误的给分支预测指令较高优先级，以减少预测错误的 代价代价 10.5 软软 件件 流流 水水 10.5.1 引言引言 软件流水是一种调度算法，它每次调度一个软件流水是一种调度算法，它每次调度一个 完整的循环，以充分利用穿越迭代的并行性完整的循环，以充分利用穿越迭代的并行性 单次迭代的操作中几乎没有什么并行性单次迭代的操作中几乎没有什么并行性 软件流水技术不断地重叠一些相继迭代，直到所软件流水技术不断地重叠一些相继迭代，直到所 有迭代都填入流水线为止有迭代都填入流水线为止 能产生高效和紧

42、凑的代码能产生高效和紧凑的代码 以一周期内可以同时发射一个读取、一个存储、以一周期内可以同时发射一个读取、一个存储、 一个算术运算（全流水）和一个分支操作的机器一个算术运算（全流水）和一个分支操作的机器 来举例来举例 10.5 软软 件件 流流 水水 每次调度一个迭代的结果见右边每次调度一个迭代的结果见右边 for (i = 0; i n; i +) / r1, r2, r3 = / r4= c / r10= n 1 l: ld r5, 0(r1+) ld r6, 0(r2+) mul r7, r5, r6 nop add r8, r7, r4 nop st 0(r3+),r8, bl r10

43、, l 该计算大部分是该计算大部分是 串行的，它需要串行的，它需要 7周期，只有循周期，只有循 环回跳指令和迭环回跳指令和迭 代中最后一条指代中最后一条指 令重叠令重叠 10.5 软软 件件 流流 水水 循环展开循环展开4次迭代的调度结果见右边次迭代的调度结果见右边 for (i = 0; i = 5) n2 = 1 + 2 (n 1) / 2); else n2 = 0; for (i = 0; i n2; i +)/ 该循环被流水化该循环被流水化 di = ai bi + c; for (i = n2; i n; i +)/ 不需要优化不需要优化 di = ai bi + c; 10.5

44、软软 件件 流流 水水 10.5.4 do-across循环循环 软件流水也可以用到迭代之间存在数据相关的循软件流水也可以用到迭代之间存在数据相关的循 环，这样的循环叫做环，这样的循环叫做do-across循环循环 for (i = 0; i n; i +) sum = sum + ai; bi = ai b; 该循环的执行不可能快于每该循环的执行不可能快于每2周期周期1次迭代次迭代 即使有更多的加法器或乘法器，也不可能更快即使有更多的加法器或乘法器，也不可能更快 吞吐能力受到穿越迭代的数据相关链的限制吞吐能力受到穿越迭代的数据相关链的限制 10.5 软软 件件 流流 水水 10.5.5 软件

45、流水的目标和约束软件流水的目标和约束 目标目标 基本目标是极大化耗时较长的循环的吞吐能力基本目标是极大化耗时较长的循环的吞吐能力 次要目标是保持所产生代码的规模较小次要目标是保持所产生代码的规模较小 达到目标的体现达到目标的体现 软件流水化的循环应该有较小的流水线稳定状态软件流水化的循环应该有较小的流水线稳定状态 实现策略实现策略 让每次迭代的相对调度都相同，并且这些迭代以让每次迭代的相对调度都相同，并且这些迭代以 同样的时间间隔逐步启动同样的时间间隔逐步启动 10.5 软软 件件 流流 水水 10.5.5 软件流水的目标和约束软件流水的目标和约束 资源约束资源约束 令机器资源由令机器资源由r

46、 = r1, r2, .表示，其中表示，其中ri是第是第i类资类资 源可用部件数源可用部件数 若循环的一次迭代需要第若循环的一次迭代需要第i类资源类资源ni个部件个部件 流水化循环的平均启动间隔至少是流水化循环的平均启动间隔至少是maxi(ni/ri)周期周期 如果如果maxi(ni/ri)小于小于1，则将源代码展开几次是有，则将源代码展开几次是有 用的用的 10.5 软软 件件 流流 水水 10.5.5 软件流水的目标和约束软件流水的目标和约束 数据相关数据相关 一个操作可能依赖于前一次迭代中同样操作的结一个操作可能依赖于前一次迭代中同样操作的结 果，不同于到目前为止碰到的数据相关果，不同于

47、到目前为止碰到的数据相关 仅用延迟来标记边不够用，需要区别不同迭代中仅用延迟来标记边不够用，需要区别不同迭代中 同一操作的实例，例如：同一操作的实例，例如： for (i = 2; i n; i +) ai = bi + ai 2 写写ai和读和读ai 2的依赖边上标记的迭代次数差的依赖边上标记的迭代次数差 是是2 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 并行编程模型并行编程模型 任务并行任务并行 数据并行数据并行 数据流并行（前面几节涉及较多）数据流并行（前面几节涉及较多） 本节内容围绕任务并行和数据并行本节内容围绕任务并行和数据并行 介绍并行计算机系统结构的概况介绍

48、并行计算机系统结构的概况 给出并行化的基本概念，程序循环的变换，还有给出并行化的基本概念，程序循环的变换，还有 对并行化有用的概念对并行化有用的概念 类似的考虑怎样用于优化数据局部性类似的考虑怎样用于优化数据局部性 以矩阵乘算法的优化为例以矩阵乘算法的优化为例 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.1 多处理器多处理器 对称多处理器的体系结构对称多处理器的体系结构 二级二级 缓存缓存 内存内存 总线总线 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 处理器处理器处理

49、器处理器处理器处理器 处理器处理器 多个高性多个高性 能处理器能处理器 集成在一集成在一 块芯片上块芯片上 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.1 多处理器多处理器 对称多处理器的体系结构对称多处理器的体系结构 二级二级 缓存缓存 内存内存 总线总线 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 处理器处理器处理器处理器处理器处理器 处理器处理器 多个高性多个高性 能处理器能处理器 集成在一集成在一 块芯片上块芯片上 通过共通过共 享内存来享内存来 进行通信进行通

50、信 必须在处理器的缓存中必须在处理器的缓存中 找到它操作的大部分数找到它操作的大部分数 据，以保证性能据，以保证性能 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.1 多处理器多处理器 分布式内存机器分布式内存机器 总线或其它互连总线或其它互连 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 处理器处理器处理器处理器处理器处理器处理器处理器 局部局部 内存内存 局部局部 内存内存 局部局部 内存内存 局部局部 内存内存 在内存分在内存分 层中又引层中又引

51、入一层入一层 处理器能处理器能 迅速访问迅速访问 自己的局自己的局 部内存部内存 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.1 多处理器多处理器 分布式内存机器分布式内存机器 总线或其它互连总线或其它互连 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 二级二级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 一级一级 缓存缓存 处理器处理器处理器处理器处理器处理器处理器处理器 局部局部 内存内存 局部局部 内存内存 局部局部 内存内存 局部局部 内存内存 在内存分在内存分 层中又引层中又引 入一层入一层 处理器能处理器能 迅速

52、访问迅速访问 自己的局自己的局 部内存部内存 非均匀内存访问的机器和消息传非均匀内存访问的机器和消息传 递的机器；为获得良好的性能递的机器；为获得良好的性能 软件都必须有很好局部性软件都必须有很好局部性 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.2 应用中的并行性应用中的并行性 并行应用性能衡量的两种标准并行应用性能衡量的两种标准 并行覆盖：整个计算中并行运行部分的百分比并行覆盖：整个计算中并行运行部分的百分比 并行粒度：处理器上无需和其它处理器同步或通并行粒度：处理器上无需和其它处理器同步或通 信的计算量信的计算量 循环对并行化来说特别有吸引力，循环可以有许循

53、环对并行化来说特别有吸引力，循环可以有许 多次迭代计算，如果这些计算相互独立，则它们是多次迭代计算，如果这些计算相互独立，则它们是 并行计算的主要来源并行计算的主要来源 许多控制结构简单、数据量大并且耗时长的科学许多控制结构简单、数据量大并且耗时长的科学 和工程应用，很容易以较细粒度被并行化和工程应用，很容易以较细粒度被并行化 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.3 循环级并行循环级并行 耗时的应用一般都使用大数组，导致程序中出现耗时的应用一般都使用大数组，导致程序中出现 有许多次迭代的循环，这些迭代经常相互独立，可有许多次迭代的循环，这些迭代经常相互独立

54、，可 以把这类循环的大量迭代分到各处理器上以把这类循环的大量迭代分到各处理器上 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.3 循环级并行循环级并行 for (i = 0; i n; i+) zi = xi yi; zi = zi zi; / 变换成如下代码变换成如下代码 b = ceil (n/m); / m个处理器个处理器, p = 0, 1, , m 1 for (i = b p; i min(n, b (p+1); i+) zi = xi yi; zi = zi zi; / 数据并行的例子数据并行的例子 10.6 并行性和数据局部性优化概述并行性和数据局部

55、性优化概述 10.6.3 循环级并行循环级并行 对并行化来说，任务级不像循环级那样有吸引力对并行化来说，任务级不像循环级那样有吸引力 对一个程序而言，独立的任务数是一个常数，它对一个程序而言，独立的任务数是一个常数，它 不像典型的循环那样，独立的计算单元随迭代次不像典型的循环那样，独立的计算单元随迭代次 数增加而增加数增加而增加 任务通常不是等规模的，因此很难保证所有的处任务通常不是等规模的，因此很难保证所有的处 理器在所有时间都处于忙碌理器在所有时间都处于忙碌 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.4 数据局部性数据局部性 程序局部性程序局部性 大多数程序

56、的大部分时间在执行一小部分代码，大多数程序的大部分时间在执行一小部分代码， 并且仅涉及一小部分数据并且仅涉及一小部分数据 时间局部性时间局部性 程序访问的内存单元在很短的时间内可能再次被程序访问的内存单元在很短的时间内可能再次被 程序访问程序访问 空间局部性空间局部性 毗邻被访问单元的内存单元在很短的时间内可能毗邻被访问单元的内存单元在很短的时间内可能 被访问被访问 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.4 数据局部性数据局部性 同一个缓存行上的元素一起被使用的情况是空间同一个缓存行上的元素一起被使用的情况是空间 局部性的一种重要形式局部性的一种重要形式 这

57、种空间局部性将缓存未命中降到最低，因此使这种空间局部性将缓存未命中降到最低，因此使 得程度获得明显的加速得程度获得明显的加速 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.4 数据局部性数据局部性 for (i = 0; i n; i+) / 该程序段对向量机来该程序段对向量机来 zi = xi yi;/ 说是一种优化形式说是一种优化形式 for (i = 0; i n; i+) zi = zi zi; for (i = 0; i n; i+) / 有较好的数据局部性有较好的数据局部性 zi = xi yi; zi = zi zi; 10.6 并行性和数据局部性优化

58、概述并行性和数据局部性优化概述 10.6.4 数据局部性数据局部性 对行为主的数组对行为主的数组z，根据空间局部性，显然更愿，根据空间局部性，显然更愿 意逐行地给该数组元素置零意逐行地给该数组元素置零 for (j = 0; j n; j+)for (i = 0; i n; i+) for (i = 0; i n; i+) for (j = 0; j n; j+) zi, j = 0; zi, j = 0; 为了获得最好的性能，应该并行化外循环为了获得最好的性能，应该并行化外循环 b = ceil (n/m); for (i = b p; i min(n, b (p+1); i+) for (

59、j = 0; j n; j+) zi, j = 0; 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.4 数据局部性数据局部性 操作在数组上的数值应用的几个重要特征操作在数组上的数值应用的几个重要特征 数组代码经常有许多可以并行化的循环数组代码经常有许多可以并行化的循环 当循环有并行性时，它们的迭代可按任意次序执当循环有并行性时，它们的迭代可按任意次序执 行，因而可重新安排计算次序以彻底改进数据局行，因而可重新安排计算次序以彻底改进数据局 部性部性 在创建相互独立的并行计算大单元时，串行执行在创建相互独立的并行计算大单元时，串行执行 这些单元往往会产生较好的数据局部性这些单元往往会产生较好的数据局部性 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述 10.6.5 矩阵乘法算法矩阵乘法算法 该算法是计算密集型的，原则上