Sparse matrix-vector multiplication by specialization

Black Silva, Edgar

Permalink

https://hdl.handle.net/2142/45518 Copy

Description

Title

Sparse matrix-vector multiplication by specialization

Author(s)

Black Silva, Edgar

Issue Date

2013-08-22T16:42:56Z

Director of Research (if dissertation) or Advisor (if thesis)

Kamin, Samuel N.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• sparse matrix-vector multiplication
• program specialization
• run-time code generation.

Abstract

Program specialization is the process of generating optimized programs based on available inputs. It is particularly applicable when some input data are used repeatedly while other input data vary. Specialization can be employed at compile-time as well as at run-time, depending on when the inputs become available. This technique has the potential of generating highly efficient codes, at the expense of the overheads of the run-time code generation. In this thesis, the potential for using specialization to obtain speed-ups in the very common numerical procedure of sparse matrix-vector multiplication, in the case where a single matrix is to be multiplied by many vectors, is explored. The main objective is the evaluation of the speed-ups that can be obtained with program specialization without considering the overheads of the code generation. Tests were prepared to probe several sparse matrix-vector multiplication methods using fifty-three sparse matrices obtained from the Matrix Market and the University of Florida Sparse Matrix Collection and run on four target platforms. In this investigation, only sequential execution was tested. The research found that two of the methods were more frequently faster that all the other methods combined and that the speed-up of these methods was significant when compared to a variant of the standard compressed sparse rows (CSR) method.

Graduation Semester

2013-08

Permalink

http://hdl.handle.net/2142/45518

Copyright and License Information

Copyright 2013 Edgar Black Silva

Owning Collections