Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2009-07-08
Parallel Computing 34, 6-8 (2008) 318-331
Computer Science
Distributed, Parallel, and Cluster Computing
Scientific paper
10.1016/j.parco.2007.12.001
The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which are also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-Scotch software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-Scotch produces consistently better orderings than ParMeTiS on large numbers of processors.
Chevalier Cédric
Pellegrini François
No associations
LandOfFree
PT-Scotch: A tool for efficient parallel graph ordering does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with PT-Scotch: A tool for efficient parallel graph ordering, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and PT-Scotch: A tool for efficient parallel graph ordering will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-320023