高品質分散式圖著色演算法

Abstract

圖著色（Graph Coloring）是一種基礎的演算法，目的是將顏色分配給圖形的節點，且相鄰節點不能擁有相同的顏色。在平行圖著色演算法中，主要評估兩個參數：顏色的品質與執行速度。我們提出的優化包含兩個部分： 首先，我們重新設計 JP-SL 的優先級分配流程，以減少全域頂點掃描的次數並在執行過程中更有效地利用平行化。其次，我們將大規模圖劃分為多個子圖，並將其分配至多個 GPU 上同時運行，以進一步提升整體執行效率。

Graph coloring is a fundamental problem involving the assignment of colors to the vertices of a graph, ensuring that no two adjacent vertices possess the same color. In parallel graph coloring, two primary parameters are evaluated: color quality and execution speed. Our optimization methodology has two parts. We first improve priority allocation by re-engineering JP-SL to minimize global vertex scans and optimize parallelism during execution. Secondly, we enhance the overall runtime by splitting the extensive graph into subgraphs and allocating them across many GPUs for concurrent execution.