  Sparse Matrix-Vector multiplication (SpMV) is an essential computational
kernel in many application scenarios. Tens of sparse matrix formats and
implementations have been proposed to compress the memory storage and speed up
SpMV performance. We develop AlphaSparse, a superset of all existing works that
goes beyond the scope of human-designed format(s) and implementation(s).
AlphaSparse automatically \emph{creates novel machine-designed formats and SpMV
kernel implementations} entirely from the knowledge of input sparsity patterns
and hardware architectures. Based on our proposed Operator Graph that expresses
the path of SpMV format and kernel design, AlphaSparse consists of three main
components: Designer, Format \& Kernel Generator, and Search Engine. It takes
an arbitrary sparse matrix as input while outputs the performant
machine-designed format and SpMV implementation. By extensively evaluating 843
matrices from SuiteSparse Matrix Collection, AlphaSparse achieves significant
performance improvement by 3.2$\times$ on average compared to five
state-of-the-art artificial formats and 1.5$\times$ on average (up to
2.7$\times$) over the up-to-date implementation of traditional auto-tuning
philosophy.
