Imperial College London
Alternate

ProfessorPaulKelly

Faculty of Engineering, Department of Computing

Professor of Software Technology
 
 
 
//

Contact

 

+44 (0)20 7594 8332p.kelly Website

 
 
//

Location

 

Level 3 (upstairs), William Penney Building, room 304William Penney LaboratorySouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Rokos:2015:10.1007/978-3-662-48096-0_32,
author = {Rokos, G and Gorman, G and Kelly, PHJ},
doi = {10.1007/978-3-662-48096-0_32},
pages = {414--425},
publisher = {Springer},
title = {A fast and scalable graph coloring algorithm for multi-core and many-core architectures},
url = {http://dx.doi.org/10.1007/978-3-662-48096-0_32},
year = {2015}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - Irregular computations on unstructured data are an important class of problems for parallel programming. Graph coloring is often an important preprocessing step, e.g. as a way to perform dependency analysis for safe parallel execution. The total run time of a coloring algorithm adds to the overall parallel overhead of the application whereas the number of colors used determines the amount of exposed parallelism. A fast and scalable coloring algorithm using as few colors as possible is vital for the overall parallel performance and scalability of many irregular applications that depend upon runtime dependency analysis. Çatalyürek et al. have proposed a graph coloring algorithm which relies on speculative, local assignment of colors. In this paper we present an improved version which runs even more optimistically with less thread synchronization and reduced number of conflicts compared to Çatalyürek et al.’s algorithm.We show that the new technique scales better on multicore and many-core systems and performs up to 1.5x faster than its predecessor on graphs with high-degree vertices, while keeping the number of colors at the same near-optimal levels.
AU  - Rokos,G
AU  - Gorman,G
AU  - Kelly,PHJ
DO  - 10.1007/978-3-662-48096-0_32
EP  - 425
PB  - Springer
PY  - 2015///
SN  - 0302-9743
SP  - 414
TI  - A fast and scalable graph coloring algorithm for multi-core and many-core architectures
UR  - http://dx.doi.org/10.1007/978-3-662-48096-0_32
UR  - http://hdl.handle.net/10044/1/27301
ER  -
Download