Increasing the Parallelism of Graph Coloring via Shortcutting

被引:14
作者
Alabandi, Ghadeer [1 ]
Powers, Evan [1 ]
Burtscher, Martin [1 ]
机构
[1] Texas State Univ, Dept Comp Sci, San Marcos, TX 78666 USA
来源
PROCEEDINGS OF THE 25TH ACM SIGPLAN SYMPOSIUM ON PRINCIPLES AND PRACTICE OF PARALLEL PROGRAMMING (PPOPP '20) | 2020年
基金
美国国家科学基金会;
关键词
Graph coloring; shortcuts; parallelism; GPU computing;
D O I
10.1145/3332466.3374519
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Graph coloring is an assignment of colors to the vertices of a graph such that no two adjacent vertices get the same color. It is a key building block in many applications. Finding a coloring with a minimal number of colors is often only part of the problem. In addition, the solution also needs to be computed quickly. Several parallel implementations exist, but they may suffer from low parallelism depending on the input graph. We present an approach that increases the parallelism without affecting the coloring quality. On 18 test graphs, our technique yields an average of 3.4 times more parallelism. Our CUDA implementation running on a Titan V is 2.9 times faster on average and uses as few or fewer colors as the best GPU codes from the literature.
引用
收藏
页码:262 / 275
页数:14
相关论文
共 50 条
[31]   Facets of the graph coloring polytope [J].
Coll, P ;
Marenco, J ;
Díaz, IM ;
Zabala, P .
ANNALS OF OPERATIONS RESEARCH, 2002, 116 (1-4) :79-90
[32]   COLORING THE EDGES OF A DIRECTED GRAPH [J].
Szabo, Sandor ;
Zavalnij, Bogdan .
INDIAN JOURNAL OF PURE & APPLIED MATHEMATICS, 2014, 45 (02) :239-260
[33]   Online Coloring a Token Graph [J].
Kevin G. Milans ;
Michael C. Wigal .
Graphs and Combinatorics, 2020, 36 :153-165
[34]   A novel scheme for graph coloring [J].
Donderia, Vishal ;
Jana, Prasanta K. .
2ND INTERNATIONAL CONFERENCE ON COMPUTER, COMMUNICATION, CONTROL AND INFORMATION TECHNOLOGY (C3IT-2012), 2012, 4 :261-266
[35]   Parameterized Mixed Graph Coloring [J].
Damaschke, Peter .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (02) :362-374
[36]   Graph coloring with decision diagrams [J].
Willem-Jan van Hoeve .
Mathematical Programming, 2022, 192 :631-674
[37]   Coloring the nodes of a directed graph [J].
Szabo, Sandor ;
Zavalnij, Bogdan .
ACTA UNIVERSITATIS SAPIENTIAE INFORMATICA, 2014, 6 (01) :117-131
[38]   Coloring the edges of a directed graph [J].
Sándor Szabó ;
Bogdán Zavalnij .
Indian Journal of Pure and Applied Mathematics, 2014, 45 :239-260
[39]   Evaluating Graph Coloring on GPUs [J].
Grosset, A. V. Pascal ;
Zhu, Peihong ;
Liu, Shusen ;
Venkatasubramanian, Suresh ;
Hall, Mary .
ACM SIGPLAN NOTICES, 2011, 46 (08) :297-298
[40]   Parallel and distributed core label propagation with graph coloring [J].
Attal, Jean-Philippe ;
Malek, Maria ;
Zolghadri, Marc .
CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE, 2019, 31 (02)