High performance Fortran for highly irregular problems
Authors:
Open Access
- 21 June 1997
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 32 (7) , 13-24
Abstract
We present a general data parallel formulation for highly irregular problems in High Performance Fortran (HPF). Our formulation consists of(1) a method for linearizing irregular data structures (2) a data parallel implementation (in HPF) of graph partitioning algorithms applied to the linearized data structure, (3) techniques for expressing irregular communication and nonuniform computations associated with the elements of linearized data structures.We demonstrate and evaluate our formulation on a parallel, hierarchical N--body method for the evaluation of potentials and forces of nonuniform particle distributions. Our experimental results demonstrate that efficient data parallel (HPF) implementations of highly nonuniform problems are feasible with the proper language/compiler/runtime support. Our data parallel N--body code provides a much needed "benchmark" code for evaluating and improving HPF compilers.Keywords
This publication has 16 references indexed in Scilit:
- Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body SimulationSIAM Journal on Scientific Computing, 1998
- A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fieldsJournal of the ACM, 1995
- An efficient communications strategy for finite element methods on the Connection Machine CM-5 systemComputer Methods in Applied Mechanics and Engineering, 1994
- An Implementation of the Fast Multipole Method without MultipolesSIAM Journal on Scientific and Statistical Computing, 1992
- The order of Appel's algorithmInformation Processing Letters, 1992
- Normalized Convergence Rates for the PSMG MethodSIAM Journal on Scientific and Statistical Computing, 1991
- Partitioning Sparse Matrices with Eigenvectors of GraphsSIAM Journal on Matrix Analysis and Applications, 1990
- Compiling collection-oriented languages onto massively parallel computersJournal of Parallel and Distributed Computing, 1990
- A Fast Adaptive Multipole Algorithm for Particle SimulationsSIAM Journal on Scientific and Statistical Computing, 1988
- A hierarchical O(N log N) force-calculation algorithmNature, 1986