HIGH-PERFORMANCE FORTRAN FOR HIGHLY IRREGULAR PROBLEMS

We present a general data parallel formulation for highly irregular pr oblems in High Performance Fortran (HPF). Our formulation consists of (1) a method for linearizing irregular data structures (2) a data para llel implementation (in HPF) of graph partitioning algorithms applied to the linearized data structure, (3) techniques for expressing irregu lar communication and nonuniform computations associated with the elem ents of linearized data structures. We demonstrate and evaluate our fo rmulation on a parallel, hierarchical N-body method for the evaluation of potentials and forces of nonuniform particle distributions. Our ex perimental results demonstrate that efficient data parallel (HPF) impl ementations of highly nonuniform problems are feasible with the proper language/compiler/runtime support. Our data parallel N-body code prov ides a much needed ''benchmark'' code for evaluating and improving HPF compilers.