  Sparse matrix computation is crucial in various modern applications,
including large-scale graph analytics, deep learning, and recommender systems.
The performance of sparse kernels 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 kernels,
such as Sparse Matrix-Vector Multiplication (SpMV), the overall family of
sparse algorithms has yet to be investigated as a whole. This paper introduces
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 (PMCs) 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. Additionally, we
propose software and hardware optimizations that designers can implement to
create a platform suitable for sparse computation. We then investigate these
optimizations using the gem5 simulator to achieve a significant speedup of up
to 2.63x compared to a CPU where the optimizations are not applied.
