Performance = Implementation + Hardware + Input Data, with application to SpMV

Algorithms are typically developed based on an implicit, abstract model of the hardware and inputs. Performance analysis of an implementation generally focuses on identifying bottlenecks utilizing methods such as Intel’s Roofline approach. However, actual performance is influenced by a complex interplay among the implementation, the hardware, and the input. In this paper, we present a methodology that considers a comprehensive view of this interaction and demonstrate how it can be applied to the sparse matrix-vector multiplication kernel, resulting in a 30.29% improvement in performance.