Header menu link for other important links
X
Graph Coloring Using GPUs
Published in Springer
2019
Volume: 11725 LNCS
   
Pages: 377 - 390
Abstract
Graph coloring is a widely studied problem that is used in a variety of applications, such as task scheduling, register allocation, eigenvalue computations, social network analysis, and so on. Many of the modern day applications deal with large graphs (with millions of vertices and edges) and researchers have exploited the parallelism provided by multi-core systems to efficiently color such large graphs. GPUs provide a promising parallel infrastructure to run large applications. In this paper, we present new schemes to efficiently color large graphs on GPUs. We extend the algorithm of Rokos et al. [21] to efficiently color graphs using GPUs. Their approach has to continually resolve conflicts for color assignment. We present a data driven variation of their algorithm and use an improved scheme for conflict resolution. We also propose two optimizations for our algorithm to reduce both the execution time and memory requirements. We have evaluated our scheme (called SIRG) against the NVIDIA cuSPARSE library and the work of Chen et al. [13], and show that SIRG runs significantly faster: geomean 3.42 and 1.76 respectively. We have also compared SIRG against the scheme of Rokos et al. [21] for CPUs and show that SIRG performs faster on most input graphs: geomean 10.37. © 2019, Springer Nature Switzerland AG.
About the journal
JournalData powered by TypesetLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherData powered by TypesetSpringer
ISSN03029743
Open AccessNo
Concepts (13)
  •  related image
    Color
  •  related image
    Eigenvalues and eigenfunctions
  •  related image
    Graphic methods
  •  related image
    Program processors
  •  related image
    COLOR ASSIGNMENTS
  •  related image
    Conflict resolution
  •  related image
    EIGENVALUE COMPUTATION
  •  related image
    Graph colorings
  •  related image
    IMPROVED SCHEME
  •  related image
    Memory requirements
  •  related image
    Multi-core systems
  •  related image
    REGISTER ALLOCATION
  •  related image
    Graph theory