Matching Items (3)
Filtering by
- Member of: ASU Electronic Theses and Dissertations
Description
With the end of Dennard scaling and Moore's law, architects have moved towards
heterogeneous designs consisting of specialized cores to achieve higher performance
and energy efficiency for a target application domain. Applications of linear algebra
are ubiquitous in the field of scientific computing, machine learning, statistics,
etc. with matrix computations being fundamental to these linear algebra based solutions.
Design of multiple dense (or sparse) matrix computation routines on the
same platform is quite challenging. Added to the complexity is the fact that dense
and sparse matrix computations have large differences in their storage and access
patterns and are difficult to optimize on the same architecture. This thesis addresses
this challenge and introduces a reconfigurable accelerator that supports both dense
and sparse matrix computations efficiently.
The reconfigurable architecture has been optimized to execute the following linear
algebra routines: GEMV (Dense General Matrix Vector Multiplication), GEMM
(Dense General Matrix Matrix Multiplication), TRSM (Triangular Matrix Solver),
LU Decomposition, Matrix Inverse, SpMV (Sparse Matrix Vector Multiplication),
SpMM (Sparse Matrix Matrix Multiplication). It is a multicore architecture where
each core consists of a 2D array of processing elements (PE).
The 2D array of PEs is of size 4x4 and is scheduled to perform 4x4 sized matrix
updates efficiently. A sequence of such updates is used to solve a larger problem inside
a core. A novel partitioned block compressed sparse data structure (PBCSC/PBCSR)
is used to perform sparse kernel updates. Scalable partitioning and mapping schemes
are presented that map input matrices of any given size to the multicore architecture.
Design trade-offs related to the PE array dimension, size of local memory inside a core
and the bandwidth between on-chip memories and the cores have been presented. An
optimal core configuration is developed from this analysis. Synthesis results using a 7nm PDK show that the proposed accelerator can achieve a performance of upto
32 GOPS using a single core.
heterogeneous designs consisting of specialized cores to achieve higher performance
and energy efficiency for a target application domain. Applications of linear algebra
are ubiquitous in the field of scientific computing, machine learning, statistics,
etc. with matrix computations being fundamental to these linear algebra based solutions.
Design of multiple dense (or sparse) matrix computation routines on the
same platform is quite challenging. Added to the complexity is the fact that dense
and sparse matrix computations have large differences in their storage and access
patterns and are difficult to optimize on the same architecture. This thesis addresses
this challenge and introduces a reconfigurable accelerator that supports both dense
and sparse matrix computations efficiently.
The reconfigurable architecture has been optimized to execute the following linear
algebra routines: GEMV (Dense General Matrix Vector Multiplication), GEMM
(Dense General Matrix Matrix Multiplication), TRSM (Triangular Matrix Solver),
LU Decomposition, Matrix Inverse, SpMV (Sparse Matrix Vector Multiplication),
SpMM (Sparse Matrix Matrix Multiplication). It is a multicore architecture where
each core consists of a 2D array of processing elements (PE).
The 2D array of PEs is of size 4x4 and is scheduled to perform 4x4 sized matrix
updates efficiently. A sequence of such updates is used to solve a larger problem inside
a core. A novel partitioned block compressed sparse data structure (PBCSC/PBCSR)
is used to perform sparse kernel updates. Scalable partitioning and mapping schemes
are presented that map input matrices of any given size to the multicore architecture.
Design trade-offs related to the PE array dimension, size of local memory inside a core
and the bandwidth between on-chip memories and the cores have been presented. An
optimal core configuration is developed from this analysis. Synthesis results using a 7nm PDK show that the proposed accelerator can achieve a performance of upto
32 GOPS using a single core.
ContributorsAnimesh, Saurabh (Author) / Chakrabarti, Chaitali (Thesis advisor) / Brunhaver, John (Committee member) / Ren, Fengbo (Committee member) / Arizona State University (Publisher)
Created2018
Description
The extent of students’ struggles in linear algebra courses is at times surprising to mathematicians and instructors. To gain insight into the challenges, the central question I investigated for this project was: What is the nature of undergraduate students’ conceptions of multiple analytic representations of systems (of equations)?
My methodological choices for this study included the use of one-on-one, task-based clinical interviews which were video and audio recorded. Participants were chosen on the basis of selection criteria applied to a pool of volunteers from junior-level applied linear algebra classes. I conducted both generative and convergent analyses in terms of Clement’s (2000) continuum of research purposes. The generative analysis involved an exploration of the data (in transcript form). The convergent analysis involved the analysis of two student interviews through the lenses of Duval’s (1997, 2006, 2017) Theory of Semiotic Representation Registers and a theory I propose, the Theory of Quantitative Systems.
All participants concluded that for the four representations in this study, the notation was varying while the solution was invariant. Their descriptions of what was represented by the various representations fell into distinct categories. Further, the students employed visual techniques, heuristics, metaphors, and mathematical computation to account for translations between the various representations.
Theoretically, I lay out some constructs that may help with awareness of the complexity in linear algebra. While there are many rich concepts in linear algebra, challenges may stem from less-than-robust communication. Further, mathematics at the level of linear algebra requires a much broader perspective than that of the ordinary algebra of real numbers. Empirically, my results and findings provide important insights into students’ conceptions. The study revealed that students consider and/or can have their interest piqued by such things as changes in register.
The lens I propose along with the empirical findings should stimulate conversations that result in linear algebra courses most beneficial to students. This is especially important since students who encounter undue difficulties may alter their intended plans of study, plans which would lead them into careers in STEM (Science, Technology, Engineering, & Mathematics) fields.
My methodological choices for this study included the use of one-on-one, task-based clinical interviews which were video and audio recorded. Participants were chosen on the basis of selection criteria applied to a pool of volunteers from junior-level applied linear algebra classes. I conducted both generative and convergent analyses in terms of Clement’s (2000) continuum of research purposes. The generative analysis involved an exploration of the data (in transcript form). The convergent analysis involved the analysis of two student interviews through the lenses of Duval’s (1997, 2006, 2017) Theory of Semiotic Representation Registers and a theory I propose, the Theory of Quantitative Systems.
All participants concluded that for the four representations in this study, the notation was varying while the solution was invariant. Their descriptions of what was represented by the various representations fell into distinct categories. Further, the students employed visual techniques, heuristics, metaphors, and mathematical computation to account for translations between the various representations.
Theoretically, I lay out some constructs that may help with awareness of the complexity in linear algebra. While there are many rich concepts in linear algebra, challenges may stem from less-than-robust communication. Further, mathematics at the level of linear algebra requires a much broader perspective than that of the ordinary algebra of real numbers. Empirically, my results and findings provide important insights into students’ conceptions. The study revealed that students consider and/or can have their interest piqued by such things as changes in register.
The lens I propose along with the empirical findings should stimulate conversations that result in linear algebra courses most beneficial to students. This is especially important since students who encounter undue difficulties may alter their intended plans of study, plans which would lead them into careers in STEM (Science, Technology, Engineering, & Mathematics) fields.
ContributorsSipes, Janet (Author) / Zandieh, Michelle J (Thesis advisor) / Milner, Fabio A (Committee member) / Roh, Kyeong H (Committee member) / Wawro, Megan (Committee member) / Zazkis, Dov (Committee member) / Arizona State University (Publisher)
Created2019
Description
Dimensionality reduction methods are examined for large-scale discrete problems, specifically for the solution of three-dimensional geophysics problems: the inversion of gravity and magnetic data. The matrices for the associated forward problems have beneficial structure for each depth layer of the volume domain, under mild assumptions, which facilitates the use of the two dimensional fast Fourier transform for evaluating forward and transpose matrix operations, providing considerable savings in both computational costs and storage requirements. Application of this approach for the magnetic problem is new in the geophysics literature. Further, the approach is extended for padded volume domains.
Stabilized inversion is obtained efficiently by applying novel randomization techniques within each update of the iteratively reweighted scheme. For a general rectangular linear system, a randomization technique combined with preconditioning is introduced and investigated. This is shown to provide well-conditioned inversion, stabilized through truncation. Applying this approach, while implementing matrix operations using the two dimensional fast Fourier transform, yields computationally effective inversion, in memory and cost. Validation is provided via synthetic data sets, and the approach is contrasted with the well-known LSRN algorithm when applied to these data sets. The results demonstrate a significant reduction in computational cost with the new algorithm. Further, this new algorithm produces results for inversion of real magnetic data consistent with those provided in literature.
Typically, the iteratively reweighted least squares algorithm depends on a standard Tikhonov formulation. Here, this is solved using both a randomized singular value de- composition and the iterative LSQR Krylov algorithm. The results demonstrate that the new algorithm is competitive with these approaches and offers the advantage that no regularization parameter needs to be found at each outer iteration.
Given its efficiency, investigating the new algorithm for the joint inversion of these data sets may be fruitful. Initial research on joint inversion using the two dimensional fast Fourier transform has recently been submitted and provides the basis for future work. Several alternative directions for dimensionality reduction are also discussed, including iteratively applying an approximate pseudo-inverse and obtaining an approximate Kronecker product decomposition via randomization for a general matrix. These are also topics for future consideration.
Stabilized inversion is obtained efficiently by applying novel randomization techniques within each update of the iteratively reweighted scheme. For a general rectangular linear system, a randomization technique combined with preconditioning is introduced and investigated. This is shown to provide well-conditioned inversion, stabilized through truncation. Applying this approach, while implementing matrix operations using the two dimensional fast Fourier transform, yields computationally effective inversion, in memory and cost. Validation is provided via synthetic data sets, and the approach is contrasted with the well-known LSRN algorithm when applied to these data sets. The results demonstrate a significant reduction in computational cost with the new algorithm. Further, this new algorithm produces results for inversion of real magnetic data consistent with those provided in literature.
Typically, the iteratively reweighted least squares algorithm depends on a standard Tikhonov formulation. Here, this is solved using both a randomized singular value de- composition and the iterative LSQR Krylov algorithm. The results demonstrate that the new algorithm is competitive with these approaches and offers the advantage that no regularization parameter needs to be found at each outer iteration.
Given its efficiency, investigating the new algorithm for the joint inversion of these data sets may be fruitful. Initial research on joint inversion using the two dimensional fast Fourier transform has recently been submitted and provides the basis for future work. Several alternative directions for dimensionality reduction are also discussed, including iteratively applying an approximate pseudo-inverse and obtaining an approximate Kronecker product decomposition via randomization for a general matrix. These are also topics for future consideration.
ContributorsHogue, Jarom David (Author) / Renaut, Rosemary A. (Thesis advisor) / Jackiewicz, Zdzislaw (Committee member) / Platte, Rodrigo B (Committee member) / Ringhofer, Christian (Committee member) / Wlefert, Bruno (Committee member) / Arizona State University (Publisher)
Created2020