多处理机并行算法的研究思路.ppt

下面就以此表达式的计算为例，经并行编译得到如下程序：  Z=E+A*B*C/D+F 的计算为例， 经并行编译得到如下程序： S1 G=A*B S2 H=C/D S3 I=G*H S4 J=E+F S5 Z=I+J 图 7.21 计算Z=E+A*B*C/D+F的并行程序数据相关图 利用FORK和JOIN语句实现这种派生和汇合关系，将程序改写为： FORK 20 10 G=A*B (进程S1) JOIN 2 GOTO 30 20 H=C/D (进程S2) JOIN 2 30 FORK 40 I=G*H (进程S3) JOIN 2 GOTO 50 40 J=E+F (进程S4) JOIN 2 50 Z=I+J (进程S5) 图 7.22 图 7.21 的计算程序在多处理 机上运行的资源时间图 　　假定A、B两个 8×8 矩阵相乘，需要在多处理机上实现任务一级即外循环的并行。用FORTRAN语言书写的程序如下： DO 10 J=0, 6 10 FORK 20 J=7 20 DO 30 I=0, 7 C(I,J)=0 DO 40 K=0, 7 40 C(I,J)=C(I,J)+A(I,K)*B(K,J) 30 CONTINUE JOIN 8 7.2.2多Cache的一致性问题的解决办法 　　1.解决进程迁移引起的多Cache不一致性 　　对于进程迁移引起的多Cache之间的不一致，可以通过禁止进程迁移的办法予以解决，也可以在进程挂起时，靠硬件方法将Cache中该进程改写过的信息块强制写回主存相应位置来解决。 　　2.以硬件为基础实现多Cache的一致性 　　以硬件为基础实现多Cache的一致性的办法有多个。最普遍采用的办法叫监视Cache协议(SnoopyProtocol)法，各个处理机中的Cache控制器随时都在监视着其他Cache的行动。对于采用总线互连共享主存的多处理机，可利用总线的播送来实现。当某台处理机首次将数据写入自身Cache中某一信息块的同时，也将其写入主存，并且利用这个写主存操作信号通知总线上所有其他处理机的Cache控制器，将总线上给出的地址与各自的Cache目录表中的信息块地址作比较。如果存有这个信息块的副本，都应把此副本作废，以便那些处理机要访问该信息块时，按缺块处理，到主存中去调，以此来实现Cache的一致性。 　　这种把数据块作废的方法叫写作废法。这样，某台处理机在将信息第一次写入Cache某信息块后，如果还有信息要写入该信息块时，就可以只写入自己的Cache中，而不用再写入主存，直到这个块要被替换时，才写回主存。另一种做法则是通知总线上所有其他处理机的Cache控制器，如有此副本的，都进行更新。这种把所有副本信息块更新的做法叫写更新法，或者叫播写法。监视Cache协议法实现简单，但只适用于总线式互连的多处理机。而且，不管是写作废还是写更新都要占用总线不少时间(虽然写作废法可比写更新法少占总线时间)，因此只能用于机数少的多处理机中。商品化的多处理机大多采用此法。如IBM公司的IBM370/168MP、IBM3033,Alliant计算机系统公司的AlliantFX，Seguent计算机系统公司的Symmetry多处理机等都采用写作废法；DEC公司的Firefly多处理机工作站则采用写更新法。 　　当多处理机的机数很多，或者不采用总线式互连时，监视Cache协议法就不适用了。例如采用多级网络互连的多处理机中，多级网络无法播送这个通知，所以要采取其他的办法。其中，主要是目录表法。这种方法要建立一个目录表。目录表中的每一项中记录一个数据块的使用情况，包括用几个标志位分别指示这个信息块的副本在其他几个处理机的Cache中是否存在。例如，用0表示对应此位之Cache中没有该副本，用1表示对应此位之Cache中有该副本。另外，还设一个标志位记录是否已有Cache向这个信息块写入过。有了这个目录表后，一个处理机在写入自身Cache的同时，只需有选择地通知所有其他存有此数据块的Cache将副本作废或更新即可。 　　目录表的具体作法又可分三种。一种是全映像目录表，表中每项有N个标志位对应于多处理机中全部N台处理机的Cache。系统中全部Cache均可同时存有同一个信息块的副本。不过，这样的目录表很庞大，硬件及控制均较复杂。另一种是有限目录表法，表中每项的标志位少于N个。因此，限制了一个数据块在各Cache中能存放的副本数目。这两种目录表都是集中地存入在共享的主存之中，因此需要