Optimizing Sparse Linear Algebra on Reconfigurable Architecture
dc.contributor.author | Park, Dong-Hyeon | |
dc.date.accessioned | 2021-09-24T19:17:35Z | |
dc.date.available | 2021-09-24T19:17:35Z | |
dc.date.issued | 2021 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/169877 | |
dc.description.abstract | The rise of cloud computing and deep machine learning in recent years have led to a tremendous growth of workloads that are not only large, but also have highly sparse representations. A large fraction of machine learning problems are formulated as sparse linear algebra problems in which the entries in the matrices are mostly zeros. Not surprisingly, optimizing linear algebra algorithms to take advantage of this sparseness is critical for efficient computation on these large datasets. This thesis presents a detailed analysis of several approaches to sparse matrix-matrix multiplication, a core computation of linear algebra kernels. While the arithmetic count of operations for the nonzero elements of the matrices are the same regardless of the algorithm used to perform matrix-matrix multiplication, there is significant variation in the overhead of navigating the sparse data structures to match the nonzero elements with the correct indices. This work explores approaches to minimize these overheads as well as the number of memory accesses for sparse matrices. To provide concrete numbers, the thesis examines inner product, outer product and row-wise algorithms on Transmuter, a flexible accelerator that can reconfigure its cache and crossbars at runtime to meet the demands of the program. This thesis shows how the reconfigurability of Transmuter can improve complex workloads that contain multiple kernels with varying compute and memory requirements, such as the Graphsage deep neural network and the Sinkhorn algorithm for optimal transport distance. Finally, we examine a novel Transmuter feature: register-to-register queues for efficient communication between its processing elements, enabling systolic array style computation for signal processing algorithms. | |
dc.language.iso | en_US | |
dc.subject | sparse linear algebra | |
dc.title | Optimizing Sparse Linear Algebra on Reconfigurable Architecture | |
dc.type | Thesis | |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Computer Science & Engineering | |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | |
dc.contributor.committeemember | Mudge, Trevor N | |
dc.contributor.committeemember | Blaauw, David | |
dc.contributor.committeemember | Dreslinski Jr, Ronald | |
dc.contributor.committeemember | Kim, Hun Seok | |
dc.subject.hlbsecondlevel | Computer Science | |
dc.subject.hlbtoplevel | Engineering | |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/169877/1/dohypark_1.pdf | |
dc.identifier.doi | https://dx.doi.org/10.7302/2922 | |
dc.identifier.orcid | 0000-0003-3052-6890 | |
dc.identifier.name-orcid | Park, Dong-hyeon; 0000-0003-3052-6890 | en_US |
dc.working.doi | 10.7302/2922 | en |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.