Accelerating Sparse Matrix Kernels with Co-Optimized Architecture

This dissertation presents an architecture to accelerate sparse matrix linear algebra,which is among the most important numerical methods for numerous science and engineering domains, such as graph analytics, in current big data driven era. Sparse matrixoperations, especially for unstructured and large matrices with very few nonzeros, aredevoid of guaranteed temporal and/or spatial locality making them inherently unsuitable for cache based general purpose commercial o-the-shelf (COTS) architectures.Lack of locality causes data dependent high latency memory accesses and eventuallyexhausts limited load buer in COTS architectures. These render sparse kernels to runat a small fraction of peak machine speed and yield poor o-chip bandwidth saturationdespite finely tuned software libraries/frameworks and optimized code. The poorutilization of compute and memory resources on COTS structures indicates significantroom for improvement using existing technology. However, a computation paradigmthat is not dependent on data locality is essential for sparse operations to achievesame level of performance that BLAS-like standards on COTS have delivered for densematrix linear algebra.An algorithm/hardware co-optimized architecture that provides a data localityindependent platform for sparse matrix operations is developed in this work. Theproposed architecture is founded on a fundamental principle of trading streamingbandwidth and compute to avoid high latency accesses. This principle stems froma counterintuitive insight that minimally required number of irregular memory accesses for sparse operations generally incur high traffic that is transferred at slowspeed, whereas, more regular accesses can provide reduced traffic overall and fastertransfer through better usage of block level data. This work finds that a scalable, high performance and parallelizable multi-way merge network, which is absent incurrent literature, is the core hardware primitive required in developing our proposedarchitecture. Through both algorithmic and circuit level techniques, this work developsa novel multi-way merge hardware primitive that meaningfully eliminates high latencyaccesses for sparse operations. This work also demonstrates methodologies to avoidstrong dependency on fast random access on-chip memory for scaling, which is a majorlimiting factor of current custom hardware solutions in handling very large problems.Using a common custom platform, this work shows implementations of SparseMatrix dense Vector multiplication (SpMV), iterative SpMV and Sparse GeneralMatrix-Matrix multiplication (SpGEMM), which are core kernels for a broad range ofgraph analytic applications. A number of architecture and circuit level optimizationtechniques for reducing o-chip traffic and improving computation throughput tosaturate extreme o-chip steaming bandwidth, provided by state of the art 3D stackingtechnology, are developed. Our proposed custom hardware is demonstrated on ASIC(fabricated in 16nm FinFET) and FPGA platforms and evaluated against state of theart COTS and custom hardware solutions. Experimental results show more than anorder of magnitude improvement over current custom hardware solutions and more thantwo orders of magnitude improvement over COTS architectures for both performanceand energy efficiency. This work is intended to contribute through a software stackprovided by GraphBLAS-like [1] standards where broadest possible audience can utilizethis architecture using a well-defined and concise set of matrix-based graph operations.