More Web Proxy on the site http://driver.im/

article

A framework for scalable greedy coloring on distributed-memory parallel computers

Authors:

Assefaw H. Gebremedhin,

Umit V. CatalyurekAuthors Info & Claims

Journal of Parallel and Distributed Computing, Volume 68, Issue 4

Pages 515 - 535

https://doi.org/10.1016/j.jpdc.2007.08.002

Published: 01 April 2008 Publication History

Abstract

We present a scalable framework for parallelizing greedy graph coloring algorithms on distributed-memory computers. The framework unifies several existing algorithms and blends a variety of techniques for creating or facilitating concurrency. The latter techniques include exploiting features of the initial data distribution, the use of speculative coloring and randomization, and a BSP-style organization of computation and communication. We experimentally study the performance of several specialized algorithms designed using the framework and implemented using MPI. The experiments are conducted on two different platforms and the test cases include large-size synthetic graphs as well as real graphs drawn from various application areas. Computational results show that implementations that yield good speedup while at the same time using about the same number of colors as a sequential greedy algorithm can be achieved by setting parameters of the framework in accordance with the size and structure of the graph being colored. Our implementation is freely available as part of the Zoltan parallel data management and load-balancing library.

References

[1]

J. Allwright, R. Bordawekar, P.D. Coddington, K. Dincer, C. Martin, A comparison of parallel graph coloring algorithms, Technical Report, NPAC Technical Report, SCCS-666, Northeast Parallel Architectures Center at Syracuse University, 1994.

[2]

Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A. and Protasi, M., Complexity and Approximation. 1999. Springer, Berlin.

Digital Library

[3]

R.H. Bisseling, Parallel Scientific Computation: A Structured Approach Using BSP and MPI, Oxford, 2004.

Digital Library

[4]

Boman, E.G., Bozdağ, D., Catalyurek, U., Gebremedhin, A.H. and Manne, F., A scalable parallel graph coloring algorithm for distributed memory computers. In: Proceedings of Euro-Par 2005, Lecture Notes in Computer Science, vol. 3648. Springer, Berlin. pp. 241-251.

Digital Library

[5]

Bozdağ, D., Catalyurek, U., Gebremedhin, A.H., Manne, F., Boman, E.G. and Özgüner, F., A parallel distance-2 graph coloring algorithm for distributed memory computers. In: Proceedings of HPCC 2005, Lecture Notes in Computer Science, vol. 3726. Springer, Berlin. pp. 796-806.

Digital Library

[6]

Coleman, T.F. and More, J.J., Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal. v1 i20. 187-209.

[7]

Devine, K., Boman, E., Heaphy, R., Hendrickson, B. and Vaughan, C., Zoltan data management services for parallel dynamic applications. Comput. Sci. Eng. v4 i2. 90-97.

Digital Library

[8]

Dolan, E.D. and Moré, J.J., Benchmarking optimization software with performance profiles. Math. Programming. v91 i2. 201-213.

[9]

Finocchi, I., Panconesi, A. and Silvestri, R., Experimental analysis of simple, distributed vertex coloring algorithms. Algorithmica. v41 i1. 1-23.

[10]

Garey, M.R. and Johnson, D.S., Computers and Intractability. 1979. Freeman, New York.

Digital Library

[11]

Gebremedhin, A.H., Guérin-Lassous, I., Gustedt, J. and Telle, J.A., Graph coloring on coarse grained multicomputers. Discrete Appl. Math. v131 i1. 179-198.

Digital Library

[12]

Gebremedhin, A.H. and Manne, F., Scalable parallel graph coloring algorithms. Concurrency: Practice and Experience. v12. 1131-1146.

[13]

Gebremedhin, A.H., Manne, F. and Pothen, A., Parallel distance-k coloring algorithms for numerical optimization. In: Proceedings of Euro-Par 2002, Lecture Notes in Computer Science, vol. 2400. Springer, Berlin. pp. 912-921.

Digital Library

[14]

Gebremedhin, A.H., Manne, F. and Pothen, A., What color is your jacobian? Graph coloring for computing derivatives. SIAM Rev. v47 i4. 629-705.

Digital Library

[15]

Gebremedhin, A.H., Manne, F. and Woods, T., Speeding up parallel graph coloring. In: Proceedings of Para 2004, Lecture Notes in Computer Science, vol. 3732. Springer, Berlin. pp. 1079-1088.

Digital Library

[16]

Genetic algorithms (evolutionary algorithms): repository of test problem generators <http://www.cs.uwyo.edu/∼wspears/generators.html>.

[17]

Gjertsen Jr., R.K., Jones, M.T. and Plassmann, P., Parallel heuristics for improved, balanced graph colorings. J. Par. and Dist. Comput. v37. 171-186.

Digital Library

[18]

Gtgraph: a suite of synthetic graph generators <http://www-static.cc.gatech.edu/∼kamesh/GTgraph/>.

[19]

Johansson, Ö., Simple distributed δ+1-coloring of graphs. Inform. Process. Lett. v70. 229-232.

Digital Library

[20]

Jones, M. and Plassmann, P., Scalable iterative solution of sparse linear systems. Parallel Comput. v20 i5. 753-773.

Digital Library

[21]

Jones, M.T. and Plassmann, P., A parallel graph coloring heuristic. SIAM J. Sci. Comput. v14 i3. 654-669.

Digital Library

[22]

G. Karypis, V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM J. Sci. Comput. 20(1).

Digital Library

[23]

Luby, M., A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. v15 i4. 1036-1053.

Digital Library

[24]

Manne, F., A parallel algorithm for computing the extremal eigenvalues of very large sparse matrices. In: Proceedings of Para 1998, Lecture Notes in Computer Science, vol. 1541. Springer, Berlin. pp. 332-336.

Digital Library

[25]

Morgenstern, C.A. and Shapiro, H.D., Heuristics for rapidly four-coloring large planar graphs. Algorithmica. v6 i6. 869-891.

[26]

Saad, Y., ILUM: a multi-elimination ILU preconditioner for general sparse matrices. SIAM J. Sci. Comput. v17. 830-847.

Digital Library

[27]

Strout, M.M., Carter, L., Ferrante, J., Freeman, J. and Kreaseck, B., Combining performance aspects of irregular Gauss--Seidel via sparse tiling. In: Pugh, W., Tseng, C.-W. (Eds.), LCPC, Lecture Notes in Computer Science, vol. 2481. Springer, Berlin. pp. 90-110.

[28]

M.M. Strout, P.D. Hovland, Metrics and models for reordering transformations, in: Proceedings of the Second ACM SIGPLAN Workshop on Memory System Performance (MSP), 2004, pp. 23--34.

Digital Library

[29]

Test data from the Parasol project <http://www.parallab.uib.no/projects/parasol/data/>.

[30]

The Second DIMACS Challenge <http://mat.gsia.cmu.edu/challenge.html>.

[31]

University of Florida matrix collection <http://www.cise.ufl.edu/research/sparse/matrices/>.

[32]

Valiant, L., A bridging model for parallel computation. Comm. ACM. v33 i8. 103-111.

Digital Library

Cited By

Brighen AChouikh AIkhlef HSlimani HRezgui AKheddouci H(2024)Giraph-Based Distributed Algorithms for Coloring Large-Scale GraphsInternational Journal of Parallel Programming10.1007/s10766-024-00781-053:1Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1007/s10766-024-00781-0
Brighen ASlimani HRezgui AKheddouci H(2024)A new distributed graph coloring algorithm for large graphsCluster Computing10.1007/s10586-023-03988-x27:1(875-891)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10586-023-03988-x
Germann TAcer SAzad ABoman EBuluç ADevine KFerdous SGawande NGhosh SHalappanavar MKalyanaraman AKhan AMinutoli MPothen ARajamanickam SSelvitopi OTallent NTumeo A(2021)EXAGRAPHInternational Journal of High Performance Computing Applications10.1177/1094342021102929935:6(553-571)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1177/10943420211029299
Show More Cited By

Index Terms

A framework for scalable greedy coloring on distributed-memory parallel computers

Recommendations

Ordering heuristics for parallel graph coloring
SPAA '14: Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures

This paper introduces the largest-log-degree-first (LLF) and smallest-log-degree-last (SLL) ordering heuristics for parallel greedy graph-coloring algorithms, which are inspired by the largest-degree-first (LF) and smallest-degree-last (SL) serial ...
Scalable Parallel Matrix Multiplication on Distributed Memory Parallel Computers
IPDPS '00: Proceedings of the 14th International Symposium on Parallel and Distributed Processing

\math. We show that such an algorithm can be parallelized on a distributed memory parallel computer (DMPC) in \math time by using \math processors. Such a parallel computation is cost optimal and matches the performance of PRAM. Further-more, our ...
Modelling the Runtime of Scientific Programs on Parallel Computers
ICPP '00: Proceedings of the 2000 International Workshop on Parallel Processing

Message-passing programs for parallel machines with a distributed address space using communication operations of portable communication libraries such as PVM and MPI guarantee portability for most of the parallel machines available. However, due to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Parallel and Distributed Computing

Journal of Parallel and Distributed Computing Volume 68, Issue 4

April, 2008

164 pages

ISSN:0743-7315

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2007.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 April 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Brighen AChouikh AIkhlef HSlimani HRezgui AKheddouci H(2024)Giraph-Based Distributed Algorithms for Coloring Large-Scale GraphsInternational Journal of Parallel Programming10.1007/s10766-024-00781-053:1Online publication date: 17-Oct-2024
https://dl.acm.org/doi/10.1007/s10766-024-00781-0
Brighen ASlimani HRezgui AKheddouci H(2024)A new distributed graph coloring algorithm for large graphsCluster Computing10.1007/s10586-023-03988-x27:1(875-891)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1007/s10586-023-03988-x
Germann TAcer SAzad ABoman EBuluç ADevine KFerdous SGawande NGhosh SHalappanavar MKalyanaraman AKhan AMinutoli MPothen ARajamanickam SSelvitopi OTallent NTumeo A(2021)EXAGRAPHInternational Journal of High Performance Computing Applications10.1177/1094342021102929935:6(553-571)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1177/10943420211029299
Besta MCarigiet AJanda KVonarburg-Shmaria ZGianinazzi LHoefler TCuicchi CQualters IKramer W(2020)High-performance parallel graph coloring with strong guarantees on work, depth, and qualityProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3433701.3433833(1-17)Online publication date: 9-Nov-2020
https://dl.acm.org/doi/10.5555/3433701.3433833
Alappat CBasermann ABishop AFehske HHager GSchenk OThies JWellein G(2020)A Recursive Algebraic Coloring Technique for Hardware-efficient Symmetric Sparse Matrix-vector MultiplicationACM Transactions on Parallel Computing10.1145/33997327:3(1-37)Online publication date: 29-Jun-2020
https://dl.acm.org/doi/10.1145/3399732
Elafrou AGoumas GKoziris NTaufer MBalaji PPeña A(2019)Conflict-free symmetric sparse matrix-vector multiplication on multicore architecturesProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356148(1-15)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356148
Firoz JZalewski MLumsdaine A(2019)A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law GraphsProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT.2019.00040(420-431)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1109/PACT.2019.00040
Benitez DEscobar JMontenegro RRodriguez E(2018)Performance model for mesh optimization on distributed-memory computersProceedings of the 25th European MPI Users' Group Meeting10.1145/3236367.3236372(1-10)Online publication date: 23-Sep-2018
https://dl.acm.org/doi/10.1145/3236367.3236372
Sallinen SIwabuchi KPoudel SGokhale MRipeanu MPearce RWest J(2016)Graph colouring as a challenge problem for dynamic graph processing on distributed systemsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.5555/3014904.3014945(1-12)Online publication date: 13-Nov-2016
https://dl.acm.org/doi/10.5555/3014904.3014945
Gebremedhin ANguyen DPatwary MPothen A(2013)ColPackACM Transactions on Mathematical Software10.1145/2513109.251311040:1(1-31)Online publication date: 3-Oct-2013
https://dl.acm.org/doi/10.1145/2513109.2513110
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents