|
Published Articles >> Table of Contents >> Abstract
16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'04)
pp. 174-179
Revisiting a BSP/CGM Transitive Closure Algorithm
Edson Norberto Caceres, Federal University of Mato Grosso do Sul, Brazil
Cristiano Costa Argemom Vieira, Federal University of Mato Grosso do Sul, Brazil
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CAHPC.2004.36
Send link to a friend
| Abstract |
|
We present a new BSP/CGM parallel algorithm for the Transitive Closure Problem. Our algorithm uses O(\frac{{n^3 }}{{p\alpha }}) local computation time with O(p/α) communication rounds, where α is the size in bits that can be stored in a primitive data item. For all the randomly generated graphs that were used in the tests, the number of communication rounds was bounded by log \frac{p}{\alpha } + 1. Our algorithm, even for the worst case, improves the previous results. The algorithm was implemented and the results show the efficiency and scalability of the presented algorithm and compare favorably with other parallel implementations.
|
 Additional Information
|
Citation:
Edson Norberto Caceres, Cristiano Costa Argemom Vieira,
"Revisiting a BSP/CGM Transitive Closure Algorithm,"
sbac-pad,
pp. 174-179,
16th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'04),
2004
|
|
