SMOReS: Sparse Matrix Omens of Reordering Success
Date
2011
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Open Access
Terms of Use
Tripod URL
Identifier
Abstract
Despite their widespread use, sparse matrix computations exhibit poor performance, due to their memory-bandwidth bound nature. Techniques have been developed that help these computations take advantage of unexploited data reuse by transforming it into data locality, generally improving performance. One such technique is to reorder the matrix prior to running a computation on it. However, reordering a matrix takes time and does not always provide performance improvements. We present a classification model that predicts, with 82% accuracy and no significantly incorrect predictions, whether reordering a matrix will improve the performance of the matrix power kernel, Akx. Our classifier is an ensemble of decision stumps generated by the AdaBoost learning algorithm and is trained on 60 matrices with a wide range of memory footprints and average number of nonzeros per row.