Presentation
Poster 12: Investigating Input Sensitivity in GPU Graph Analytics with Machine Learning
Event Type
ACM Student Research Competition: Graduate Posters
ACM Student Research Competition: Undergraduate Posters
Posters
TP
EX
EXH
Student Program
TimeThursday, 21 November 20198:30am - 5pm
LocationE Concourse
DescriptionGraph algorithms are at the core of data-intensive applications. As such, efficient graph processing is of great importance. Irregularity in real-world graphs can make performance unpredictable and non-portable across different inputs and architectures. Given a type of graph, the same optimized implementation of an algorithm can produce performance numbers that differ by orders-of-magnitude. We conduct extensive analysis on a set of 1238 graphs to identify input-sensitive performance inefficiencies, including two that have not been studied: (i) register pressure and (ii) CPU-GPU data movement via demand paging. We then build a multiclass decision tree classifier that characterizes the irregular properties of graphs from our data and maps them to an optimal control parameterization at the compiler, system and algorithmic layers, that yield the highest overall algorithmic performance. We then integrate the classifier into a system where it will process a new graph and generate a kernel on the predicted optimal configuration.
Archive
