Supervisor: Apan Qasem (Texas State University)
Abstract: Graph 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.
ACM-SRC Semi-Finalist: yes
Poster Summary: PDF
Back to Poster Archive Listing