硬件和软件并行性.ppt

Advanced Computer Architecture 第二章 程序和网络特性 程序行为的基本特征： 计算粒度 程序划分条件 软件与硬件的匹配 程序流机制 并行性的编译支持 主要互连网络： 静态/动态互连网络 网络复杂性 通信带宽 数据寻径功能 2．1．1．相关性 通常相关性有数据相关、控制相关、资源相关等。通过相关图来观察可并行化和向量化的地方。 相关性有： l局部相关：数据相关、存储器相关、寄存器相关、… l全局相关：数据相关、转移相关、中断相关、…  Advanced Computer Architecture * Advanced Computer Architecture * 2．1 并行性条件 并行处理的三个关键领域（H.T.Kung,1991） 并行计算的计算模型 并行系统结构中的处理机间的通信 将并行系统加入通用计算环境的系统集成 并行性形式的依赖：（时间、空间、性能、价格因素之间的折中） 并行性级别 计算粒度 时间与空间复杂性 通信时延 调度策略 负载平衡 例：（数据相关）定义五种数据相关： （1） 流相关：如果从S1到S2存在执行通路，而且如果S1至少有一个输出可供S2用作输入，则S2与S1流相关。表示为S1→S2. （2） 反相关：如果在程序次序中S2紧接S1，而且如果S2的输出与S1的输入重叠，则S2与S1反相关。表示为S1→S2。 （3） 输出相关：如果两条语句能产生同一输出变量，则它们是输出相关。表示为S1→S2。 （4） I/O相关：读与写都是I/O语句。 (5）未知相关：下列情况，两条语句之间的相关关系不能确定 l变量下标就是它本身（间接寻址）； l下标不包括循环指标变量； l带有不同循环变量系数的下标的变量不止一次地出现； l下标在循环指标变量中是非线性的。 S1： Load R1，A /R1←Memory（A）/ S2： Add R2，R1 /R2←（R1）+（R2）/ S3： Move R1，R3 /R1←（R3）/ S4： Store B，R1 /Memory（B）←（R1）/ 上面四条语句中包含有相关关系： lS2与S1是流相关：变量A通过寄存器R1传送。 lS3与S2是反相关：寄存器R1的内容存在潜在的冲突。 lS3与S1是输出相关：它们二者都要修改同一个寄存器R1。 但是S2与S4无关。（图2-1b） 控制相关： 语句执行次序在运行前不能确定的情况。例如条件转移语句。控制相关常使正在开发的并行性中止，因此要使用编译技术来克服控制相关。 资源相关： 与并行事件利用整数部件、浮点部件、寄存器、存储器等共享资源时发生的冲突有关。如ALU相关、存储器相关等等。 Bernstein条件（1966）：检测程序的并行性 设有两个进程（进程的定义：与不同处理级别上的程序段抽象相对应的软件实体）P1和P2，它们的输入集合分别为I1和I2，输出集合分别为O1和O2。如果这两个进程不相关（流不相关、反不相关、输出不相关…），那么它们就能并行运行，表示为P1∥P2。 形式化表示： I1∩O2=φ I2∩O1=φ O1∩O2=φ 例：（用Bernstein条件来检测程序的并行性） 设五条语句，每条语句只需要一步（即不考虑流水线）。 P1： C=D*E P2： M=G+C P3： A=B+C P4： C=L+M P5： F=G/E （图2-2） 图2-2a表示它们的数据相关和资源相关。 图2-2b表示顺序执行（需五步）。 图2-2c表示并行执行（两个加法器，需三步）。 按Bernstein条件，两两成对。 有10对（P1P2，P1P3，P1P4，P1P5，P2P3，P2P4，P2P5，P3P4，P3P5，P4P5）要进行并行性检测。 检测结果：P1P2（C流相关），P1P3（C流相关），P1P4（C输出相关），P1∥P5，P2∥P3，P2P4（C流相关），P2∥P5，P3P4（C流相关），P3∥P5，P4∥P5。 无资源冲突可并行执行。 有五对P1∥P5，P2∥P3，P2∥P5，P3∥P5，P4∥P5。 但具有传递并行性只有P2∥P3∥P5，而P1与P4会引起传递相关。 一般地说并行性关系有： l可交换性： Pi∥Pj隐含着Pj∥Pi。 l传递性： 只有P2∥P3∥P5有传递性。有不能传递的，即Pi∥Pj和Pj∥Pk但 不一定保证Pi∥Pk。 l结合性： Pi∥Pj∥Pk隐含（Pi∥Pj）∥Pk= Pi∥（Pj∥Pk）。 2．1．2 硬件和软件并行性 （1） 硬件并行性： l机器结构和硬件多样性所决定的并行性类型；它是价格和性能折衷的函数；是同时可执行操作的资源利用方式。 l处理机并行性描述的一种方法：每个机