Skip Navigation

The Computer Journal 2003 46(4):391-400; doi:10.1093/comjnl/46.4.391
© 2003 by British Computer Society
This Article
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Gibbons, A.
Right arrow Articles by Rytter, W.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Coarse-Grained Parallel Transitive Closure Algorithm: Path Decomposition Technique

Alan Gibbons1, Aris Pagourtzis2,3, Igor Potapov2 and Wojciech Rytter2,4

1 Department of Computer Science, King's College London, Strand, London WC2R 2LS, UK 2 Department of Computer Science, University of Liverpool, Chadwick Building, Peach Street, Liverpool L69 7ZF, UK 3 Computer Science, Department of Electrical and Computer Engineering, National Technical University of Athens, Greece 4 Institute of Informatics, Warsaw University, Poland

We investigate the relation between fine-grained and coarse-grained distributed computations of a class of problems related to the generic transitive closure problem (TC for short). We choose an intricate systolic algorithm for the TC problem, by Guibas, Kung and Thompson (GKT algorithm for short), as a starting point due to its particularly close relationship to matrix multiplication. The GKT algorithm reduces the TC problem to three successive parallel matrix multiplications. We extract the main ideas of this algorithm, namely different path decompositions related to min-paths and max-paths computations and devise a two-pass parallel algorithm, such that the second pass is purely a triangular matrix multiplication involving exactly $\frac13$ of the total number of elementary operations (multiplying two single elements of the matrix). This is helpful in coarse-grained parallel computations since matrix multiplication is well parallelizable. A novel approach is used and as a first result a more efficient and simpler two-pass fine-grained algorithm is designed. The second result is a non-trivial transformation of this fine-grained algorithm into a coarse-grained (and more practical) version. The full proof of correctness of the transformation, which is presented in the appendices, is quite complex and is the hardest result of the paper. Our algorithms are specially structured to directly show the correspondence between the main fine-grained and the main coarse-grained operations.

Received 17 December, 2001. Revised 9 October, 2002.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.