Sparse matrix-vector multiplication by specialization

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2013

Author dc:creator

• Black Silva, Edgar

Contributors dc:contributor

• Kamin, Samuel N.

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

Statement dc:rights

• Copyright 2013 Edgar Black Silva

Language dc:language

en

Handle dc:identifier

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

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/45518