GREEDY ALGORITHMS FOR DISTANCE-2 GRAPH COLORING AND BIPARTITE GRAPH PARTIAL COLORING

Mustafa Kemal Taş
Computer Science and Engineering, MSc. Thesis, 2019

Thesis Jury

Asst.Prof Kamer Kaya.(Thesis Advisor), Assoc.Prof. Hüsnü Yenigün,

Assoc.Prof. Hasan Sözer ( Özyeğin University)

Date & Time: July 12th, 2019 – 2:30 PM

Place: FENS L058

Keywords : graph coloring, distance-2 coloring, bipartite graph partial coloring, balanced colorin

Abstract

In parallel computing, a valid graph coloring yields a lock-free processing of the colored tasks, data points, etc., without expensive synchronization mechanisms. However, the coloring stage is not free and the overhead can be significant. In particular, for distance-2 graph coloring (D2GC) and bipartite graph partial coloring (BGPC) 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, having millions or even billions of vertices and edges.

In this thesis, we propose a novel greedy algorithm for the distance-2 graph coloring problem on shared-memory architectures. We then extend the algorithm to bipartite graph partial coloring problem, which is struc- turally very similar to D2GC. Proposed algorithms yield a better parallel coloring performance compared to the existing shared-memory coloring algo- rithms, by employing greedier and more optimistic techniques. In particular, when compared to the state-of-the-art the proposed algorithms obtain 25× speedup with 16 cores, without decreasing the coloring quality. Moreover, we extend the existing distance-2 graph coloring algorithm to manycore archi- tectures. Due to architectural limitations, the multicore algorithm can not easily be extended to manycore. Thus several optimizations are proposed to overcome such obstacles. In addition to multi and manycore implementa- tions, we also offer novel optimizations for both D2GC and BGPC on social network graphs. Exploiting the structural properties of social graphs, we propose faster heuristics to increase the performance without decreasing the coloring quality. Finally, we propose two costless balancing heuristics that can be applied to both BGPC and D2GC, which would yield a better color- based parallelization performance with a better load-balancing, especially on manycore architectures.