Analysing and Tuning the Performance of Graph Processing Algorithms: a Statistical Modeling Approach
Performance Analysis and Optimization
TimeWednesday, June 19th2:45pm - 3:15pm
DescriptionLarge-scale and complex graph processing applications form a challenging domain for high-performance computing. Despite graph processing algorithms being considered parallelism-unfriendly, the use of parallel architectures like multi-core CPUs and GPUs have proven revolutionary for these applications. However, analysing and modeling the performance of these algorithms on parallel platforms remains a challenge: the tight dependencies between platform, algorithm, and dataset are proven difficult to analytically determine, model, and feed back into the algorithm design.
In this work, we present a comprehensive framework for graph processing performance analysis, and further demonstrate its use for performance modeling and tuning. Our solution is based on a statistical approach, and combines efficient model training with accurate predictions. We are further able to use these predictions to improve algorithm execution. Finally, we present the performance analysis and tuning of two case-studies (BFS and PageRank), and demonstrate how to use performance modeling to obtain better implementations, which clearly outperform state-of-the-art implementations.