Performance Aspects of Parallel Multigrid Methods

U. Rüde ^{∗}

April 17, 1996

Abstract

Parallel computers are usually defined as machines having several different processing units (CPUs). However, parallel execution is much more common, since each single modern CPU is internally a parallel processor having multiple execution units and/or making extensive use of pipelining. Typical current microprocessor designs (as used in PCs as well as parallel computers) have two or four execution units each operating with 5–9 pipeline stages, so that to exploit such a processor fully, something like 20 or more elementary operations must be executed in parallel at each time. This instruction level parallelism is usually not used explicitly since the compiler can — in principle — automatically generate the necessary machine instructions. Despite this, many numerical programs exploit the CPU internal parallelism only very poorly. A closer look reveals that in many applications the bottleneck is increasingly memory access, not the CPU speed. This is especially true for many iterative solvers, including multigrid and related methods. Thus the compute time is more determined by memory latency and bandwidth than by CPU speed, and by how well it is possible to exploit a hierarchical memory design using several layers of cache and virtual shared memory. These issues will be discussed from the perspective of multigrid and iterative algorithms.

∗Institut für Mathematik, Universität Augsburg, D-86159 Augsburg, Germany, e-mail:

ruede@informatik.tu-muenchen.de