Cache-aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions

Beitrag in einer Fachzeitschrift


Details zur Publikation

Autor(en): Weiß C, Kowarschik M, Rüde U, Wolfgang K
Zeitschrift: Computing
Verlag: Springer Verlag (Germany)
Jahr der Veröffentlichung: 2000
Band: 64
Heftnummer: 4
Seitenbereich: 381-399
ISSN: 0010-485X


Abstract

Conventional implementations of iterative numerical algorithms, especially multigrid methods, merely reach a disappointing small percentage of the theoretically available CPU performance when applied to representative large problems. One of the most important reasons for this phenomenon is that the need for data locality due to poor main memory latency and limited bandwidth is entirely neglected by many developers designing numerical software. Only when most of the data to be accessed during the computation arc found in the system cache (or in one of the caches if the machine architecture comprises a cache hierarchy) fast program execution can be expected. Otherwise, i.e. in case of a significant rate of cache misses, the processor must stay idle until the necessary operands are fetched from main memory, whose cycle time is in general extremely large compared to the time needed to execute a floating point instruction. In this paper, we describe program transformation techniques developed to improve the cache performance of two-dimensional multigrid algorithms. Although we merely consider the solution of Poisson's equation on the unit square using structured grids, our techniques provide valuable hints towards the efficient treatment of more general problems.


FAU-Autoren / FAU-Herausgeber

Rüde, Ulrich Prof. Dr.
Lehrstuhl für Informatik 10 (Systemsimulation)


Zitierweisen

APA:
Weiß, C., Kowarschik, M., Rüde, U., & Wolfgang, K. (2000). Cache-aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions. Computing, 64(4), 381-399.

MLA:
Weiß, Christian, et al. "Cache-aware Multigrid Methods for Solving Poisson's Equation in Two Dimensions." Computing 64.4 (2000): 381-399.

BibTeX: 

Zuletzt aktualisiert 2018-19-09 um 14:38