William Hasenplaugh
Tim Kaler
Tao B. Schardl
Charles E. Leiserson
ABSTRACT
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 heuristics, respectively. We show that although LF and SL, in practice, generate colorings with relatively small numbers of colors, they are vulnerable to adversarial inputs for which any parallelization yields a poor parallel speedup. In contrast, LLF and SLL allow for provably good speedups on arbitrary inputs while, in practice, producing colorings of competitive quality to their serial analogs.
We applied LLF and SLL to the parallel greedy coloring algorithm introduced by Jones and Plassmann, referred to here as JP. Jones and Plassman analyze the variant of JP that processes the vertices of a graph in a random order, and show that on an O(1)-degree graph G=(V,E), this JP-R variant has an expected parallel running time of O(lgV/lglgV) in a PRAM model. We improve this bound to show, using work-span analysis, that JP-R, augmented to handle arbitrary-degree graphs, colors a graph G=(V,E) with degree Delta using Theta(V+E) work and O(lgV+ lg Delta . min sqrt-E, Delta +lg DeltaVlglgV) expected span. We prove that JP-LLF and JP-SLL --- JP using the LLF and SLL heuristics, respectively --- execute with the same asymptotic work as JP-R and only logarithmically more span while producing higher-quality colorings than JP-R in practice.
We engineered an efficient implementation of JP for modern shared-memory multicore computers and evaluated its performance on a machine with 12 Intel Core-i7 (Nehalem) processor cores. Our implementation of JP-LLF achieves a geometric-mean speedup of 7.83 on eight real-world graphs and a geometric-mean speedup of 8.08 on ten synthetic graphs, while our implementation using SLL achieves a geometric-mean speedup of 5.36 on these real-world graphs and a geometric-mean speedup of 7.02 on these synthetic graphs. Furthermore, on one processor, JP-LLF is slightly faster than a well-engineered serial greedy algorithm using LF, and likewise, JP-SLL is slightly faster than the greedy algorithm using SL.
- L. Adams and J. Ortega. A multi-color SOR method for parallel computation. In ICPP, 1982.Google Scholar
- J. R. Allwright, R. Bordawekar, P. D. Coddington, K. Dincer, and C. L. Martin. A comparison of parallel graph coloring algorithms. Technical report, Northeast Parallel Architecture Center, Syracuse University, 1995.Google Scholar
- N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 1986. Google ScholarDigital Library
- E. M. Arkin and E. B. Silverberg. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics, 1987. Google ScholarDigital Library
- L. Barenboim and M. Elkin. Distributed (ΔGoogle Scholar
- 1)$-coloring in linear (in Δ) time. In ACM STOC, 2009.Google Scholar
- S. Berchtold, C. Böhm, B. Braunmüller, D. A. Keim, and H.-P. Kriegel. Fast parallel similarity search in multimedia databases. In ACM SIGMOD Int.\@ Conf.\@ on Management of Data, 1997. Google ScholarDigital Library
- D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1989. Google ScholarDigital Library
- G. E. Blelloch, J. T. Fineman, and J. Shun. Greedy sequential maximal independent set and matching are parallel on average. In ACM SPAA, 2012. Google ScholarDigital Library
- R. D. Blumofe and C. E. Leiserson. Space-efficient scheduling of multithreaded computations. SICOMP, 1998. Google ScholarDigital Library
- R. D. Blumofe and C. E. Leiserson. Scheduling multithreaded computations by work stealing. JACM, 1999. Google ScholarDigital Library
- D. Brélaz. New methods to color the vertices of a graph. CACM, 1979. Google ScholarDigital Library
- R. P. Brent. The parallel evaluation of general arithmetic expressions. JACM, 1974. Google ScholarDigital Library
- P. Briggs. Register allocation via graph coloring. PhD thesis, Rice University, 1992. Google ScholarDigital Library
- Ü. V. Çatalyürek, J. Feo, A. H. Gebremedhin, M. Halappanavar, and A. Pothen. Graph coloring algorithms for muti-core and massively multithreaded architectures. CoRR, 2012.Google Scholar
- G. J. Chaitin. Register allocation & spilling via graph coloring. In ACM SIGPLAN Notices, 1982. Google ScholarDigital Library
- G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E. Hopkins, and P. W. Markstein. Register allocation via coloring. Computer Languages, 1981. Google ScholarDigital Library
- D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-MAT: A recursive model for graph mining. In SDM. SIAM, 2004.Google ScholarCross Ref
- R. Cole and U. Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control, 1986. Google ScholarDigital Library
- T. Coleman and J. Moré. Estimation of sparse Jacobian matrices and graph coloring problems. SIAM J. Numer. Anal., 1983.Google Scholar
- M. E. Conway. A multiprocessor system design. In AFIPS, 1963. Google ScholarDigital Library
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, third edition, 2009. Google ScholarDigital Library
- K. Diks. A fast parallel algorithm for six-colouring of planar graphs. In Mathematical Foundations of Computer Science. 1986. Google ScholarDigital Library
- C. Dwork, M. Herlihy, and O. Waarts. Contention in shared memory algorithms. In STOC, 1993. Google ScholarDigital Library
- D. L. Eager, J. Zahorjan, and E. D. Lazowska. Speedup versus efficiency in parallel systems. IEEE Trans. Comput., 1989. Google ScholarDigital Library
- M. Fischetti, S. Martello, and P. Toth. The fixed job schedule problem with spread-time constraints. Operations Research, 1987. Google ScholarDigital Library
- M. Garey, D. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1976.Google Scholar
- A. H. Gebremedhin and F. Manne. Scalable parallel graph coloring algorithms. Concurrency: Practice and Experience, 2000.Google ScholarCross Ref
- A. H. Gebremedhin, D. Nguyen, M. M. A. Patwary, and A. Pothen. ColPack: Software for graph coloring and related problems in scientific computing. ACM Trans. on Mathematical Software, 2013. Google ScholarDigital Library
- R. K. Gjertsen Jr., M. T. Jones, and P. E. Plassmann. Parallel heuristics for improved, balanced graph colorings. JPDC, 1996. Google ScholarDigital Library
- A. V. Goldberg, S. A. Plotkin, and G. E. Shannon. Parallel symmetry-breaking in sparse graphs. In SIAM J. Disc. Math, 1987. Google ScholarDigital Library
- M. Goldberg and T. Spencer. A new parallel algorithm for the maximal independent set problem. SICOMP, 1989. Google ScholarDigital Library
- R. L. Graham. Bounds for certain multiprocessing anomalies. The Bell System Technical Journal, 1966.Google ScholarCross Ref
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., 2008. Google ScholarDigital Library
- Intel. Intel Cilk Plus. Available fromtexttthttp://software.intel.com, 2013.Google Scholar
- M. T. Jones and P. E. Plassmann. A parallel graph coloring heuristic. SIAM Journal on Scientific Computing, 1993. Google ScholarDigital Library
- M. T. Jones and P. E. Plassmann. Scalable iterative solution of sparse linear systems. Parallel Computing, 1994. Google ScholarDigital Library
- T. Kaler, W. Hasenplaugh, T. B. Schardl, and C. E. Leiserson. Executing dynamic data-graph computations deterministically using chromatic scheduling. In SPAA, 2014. Google ScholarDigital Library
- F. Kuhn. Weak graph colorings: distributed algorithms and applications. In ACM SPAA, 2009. Google ScholarDigital Library
- F. Kuhn and R. Wattenhofer. On the complexity of distributed graph coloring. In PODC, 2006. Google ScholarDigital Library
- J. Leskovec. SNAP: Stanford Network Analysis Platform. Available from http://snap.stanford.edu/data/index.html, 2013.Google Scholar
- N. Linial. Locality in distributed graph algorithms. SICOMP, 1992. Google ScholarDigital Library
- L. Lo'vasz, M. Saks, and W. T. Trotter. An on-line graph coloring algorithm with sublinear performance ratio. Discrete Math., 1989. Google ScholarDigital Library
- M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput., 1986. Google ScholarDigital Library
- D. Marx. Graph colouring problems and their applications in scheduling. John von Neumann Ph.D. Students Conf., 2004.Google Scholar
- D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. JACM, 1983. Google ScholarDigital Library
- J. Mitchem. On various algorithms for estimating the chromatic number of a graph. The Computer Journal, 1976.Google ScholarCross Ref
- M. S. Papamarcos and J. H. Patel. A low-overhead coherence solution for multiprocessors with private cache memories. In ISCA, 1984. Google ScholarDigital Library
- Y. Saad. SPARSKIT: A basic toolkit for sparse matrix computations. Research Institute for Advanced Computer Science, NASA Ames Research Center, 1990.Google Scholar
- A. Sariyuce, E. Saule, and U. Catalyurek. Improving graph coloring on distributed-memory parallel computers. In HiPC, 2011. Google ScholarDigital Library
- J. Shun, G. E. Blelloch, J. T. Fineman, P. B. Gibbons, A. Kyrola, H. V. Simhadri, and K. Tangwongsan. Brief announcement: the Problem Based Benchmark Suite. In SPAA, 2012. Google ScholarDigital Library
- D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 1967.Google Scholar
Index Terms
- Ordering heuristics for parallel graph coloring
Recommendations
List-coloring the square of a subcubic graph
The square G2 of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G2) ≤ 7. Kostochka and Woodall ...
Heuristic methods for graph coloring problems
SAC '05: Proceedings of the 2005 ACM symposium on Applied computingIn this work, the Graph Coloring Problem and its generalizations - the Bandwidth Coloring Problem, the Multicoloring Problem and the Bandwidth Multicoloring Problem - are studied. A Squeaky Wheel Optimization with Tabu Search heuristic is developed and ...
A graph coloring heuristic using partial solutions and a reactive tabu scheme
Most of the recent heuristics for the graph coloring problem start from an infeasible k-coloring (adjacent vertices may have the same color) and try to make the solution feasible through a sequence of color exchanges. In contrast, our approach (called ...
Comments