Identification of regular patterns within sparse data structures
| dc.contributor.author | Augustine, Travis, author | |
| dc.contributor.author | Pouchet, Louis-Noël, advisor | |
| dc.contributor.author | Rajopadhye, Sanjay, committee member | |
| dc.contributor.author | Bohm, Anton, committee member | |
| dc.contributor.author | Wilson, James, committee member | |
| dc.date.accessioned | 2020-06-22T11:52:34Z | |
| dc.date.available | 2020-06-22T11:52:34Z | |
| dc.date.issued | 2020 | |
| dc.description.abstract | Sparse matrix-vector multiplication (SpMV) is an essential computation in linear algebra. There is a well-known trade-off between operating on a dense or a sparse structure when performing SpMV. In the dense version of SpMV, useless operations are performed but the computation is amenable SIMD vectorization. In the sparse version, only useful operations are executed. However, an indirection array must be used, thus hindering the compiler's ability to perform optimizations that exploit the vector units available on the majority of modern processors. Our process automatically builds sets of regular sub-computations from the irregular sparse data structure. We mine for regular regions in the irregular data structure, grouping together non-contiguous points from the reorderable set of coordinates representing the sparse structure. The coordinates become partitioned into groupings of coordinates of pre-defined shapes using polyhedra. This partition models the exact same points from the input set of coordinates in a way that is specialized to the input's sparsity pattern. Once we have obtained a partition of the points into sets of polyhedra, we then scan these polyhedra to synthesize code that does not store any coordinates of zero-valued elements and does not require any indirection array to access data, thus making it amenable to SIMD vectorization. | |
| dc.format.medium | born digital | |
| dc.format.medium | masters theses | |
| dc.identifier | Augustine_colostate_0053N_15908.pdf | |
| dc.identifier.uri | https://hdl.handle.net/10217/208429 | |
| dc.language | English | |
| dc.language.iso | eng | |
| dc.publisher | Colorado State University. Libraries | |
| dc.relation.ispartof | 2020- | |
| dc.rights | Copyright and other restrictions may apply. User is responsible for compliance with all applicable laws. For information about copyright law, please see https://libguides.colostate.edu/copyright. | |
| dc.subject | SpMV | |
| dc.title | Identification of regular patterns within sparse data structures | |
| dc.type | Text | |
| dcterms.rights.dpla | This Item is protected by copyright and/or related rights (https://rightsstatements.org/vocab/InC/1.0/). You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s). | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Colorado State University | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science (M.S.) |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Augustine_colostate_0053N_15908.pdf
- Size:
- 748.94 KB
- Format:
- Adobe Portable Document Format