hile(s<N)and (a(i, s)=0 or a(s,j=0)do endwhile ifs<N then m(1,j=l else m(i,j=0 /*计算结果从M写回A* (3. 2)for i=0 to N for i=0 to N-l do enamor 112传递闭包并行算法 本小节将把上一小节里的算法并行化。在图论问题的并行化求解中,经常使用将N个 顶点(或连通分量)平均分配给p个处理器并行处理的基本思想。其中每个处理器分配到n 个顶点,即n=Np。无法整除时,一般的策略是在尽量均分的前提下,给最后一个处理器分 配较少的顶点。为了使算法简明,在本章中,仅在算法的MPI实现中才考虑不能整除的情 况。在以后的几节中,N、p、n都具有上面约定的意义,不再多说。 为了并行处理,这里将矩阵(A+1)进行划分,分别交给p个处理器。在每次矩阵乘法的 计算中,将NXN的结果矩阵(A+)2均匀划分成p×p个子块,每块大小为nxn。处理器 负责计算位于第i子块行上的p个子块。对整个子块行的计算由p次循环完成,每次计算 个子块。每个处理器为了计算一个n×n大小的子块,需要用到源矩阵(A+D中对应的连续n 行(局部数据a)和连续n列的数据(局部数据b)。计算完成后,各处理器循环交换局部数 据b,就可以进行下一个子块的计算了。 于是,总体算法由2层循环构成,外层是矩阵M=A+1的ogN次自乘,每次首先完成矩 阵M的一次自乘,然后将结果写回M;内层是p个子块的计算,每次首先完成各自独立的 计算,然后处理器间循环交换局部数据b。算法运行期间,矩阵M的数据作为全局数据由 处理器0维护 根据以上思想,并行算法描述见下面的算法15.2,使用了p个处理器,其时间复杂度为 O(NpgN)。其中myid是处理器编号,下同。 算法152传递闭包并行算法 输入:图G的布尔邻接矩阵A 输出:A的传递闭包M procedure closure-parallel 体*由处理器0读入矩阵A到M中,并进行M=M+运算 对应源程序中 readmatrixo函数*/ (1) if myid=0 then (1.1)读入矩阵A,放入M中 (1. 2)for i =0 to N-l dowhile (s<N) and (a(i,s)=0 or a(s,j)=0) do s = s+1 endwhile if s<N then m(i,j)=1 else m(i,j)=0 endfor endfor /* 计算结果从 M 写回 A */ (3.2)for i=0 to N-1 do for j=0 to N-1 do a(i, j) = m(i, j) endfor endfor endfor End 1.1.2 传递闭包并行算法 本小节将把上一小节里的算法并行化。在图论问题的并行化求解中，经常使用将 N 个 顶点（或连通分量）平均分配给 p 个处理器并行处理的基本思想。其中每个处理器分配到 n 个顶点，即 n=N/p。无法整除时，一般的策略是在尽量均分的前提下，给最后一个处理器分 配较少的顶点。为了使算法简明，在本章中，仅在算法的 MPI 实现中才考虑不能整除的情 况。在以后的几节中，N、p、n 都具有上面约定的意义，不再多说。 为了并行处理，这里将矩阵(A+I)进行划分，分别交给 p 个处理器。在每次矩阵乘法的 计算中，将 N×N 的结果矩阵(A+I)2 均匀划分成 p×p 个子块，每块大小为 n×n。处理器 i 负责计算位于第 i 子块行上的 p 个子块。对整个子块行的计算由 p 次循环完成，每次计算一 个子块。每个处理器为了计算一个 n×n 大小的子块，需要用到源矩阵(A+I)中对应的连续 n 行（局部数据 a）和连续 n 列的数据（局部数据 b）。计算完成后，各处理器循环交换局部数 据 b，就可以进行下一个子块的计算了。 于是，总体算法由 2 层循环构成，外层是矩阵 M=A+I 的㏒ N 次自乘，每次首先完成矩 阵 M 的一次自乘，然后将结果写回 M；内层是 p 个子块的计算，每次首先完成各自独立的 计算，然后处理器间循环交换局部数据 b。算法运行期间，矩阵 M 的数据作为全局数据由 处理器 0 维护。 根据以上思想，并行算法描述见下面的算法 15.2，使用了 p 个处理器，其时间复杂度为 O(N3 /p ㏒ N)。其中 myid 是处理器编号，下同。 算法 15.2 传递闭包并行算法 输入：图 G 的布尔邻接矩阵 A 输出：A 的传递闭包 M procedure closure-parallel Begin /* 由处理器 0 读入矩阵 A 到 M 中，并进行 M=M+I 运算 对应源程序中 readmatrix()函数 */ (1) if myid=0 then (1.1) 读入矩阵 A，放入 M 中 (1.2) for i=0 to N-1 do m(i,i)=1