  Sparse matrix computation is crucial in various modern applications,
including large-scale graph analytics, deep learning, and recommendation
systems. The performance of these algorithms varies greatly depending on the
structure of the input matrix, making it difficult to gain a comprehensive
understanding of sparse computation and its relationship to inputs, algorithms,
and target machine architecture. Despite extensive research on certain sparse
algorithms, such as SpMV, the overall family of sparse algorithms has yet to be
investigated as a whole. In this paper, we introduce SpChar, a workload
characterization methodology for general sparse computation. SpChar employs
tree-based models to identify the most relevant hardware and input
characteristics, starting from hardware and input-related metrics gathered from
Performance Monitoring Counters and matrices. Our analysis enables the creation
of a characterization loop that facilitates the optimization of sparse
computation by mapping the impact of architectural features to inputs and
algorithmic choices. We apply SpChar to more than 600 matrices from the
SuiteSparse Matrix collection and three state-of-the-art Arm CPUs to determine
the critical hardware and software characteristics that affect sparse
computation. In our analysis, we determine that the biggest limiting factors
for high-performance sparse computation are (1) the latency of the memory
system, (2) the pipeline flush overhead resulting from branch misprediction,
and (3) the poor reuse of cached elements. However, the degree to which those
impact the performance of a CPU greatly depends on the algorithm and the input
data.
