程序并行性ppt课件.ppt

《程序并行性ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机系统结构第二十一讲程序并行性1并行性分析一、并行性检测1.相关类型数据相关—RAW相关，数据反相关—WAR相关，数据输出相关—WAW相关，控制相关—条件语句。2.并行性检测--伯恩斯坦准则Ii—读单元集，Oi—写单元集，P1、P2可并行条件：I1∩O2=φ，并且I2∩O1=φ，并且O1∩O2=φ。每个程序段在执行过程中通常要使用输入和输出这两个分离的变量集。若用Ii表示Pi程序段中操作所要读取的存储单元集，用Oi表示要写入的存储单元集，则P1和P2两个程序段能并行执行的伯恩斯坦准则是：2例：假设两个处理机执行下面P1、P2程序，判断它们能否并行执行。P

2、1：A＝B＋C＋DP2：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例：若有3个程序段P1，P2和P3，分别求3个矩阵算术表达式，判断3台处理机能否并行执行。P1：X＝(A＋B)×(A-B)P2：Y＝(C＋1)×（C＋D）－1P3：Z＝X+Y其中，A、B、C、D、X和Y均为N×N的矩阵。[解]它们的输入、输出变量集分别为I1={A,B}  I2={C

3、,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程序段执行完毕方可开始执行。4二、并行程序设计语言1.开发方式语言形成方式：扩充语言功能、重新设计并行语言对语言的要求：灵活性、效率程序设计方式：显式、隐式2.扩展语言中三种并行结构FORK-JOIN：不同机器有不同形式，效果相同FORKA：派生一个进程，当前进程继续，JOINJ：J为已派生出的并发进程的个数。JOIN语句附带有一

4、个计数器。计数器C初值为0。执行JOIN语句计数器C的内容加1，与J比较，若等于J继续后继指令，并使C=0。否则，结束该进程，释放PE。5例：3个PE并行处理8×8矩阵乘法。DO10J=0，610FORK20/*派生处理第0~6进程*/J=7/*当前进程处理第7进程*/20DO40I=0，7/*处理0~7行*/C(I,J)=0DO30K=0,7/*处理C(I,J)*/30C(I,J)=C(I,J)+A(I,K)*B(K,J)40CONTINUEJOIN8…6PEtJ=0J=1J=2J=3J=7J=4J=5J=67次C=1C=2C=3C=4C=5C=6C=7C

5、=87块结构语言：把可并行执行的进程用cobegin-coend括起来处理,最后一条语句执行完成后，方可执行后续语句。该语句可嵌套；可使用共享变量，但不允许修改。S0S2S4S3S5S1S7S6S88三、并行算法分为同步并行算法、异步并行算法、宏流水线算法。1.同步并行算法进程某些段要等待其它进程以保持同步的并行算法。同步并行算法只适用于进程速度波动较小的情况。2.异步并行算法进程间的通信通过全局变量或共享数据进行的，不需要等待任何输入触发。有简单异步迭代算法和自适应算法两种。异步并行算法通过进程交替进行，提高处理速度。3.宏流水并行算法计算可分为几部分的输

6、出是另一部分输入的算法。9粒度划分与组合并行程序设计时要回答两个基本问题：（1）如何将程序划分成并行模块、子任务以获得最短执行时间。（2）计算中的并发粒度为多大会比较理想。这与问题以及机器都有关，需要在并行性与调度开销之间做折衷多处理机的性能衡量任务粒度大小的一个依据是E/C的比值E----程序有效计算的执行时间C----处理机间的通信的辅助开销时间多处理机的性能很大程度上依赖于E/C比值10任务粒度过小，辅助开销大，系统效率底；任务粒度过大，并行度低，系统性能不会高；只有E/C的值比较大时，开发并行性才能得到好处。11细粒度程序的调度1.一个细粒度程序调

7、度的例子Vara,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,qBegin1a:=12b:=23c:=34d:=45e:=56f:=67g:=a*b8h:=c*d9i:=d*e10j:=e*f11k:=d*f12l:=j*k13m:=4*l14n:=3*m15o:=n*i16p:=o*h17q=p*gEnd12指令1，2，3，4，5，6是存储器访问（取数据）操作，每个结点用一个周期进行寻址，用六个周期从存储器取数。指令7-17是CPU操作，每个需要两个周期完成。程序图：每个结点相当于程序中的计算单元粒度用执行结点中全部操作所需要的基本时间来度

8、量（处理机和存储器）程序图中的结点表示如下图：13n