Techniques for improving the data locality of iterative methods

Research Report MRR97-038

Techniques for improving the data locality of iterative methods

Linda Stals, Ulrich Rüde

Abstract: The numerical solution of partial differential equations leads to large, sparse systems of equations with up a several millions of unknowns. Fast iterative algorithms for the solution of these systems are typically based on the multilevel principle. Unfortunately, some of the commonly used programming techniques lead to a high overhead on many advanced computer architectures. A fundamental problem arises from hierarchical memory architectures with several layers of caches. Their effective use requires programs with data access locality. Unfortunately, iterative solvers are typically implemented by using global sweeps over the whole data set, and thus their performance is essentially limited by the speed of the memory system. This article introduces techniques to improve the data locality and therefore the efficiency of multigrid algorithms.

This service is maintained by the Mathematical Sciences Institute (MSI)
Comments to webmaster@maths.anu.edu.au URL: http://wwwmaths.anu.edu.au/