Optimizing sparse computations jointly

Abstract

This work proposes a framework called FuSy that analyzes the data dependence graphs (DAGs) of two sparse kernels and creates an efficient schedule to execute the kernels in combination. Sparse kernels are frequently used in scientific codes and in machine learning algorithms and very often they are used in combination. Iterative linear system solvers are an example where kernels such as sparse triangular solver (SpTRSV) and sparse matrix-vector multiplication (SpMV) are called consecutively in each iteration of the solver. Prior approaches typically optimize these sparse kernels independently leading to high synchronization overheads and low locality. We propose an approach that analyzes the DAGs of two sparse kernels and then creates a new order of execution that enables running the two kernels efficiently in parallel. To investigate the efficiency of our approach, we compare it with the state-of-the-art MKL library for two kernel combinations, SpTRSV-SpMV and SpMV-SpTRSV which are commonly used in iterative solvers. Experimental results show that our approach is on average 2.6X and 1.8X faster than the MKL library for a set of matrices from the Suitesparse matrix repository.