The Impact of Hierarchical Memory Systems on Linear Algebra Algorithm Design

Gallivan, Kyle; Jalby, William; Meier, Ulrike; Sameh, Ahmed

Permalink

https://hdl.handle.net/2142/126870 Copy

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