The Library
Feluca : A two-stage graph coloring algorithm with color-centric paradigm on GPU
Tools
Zheng, Zhigao, Shi, Xuanhua, He, Ligang, Jin, Hai, Wei, Shuo, Dai, Hulin and Peng, Xuan (2021) Feluca : A two-stage graph coloring algorithm with color-centric paradigm on GPU. IEEE Transactions on Parallel and Distributed Systems, 32 (1). pp. 160-173. doi:10.1109/TPDS.2020.3014173 ISSN 1045-9219.
|
PDF
WRAP-Feluca-A-two-stage-graph-coloring-algorithm-color-centric-paradigm-He-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1539Kb) | Preview |
Official URL: http://dx.doi.org/10.1109/TPDS.2020.3014173
Abstract
In this paper, we propose a two-stage high-performance graph coloring algorithm, called Feluca, aiming to address the above challenges. Feluca combines the recursion-based method with the sequential spread-based method. In the first stage, Feluca uses a recursive routine to color a majority of vertices in the graph. Then, it switches to the sequential spread method to color the remaining vertices in order to avoid the conflicts of the recursive algorithm. Moreover, the following techniques are proposed to further improve the graph coloring performance. i) A new method is proposed to eliminate the cycles in the graph; ii) a top-down scheme is developed to avoid the atomic operation originally required for color selection; and iii) a novel color-centric coloring paradigm is designed to improve the degree of parallelism for the sequential spread part. All these newly developed techniques, together with further GPU-specific optimizations such as coalesced memory access, comprise an efficient parallel graph coloring solution in Feluca. We have conducted extensive experiments on NVIDIA GPUs. The results show that Feluca can achieve 1.76 - 12.98x speedup over the state-of-the-art algorithms.
Item Type: | Journal Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software T Technology > T Technology (General) |
|||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
Library of Congress Subject Headings (LCSH): | Graph coloring , Graphics processing units , Parallels (Geometry) , Graph algorithms | |||||||||
Journal or Publication Title: | IEEE Transactions on Parallel and Distributed Systems | |||||||||
Publisher: | IEEE | |||||||||
ISSN: | 1045-9219 | |||||||||
Official Date: | 1 January 2021 | |||||||||
Dates: |
|
|||||||||
Volume: | 32 | |||||||||
Number: | 1 | |||||||||
Page Range: | pp. 160-173 | |||||||||
DOI: | 10.1109/TPDS.2020.3014173 | |||||||||
Status: | Peer Reviewed | |||||||||
Publication Status: | Published | |||||||||
Reuse Statement (publisher, data, author rights): | © 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. | |||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||
Date of first compliant deposit: | 13 August 2020 | |||||||||
Date of first compliant Open Access: | 14 August 2020 | |||||||||
RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year