摘要
连通分量和最小生成树是图论中的两个基本问题 ,在许多领域都有很多应用 .对于顶点数为 n的图和规模为 p× p的虫孔路由二维网孔机器 ,该文针对 p n和 n <p n2 分别提出了连通分量算法和最小生成树算法 ,算法的时间复杂度分别为 O(n2 / p +nlogp)和 O((n2 / p) log2 n) .当 plogp n时 ,时间复杂度为 O(n2 / p ) ,此时算法的运算成本达到最优 ;当 p =n2 时 ,时间复杂度为 O(log2 n) ,此时连通分量和最小生成树算法都改进了存储转发路由技术下的时间复杂度下界 O(n) ,同其它所有运行在非总线连接分布式存储的并行计算机上的算法相比 。
Connected components and minimum spanning tree(MST) are two basic problems in graph theory. They have various applications in many domains and attract a lot of attention. Wormhole routing has emerged as the widely used switching technique in massively parallel computers. With wormhole routing, the distance between the source and the destination node has little effect on communication latency. Based on the pointer jumping technique, this paper presents a connected component parallel algorithm on p×p wormhole routed 2D meshes for the case of pn and n<pn 2 respectively, here n is the number of the vertices in the graph. In the case of pn , the algorithm assigns n/p rows of the adjacent matrix to one processor, keeps the number of the rows assigned to a processor the same during its execution and runs in time O(n 2 /p+n log p) . The running time and the cost of the algorithms become O(n 2 /p) and O(n 2 ) respectively when p log pn , and the cost is optimal in this special case. In the case of p log pn, the algorithm assigns n 2 /p columns of a row to one processor. Its running time is O(n 2 /p ) and become O( log 2 n ) when p=n 2 . This improves the time lower bound O(n) on n×n store and forward routed 2D mesh, and compared to the other known algorithms running on various non bus connected parallel machines with distributed memory, its time complexity is optimal in this special case. With the same idea, this paper also presents two MST parallel algorithms on the same model and with the same time complexities.
出处
《计算机学报》
EI
CSCD
北大核心
2002年第6期591-598,共8页
Chinese Journal of Computers
