Greed Is Good: Parallel Algorithms for Bipartite-Graph Partial Coloring on Multicore Architectures
Greed Is Good: Parallel Algorithms for Bipartite-Graph Partial Coloring on Multicore Architectures
复制标题
DOI：
10.1109/icpp.2017.59
复制
发表时间：
2017-05
期刊：
影响因子：
--
通讯作者：
Mustafa Kemal Tas;K. Kaya;Erik Saule
中科院分区：
文献类型：
--
作者：
Mustafa Kemal Tas;K. Kaya;Erik Saule
在并行计算中，有效的图着色产生对着色任务、数据点等的无锁处理，而不需要昂贵的同步机制。然而，上色并不是免费的，而且开销可能会很大。特别地，对于在科学计算和数值优化领域中具有不同用例的二部图部分着色(BGPC)和距离2图着色(D2GC)问题，对于许多现实中的图，在单个线程的情况下，着色开销可能在几分钟量级。与现有的共享内存BGPC算法相比，所提出的算法采用了更贪婪和更乐观的技术，产生了更好的并行着色性能。特别是，在16核上，所提出的算法比ColPack库中的对应算法快4倍以上，据我们所知，ColPack库是唯一公开可用的多核体系结构的着色库。除了BGPC之外，所提出的技术还被用于设计并行距离-2图着色算法，并且观察到了类似的性能改善。最后，我们针对BGPC提出了两种无代价的平衡启发式算法，可以几乎免费地减少颜色集在基数上的偏度和不平衡。启发式算法也可以用于D2GC问题，一般来说，它们可能会产生更好的基于颜色的并行性能，特别是在多核架构上。
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. Compared 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 4x 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.