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)

[thumbnail of greed.pdf] PDF
Restricted to Repository staff only

Download (1MB) | Request a copy


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
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: Kamer Kaya
Date Deposited: 20 Aug 2017 16:15
Last Modified: 26 Apr 2022 09:27

Actions (login required)

View Item
View Item