Memory Efficiency Implications on Sparse Matrix Operations

1 online resource (127 pages) : PDF

2014

University of North Carolina at Charlotte

Sparse Matrices are very large matrices with very few nonzero elements and operations on sparse matrices are central to many numerical and graph algorithms. The fundamental bottleneck in these operations is the usage of specialized storage formats which only store the NonZero (NZ) elements and the indirect memory references required to access those elements. This makes the operations very sensitive to memory latency and bandwidth. Unfortunately, microprocessor trends are not encouraging for sparse matrix operations: latency is increasing and bandwidth is becoming more scarce. This results in many important applications having very poor computation performance. This dissertation describes a new sparse matrix format called Variable Dual Compressed Blocks (VDCB) that divides a matrix into a number of smaller, variable-sized submatrices with a bitmap to indicate the presence of NZ values. When used in conjunction with customized memory subsystem, this converts the memory reference pattern from random look-ups to a serial access pattern. To quantify how detrimental the legacy sparse matrix storage formats are, the proposed system has been implemented on an FPGA device and two common sparse matrix operations, Sparse Matrix Vector Multiplication (SMVM) and Sparse Matrix Matrix Multiplication (SMMM), were evaluated. These two operations represent a number of challenges for the memory and computation subsystems. Results demonstrate gains in bandwidth efficiency, significant impact on the performance of the SMVM and SMMM operations, and the scalability of the approach.

doctoral dissertations

Electrical engineering
Computer engineering

Ph.D.

Accelerators
FPGAs
High Performance Computing
Memory Bandwidth
Sparse Matrix
Storage Formats

Electrical Engineering

Sass, Ronald

Joshi, Bharat
Conrad, James
Subramanian, Kalpathi

Thesis (Ph.D.)--University of North Carolina at Charlotte, 2014.

This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). For additional information, see http://rightsstatements.org/page/InC/1.0/.

Copyright is held by the author unless otherwise indicated.

Jain_uncc_0694D_10592

http://hdl.handle.net/20.500.13093/etd:1078