skip to main content
poster

Evaluating graph coloring on GPUs

Published:12 February 2011Publication History
Skip Abstract Section

Abstract

This paper evaluates features of graph coloring algorithms implemented on graphics processing units (GPUs), comparing coloring heuristics and thread decompositions. As compared to prior work on graph coloring for other parallel architectures, we find that the large number of cores and relatively high global memory bandwidth of a GPU lead to different strategies for the parallel implementation. Specifically, we find that a simple uniform block partitioning is very effective on GPUs and our parallel coloring heuristics lead to the same or fewer colors than prior approaches for distributed-memory cluster architecture. Our algorithm resolves many coloring conflicts across partitioned blocks on the GPU by iterating through the coloring process, before returning to the CPU to resolve remaining conflicts. With this approach we get as few color (if not fewer) than the best sequential graph coloring algorithm and performance is close to the fastest sequential graph coloring algorithms which have poor color quality.

References

  1. D. Zuckerman, "Linear degree extractors and the inapproximability of max clique and chromatic number," Theory of Computing, vol. 3, no. 1, pp. 103--128, 2007.Google ScholarGoogle ScholarCross RefCross Ref
  2. H. Al-Omari and K. Sabri, "New graph coloring algorithms," Am. J. Math. & Stat, vol. 2, no. 4, pp. 739--741, 2006.Google ScholarGoogle Scholar
  3. A. Gebremedhin and F. Manne, "Scalable parallel graph coloring algorithms," Concurrency: Practice and Experience, vol. 12, no. 12, pp. 1131--1146, 2000.Google ScholarGoogle ScholarCross RefCross Ref
  4. A. M. F. B. E. C. Bozdag, D Gebremedhin, "A framework for scalable greedy coloring on distributed-memory parallel computers," Journal of Parallel and Distributed Computing, vol. 68, no. 4, pp. 515--535, 2008. Google ScholarGoogle ScholarDigital LibraryDigital Library
  5. "The university of florida sparse matrix collection.Google ScholarGoogle Scholar

Index Terms

  1. Evaluating graph coloring on GPUs

      Recommendations

      Comments

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in

      Full Access

      • Published in

        cover image ACM SIGPLAN Notices
        ACM SIGPLAN Notices  Volume 46, Issue 8
        PPoPP '11
        August 2011
        300 pages
        ISSN:0362-1340
        EISSN:1558-1160
        DOI:10.1145/2038037
        Issue’s Table of Contents
        • cover image ACM Conferences
          PPoPP '11: Proceedings of the 16th ACM symposium on Principles and practice of parallel programming
          February 2011
          326 pages
          ISBN:9781450301190
          DOI:10.1145/1941553
          • General Chair:
          • Calin Cascaval,
          • Program Chair:
          • Pen-Chung Yew

        Copyright © 2011 Authors

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Publication History

        • Published: 12 February 2011

        Check for updates

        Qualifiers

        • poster

      PDF Format

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader