SMOReS: Sparse Matrix Omens of Reordering Success

Title:	SMOReS: Sparse Matrix Omens of Reordering Success
Author:	Wood, Samantha
Advisor:	Wonnacott, David G.; Strout, Michelle Mills
Department:	Haverford College. Dept. of Computer Science
Type:	Thesis (B.S.)
Issue Date:	2011
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.
Subject:	Sparse matrices
Subject:	Sparse matrices -- Mathematical models
Terms of Use:	http://creativecommons.org/licenses/by-nc/3.0/us/
Permanent URL:	http://hdl.handle.net/10066/7572

Files in this item

Files	Description	Size	Format
2011WoodS_release.pdf	Archive Staff Only	82.60Kb	application/pdf
2011WoodS_thesis.pdf	Thesis	667.1Kb	application/pdf

Wood, Samantha. "SMOReS: Sparse Matrix Omens of Reordering Success". 2011. Available electronically from http://hdl.handle.net/10066/7572.