Innovative Unit-Vector-Block Storage Format of Sparse Matrix and Vector

Sparse Matrix-Vector Multiplication (SpMV) operation is widely used in many iterative numerical algorithms, such as high performance computing, machine learning, and graph processing. However, peak performance is limited due to the fact that the commonly used algorithms alternate between compute-bound and memory-bound steps. This paper introduces a new storage format UVB (Unit Vector Block) for sparse matrix and vector, which needs less memory capacity compared to current popular formats for sparse vector and matrix such as COO, CSR, DIA, ELL and etc. Moreover, a new SpMV algorithm based on this new format can make full use of Intel® AVX-512 instruction set, and decrease the execution time by up to 99% compared with the most popular LIBSVM kernel.

• Publication year

  2019

• Venue

  International Conference on Communication, Computing & Security

• Publication date

  2019-02-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.1109/CCOMS.2019.8821708
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A High Memory Bandwidth FPGA Accelerator for Sparse Matrix-Vector Multiplication

  2014cited by this paper
• Efficient sparse matrix multiple-vector multiplication using a bitmapped format

  2013cited by this paper
• Towards a Universal FPGA Matrix-Vector Multiplication Architecture

  2012cited by this paper
• Reduced-Bandwidth Multithreaded Algorithms for Sparse Matrix-Vector Multiplication

  2011cited by this paper
• Improving the Performance of the Sparse Matrix Vector Product with GPUs

  2010cited by this paper
• Efficient Sparse Matrix-Vector Multiplication on CUDA

  2008cited by this paper
• Optimizing Sparse Matrix-Vector Multiplication on GPUs using Compile-time and Run-time Strategies

  2008cited by this paper
• Sparse Matrix-Vector multiplication on FPGAs

  2005cited by this paper
• Vectorized Sparse Matrix Multiply for Compressed Row Storage Format

  2005influential reference
• ITPACK project: Past, present, and future

  1984influential reference

• A Storage Optimization Scheme for PITD Method Using Sparse Matrix-Vector Multiplication

  2025cites this paper