Sparse-Aware CARM: Rooflining Locality of Sparse Computations

Sparse computation is a centre focus of modern high performance computing research. However, the complexity associated with the variety of algorithms, storage formats and data diversity, makes improving the performance of sparse computations on general-purpose hardware a strenuous task. For this purpose, the Cache Aware Rooine Model (CARM) can be a useful tool, mainly due to its intuitive analysis of the application bottlenecks and the ability to pinpoint how close the examined application is to exploit the maximum attainable performance of a micro-architecture. However, the CARM’s absolute architecture rooflines are not always sufficient to represent sparse computation scenarios, which are limited by indirect and irregular memory accesses, thus challenging the accuracy of characterization and insights obtained from the model. To improve the CARM insightfulness for sparse computations, this paper proposes a new modeling methodology that derives more representative processing upper-bounds for sparse computing scenarios, which can be applied to different formats and computation types. The proposed sparse-aware CARM is utilized to profile SpMV kernel providing more accurate cache locality insights regarding the memory accesses, for various multi-threaded execution scenarios. Additionally, possible optimization paths are explored, such as reordering for improving performance and core frequency scaling to boost energy efficiency.