第十章第十章 依赖于机器的优化依赖于机器的优化在指令级并行的机器上，程序的运行速度依在指令级并行的机器上，程序的运行速度依赖于下面几个因素赖于下面几个因素 程序中潜在的并行程序中潜在的并行 处理器上可用的并行处理器上可用的并行 从串行程序提取并行的能力从串行程序提取并行的能力 在给定的调度约束下发现最佳并行调度的能力在给定的调度约束下发现最佳并行调度的能力并行的提取和并行执行的调度都可以静态地并行的提取和并行执行的调度都可以静态地在软件中或动态地在硬件中完成在软件中或动态地在硬件中完成第十章第十章 依赖于机器的优化依赖于机器的优化本章内容本章内容 使用使用指令级并行指令级并行的基础问题的基础问题 提取并行的数据相关性分析提取并行的数据相关性分析 代码调度的基本概念代码调度的基本概念 基本块调度的技术、发现通用程序中的高度数据基本块调度的技术、发现通用程序中的高度数据相关控制流的方法、调度数值程序的软件流水线相关控制流的方法、调度数值程序的软件流水线技术技术 在在多处理器系统多处理器系统上，使用数组的计算密集型程序上，使用数组的计算密集型程序的并行化和数据局部性优化的概念和方法的并行化和数据局部性优化的概念和方法10.1 处理器体系结构处理器体系结构在考虑指令级并行时，通常想象成一个处理在考虑指令级并行时，通常想象成一个处理器在单个时钟周期内发射几个操作器在单个时钟周期内发射几个操作事实上，在每周期内发射一个操作是可能的事实上，在每周期内发射一个操作是可能的, 而指令级并行的获得是通过使用流水线技术而指令级并行的获得是通过使用流水线技术本节先解释流水线，然后讨论多指令发射本节先解释流水线，然后讨论多指令发射10.1 处理器体系结构处理器体系结构10.1.1 指令流水线和分支延迟指令流水线和分支延迟 ii + 1i + 2i + 3i + 41. IF2. IDIF3. EXIDIF4. MEMEXIDIF5. WBMEMEXIDIF6.WBMEMEXID7.WBMEMEX8.WBMEM9.WB取指令取指令IF, 译码译码ID, 执行操作执行操作EX, 访问内存访问内存MEM, 回写结果回写结果WB5级指令流水线中级指令流水线中的的5条连续指令条连续指令 10.1 处理器体系结构处理器体系结构10.1.1 指令流水线和分支延迟指令流水线和分支延迟分支延迟分支延迟发现应该执行一个分支而不是直接后继发现应该执行一个分支而不是直接后继转转向向一一个个分分支支时时会会引引起起取取分分支支目目的的地地址址指指令令的的延延迟并引起指令流水线迟并引起指令流水线“打嗝打嗝”可可以以通通过过使使用用硬硬件件，根根据据分分支支的的执执行行历历史史来来预预测测分支结果并从预测的目的地址预取指令分支结果并从预测的目的地址预取指令分支延迟不可避免，因为分支预测会发生偏差分支延迟不可避免，因为分支预测会发生偏差10.1 处理器体系结构处理器体系结构10.1.2 流水化的执行流水化的执行如果不依赖一条指令结果的随后指令在该结如果不依赖一条指令结果的随后指令在该结果产生前就被允许执行果产生前就被允许执行有有些些指指令令的的执执行行需需要要几几个个周周期期，几几个个操操作作同同时时出出现在它们的执行级上可能的现在它们的执行级上可能的如如果果最最长长的的执执行行流流水水线线是是n级级，n个个操操作作同同时时进进行行的可能性是存在的的可能性是存在的并非所有的指令都能被完全流水化，例如浮点除并非所有的指令都能被完全流水化，例如浮点除 通用处理器大都动态察觉相继指令之间的依赖性通用处理器大都动态察觉相继指令之间的依赖性 嵌入式系统把数据相关性的检查交给软件嵌入式系统把数据相关性的检查交给软件10.1 处理器体系结构处理器体系结构10.1.3 多指令发射多指令发射 每周期发射几个操作，让更多操作同时进行每周期发射几个操作，让更多操作同时进行超长指令字机器超长指令字机器将若干个操作编码在单周期中发射将若干个操作编码在单周期中发射编译器需要确定哪些操作可以并行发射编译器需要确定哪些操作可以并行发射超标量机器超标量机器超标量机器有按普通顺序执行语义的正规指令集超标量机器有按普通顺序执行语义的正规指令集硬硬件件自自动动察察觉觉指指令令之之间间的的相相关关性性，并并且且在在它它们们的的操作数可用时就发射它们操作数可用时就发射它们更复杂的调度器能够更复杂的调度器能够“乱序乱序”执行指令执行指令10.2 代码调度的约束代码调度的约束 代码调度代码调度用在代码生成器产生的机器代码上的优化技术用在代码生成器产生的机器代码上的优化技术本节讨论代码调度的约束本节讨论代码调度的约束控制相关约束控制相关约束 在在原原程程序序中中执执行行的的所所有有操操作作都都必须在优化代码中执行必须在优化代码中执行数据相关约束数据相关约束 优优化化程程序序中中的的操操作作产产生生的的结结果果必须同原程序对应操作的结果一样必须同原程序对应操作的结果一样资源约束资源约束 调度不能过分占用机器的资源调度不能过分占用机器的资源优化程序很难调试优化程序很难调试内存状态可能和顺序执行的任何内存状态不匹配内存状态可能和顺序执行的任何内存状态不匹配10.2 代码调度的约束代码调度的约束 10.2.1 数据相关数据相关真相关真相关 如如果果对对同同一一个个单单元元先先写写后后读读，那那么么读读依赖于所写的值依赖于所写的值反相关反相关 如如果果对对同同一一个个单单元元先先读读后后写写。可可以以通通过把值存在不同的单元来删除反相关过把值存在不同的单元来删除反相关输出相关输出相关 如如果果对对同同一一个个单单元元先先后后写写两两次次。也也可可删除删除数数据据相相关关概概念念可可同同时时用用于于内内存存访访问问和和寄寄存存器器访问访问10.2 代码调度的约束代码调度的约束 10.2.2 发现内存访问中的相关性发现内存访问中的相关性例例(1) a = 1(2) p = 2(3) x = a语句语句(1)和和(2)可能构成输出相关可能构成输出相关语句语句(1)和和(3)可能构成真相关可能构成真相关语句语句(2)和和(3)可能构成真相关可能构成真相关除非编译器知道除非编译器知道p不可能指向不可能指向a，否则，否则3个操作必须个操作必须串行执行串行执行10.2 代码调度的约束代码调度的约束 10.2.2 发现内存访问中的相关性发现内存访问中的相关性发现数据相关需要不同形式的分析发现数据相关需要不同形式的分析数组元素间的别名分析数组元素间的别名分析Ai和和Aj是否互为别名是否互为别名指针别名分析指针别名分析若若p和和q相等，则相等，则 p和和 q、p-next和和q-next、p-data和和q-data等都分别互为别名等都分别互为别名过程间分析过程间分析引引用用调调用用场场合合：形形参参和和形形参参之之间间、形形参参和和全全局局变变量之间因实参而引起互为别名量之间因实参而引起互为别名10.2 代码调度的约束代码调度的约束 10.2.3 寄存器使用和并行执行之间的折衷寄存器使用和并行执行之间的折衷例：例：(a + b) + c + (d + e)LD R1, aLD R2, bADD R1, R1, R2LD R2, cADD R1, R1, R2LD R2, dLD R3, eADD R2, R2, R3ADD R1, R1, R2+e+c+ab+d若瞄准极小化寄存器若瞄准极小化寄存器的使用个数，则只需的使用个数，则只需使用使用3个寄存器个寄存器 10.2 代码调度的约束代码调度的约束 10.2.3 寄存器使用和并行执行之间的折衷寄存器使用和并行执行之间的折衷例：例：(a + b) + c + (d + e)LD R1, aLD R2, bADD R1, R1, R2LD R2, cADD R1, R1, R2LD R2, dLD R3, eADD R2, R2, R3ADD R1, R1, R2+e+c+ab+d完成整个计算需要完成整个计算需要7步步10.2 代码调度的约束代码调度的约束 10.2.3 寄存器使用和并行执行之间的折衷寄存器使用和并行执行之间的折衷例：例：(a + b) + c + (d + e) +e+c+ab+d如果对每个中间结果如果对每个中间结果使用不同寄存器，则使用不同寄存器，则完成计算只需要完成计算只需要4步步R1 = aR6 = R1+R2R8 = R6+R3R9 = R8+R7R2 = bR7 = R4+R5R3 = cR4 = d R5 = e10.2 代码调度的约束代码调度的约束 10.2.4 寄存器分配和代码调度的次序安排寄存器分配和代码调度的次序安排先寄存器分配先寄存器分配结果代码中会有很多存储相关结果代码中会有很多存储相关非数值应用本质上没有多少并行，采用这种方式非数值应用本质上没有多少并行，采用这种方式先代码调度先代码调度导致寄存器溢出，抵消指令级并行的优点导致寄存器溢出，抵消指令级并行的优点适用于有许多大表达式的数值应用适用于有许多大表达式的数值应用在在假假定定伪伪寄寄存存器器就就是是物物理理寄寄存存器器情情况况下下，先先调调度度指指令令，然然后后寄寄存存器器分分配配，把把处处理理寄寄存存器器溢溢出出的的代代码附加在必要的地方，并再次进行代码调度码附加在必要的地方，并再次进行代码调度10.2 代码调度的约束代码调度的约束 10.2.5 控制相关控制相关 在在非非数数值值计计算算中中，基基本本块块非非常常小小，其其中中的的操操作作通通常高度相关，几乎不能并行常高度相关，几乎不能并行调查跨基本块的并行是至关重要的调查跨基本块的并行是至关重要的若若一一条条指指令令很很可可能能被被执执行行且且有有空空闲闲的的资资源源可可“免免费费”用用于于完完成成该该指指令令的的操操作作，则则可可以以投投机机地地执执行行该指令；若投机成功，则程序运行得快一些该指令；若投机成功，则程序运行得快一些例例 if (a t) b = a a依赖于比较依赖于比较a t的结果的结果 b = a a; 若若a a不会产生副作用，则不会产生副作用，则d = a + c; a a可以投机地执行可以投机地执行10.2 代码调度的约束代码调度的约束 10.2.6 投机执行的支持投机执行的支持内内存存读读取取是是一一类类使使用用频频繁繁，且且能能从从投投机机执执行行大大大大获益的指令获益的指令但在但在 if (p != null)q = p中，投机地对中，投机地对p脱引用将引起该程序因脱引用将引起该程序因p等于等于null而错误地停止而错误地停止许多高性能处理器提供专门的特性来支持投机地许多高性能处理器提供专门的特性来支持投机地内存访问内存访问10.2 代码调度的约束代码调度的约束 10.2.6 投机执行的支持投机执行的支持预取指令预取指令在在数数据据使使用用前前将将其其从从内内存存取取到到缓缓存存,若该单元无效或访问它会引起缺页，则忽略若该单元无效或访问它会引起缺页，则忽略 抑制位抑制位允允许许投投机机地地从从内内存存将将数数据据读读取取到到寄寄存存器器堆堆，若若出出现现非非法法内内存存访访问问或或缺缺页页，则则设设置置目目标标寄存器的抑制位寄存器的抑制位判定指令判定指令在判定条件为真时才执行的指令在判定条件为真时才执行的指令例例 if (a = 0)翻译成翻译成 ADD R3, R4, R5b = c + d; CMOVZ R2, R3, R1假定假定a、b、c和和d分别被分配了分别被分配了R1、R2、R4和和R5可用来将相邻基本块组合成一个更大基本块可用来将相邻基本块组合成一个更大基本块10.2 代码调度的约束代码调度的约束 10.2.7 一个基本的机器模型一个基本的机器模型机器模型机器模型M = (R, T)T：操作类型集，如读取、存储和算术运算等：操作类型集，如读取、存储和算术运算等R = r1, r2, ：硬硬件件资资源源向向量量集集，如如内内存存访访问问部部件、算术运算部件和浮点功能部件件、算术运算部件和浮点功能部件ri代表第代表第i类资源中可用的部件数类资源中可用的部件数每每个个操操作作有有一一组组输输入入操操作作数数、一一组组输输出出操操作作数数和和一个资源需求一个资源需求和每个输入操作数相关的是一个输入延迟和每个输入操作数相关的是一个输入延迟和每个输出操作数相关的是一个输出延迟和每个输出操作数相关的是一个输出延迟10.2 代码调度的约束代码调度的约束 10.2.7 一个基本的机器模型一个基本的机器模型机器模型机器模型M = (R, T)对对每每种种操操作作类类型型t，资资源源使使用用由由一一张张二二维维资资源源预预留留表表RTt来建模来建模条条目目RTti, j是是t类类型型的的一一个个操操作作在在它它被被发发射射i时时钟钟周期后，使用第周期后，使用第j种资源的部件数种资源的部件数对任何对任何t、i和和j，RTti, j必须小于或等于必须小于或等于Rj10.3 基基 本本 块块 调调 度度10.3.1 数据依赖图数据依赖图基本块由数据依赖图基本块由数据依赖图G = (N, E)来表示来表示结点集合结点集合N表示该块的机器指令中的操作集合表示该块的机器指令中的操作集合有向边集合有向边集合E表示这些操作之间的数据相关约束表示这些操作之间的数据相关约束G的结点集的结点集N和边集和边集E按如下两步构造按如下两步构造N中中的的每每个个操操作作n有有一一张张资资源源预预留留表表RTn，其其值值直直接就是接就是n的操作类型的资源预留表的操作类型的资源预留表每每条条边边e都都标标示示有有延延迟迟de，表表示示e的的目目的的结结点点必必须须在它源结点发射在它源结点发射de个时钟周期之后才可以发射个时钟周期之后才可以发射10.3 基基 本本 块块 调调 度度数据依赖图数据依赖图资源预留表资源预留表alu menLD R2, 0(R1)ST 4(R1), R2 LD R3, 8(R1)ADD R3, R3, R2ADD R3, R3, R4ST 0(R7), R7 ST 12(R1), R3 222111111i1i2i3i4i5i6i7灰色表灰色表示示1 白色表白色表示示0操作是全流水操作是全流水的，只需显示的，只需显示在第在第1行使用行使用的资源的资源 10.3 基基 本本 块块 调调 度度10.3.2 基本块的表调度基本块的表调度关键路径包括最后关键路径包括最后5个结点，故第个结点，故第3条指令先调度条指令先调度再调度第再调度第1条指令，因为第条指令，因为第4条指令还需等条指令还需等1周期周期第第4周期调度周期调度2条条资源预留表资源预留表alu men调度表调度表LD R3, 8(R1) ADD R3, R3, R2ADD R3, R3, R4ST 0(R7), R7ST 12(R1), R3ST 4(R1), R2 LD R2, 0(R1) 10.3 基基 本本 块块 调调 度度10.3.2 基本块的表调度基本块的表调度根根据据每每个个结结点点同同先先前前已已经经被被调调度度的的各各结结点点之之间间的的数数据据相相关关约约束束，来来计计算算一一个个结结点点可可以以执执行行的的最最早早时间槽时间槽这这个个结结点点所所需需资资源源根根据据一一张张资资源源预预留留表表来来进进行行检检查查，该该资资源源预预留留表表收收集集了了所所有有到到目目前前为为止止被被占占用用资资源源。这这个个结结点点的的调调度度按按有有足足够够资资源源的的最最早早时时间间槽来安排槽来安排10.4 全局代码调度全局代码调度对对于于有有适适度度指指令令级级并并行行的的机机器器，仅仅对对每每个个基基本块进行紧凑调度会引起许多资源空闲本块进行紧凑调度会引起许多资源空闲全全局局调调度度：为为了了更更好好地地利利用用机机器器资资源源，需需要要考考虑虑把把指指令令从从一一个个基基本本块块移移到到另另一一个个基基本本块块的代码生成策略的代码生成策略必须保证必须保证原来程序中所有指令在优化程序中都被执行原来程序中所有指令在优化程序中都被执行当当优优化化程程序序可可以以投投机机地地执执行行额额外外指指令令时时，这这些些指指令肯定不能有任何多余的副作用令肯定不能有任何多余的副作用10.4 全局代码调度全局代码调度10.4.1 简单的代码移动简单的代码移动先用例子展示操作在基本块之间移动涉及的问题先用例子展示操作在基本块之间移动涉及的问题 L:if (a = 0) goto Lc = be = d + d(a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代码调度全局代码调度假定假定a, b, c, d和和e的地址不同，分别保存在的地址不同，分别保存在R1到到R5由由于于数数据据相相关关，块块内内的的指指令令必必须须串串行行执执行行，且且插插入入 NOPL:if (a = 0) goto Lc = be = d + d(a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代码调度全局代码调度假定机器在一个时钟周期执行任意的两个操作假定机器在一个时钟周期执行任意的两个操作读取操作有读取操作有2周期的延迟，其他指令周期的延迟，其他指令1周期的延迟周期的延迟L:if (a = 0) goto Lc = be = d + d(a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代码调度全局代码调度B3肯定要执行，因而可以和肯定要执行，因而可以和B1并行执行并行执行B2的读取操作在执行的读取操作在执行B1时投机地完成时投机地完成B2的存储操作放到的存储操作放到B3的的一份拷贝中一份拷贝中L:if (a = 0) goto Lc = be = d + d(a) 源代码源代码(b) 局部调度的机器代码局部调度的机器代码LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代码调度全局代码调度L:全局调度前后的流图全局调度前后的流图if (a = 0) goto Lc = be = 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, LST 0(R5), R8, ST 0(R3), R7L:(c) 全局调度的机器代码全局调度的机器代码B1B3 B3LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代码调度全局代码调度基本块之间的基本块之间的支配关系支配关系指令在基本块之间的移动因支配关系不同而不同指令在基本块之间的移动因支配关系不同而不同B1和和B3控制等价：控制等价：B1支配支配B3，B3后支配后支配B1B1支配支配B2，但是但是B2并非后支配并非后支配B1B2不支配不支配B3，但是但是B3后支配后支配B2LD R6, 0(R1) NOPBEQZ R6, LLD R7, 0(R2) NOPST 0(R3), R7 LD R8, 0(R4) NOPADD R8, R8, R8ST 0(R5), R8B2B1B3L:10.4 全局代码调度全局代码调度10.4.2 向上的代码移动向上的代码移动从块从块src向上移动到块向上移动到块dst，假定移动未违反数据相，假定移动未违反数据相关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快若若dst和和src等等价价，则则被被移移动动操操作作应应该该被被执执行行时时，它它正好仅被执行一次正好仅被执行一次dstsrc10.4 全局代码调度全局代码调度10.4.2 向上的代码移动向上的代码移动从块从块src向上移动到块向上移动到块dst，假定移动未违反数据相，假定移动未违反数据相关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快若若dst和和src等等价价，则则被被移移动动操操作作应应该该被被执执行行时时，它它正好仅被执行一次正好仅被执行一次若若src未未后后支支配配dst，被被移移动动操操作作可可利利用用空空闲闲资资源源免免费执行，在控制流到达费执行，在控制流到达src时获益时获益dstsrc10.4 全局代码调度全局代码调度10.4.2 向上的代码移动向上的代码移动从块从块src向上移动到块向上移动到块dst，假定移动未违反数据相，假定移动未违反数据相关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快若若dst和和src等等价价，则则被被移移动动操操作作应应该该被被执执行行时时，它它正好仅被执行一次正好仅被执行一次若若src未后支配未后支配dst，被移动操作可利用空闲资源免，被移动操作可利用空闲资源免费执行，在控制流到达费执行，在控制流到达src时获益时获益若若dst不支配不支配src，需要插入被移动操作的拷贝需要插入被移动操作的拷贝 dstsrc10.4 全局代码调度全局代码调度10.4.3 向下的代码移动向下的代码移动从块从块src向下移动到块向下移动到块dst，假定移动未违反数据相，假定移动未违反数据相关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快若若dst和和src等等价价，则则被被移移动动操操作作应应该该被被执执行行时时，它它正好仅被执行一次正好仅被执行一次srcdst10.4 全局代码调度全局代码调度10.4.3 向下的代码移动向下的代码移动从块从块src向下移动到块向下移动到块dst，假定移动未违反数据相，假定移动未违反数据相关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快若若dst和和src等等价价，则则被被移移动动操操作作应应该该被被执执行行时时，它它正好仅被执行一次正好仅被执行一次src未未后后支支配配dst, 向向下下移移动动的的代代码码经经常常是是存存储储操操作作, 复制从复制从src到到dst路径上的各块，并把路径上的各块，并把被移动操作仅放置在被移动操作仅放置在dst的新拷贝中的新拷贝中srcdst10.4 全局代码调度全局代码调度9.5节的例子可作为参考节的例子可作为参考B1B2B3B4a = b + cB5B6B7d = b + cB1B2B3B4t = b + ca = tB4 B5d = td = b + cB6B6 B710.4 全局代码调度全局代码调度10.4.3 向下的代码移动向下的代码移动从块从块src向下移动到块向下移动到块dst，假定移动未违反数据相，假定移动未违反数据相关，并使得通过关，并使得通过dst到到src的路径运行得较快的路径运行得较快若若dst和和src等等价价，则则被被移移动动操操作作应应该该被被执执行行时时，它它正好仅被执行一次正好仅被执行一次src未未后后支支配配dst, 向向下下移移动动的的代代码码经经常常是是存存储储操操作作, 复制从复制从src到到dst路径上的各块，并把路径上的各块，并把被移动操作仅放置在被移动操作仅放置在dst的新拷贝中的新拷贝中 dst没有后支配没有后支配src，插入补偿代码以，插入补偿代码以保证被移动操作在不经保证被移动操作在不经dst路径上也执行路径上也执行srcdst10.4 全局代码调度全局代码调度10.4.4 更新数据相关更新数据相关代码移动会改变操作之间的数据相关关系代码移动会改变操作之间的数据相关关系两两个个对对x的的赋赋值值之之一一可可以以移移动动到到最最上上面面的的基基本本块块，该变换能维持原来程序中的所有相关性该变换能维持原来程序中的所有相关性一旦一个对一旦一个对x的赋值被上移，另一个就不能移动了的赋值被上移，另一个就不能移动了移动使得移动使得x在最上面块的出口在最上面块的出口由不活跃变成活跃由不活跃变成活跃一个变量在某个程序点一个变量在某个程序点活跃，则就不能把对它的投机活跃，则就不能把对它的投机定值移到该点的上面定值移到该点的上面x = 1x = 210.4 全局代码调度全局代码调度10.4.5 全局调度的其他问题全局调度的其他问题 程程序序调调度度应应该该使使经经常常执执行行的的路路径径运运行行得得快快一一些些，不经常执行的路径可能会因调度变得慢一些不经常执行的路径可能会因调度变得慢一些 编译器可用来估计执行频率的技术有若干种编译器可用来估计执行频率的技术有若干种(1) 内循环比外循环执行得更频繁内循环比外循环执行得更频繁(2) 分支指令往回跳转比不跳转要更经常分支指令往回跳转比不跳转要更经常(3)看看守守程程序序出出口口或或异异常常处处理理例例程程的的分分支支语语句句很很少被执行少被执行最最好好的的频频率率估估计计来来自自动动态态剖剖析析，程程序序被被静静态态插插桩桩以用来运行时记录条件分支每次的走向以用来运行时记录条件分支每次的走向10.4 全局代码调度全局代码调度10.4.5 全局调度的其他问题全局调度的其他问题 最简单的全局调度算法也相当复杂，不介绍最简单的全局调度算法也相当复杂，不介绍 在在一一些些全全局局调调度度算算法法中中，循循环环迭迭代代的的边边界界是是代代码码移移动动的一种屏障，需循环展开的一种屏障，需循环展开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 静态调度器和动态调度器的相互影响静态调度器和动态调度器的相互影响动态调度器的优点是可以根据运行时的情况建立新动态调度器的优点是可以根据运行时的情况建立新的调度表，无需事先编码所有可能的调度表的调度表，无需事先编码所有可能的调度表10.4 全局代码调度全局代码调度10.4.6 静态调度器和动态调度器的相互影响静态调度器和动态调度器的相互影响存在动态调度情况下，静态调度器的作用存在动态调度情况下，静态调度器的作用保保证证尽尽早早地地取取高高延延迟迟的的指指令令，使使得得动动态态调调度度器器能能够尽早发射它们够尽早发射它们尽尽早早安安排排预预取取指指令令，使使数数据据到到要要用用时时已已经经在在缓缓存存, 或尽早安排可能不命中缓存的操作或尽早安排可能不命中缓存的操作只只需需要要给给数数据据相相关关的的操操作作安安排排正正确确的的次次序序，无无需需通过极小化延迟来分离每一对数据相关的操作通过极小化延迟来分离每一对数据相关的操作给给分分支支预预测测指指令令较较高高优优先先级级，以以减减少少预预测测错错误误的的代价代价10.5 软软 件件 流流 水水 10.5.1 引言引言软件流水是一种调度算法，它每次调度一个软件流水是一种调度算法，它每次调度一个完整的循环，以充分利用穿越迭代的并行性完整的循环，以充分利用穿越迭代的并行性单次迭代的操作中几乎没有什么并行性单次迭代的操作中几乎没有什么并行性软软件件流流水水技技术术不不断断地地重重叠叠一一些些相相继继迭迭代代，直直到到所所有迭代都填入流水线为止有迭代都填入流水线为止能产生高效和紧凑的代码能产生高效和紧凑的代码以一周期内可以同时发射一个读取、一个存储、以一周期内可以同时发射一个读取、一个存储、一个算术运算（全流水）和一个分支操作的机器一个算术运算（全流水）和一个分支操作的机器来举例来举例10.5 软软 件件 流流 水水 每次调度一个迭代的结果见右边每次调度一个迭代的结果见右边for (i = 0; i n; i +) / R1, R2, R3 = &A, &B, &D Di = Ai Bi + c; / 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, L 该计算大部分是该计算大部分是串行的，它需要串行的，它需要7周期，只有循周期，只有循环回跳指令和迭环回跳指令和迭代中最后一条指代中最后一条指令重叠令重叠 10.5 软软 件件 流流 水水 循环展开循环展开4次迭代的调度结果见右边次迭代的调度结果见右边for (i = 0; i = 5)N2 = 1 + 2 (N 1) / 2);elseN2 = 0;for (i = 0; i N2; i +)/ 该循环被流水化该循环被流水化Di = Ai Bi + c;for (i = N2; i N; i +)/ 不需要优化不需要优化Di = Ai Bi + c;10.5 软软 件件 流流 水水 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 软件流水的目标和约束软件流水的目标和约束目标目标基本目标是极大化耗时较长的循环的吞吐能力基本目标是极大化耗时较长的循环的吞吐能力次要目标是保持所产生代码的规模较小次要目标是保持所产生代码的规模较小达到目标的体现达到目标的体现软件流水化的循环应该有较小的流水线稳定状态软件流水化的循环应该有较小的流水线稳定状态实现策略实现策略 让让每每次次迭迭代代的的相相对对调调度度都都相相同同，并并且且这这些些迭迭代代以以同样的时间间隔逐步启动同样的时间间隔逐步启动10.5 软软 件件 流流 水水 10.5.5 软件流水的目标和约束软件流水的目标和约束资源约束资源约束令令机机器器资资源源由由R = r1, r2, .表表示示，其其中中ri是是第第i类类资资源可用部件数源可用部件数若循环的一次迭代需要第若循环的一次迭代需要第i类资源类资源ni个部件个部件流水化循环的平均启动间隔至少是流水化循环的平均启动间隔至少是maxi(ni/ri)周期周期如如果果maxi(ni/ri)小小于于1，则则将将源源代代码码展展开开几几次次是是有有用的用的10.5 软软 件件 流流 水水 10.5.5 软件流水的目标和约束软件流水的目标和约束数据相关数据相关一一个个操操作作可可能能依依赖赖于于前前一一次次迭迭代代中中同同样样操操作作的的结结果，不同于到目前为止碰到的数据相关果，不同于到目前为止碰到的数据相关仅仅用用延延迟迟来来标标记记边边不不够够用用，需需要要区区别别不不同同迭迭代代中中同一操作的实例，例如：同一操作的实例，例如：for (i = 2; i n; i +)Ai = Bi + Ai 2写写Ai和读和读Ai 2的依赖边上标记的迭代次数差的依赖边上标记的迭代次数差是是210.6 并行性和数据局部性优化概述并行性和数据局部性优化概述并行编程模型并行编程模型任务并行任务并行数据并行数据并行流水线并行（前面几节涉及较多）流水线并行（前面几节涉及较多）本节内容围绕任务并行和数据并行本节内容围绕任务并行和数据并行介绍并行计算机系统结构的概况介绍并行计算机系统结构的概况给给出出并并行行化化的的基基本本概概念念，程程序序循循环环的的变变换换，还还有有对并行化有用的概念对并行化有用的概念类似的考虑怎样用于优化数据局部性类似的考虑怎样用于优化数据局部性以矩阵乘算法的优化为例以矩阵乘算法的优化为例 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.1 多处理器多处理器对称多处理器的体系结构对称多处理器的体系结构二级二级缓存缓存内存内存总线总线二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器多个高性多个高性能处理器能处理器集成在一集成在一块芯片上块芯片上10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.1 多处理器多处理器对称多处理器的体系结构对称多处理器的体系结构二级二级缓存缓存内存内存总线总线二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器多个高性多个高性能处理器能处理器集成在一集成在一块芯片上块芯片上 通过共通过共享内存来享内存来进行通信进行通信必须在处理器的缓存中必须在处理器的缓存中找到它操作的大部分数找到它操作的大部分数据，以保证性能据，以保证性能10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.1 多处理器多处理器分布式内存机器分布式内存机器总线或其它互连总线或其它互连二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器局部局部内存内存局部局部内存内存局部局部内存内存局部局部内存内存在内存分在内存分层中又引层中又引入一层入一层处理器能处理器能迅速访问迅速访问自己的局自己的局部内存部内存 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.1 多处理器多处理器分布式内存机器分布式内存机器总线或其它互连总线或其它互连二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存二级二级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存一级一级缓存缓存处理器处理器处理器处理器处理器处理器处理器处理器局部局部内存内存局部局部内存内存局部局部内存内存局部局部内存内存在内存分在内存分层中又引层中又引入一层入一层处理器能处理器能迅速访问迅速访问自己的局自己的局部内存部内存 非均匀内存访问的机器和消息传非均匀内存访问的机器和消息传递的机器；为获得良好的性能递的机器；为获得良好的性能软件都必须有很好局部性软件都必须有很好局部性 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.2 应用中的并行性应用中的并行性并行应用性能衡量的两种标准并行应用性能衡量的两种标准并行覆盖：整个计算中并行运行部分的百分比并行覆盖：整个计算中并行运行部分的百分比并并行行粒粒度度：处处理理器器上上无无需需和和其其它它处处理理器器同同步步或或通通信的计算量信的计算量循环对并行化来说特别有吸引力，循环可以有许循环对并行化来说特别有吸引力，循环可以有许多次迭代计算，如果这些计算相互独立，则它们是多次迭代计算，如果这些计算相互独立，则它们是并行计算的主要来源并行计算的主要来源许多控制结构简单、数据量大并且耗时长的科学许多控制结构简单、数据量大并且耗时长的科学和工程应用，很容易以较细粒度被并行化和工程应用，很容易以较细粒度被并行化 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.3 循环级并行循环级并行耗时的应用一般都使用大数组，导致程序中出现耗时的应用一般都使用大数组，导致程序中出现有许多次迭代的循环，这些迭代经常相互独立，可有许多次迭代的循环，这些迭代经常相互独立，可以把这类循环的大量迭代分到各处理器上以把这类循环的大量迭代分到各处理器上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 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.3 循环级并行循环级并行对并行化来说，任务级不像循环级那样有吸引力对并行化来说，任务级不像循环级那样有吸引力对对一一个个程程序序而而言言，独独立立的的任任务务数数是是一一个个常常数数，它它不不像像典典型型的的循循环环那那样样，独独立立的的计计算算单单元元随随迭迭代代次次数增加而增加数增加而增加任任务务通通常常不不是是等等规规模模的的，因因此此很很难难保保证证所所有有的的处处理器在所有时间都处于忙碌理器在所有时间都处于忙碌10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.4 数据局部性数据局部性程序局部性程序局部性大大多多数数程程序序的的大大部部分分时时间间在在执执行行一一小小部部分分代代码码，并且仅涉及一小部分数据并且仅涉及一小部分数据时间局部性时间局部性 程程序序访访问问的的内内存存单单元元在在很很短短的的时时间间内内可可能能再再次次被被程序访问程序访问空间局部性空间局部性毗毗邻邻被被访访问问单单元元的的内内存存单单元元在在很很短短的的时时间间内内可可能能被访问被访问10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.4 数据局部性数据局部性同同一一个个缓缓存存行行上上的的元元素素一一起起被被使使用用的的情情况况是是空空间间局部性的一种重要形式局部性的一种重要形式这这种种空空间间局局部部性性将将缓缓存存未未命命中中降降到到最最低低，因因此此使使得程度获得明显的加速得程度获得明显的加速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 并行性和数据局部性优化概述并行性和数据局部性优化概述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 (j = 0; j n; j+) Zi, j = 0;10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.4 数据局部性数据局部性操作在数组上的数值应用的几个重要特征操作在数组上的数值应用的几个重要特征数组代码经常有许多可以并行化的循环数组代码经常有许多可以并行化的循环当循环有并行性时，它们的迭代可按任意次序执当循环有并行性时，它们的迭代可按任意次序执行，因而可重新安排计算次序以彻底改进数据局行，因而可重新安排计算次序以彻底改进数据局部性部性在创建相互独立的并行计算大单元时，串行执行在创建相互独立的并行计算大单元时，串行执行这些单元往往会产生较好的数据局部性这些单元往往会产生较好的数据局部性10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.5 矩阵乘法算法矩阵乘法算法该该算算法法是是计计算算密密集集型型的的，原原则则上上内内存存访访问问不不应应该该构成瓶颈构成瓶颈假定矩阵的布局是行为主假定矩阵的布局是行为主假定正好假定正好c个数组个数组元素能够放满一个元素能够放满一个缓存行，缓存行，X的一行仅的一行仅散布在散布在n/c个缓存行上个缓存行上假定缓存足以放下假定缓存足以放下X所所有的缓存行，读入有的缓存行，读入X出出现现n2/c次缓存未命中次缓存未命中for (i = 0; i n; i+)for (j = 0; j n; j+) Zi, j = 0.0; for (k = 0; k n; k+) Zi, j = Zi, j + Xi, k Yk, j;10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.5 矩阵乘法算法矩阵乘法算法先考虑在单处理器上顺序执行先考虑在单处理器上顺序执行j = 0 1 n 1i = 0XY 完成完成Z一行元一行元素的计算，素的计算，取取Y出现的缓出现的缓存未命中次数存未命中次数在在n2/c和和n2之间之间 完成整个完成整个Z，Y未命中次数未命中次数在在n2/c和和n3之间之间10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.5 矩阵乘法算法矩阵乘法算法再考虑在再考虑在p个处理器上并行计算个处理器上并行计算把把Z不不同同行行的的计计算算指指派派到到不不同同处处理理器器，每每个个处处理理器计算器计算Z的连续的连续n/p行行每每个个处处理理器器访访问问矩矩阵阵X和和Z的的n/p行行以以及及整整个个Y，用用n3/p次乘加运算来完成对次乘加运算来完成对Z的的n2/p个元素的计算个元素的计算虽虽然然计计算算时时间间与与p成成比比例例减减少少，但但通通信信代代价价却却与与p成成比比例例增增加加，因因为为交交付付给给p个个处处理理器器之之缓缓存存的的总总缓缓存行是存行是n2/c + pn2/cp逼近逼近n时，计算时间为时，计算时间为O(n2)，通信代价为，通信代价为O(n3) 10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.6 矩阵乘法算法的优化矩阵乘法算法的优化 复用在缓存的数据才代表数据局部性好复用在缓存的数据才代表数据局部性好复用应该很快发生，数据才可能还在缓存复用应该很快发生，数据才可能还在缓存在在上上述述算算法法中中，n2个个乘乘加加操操作作隔隔开开了了矩矩阵阵Y中中同同一一个个数数据据的的复复用用，n个个乘乘加加操操作作隔隔开开了了Y中中同同一一个个缓缓存行的复用存行的复用分分块块是是重重排排循循环环中中迭迭代代次次序序的的一一种种方方法法，它它能能够够极大地改进程序的局部性极大地改进程序的局部性10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.6 矩阵乘法算法的优化矩阵乘法算法的优化 从从第第4到到7行行的的程程序序计计算算左左上上角角为为Xii, kk和和Ykk, jj的两块对左上角为的两块对左上角为Zii, jj的块的贡献的块的贡献for (ii = 0; ii n; ii = ii + b) for (jj = 0; jj n; jj = jj + b)for (kk = 0; kk n; kk = kk + b) for (i = ii; i ii + b; i+) for (j = jj; j jj + b; j+)for (k = kk; k kk + b; k+) Zi, j = Zi, j +Xi, k Yk, j;bn10.6 并行性和数据局部性优化概述并行性和数据局部性优化概述10.6.6 矩阵乘法算法的优化矩阵乘法算法的优化 适当选择适当选择b，使，使3个矩阵都有一个块可以装到缓存个矩阵都有一个块可以装到缓存把把X或或Y一块取到缓存，会出现一块取到缓存，会出现b2/c次缓存未命中次缓存未命中对对于于X和和Y的的一一对对块块，第第4到到7行行的的程程序序完完成成b3次次乘乘加计算加计算由由于于整整个个矩矩阵阵乘乘法法需需要要n3次次乘乘加加计计算算，则则取取一一对对块到缓存的总次数是块到缓存的总次数是n3/b3对对于于X和和Y的的一一对对块块会会有有2b2/c次次缓缓存存未未命命中中，因因此此缓存未命中的总次数是缓存未命中的总次数是2n3/bc和和节节的的O(n3/c)，甚甚至至O(n3)次次缓缓存存未未命命中中相相比比，在在b较大时，较大时，2n3/bc能体现出分开方法的好处能体现出分开方法的好处习习 题题第一次：第一次：10.1, 10.3第二次：第二次：10.5, 10.6