A runtime data mapping scheme for irregular problems

Abstract

In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. In this paper, the authors study the problem of automatically choosing data distributions for irregular problems. Irregular problems are programs where the data access pattern cannot be determined during compilation. The authors describe a method by which data arrays can be automatically mapped at runtime. The mapping is based on the computational patterns in one or more user-specified loops. A distributed memory compiler generates code that, at runtime, generates a distributed data structure to represent the computational pattern of the chosen loop. This computational pattern is used to determine how data arrays are to be partitioned. The compiler generates code to pass the distributed data structure to a partitioner. The work described is being pursued in the context of the CRPC Fortran D project.