Abstract Level Parallelization of Finite Difference Methods

Article type: Research Article

Authors: Vollebregt, Edwin

Affiliations: Faculty of Technical Mathematics and Informatics, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands; tel: +31‐15 278 58 05; fax: +31‐15 278 72 09; e‐mail: edwin@pa.twi.tudelft.nl

Abstract: A formalism is proposed for describing finite difference calculations in an abstract way. The formalism consists of index sets and stencils, for characterizing the structure of sets of data items and interactions between data items (“neighbouring relations”). The formalism provides a means for lifting programming to a more abstract level. This simplifies the tasks of performance analysis and verification of correctness, and opens the way for automatic code generation. The notation is particularly useful in parallelization, for the systematic construction of parallel programs in a process/channel programming paradigm (e.g., message passing). This is important because message passing, unfortunately, still is the only approach that leads to acceptable performance for many more unstructured or irregular problems on parallel computers that have non‐uniform memory access times. It will be shown that the use of index sets and stencils greatly simplifies the determination of which data must be exchanged between different computing processes.

Journal: Scientific Programming, vol. 6, no. 4, pp. 331-344, 1997