阵A分成p个大小为m×m的子块,m=「n/pp个子块组成一个√x√P的子块阵列。 记其中第i行第j列的子块为Ay,它含有A的第(-1)m+1至第Ⅷm行中的第(-1)m+1至第jm 列的所有元素。对每一处理器按行主方式赋以二维下标,记编号为i的处理器的二维下标为 (),其中=/,=md√,将A的子块存入下标为(a)表示的对应处理器中 这样,转置过程分两步进行:第一步,子块转置,具体过程如图1.1所示;第二步,处理器 内部局部转置。 为了避免对应子块交换数据时处理器发生死锁,可令下三角子块先向与之对应的上三角 子块发送数据,然后从上三角子块接收数据:上三角子块先将数据存放在缓冲区bur中 然后从与之对应的下三角子块接收数据:最后再将缓冲区中的数据发送给下三角子块。具体 并行算法框架描述如下 算法182网孔上的矩阵转置算法 输入:矩阵Axn 输出:矩阵A1x的转置Anxm 对所有处理器 my rank( my rank=0,…p-1)同时执行如下的算法: (1)计算子块的行号y= my ran/ sqrt(p),计算子块的列号l= my rank mod sqrt(p) (2(ux<)then/*对存放下三角块的处理器* (2.1)将所存的子块发送到其对角块所在的处理器中 (2.2)接收其对角块所在的处理器中发来的子块 件对存放上三角块的处理器* (2.3)将所存的子块在缓冲区bur中做备份 (24)接收其对角块所在的处理器中发来的子块 (2.5)将 buffer中所存的子块发送到其对角块所在的处理器中 end if (3)fori=1 to m do/*处理器内部局部转置* forj=l to i do 交换a[门和叫门 若记t为发送启动时间,l为单位数据传输时间,b为处理器间的延迟时间,则第一步 由于每个子块有πr个元素,又由于通信过程中为了避免死锁,错开下三角子块与上三角 子块的发送顺序,因此子块的交换时间为2(,+1n2/p+1nVP):第二步,假定一对数据 的交换时间为一个单位时间,则局部转置时间为n2/2p。因此所需的并行计算时间 +2,√p+21-+t1√p MPI源程序请参见所附光盘。阵 A 分成 p 个大小为 m×m 的子块， m = n / p。p 个子块组成一个 p  p 的子块阵列。 记其中第 i 行第 j 列的子块为 Aij，它含有 A 的第(i-1)m+1 至第 im 行中的第(j-1)m+1 至第 jm 列的所有元素。对每一处理器按行主方式赋以二维下标，记编号为 i 的处理器的二维下标为 (v,u)，其中 v = i / p ，u = i mod p ，将 A 的子块存入下标为(v,u)表示的对应处理器中。 这样，转置过程分两步进行：第一步，子块转置，具体过程如图 1.1 所示；第二步，处理器 内部局部转置。 为了避免对应子块交换数据时处理器发生死锁，可令下三角子块先向与之对应的上三角 子块发送数据，然后从上三角子块接收数据；上三角子块先将数据存放在缓冲区 buffer 中， 然后从与之对应的下三角子块接收数据；最后再将缓冲区中的数据发送给下三角子块。具体 并行算法框架描述如下： 算法 18.2 网孔上的矩阵转置算法 输入：矩阵 An×n 输出：矩阵 An×n 的转置 A T n×n Begin 对所有处理器 my_rank(my_rank=0,…,p-1)同时执行如下的算法: (1)计算子块的行号 v=my_rank/ sqrt(p), 计算子块的列号 u=my_rank mod sqrt(p) (2)if (u<v) then /*对存放下三角块的处理器*/ (2.1)将所存的子块发送到其对角块所在的处理器中 (2.2)接收其对角块所在的处理器中发来的子块 else /*对存放上三角块的处理器*/ (2.3)将所存的子块在缓冲区 buffer 中做备份 (2.4)接收其对角块所在的处理器中发来的子块 (2.5)将 buffer 中所存的子块发送到其对角块所在的处理器中 end if (3)for i=1 to m do /*处理器内部局部转置*/ for j=1 to i do 交换 a[i,j]和 a[j,i] end for end for End 若记 ts 为发送启动时间, tw 为单位数据传输时间，th 为处理器间的延迟时间，则第一步 由于每个子块有 n 2 /p 个元素，又由于通信过程中为了避免死锁，错开下三角子块与上三角 子块的发送顺序，因此子块的交换时间为 2( / ) 2 t s + twn p + t h p ；第二步，假定一对数据 的交换时间为一个单位时间，则局部转置时间为 n2 / 2p 。因此所需的并行计算时间 t p p n t p t p n Tp = + s + w + h 2 2 2 2 2 。 MPI 源程序请参见所附光盘