Rosko: Row Skipping Outer Products for Sparse Matrix Multiplication
  Kernels
Vikas Natesh Andrew Sabot H. T. Kung Mark Ting
We propose Rosko -- row skipping outer products -- for deriving sparse matrix
multiplication (SpMM) kernels in reducing computation and memory access
requirements of deep neural networks (DNNs). Rosko allows skipping of entire
row computations during program execution with low sparsity-management
overheads. We analytically derive sparse CPU kernels that adapt to given
hardware characteristics to effectively utilize processor cores and minimize
data movement without the need for auto-tuning or search space exploration.
Rosko can be integrated with other outer product scheduling methods, allowing
them to leverage row skipping by using Rosko's packing format to skip
unnecessary computation.
  Rosko kernels outperform existing auto-tuning and search-based solutions as
well as state-of-the-art vendor-optimized libraries on real hardware across a
variety of neural network workloads. For matrices with sparsities ranging from
65% to 99.8% typically found in machine learning, Rosko kernels achieve up to a
6.5x runtime reduction on Intel and ARM CPUs.