编译原理课件chap12.ppt

第十二章并行编译基础 第十二章并行编译基础 并行计算机是近二十几年来发展迅速的一类计算机 并行编译系统已经成为了现代高性能计算机系统中一个重要的部分 并行程序设计主要有两种途径 即使用并行程序设计语言编写并行程序 或将串行程序并行化 因此 并行编译系统就是能够处理并程序设计语言 能够实现串行程序并行化 具有并行优化能力的编译系统 并行编译技术中两个最重要的内容便是串行程序的向量化和并行化 第十二章并行编译基础 向量化是将串行程序中可向量化的部分改写成用向量运算表示的等价程序 其编译技术已趋成熟 并行化 是将串行程序中可并行化的部分改写成在多处理机上并行执行的等价程序 由于涉及到数据的私有化 分布和通信 以及并行任务划分等诸多问题 因此并行化技术是难度很大且仍在研究之中的技术 向量化和并行化这两种编译技术有很大的共同之处 其一是它们的优化对象是相同 二者均把源程序中的循环作为优化的对象 其二是它们所依赖的基础技术相同 二者均把数据依赖关系分析技术作为优化的依据 第十二章并行编译基础 所以从原理上讲数据依赖关系分析技术在本章的地位是十分重要的 本章介绍并行编译技术的基础知识 主要是依赖关系分析的基础理论以及向量化 并行化的基础知识 12 1节简单介绍现代高性能计算机的体系结构和并行编译系统的结构 以作为后续各章的基础 12 2节介绍若干预备概念 12 3节介绍数据依赖关系的若干定义 12 4 12 5节讲述数据依赖关系分析技术 12 6节讲述如何根据依赖关系判别可向量化循环与可并行化循环 这几节是各种并行优化的理论基础 也是本章学习的重点 第十二章并行编译基础 12 1并行计算机及其编译系统并行计算机体系结构大致可分为向量计算机 共享存储器多处理机以及分布存储器大规模并行计算机三类 12 1 1向量计算机向量是由类型相同的标量数据项组成的集合 向量计算机是具有向量处理能力的计算机 它是在标量处理机的基础上增加了向量处理部分而构成的 向量处理部分通常含有若干向量寄存器 若干向量流水功能部件 以及一个控制向量操作长度的寄存器 与标量操作只对一个或一对操作数进行处理不同 向量操作同时对向量的所有元素进行处理 每次向量操作涉及的元素数由向量长度寄存器控制 第十二章并行编译基础 并行编译针对向量计算机的一个重要功能是串行程序向量化 显然程序中的向量成分越多 向量机的运行效率就越高 向量化自动地寻找源程序中可以向量化的循环 必要时对循环作适当的改写或变换 以利于向量化 12 1 2共享存储器多处理机共享存储器多处理机是由多个处理机和一个共享存储器 以及专门的同步通信部件构成的计算机系统 共享存储器多处理机在更大的范围内提供了并行处理能力 向量机只能并行处理向量操作 而多处理机可以并行执行多个循环迭代 语句块 子程序段 当多处理机系统的每一个处理机都是向量机时 还可以实现高层并行处理和低层向量处理 第十二章并行编译基础 共享贮存多处理机的并行编译系统由许多专门的工作要做 这些工作包括 串行程序并行化和编译并行语法成分12 1 3分布式存储器大规模并行计算机这类计算机是有成百 上千乃至上万个结点构成的并行机 每个结点有自己的处理机和存储器 结点之间以互联网络相连 目前大规模并行机上的并行编译系统主要是针对数据并行语言的 它需要完成以下几种处理 第十二章并行编译基础 数据分布 数据分布的目的是提高数据的局部性和并行性 减少通信开销 从而提高程序的执行速度 任务划分 任务划分是指如何在多个处理机上分配并行任务 使得程序可以高效地并行执行 同步与通信 并行编译对同步与通信的处理主要包括确定同步与通信点并插入相应的并行库子程序调用 以及同步同信优化 12 1 4并行编译系统的结构从功能上看 并行编译系统通常包括程序分析 程序优化和并行代码生成三个部分 12 2基本概念12 2 1向量与向量的次序 第十二章并行编译基础 考虑迪卡尔乘积Zm 其中Z示所有整数组成的集合 称Zm的元素i i1 i2 im 是大小为m的整向量或Zm的向量 任何大小的零向量 0 0 0 均记为0 非零向量i i1 i2 im 的前导元素是它的第一个非零元素 如果前导元素为il 1 l m 称整数l为向量的的层次 记为lev i Zm的零向量的层次为m 1 若向量的的前导元素为正 则称向量i为正向量 反之 若前导元素为负 则称为负向量 零向量和正向量统称为非负向量 Zm的向量之间存在着字典序 设i i1 i2 im j j1 j2 jm 向量i j当且仅当存在整数l 1 l m 使得 i1 j1 i2 j2 il 1 ji 1且il jl换言之 即i j当且仅当j i的方向向量是形式为 0 0 1 且层次为l的正向量 我们用记号i j表示i j或者i j 第十二章并行编译基础 12 2 2循环模型与索引空间本章的后续部分 当说到循环嵌套L时 均指如下形式的FORTRAN循环模型 L1 doI1 p1 q1L2 doI2 p2 q2 LmdoIm pm qmH I1 I2 Im enddo enddoenddo 第十二章并行编译基础 其中 Ir称为索引变量 pr qr分别称为循环初值和循环终值 1 r m p1 q1为常数 pr qr 1 r m 是I1 I2 Ir 1的整值函数 H I1 I2 Im 是由赋值语句组成的集合 记I I1 I2 Im 称之为循环嵌套L的索引向量 I的值称为索引值或索引点 即大小为m的整向量 i1 i2 im 其中p1 i1 q1p2 i1 i2 q2 i1 pm i1 i2 Im 1 im qm i1 i2 Im 1 L的索引空间由所有索引点组成 它是Zm的子空间 若循环的初值与终值均与I1 I2 Im无关且对每个r Pr qr 则索引点的个数是 mr 1 qr pr 1 第十二章并行编译基础 L的循环体是H I1 I2 Im 或H I 给定一个索引值I i1 i2 im 便确定了H的一个实例H I H i1 i2 im 称之为L的一个迭代 由FORTRAN循环的定义 此循环嵌套的迭代是按索引值的字典序顺序执行的 即迭代H I 先于迭代H j 而执行当且仅当I j 对于循环嵌套L 给定一个索引点I i1 i2 im 相应的有一个迭代点I i1 i2 im 索引点与迭代点之间有如下关系 ir pr ir 1 r m L的迭代空间由所有的迭代点组成 它也是Zm的子空间 当pr 0 1 r m 时 索引空间与迭代空间是同一个空间 12 2 3输入与输出集合为了简洁起见 我们用字母S T U V 表示程序中的语句并仅涉及赋值语句 赋值语句的一般形式为 第十二章并行编译基础 S x E其中 x是一个变量 它既可以是简单变量也可以是数组元素 E是一个表达式 对于这样一个语句S 它的输出变量是x 输入变量时出现在E中的任何变量 一般地 输出变量代表这对存储器的写操作 输入变量代表这对存储器的读操作 由语句S的输出语句组成的集合称为S的输出变量集合 记为OUT S 由语句S的所有输入变量组成的集合称为S的输入变量集合 记为IN S 12 2 4语句的执行顺序若在程序中语句S词法上先于语句T 则记为S T S T表示S要麽词法上先于T 要么S与T为同一条语句 我们用 表示语句间的执行顺序 S T表示语句S先于语句T而执行 S i T j 表示循环体中实例S i 先于T的实例T j 而执行 第十二章并行编译基础 引理12 1设S和T是循环嵌套L的循环体内的二条语句 在L的执行中 S的实例S i 先于T的实例T j 而执行当且仅当下列条件之一成立 1 i j 或者 2 i j且S T12 3依赖关系对于计算机程序 当事件或动作A必须先于事件B而发生时 称B依赖于A 我们称这种关系为依赖关系 有时依赖关系是由于读 写或计算 使用同一数据而引起的 称这种关系为数据依赖关系 有时候 依赖关系是由于程序流程而引起的 如一个分支程序是否被执行或跳出循环等 称这种情形为控制依赖关系 第十二章并行编译基础 12 3 1依赖关系定义数据依赖关系定义1已知语句S和T 若存在着变量x使之满足如下述条件之一者 则称语句T依赖于语句S 记为S T 否则 语句S与T之间不存在依赖关系 1 若同时有x OUT S x IN T 且T使用由S计算出的x值 则称T流依赖于S记为S fT 2 若同时有x IN S x OUT T 但S使用x的值先于T对于x的定值 则称T反依赖于S记为S aT 3 若同时有x OUT S x OUT T S对x的定值先于T对x的定值 则称T输出依赖于S记为S 0T 例12 7 考虑下述语句 S A B DT C A 3U A A cV E A 2 第十二章并行编译基础 求它们之间数据依赖关系解 S fT S fU S 0UT fU T aU U fV数据依赖关序定义2设语句S和T是循环嵌套L中的二个语句 语句T依赖于语句S 记为S T 如果存在S的一个实例S i T的一个实例T j 以及S的一个变量u T的一个变量 v使得 1 u和v至少有一个是它所在语句的输出变量 2 u在实例S i 中和v在实例T j 中都表示同一个存储单元M 3 在L的顺序执行中 S i 先于T j 被执行 4 在L的顺序执行中 从S i 结束执行到T j 开始执行期间 没有其它对T依赖于S的操作 如果变量u v和实例S i T j 满足这四个条件 则称变量u v引起T依赖于S 称实例T j 依赖于实例S i 第十二章并行编译基础 由u v引起的依赖关系是 流依赖 如果u OUT S v IN T 反依赖 如果u IN S v OUT T 输出依赖 如果u OUT S v OUT T 在此定义中 语句S和T不必是不同的 但条件3要求实例S i 和T j 是不同的 T对S的依赖关系是所有满足上述条件的偶对S i T j 组成的集合 即 f a 0 12 3 2语句依赖图一给定程序的语句依赖关系图是关系 的有向图 图中每个结点表示一个语句 结点S和T有一条弧当且仅当S T 用弧表示流依赖 用短线的弧表示反依赖 用带小圈的弧表示输出依赖 依赖关系 的传递闭包 记为 是间接依赖关系 因此 若在语句依赖图上存在这一条从S至T的路径 则语句T间接依赖于语句S 记为S T 第十二章并行编译基础 12 3 3依赖距离 依赖方向与依赖层次设语句S和T是循环嵌套L中的语句 如果语句T依赖于