开始,各处理器的存储内容如图12(a)所示。此时各处理器并行计算C=AXB其中 产=0,1,…p-1,此后第i号处理器将其所存储的B的列块送至第μ-1号处理器(第0号处理器 将B的列块送至第p-1号处理器中,形成循环传送),各处理器中的存储内容如图1.2(b)所 示。它们再次并行计算C=A1XB,这里产=(+1)modp。B的列块在各处理器中以这样的方 式循环传送p-1次并做p次子矩阵相乘运算,就生成了矩阵C的所有子矩阵。编号为i的处 理器的内部存储器存有子矩阵Co,C,…Cφl)。为了避免在通信过程中发生死锁,奇数号及 偶数号处理器的收发顺序被错开,使偶数号处理器先发送后接收;而奇数号处理器先将B 的列块存于缓冲区bur中,然后接收编号在其后面的处理器所发送的B的列块,最后再将 缓冲区中原矩阵B的列块发送给编号在其前面的处理器,具体并行算法框架描述如下: 算法186矩阵并行分块乘法算法 输入:Amxn,Bnx 输出:Cm 对所有处理器 my rank( my rank=0,…p-1)同时执行如下的算法: (1)目前计算C的子块号l=(+ my rank)modp (2)for =0 to u-I do c{.==0 for so to n-l do c{.二小=c[,]+a[=,s]*b|s end for end for (3)计算左邻处理器的标号mml=(p+ my rank-1)modp 计算右邻处理器的标号mpl=( my_ rank+1)modp (4)if(i≠p1)then (4l)ir( my rank mod2=0)then/*编号为偶数的处理器* (i)将所存的B的子块发送到其左邻处理器中 (i)接收其右邻处理器中发来的B的子块 (42if( my rank mod2≠0)then/*编号为奇数的处理器* (i)将所存的B子块在缓冲区 buffer中做备份 (i)接收其右邻处理器中发来的B的子块 (i)将 buffer I所存的B的子块发送到其左邻处理器中 en 设一次乘法和加法运算时间为一个单位时间,由于每个处理器计算p个u×n与n×v 阶的子矩阵相乘,因此计算时间为u考np;所有处理器交换数据p1次,每次的通信量为 γn,通信过程中为了避免死锁,错开奇数号及偶数号处理器的收发顺序,通信时间为 2(p-1)(tx+my*tn)=Onk),所以并行计算时间Tp=p+2p-1)(L+mv)=mnk/p+2(p-1)(+mvtm) MPI源程序请参见所附光盘开始，各处理器的存储内容如图 1.2 (a)所示。此时各处理器并行计算 Cii= Ai×Bj 其中 i=0,1,…,p-1，此后第 i 号处理器将其所存储的 B 的列块送至第 i-1 号处理器（第 0 号处理器 将 B 的列块送至第 p-1 号处理器中，形成循环传送），各处理器中的存储内容如图 1.2 (b)所 示。它们再次并行计算 Cij= A i×B j，这里 j=(i+1)modp。B 的列块在各处理器中以这样的方 式循环传送 p-1 次并做 p 次子矩阵相乘运算，就生成了矩阵 C 的所有子矩阵。编号为 i 的处 理器的内部存储器存有子矩阵 Ci0,Ci1,…,Ci(p-1)。为了避免在通信过程中发生死锁，奇数号及 偶数号处理器的收发顺序被错开，使偶数号处理器先发送后接收；而奇数号处理器先将 B 的列块存于缓冲区 buffer 中，然后接收编号在其后面的处理器所发送的 B 的列块，最后再将 缓冲区中原矩阵 B 的列块发送给编号在其前面的处理器，具体并行算法框架描述如下： 算法 18.6 矩阵并行分块乘法算法 输入：Am×n, Bn×k, 输出：Cm×k Begin 对所有处理器 my_rank(my_rank=0,…,p-1)同时执行如下的算法: (1)目前计算 C 的子块号 l=(i+my_rank) mod p (2)for z=0 to u-1 do for j=0 to v-1 do c[l,z,j]=0 for s=0 to n-1 do c[l,z,j]=c[l,z,j]+ a[z,s]*b[s,j] end for end for end for (3)计算左邻处理器的标号 mm1=(p+my_rank-1) mod p 计算右邻处理器的标号 mp1=(my_rank+1) mod p (4)if (i≠p-1) then (4.1)if (my_rank mod 2= 0) then /*编号为偶数的处理器*/ (i)将所存的 B 的子块发送到其左邻处理器中 (ii)接收其右邻处理器中发来的 B 的子块 end if (4.2)if (my_rank mod 2≠ 0) then /*编号为奇数的处理器*/ (i)将所存的 B 子块在缓冲区 buffer 中做备份 (ii)接收其右邻处理器中发来的 B 的子块 (iii)将 buffer 中所存的 B 的子块发送到其左邻处理器中 end if end if End 设一次乘法和加法运算时间为一个单位时间，由于每个处理器计算 p 个 u×n 与 n×v 阶的子矩阵相乘，因此计算时间为 u*v*n*p；所有处理器交换数据 p-1 次，每次的通信量为 v*n，通信过程中为了避免死锁，错开奇数号及偶数号处理器的收发顺序，通信时间为 2(p-1)(ts+nv*tw)=O(nk)，所以并行计算时间 Tp=uvnp+2(p-1)(ts+nvtw)=mnk / p+2(p-1)(ts+nvtw)。 MPI 源程序请参见所附光盘