Withdraw
Loading…
The Impact of Hierarchical Memory Systems on Linear Algebra Algorithm Design
Gallivan, Kyle; Jalby, William; Meier, Ulrike; Sameh, Ahmed
Loading…
Permalink
https://hdl.handle.net/2142/126870
Description
- Title
- The Impact of Hierarchical Memory Systems on Linear Algebra Algorithm Design
- Author(s)
- Gallivan, Kyle
- Jalby, William
- Meier, Ulrike
- Sameh, Ahmed
- Issue Date
- 1987-09-14
- Keyword(s)
- Algorithms, applications, performance-evaluation
- Date of Ingest
- 2025-03-25T14:56:31-05:00
- Abstract
- Linear algebra algorithms based on the BLAS or extended BLAS are not able to achieve high performance on multivector processors with a hierarchical memory system due to a lack of data locality. For such machines, it is necessary to implement ‘block’ linear algebra algorithms in terms of matrix-matrix primitives (BLAS3). The design of efficient linear algebra algorithms for these architectures requires an analysis of the behavior of the matrix-matrix primitives and the resulting block algorithms as a function of certain system parameters (cache size, number of processors…). It is particularly crucial that the analysis of this behavior identifies the limits of performance improvement possible via blocking and any contradictory trends that require tradeoff consideration. Ideally, the analysis should also yield insight into techniques a compiler could use to automatically restructure code to improve performance on systems with hierarchical memories. In this paper, a methodology which facilitates such an analysis is proposed and used to analyze the performance behavior of the BLAS3 primitives used in block methods. A similar analysis of the blocksize/performance relationship is also performed at the algorithm level for block versions of the LU decomposition and the Gram-Schmidt orthogonalization procedures.
- Publisher
- Center for Supercomputing Research and Development, University of Illinois at Urbana-Champaign
- Series/Report Name or Number
- CSRD-625
- Type of Resource
- text
- Genre of Resource
- article
- technical report
- Language
- eng
- Sponsor(s)/Grant Number(s)
- NSF DCR84-10110; NSF DCR85-09970; DOE DE-FG02- 85ER25001; AFOSR-85-0211;
Owning Collections
Manage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…