The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Sparse matrix product implementation on field programmable gate arrays (EPGAS)
Author:	Sheth, Amit Mahendra
View Online:	njit-etd2003-062 (x, 55 pages ~ 3.7 MB pdf)
Department:	Department of Electrical and Computer Engineering
Degree:	Master of Science
Program:	Electrical Engineering
Document Type:	Thesis
Advisory Committee:	Ziavras, Sotirios (Committee co-chair) Agrawal, Vishwani D. (Committee co-chair) Carpinelli, John D. (Committee member) Rojas-Cessa, Roberto (Committee member)
Date:	2003-05
Keywords:	Sparse matrices Field programmable gate arrays
Availability:	Unrestricted
Abstract:	If dense matrix multiplication algorithms are used with sparse matrices, they can result in a large number of redundant calculations, as numerous elements in sparse matrices are zero valued, thus available resources and time may be wasted. The algorithm discussed here aims to take advantage of the sparseness of the matrices by multiplying only nonzero elements. The NIOS development board from Altera is used for implementing the above algorithm. First a sequential program in the C programming language is downloaded onto the FPGA and run by the NIOS soft-processor. Then the same board is also used for a parallel implementation of the above algorithm using three NIOS soft-processors within the same FPGA. Such an approach is very critical because current FPGAs do not contain enough resources to solve large problems. For example, we cannot build large memory systems within FPGAs so we need to employ algorithms that have rather limited memory requirements. Our proposed matrix multiplication algorithm for sparse matrices uses the available memory space very cautiously and also results in good execution times. Performance results testify to this fact.