Sparse Matrix-Vector Multiplication Based on Network-on-Chip

Sparse matrix-vector multiplication (SMVM) arises in a wide range of applications, and it often dominates the computational cost when solving sparse systems of linear equations or sparse eigenvalue problems iteratively.

The performance of this kernel on general purpose processors is much less than the peak performance due to the high number of required memory operations compared to the number of floating-point operations and poor cache utilization caused by irregular memory access patterns and indirect memory references. Extensive research has been carried out in order to enhance the performance of this operation by using efficient data structures, matrix reordering techniques, parallel implementations, and accelerators.

With the increasing number of cores inside a single chip, providing efficient communication infrastructure became a critical challenge. Therefore, Network-on-Chip (NoC) is used in order to replace shared-bus connections by network-based communication. The extensibility and the flexibility of NoCs make them a promising solution for parallel implementations of algorithms with irregular data structures. For matrices with arbitrary sparsity structures, SMVM is a task which may exhibit very irregular data structures.

In order to achieve an efficient implementation of SMVM on NoC, investigations in different directions and combination of various results are required. First, SMVM data mapping methods are discussed in order to achieve balanced load distribution and minimal communication cost in the NoC. Second, as SMVM is mostly done in iterative algorithms, a combined design of algorithm and architecture is of high importance. A reduction mechanism is proposed to reduce the computational effort of SMVM on NoC benefiting from the robustness of iterative solvers. This mechanism reduces the number of matrix nonzero elements successively during the run of the iterative solver, without affecting the correctness of the solution. Third, an NoC simulation tool is built in order to facilitate investigations on various design factors. The proposed OMNeT++ based NoC simulator provides flexibility and extensibility not provided in hardware.

Finally, an FPGA prototype is proposed for performing SMVM on a data mapping-based NoC architecture.