Bilkent University
Department of Computer Engineering
CS 690 SEMINAR
Reordering Methods for Improving the Performance of Parallel Sparse Matrix-Vector Multiplication on Many-Core Architectures
Nabil Abubaker
PhD Student
Computer Engineering Department
Bilkent University
Sparse Matrix-Vector Multiplication (SpMV) of the form y=Ax is a very important kernel operation in many scientific applications. Even though there exist several ways to store and process the sparse matrices efficiently, the SpMV still suffers from poor utilization of the CPU cache due to accessing the entries of input (x) vector and output (y) vector in a highly irregular fashion. Such irregular accesses make the life of the hardware prefetcher harder as it fails to capture them, therefore fails to predict the correct next element to be brought to the cache. One way to improve the cache utilization is to reorder the rows and columns of the input matrix in a way that rows/ columns that have similar nonzero patterns are clustered near each other. In this work, we propose novel graph/ hypergraph models that encapsulates better representations of the similarities between rows and columns in order to produce a better reordering for the input matrix. Our methods target exploiting both spatial and temporal localities by reordering both the rows and the columns of the input matrix. Our conducted experiments on Intel’s Xeon Phi and Xeon processors show that our methods outperform state-of-the-art reordering methods in terms of Gflop/s. We also demonstrate the importance of the reordering methods in utilizing the vectorized operations (SIMD) on today’s processors and hardware accelerators.
DATE: 12 March, 2018, Monday, CS590 & CS690 presentations begin at @ 15:40
PLACE: EA-409