CaltechTHESIS
  A Caltech Library Service

Floating-point sparse matrix-vector multiply for FPGAs

Citation

deLorimier, Michael (2006) Floating-point sparse matrix-vector multiply for FPGAs. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-05132005-144347

Abstract

Large, high density FPGAs with high local distributed memory bandwidth surpass the peak floating-point performance of high-end, general-purpose processors. Microprocessors do not deliver near their peak floating-point performance on efficient algorithms that use the Sparse Matrix-Vector Multiply (SMVM) kernel. In fact, microprocessors rarely achieve 33% of their peak floating-point performance when computing SMVM. We develop and analyze a scalable SMVM implementation on modern FPGAs and show that it can sustain high throughput, near peak, floating-point performance. Our implementation consists of logic design as well as scheduling and data placement techniques. For benchmark matrices from the Matrix Market Suite we project 1.5 double precision Gflops/FPGA for a single VirtexII-6000-4 and 12 double precision Gflops for 16 Virtex IIs (750 Mflops/FPGA). We also analyze the asymptotic efficiency of our architecture as parallelism scales using a constant rent-parameter matrix model. This demonstrates that our data placement techniques provide an asymptotic scaling benefit.

While FPGA performance is attractive, higher performance is possible if we re-balance the hardware resources in FPGAs with embedded memories. We show that sacrificing half the logic area for memory area rarely degrades performance and improves performance for large matrices, by up to 5 times. We also 0 the performance effect of adding custom floating-point using a simple area model to preserve total chip area. Sacrificing logic for memory and custom floating-point units increases single FPGA performance to 5 double precision Gflops.

Item Type:Thesis (Master's thesis)
Subject Keywords:Floating Point; FPGA; Reconfigurable Architecture; Sparse Matrix
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • DeHon, Andre
Thesis Committee:
  • Unknown, Unknown
Defense Date:5 June 2005
Author Email:mdel (AT) cs.caltech.edu
Record Number:CaltechETD:etd-05132005-144347
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-05132005-144347
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1776
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:13 May 2005
Last Modified:26 Dec 2012 02:41

Thesis Files

[img]
Preview
PDF (smvm_thesis.pdf) - Final Version
See Usage Policy.

539Kb

Repository Staff Only: item control page