A Library for Pattern-based Sparse Matrix Vector Multiply

Simple item page
dc.contributor.authorBelgin, Mehmeten
dc.contributor.authorBack, Godmar V.en
dc.contributor.authorRibbens, Calvin J.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:35:52Zen
dc.date.available2013-06-19T14:35:52Zen
dc.date.issued2009en
dc.description.abstractPattern-based Representation (PBR) is a novel approach to improving the performance of Sparse Matrix-Vector Multiply (SMVM) numerical kernels. Motivated by our observation that many matrices can be divided into blocks that share a small number of distinct patterns, we generate custom multiplication kernels for frequently recurring block patterns. The resulting reduction in index overhead significantly reduces memory bandwidth requirements and improves performance. Unlike existing methods, PBR requires neither detection of dense blocks nor zero filling, making it particularly advantageous for matrices that lack dense nonzero concentrations. SMVM kernels for PBR can benefit from explicit prefetching and vectorization, and are amenable to parallelization. The analysis and format conversion to PBR is implemented as a library, making it suitable for applications that generate matrices dynamically at runtime. We present sequential and parallel performance results for PBR on two current multicore architectures, which show that PBR outperforms available alternatives for the matrices to which it is applicable, and that the analysis and conversion overhead is amortized in realistic application scenarios.en
dc.format.mimetypeapplication/pdfen
dc.identifierhttp://eprints.cs.vt.edu/archive/00001103/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00001103/01/PBR_Technical_Report.pdfen
dc.identifier.trnumberTR-09-27en
dc.identifier.urihttp://hdl.handle.net/10919/20217en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subjectMathematical softwareen
dc.titleA Library for Pattern-based Sparse Matrix Vector Multiplyen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
PBR_Technical_Report.pdf
Size:
950.13 KB
Format:
Adobe Portable Document Format
Download

Collections

Computer Science Technical Reports