Greed is good: parallel algorithms for bipartite-graph partial coloring on multicore architectures

Taş, Mustafa Kemal and Kaya, Kamer and Saule, Erik (2017) Greed is good: parallel algorithms for bipartite-graph partial coloring on multicore architectures. In: 46th International Conference on Parallel Processing (ICPP 2017) , Bristol, UK (Accepted/In Press)

[img]PDF - Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, coloring is not free and the overhead can be significant. In particular, for the bipartite-graph partial coloring (BGPC) and distance-2 graph coloring (D2GC) problems, which have various use-cases within the scientific computing and numerical optimization domains, the coloring overhead can be in the order of minutes with a single thread for many real-life graphs. In this work, we propose parallel algorithms for bipartite- graph partial coloring on shared-memory architectures. Com- pared to the existing shared-memory BGPC algorithms, the proposed ones employ greedier and more optimistic techniques that yield a better parallel coloring performance. In particular, on 16 cores, the proposed algorithms are more than 4× faster than their counterparts in the ColPack library which is, to the best of our knowledge, the only publicly-available coloring library for multicore architectures. In addition to BGPC, the proposed techniques are employed to devise parallel distance-2 graph coloring algorithms and similar performance improvements have been observed. Finally, we propose two costless balancing heuristics for BGPC that can reduce the skewness and imbalance on the cardinality of color sets (almost) for free. The heuristics can also be used for the D2GC problem and in general, they will probably yield a better color-based parallelization performance especially on many-core architectures.

Item Type:Papers in Conference Proceedings
Subjects:Q Science > QA Mathematics > QA075 Electronic computers. Computer science
ID Code:32993
Deposited By:Kamer Kaya
Deposited On:20 Aug 2017 16:15
Last Modified:20 Aug 2017 16:15

Repository Staff Only: item control page