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.
Publié le : 2015-02-04
Classification:  FPGA, sparse matrices, sparse BLAS, matrices multiplication,  65F50
@article{cai2795,
     author = {Ernest Jamro; AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow and Tomasz Pabi\'s; AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow and Pawe\l\ Russek; AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow and Kazimierz Wiatr; AGH University of Science and Technology, Department of Electronics, Al. Mickiewicza 30, 30-059 Krakow},
     title = {The Algorithms for FPGA Implementation of Sparse Matrices Multiplication},
     journal = {Computing and Informatics},
     volume = {33},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai2795}
}
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. The Algorithms for FPGA Implementation of Sparse Matrices Multiplication. Computing and Informatics, Tome 33 (2015) no. 3, . http://gdmltest.u-ga.fr/item/cai2795/