并行计算-实验指导-实验03图论

《并行计算-实验指导-实验03图论》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验3图论1传递闭包11.1传递闭包串行算法21.2传递闭包并行算法32连通分量52」顶点倒塌法算法原理描述52.2连通分量并行算法53单源最短路径73」最短路径串行算法73.2最短路径并行算法84最小生成树104」最小生成树串行算法114.2最小生成树并行算法125小结14参考文献15附录连通分量并行算法的MPI源程序15图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应川。但很多图论问题虽易表达，却难以求解，其屮右相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程实现，包括传递闭

2、包、连通分量、最短路径和最小生成树等。1传递闭包设A是一个含N个顶点的有向图G的布尔邻接矩阵(BooleanAdjacentMatrix),即元素aij=l当且仅当从顶点i至Uj有一・条有向边。所谓A的传递闭包(TransitiveClosure),记为A+,是一个NXN的布尔矩阵,其元素bij=l当且仅当：①i=j；或②从i出发存在有向路径到j,乂称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包，就称为传递闭包问题。传递闭包问题有很强的应用背景，在科学计算中广泛存在。传递闭包问题的经典解法Z—就是利用布尔矩阵的乘法來求解。本节将把这一算法分别在串行和并行机上实现

3、。1.1传递闭包串行算法禾I」川布尔矩阵相乘求解传递闭包问题的原理为：对于布尔矩阵(A+护屮的任一元素bybi尸1表示从i到j存在长度小于等于k的可达路径，否则，切=0。显然对于k=l,(A+I)'中切=1当且仅当从i到j路径长度为0(冃)或为1(从i到j存在有向边)；(A+I)2中，bij=l当且仅当从i到j路径长度小于等于2；((A+I)2)2屮，bij=l当且仅当从i至1打路径长度小于等于4,等等。因为任意两点间如果存在可达路径，长度最多为N-1,所以k^N-1时，(A+I)*就是所求的传递闭包A+。于是(A+I)矩阵的咤N次口乘Z后所得的矩阵就是所求的传递闭包。根

4、据前面的叙述，很口然的有下面的传递闭包串行算法15.1,其时间复杂度为0(N3logN)o算法15・1传递闭包串行算法输入：图G的布尔邻接矩阵A输出：A的传递闭包MprocedureclosureBegin(1)读入矩阵A/*以下作A=A+I的运算*/(2)fori=0toN-ldoa(i,i)=1endfor/*以下是A矩阵的bgN次自乘，结果放入M矩阵；每次乘后，结果写回A矩阵*/(3)fork=ltobgNdo(3.1)fori=0toN-ldoforj=0toN-ldos=0while(s

5、ileifs

6、虑不能整除的情况。在以后的几节中，N、p、n都具有上面约定的意义，不再多说。为了并行•处理，这里将矩阵(A+I)进行划分，分別交给p个处理粘。在每次矩阵乘法的计算中，将NXN的结果矩阵(A+I)2均匀划分成pXp个子块，每块人小为nXn。处理器i负责计算位于第i子块行上的p个子块。对整个子块行的计算由p次循环完成，每次计算一个子块。每个处理器为了计算一个nXn人小的子块，需要用到源矩阵(A+I)中对应的连续n行(局部数据a)和连续n列的数据(局部数据b)。计算完成后，各处理器循环交换局部数据b,就可以进行下一个子块的计算了。于是，总体算法由2层循环构成，外层是矩阵M=A+

7、I的bgN次自乘，每次首先完成矩阵M的一次自乘，然后将结果写回M；内层是p个子块的计算，每次首先完成各口独立的计算，然后处理器间循环交换局部数据b°算法运行期间，矩阵M的数据作为全局数据由处理器()维护。根据以上思想，并行算法描述见下血的算法15.2,使用了p个处理器，其时间复杂度为O(N3/plogN)o其中myid是处理器编号，下同。算法15・2传递闭包并行算法输入：图G的布尔邻接矩阵A输出：A的传递闭包Mprocedureclosure・parallelBegin/*由处理器0读入矩阵A到M中，并进行“=1+1运算対应