Optimal Graph Algorithms on Wormhole Routed 2D Meshes
Xu Yin · Chinese Journal of Computers · 2002
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 npn 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.