21程序并行性.ppt

细粒度程序的调度1.一个细粒度程序调度的例子 Var a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q Begin 1 a:=1 2 b:=2 3 c:=3 4 d:=4 5 e:=5 6 f:=6 7 g:= a*b 8 h:= c*d 9 i:= d*e 10 j:= e*f 11 k:= d*f 12 l:= j*k 13 m:= 4*l 14 n:= 3*m 15 o:= n*i 16 p:= o*h 17 q= p*g End * 重庆大学计算机学院 计算机系统结构 计 算 机 系 统 结 构 第二十一讲 程序并行性 并行性分析 一、并行性检测 1.相关类型 数据相关—RAW相关，数据反相关—WAR相关， 数据输出相关—WAW相关，控制相关—条件语句。 2.并行性检测 --伯恩斯坦准则 Ii—读单元集，Oi—写单元集， P1、P2可并行条件： I1∩O2=φ，并且I2∩O1=φ，并且O1∩O2=φ。 每个程序段在执行过程中通常要使用输入和输出这两个分离的变量集。若用Ii表示Pi程序段中操作所要读取的存储单元集，用Oi表示要写入的存储单元集，则P1和P2两个程序段能并行执行的伯恩斯坦准则是： 例：假设两个处理机执行下面P1、P2程序，判断它们能否并行执行。 ???????????? P1： A＝B＋C＋D ???????????? P2： E＝A*D [解] 根据伯恩斯坦准则： ????? I1={B，C，D}?? O1={A}?? I2={A，D}?? O2={E} 所以有下式： ????? I1∩O2={B，C，D}∩{E}=Φ； ????? I2∩O1={A，D}∩{A}≠Φ 不满足伯恩斯坦准则，出现数据相关，因此P1和P2不能并行执行。 例：若有3个程序段P1，P2和P3，分别求3个矩阵算术表达式，判断3台处理机能否并行执行。 ????? P1： X＝(A＋B)×(A-B) ????? P2： Y＝(C＋1)×（C＋D）－1 ????? P3： Z＝X+Y 其中，A、B、C、D、X和Y均为N×N的矩阵。 [解] 它们的输入、输出变量集分别为 ????? I1={A,B}?? I2={C,D}?? I3={X,Y} ????? O1={X}???? O2={Y}???? O3={Z} 由于I1∩O2＝Ф，I2∩O1＝Ф以及O1∩O2＝Ф，故P1和P2两个程序段可以并行执行；由于I3∩O1≠Ф和I3∩O2≠Ф，故P3程序段必须在P1和P2程序段执行完毕方可开始执行。 二、并行程序设计语言 1.开发方式 语言形成方式：扩充语言功能、重新设计并行语言 对语言的要求：灵活性、效率 程序设计方式：显式、隐式 2.扩展语言中三种并行结构 FORK-JOIN：不同机器有不同形式，效果相同 FORK A： 派生一个进程，当前进程继续， JOIN J： J为已派生出的并发进程的个数。 JOIN语句附带有一个计数器。计数器C初值为0。执行JOIN语句计数器C的内容加1，与J比较，若等于J继续后继指令，并使C=0。否则，结束该进程，释放PE。 例：3个PE并行处理8×8矩阵乘法。 DO 10 J=0，6 10 FORK 20 /*派生处理第0~6进程*/ J=7 /*当前进程处理第7进程*/ 20 DO 40 I=0，7 /*处理0~7行*/ C(I,J)=0 DO 30 K=0,7 /*处理C(I,J)*/ 30 C(I,J)=C(I,J)+A(I,K)*B(K,J) 40 CONTINUE JOIN 8 … PE t J=0 J=1 J=2 J=3 J=7 J=4 J=5 J=6 7次 C=1 C=2 C=3 C=4 C=5 C=6 C=7 C=8 块结构语言： 把可并行执行的进程用cobegin-coend括起来处理,最后一条语句执行完成后，方可执行后续语句。 该语句可嵌套；可使用共享变量，但不允许修改。 S0 S2 S4 S3 S5 S1 S7 S6 S8 三、并行算法 分为同步并行算法、异步并行算法、宏流水线算法。 1.同步并行算法 进程某些段要等待其它进程以保持同步的并行算法。 同步并行算法只适用于进程速度波动较小的情况。 2.异步并行算法 进程间的通