Files in this item

FilesDescriptionFormat

application/pdf

application/pdfEdgar_Black Silva.pdf (2MB)
(no description provided)PDF

Description

Title:Sparse matrix-vector multiplication by specialization
Author(s):Black Silva, Edgar
Advisor(s):Kamin, Samuel N.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(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.
Issue Date:2013-08-22
URI:http://hdl.handle.net/2142/45518
Rights Information:Copyright 2013 Edgar Black Silva
Date Available in IDEALS:2013-08-22
Date Deposited:2013-08


This item appears in the following Collection(s)

Item Statistics