Parallel transitive closure algorithm

Brazilian Computer Society. Journal

J. L. Szwarcfiter¹  A. A. Castro²  S. W. Song³  C. E. R. Alves⁵  E. N. Cá⁷  ceres⁸ 

[1] , Brazil;Universidade Federal de Mato Grosso do Sul, Campo Grande, Brazil;Universidade Federal de Mato Grosso do Sul, Ponta PorãUniversidade Federal do ABC, Santo AndréUniversidade SãUniversidade de São Judas Tadeu, São Paulo, Brazil;o Paulo, Sã

关键词: Transitive closure;    Parallel algorithms;    Scalable algorithms;    BSP/CGM algorithms;   

DOI  :  10.1007/s13173-012-0089-z

学科分类：农业科学（综合）

来源: Springer U K

【 摘 要 】

Using the BSP/CGM model, with \(p\) processors, where \(p \ll n\), we present a parallel algorithm to compute the transitive closure of a digraph \(D\) with \(n\) vertices and \(m\) edges. Our algorithm uses \(\log p + 1\) communication rounds if the input is an acyclic directed graph labeled using a linear extension. For general digraphs, the algorithm requires \(p\) communication rounds in the worst case. In both cases, \(O(M/p)\) local computation is performed per round, where \(M\) is the amount of computation needed to compute a sequential transitive closure of a digraph. The presented algorithm can be implemented using any sequential algorithm that computes the transitive closure of a digraph \(D\). We have implemented the algorithm using the Warshall transitive closure algorithm on two Beowulf clusters using MPI. The implementation results show its efficiency and scalability. It also compares favorably with other parallel implementations. The worst case (communication rounds) for a digraph was derived through an artificially elaborated example. However, in all our test cases, the algorithm never requires more than \(\log p + 1\) communication rounds and presents very promising implementation results. The algorithm also can be applied to any \(n \times n\) matrix that represents a binary relation.

【 授权许可】

CC BY