high performance computing on graphics processing units: hgpu.org

In recent years, the production and usage of vast graphs from different disciplines—social networks, geographical navigation, and internet routing to name a few—has required fast and scalable algorithms. Reachability, single source shortest path, partitioning, and coloring are some of the problems that are commonly applied to graphs. In this thesis, we focus on the problem of graph coloring. To color a graph, we assign a label, called color, to each of its nodes. Colors must be assigned so that no two nodes connected by an edge share the same color. Many scalable algorithms have been proposed; we select, discuss and implement a suite of algorithms for both multi-core CPU and many-core GPU architectures. In particular, we implement the Greedy, Gebremedhin-Manne, and Jones-Plassmann algorithms for multi-core CPU architectures, and the Jones-Plassmann-Luby algorithm for many-core GPU architectures with the help of the CUDA framework. For the latter, we propose a cost-free technique, called index shifting, to lower computation time and reduce the number of colors produced for the solution. We compare the results of our software with cuSPARSE’s csrcolor and Gunrock’s state-of-the-art implementations, both in terms of computation time and quality of the solution, i.e., the number of colors. We show how our fastest implementation on the GPU produces on average 10% fewer colors than Gunrock’s implementation, while also being 2.5 times faster. In recent years, the production and usage of vast graphs from different disciplines—social networks, geographical navigation, and internet routing to name a few—has required fast and scalable algorithms. Reachability, single source shortest path, partitioning, and coloring are some of the problems that are commonly applied to graphs. In this thesis, we focus on the problem of graph coloring. To color a graph, we assign a label, called color, to each of its nodes. Colors must be assigned so that no two nodes connected by an edge share the same color. Many scalable algorithms have been proposed; we select, discuss and implement a suite of algorithms for both multi-core CPU and many-core GPU architectures. In particular, we implement the Greedy, Gebremedhin-Manne, and Jones-Plassmann algorithms for multi-core CPU architectures, and the Jones-Plassmann-Luby algorithm for many-core GPU architectures with the help of the CUDA framework. For the latter, we propose a cost-free technique, called index shifting, to lower computation time and reduce the number of colors produced for the solution. We compare the results of our software with cuSPARSE’s csrcolor and Gunrock’s state-of-the-art implementations, both in terms of computation time and quality of the solution, i.e., the number of colors. We show how our fastest implementation on the GPU produces on average 10% fewer colors than Gunrock’s implementation, while also being 2.5 times faster.