(2)各处理器变量初始化 *以下是主循环,矩阵M的ogN次自乘* (3)for i=l to log N par do /*以下向各处理器发送对应子块行和列数据 对应源程序中 sendmatrixo函数* (3. 1)for l to p-l de i)处理器0发送第j个子块行的数据给处理器j,成为j的局部数据a (ⅱi)处理器0发送第j个子块列的数据给处理器j,成为j的局部数据b endor /*以下是各处理器接收接收和初始化局部数据a和b 对应源程序中 getmatrixO函数* (32)处理器0更新自己的局部数据a和b (3.3)处理器1到p1从处理器0接受数据,作为局部数据a和b /*以下是乘法运算过程,对应源程序中 paramus函数* (3.4)for j=0 to p-l do (i)处理器k计算结果矩阵的子块(k,(k+j)modp) (ⅱi)各处理器将数据b发送给前一个处理器 i)各处理器从后一个处理器接收数据b /*以下是各处理器将局部计算结果写回M数组 对应源程序中 writeback(函数* (3.5 )if myid=0 then (i)计算结果直接写入矩阵M (ⅱi)接受其它处理器发送来的计算结果并写入M el se 发送计算结果的myid子块行数据给处理器0 endor MPI源程序请参见所附光盘。 12连通分量 图G的一个连通分量 Connected Component)是G的一个最大连通子图,该子图中每对 顶点间均有一条路径。根据图G,如何找出其所有连通分量的问题称为连通分量问题。解决 该问题常用的方法有3种:①使用某种形式的图的搜索技术:②通过图的布尔邻接矩阵计算 传递闭包:;③顶点倒塌算法。本节将介绍如何在并行环境下实现顶点倒塌算法。 121顶点倒塌法算法原理描述 顶点倒塌( Vertex Collapse)算法中,一开始图中的N个顶点看作N个孤立的超顶点(S Vertex),算法运行中,有边连通的超顶点相继合并,直到形成最后的整个连通分量。每个顶endfor endif (2) 各处理器变量初始化 /* 以下是主循环，矩阵 M 的㏒ N 次自乘 */ (3) for i=1 to ㏒ N par_do /* 以下向各处理器发送对应子块行和列数据 对应源程序中 sendmatrix()函数 */ (3.1)for j=1 to p-1 do (ⅰ) 处理器 0 发送第 j 个子块行的数据给处理器 j，成为 j 的局部数据 a (ⅱ) 处理器 0 发送第 j 个子块列的数据给处理器 j，成为 j 的局部数据 b endfor /* 以下是各处理器接收接收和初始化局部数据 a 和 b 对应源程序中 getmatrix()函数 */ (3.2)处理器 0 更新自己的局部数据 a 和 b (3.3)处理器 1 到 p-1 从处理器 0 接受数据，作为局部数据 a 和 b /* 以下是乘法运算过程，对应源程序中 paramul()函数 */ (3.4)for j=0 to p-1 do (ⅰ) 处理器 k 计算结果矩阵的子块(k, ((k+j) mod p)) (ⅱ) 各处理器将数据 b 发送给前一个处理器 (ⅲ) 各处理器从后一个处理器接收数据 b endfor /* 以下是各处理器将局部计算结果写回 M 数组 对应源程序中 writeback()函数 */ (3.5)if myid=0 then (ⅰ) 计算结果直接写入矩阵 M (ⅱ) 接受其它处理器发送来的计算结果并写入 M else 发送计算结果的 myid 子块行数据给处理器 0 endif endfor End MPI 源程序请参见所附光盘。 1.2 连通分量 图 G 的一个连通分量(Connected Component)是 G 的一个最大连通子图，该子图中每对 顶点间均有一条路径。根据图 G，如何找出其所有连通分量的问题称为连通分量问题。解决 该问题常用的方法有 3 种：①使用某种形式的图的搜索技术；②通过图的布尔邻接矩阵计算 传递闭包；③顶点倒塌算法。本节将介绍如何在并行环境下实现顶点倒塌算法。 1.2.1 顶点倒塌法算法原理描述 顶点倒塌（Vertex Collapse）算法中，一开始图中的N个顶点看作N个孤立的超顶点(Super Vertex)，算法运行中，有边连通的超顶点相继合并，直到形成最后的整个连通分量。每个顶