The Algorithms for FPGA Implementation of Sparse Matrices Multiplication

Authors

  • Ernest Jamro AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow
  • Tomasz Pabiś AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow
  • Paweł Russek AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow
  • Kazimierz Wiatr AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow

Keywords:

FPGA, sparse matrices, sparse BLAS, matrices multiplication

Abstract

In comparison to dense matrices multiplication, sparse matrices multiplication real performance for CPU is roughly 5--100 times lower when expressed in GFLOPs. For sparse matrices, microprocessors spend most of the time on comparing matrices indices rather than performing floating-point multiply and add operations. For 16-bit integer operations, like indices comparisons, computational power of the FPGA significantly surpasses that of CPU. Consequently, this paper presents a novel theoretical study how matrices sparsity factor influences the indices comparison to floating-point operation workload ratio. As a result, a novel FPGAs architecture for sparse matrix-matrix multiplication is presented for which indices comparison and floating-point operations are separated. We also verified our idea in practice, and the initial implementations results are very promising. To further decrease hardware resources required by the floating-point multiplier, a reduced width multiplication is proposed in the case when IEEE-754 standard compliance is not required.

Downloads

Download data is not yet available.

Downloads

How to Cite

Jamro, E., Pabiś, T., Russek, P., & Wiatr, K. (2015). The Algorithms for FPGA Implementation of Sparse Matrices Multiplication. Computing and Informatics, 33(3), 667–684. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/2795

Most read articles by the same author(s)