SC17 Denver, CO

Speeding Up GPU Graph Processing Using Structural Graph Properties


Student: Merijn Elwin Verstraaten (University of Amsterdam)
Advisor: Ana Lucia Varbanescu (University of Amsterdam)
Abstract: Due to its wide applicability and flexibility, graph processing is an increasingly important part of data science. To scale complex graph analytics computations to large datasets it is becoming popular to utilise accelerator-based architectures, such as Graphical Processing Units (GPUs).

Mapping irregular graph algorithms to hardware designed for highly regular parallelism is a complex task. There are often multiple ways to parallelise the same operation on the GPU. Which of these parallelisation strategies is the fastest is dependent on the structure of the input graph. Performance differences can be an order of magnitude or more, and the optimal strategy varies from graph to graph.

The goal of my PhD research is to identify how structural properties impact the performance of different strategies and use this information to speed-up GPU graph processing by predicting the fastest parallelisation of an algorithm for a specific input graph.


Summary: pdf
Presentation: pdf
Poster: pdf


Doctoral Showcase Index