Presentation
Combining HTM with RCU to Speed Up Graph Coloring on Multicore Platforms
Event Type
Research Paper
Computer Architecture
Graph Algorithms
Parallel Algorithms
Parallel Applications
TimeTuesday, June 26th12pm - 12:30pm
LocationAnalog 1, 2
DescriptionAbstract. Graph algorithms are hard to parallelize, as they exhibit
varying degrees of parallelism and perform irregular memory accesses.
Graph coloring is a well studied problem, that colors the vertices of a
graph, such that no adjacent vertices have the same color. This is a necessity for a large number of applications that require a coloring with few colors in near-linear time. In this work, we propose a simple and fast parallel graph coloring algorithm, well suited for shared memory
architectures. Our algorithm employs Hardware Transactional Memory
(HTM) to detect coloring inconsistencies between adjacent vertices, and
exploits Read-Copy-Update (RCU) to enable high performance and ensure correctness.
We evaluate our algorithm on an Intel Haswell server using large-scale
synthetic and real-world graphs, chosen to vary in terms of density and
structure. With 14 threads, we achieved a geometric-mean speedup of
4.35 and a maximum speedup of 11.44.
varying degrees of parallelism and perform irregular memory accesses.
Graph coloring is a well studied problem, that colors the vertices of a
graph, such that no adjacent vertices have the same color. This is a necessity for a large number of applications that require a coloring with few colors in near-linear time. In this work, we propose a simple and fast parallel graph coloring algorithm, well suited for shared memory
architectures. Our algorithm employs Hardware Transactional Memory
(HTM) to detect coloring inconsistencies between adjacent vertices, and
exploits Read-Copy-Update (RCU) to enable high performance and ensure correctness.
We evaluate our algorithm on an Intel Haswell server using large-scale
synthetic and real-world graphs, chosen to vary in terms of density and
structure. With 14 threads, we achieved a geometric-mean speedup of
4.35 and a maximum speedup of 11.44.