Implementation of data distribution and parallelism in HPF

Abstract

Translation of sequential data-parallel programs to SPMD programs for Distributed Memory Machines requires distribution of data and computation across processors. Many data-parallel languages allow users to express distribution of data and computation. High Performance Fortran (HPF) is an extension to FORTRAN for expressing data and control parallelism. HPF 1.0 (1993) supports regular data distribution, i.e., block, cyclic, and block-cyclic. For some programs, a "good" data distribution is non-regular. Vienna Fortran, Fortran D, and more recently HPF 2.0 (1997) support dynamic irregular distributions based on user-provided mapping functions. However, obtaining these mapping functions is a difficult task. This work describes the use of profiling data access patterns of arrays to choose a "good" (not necessarily optimal) distribution for arrays within a loop nest. This is done by partitioning an array of dimension n into n-dimensional data cubes that are distributed among available processors. We introduce a term "semi-regular(c)" data distribution to describe static or dynamic data distribution for which the granularity of distribution is a data cube of size c^d, i.e., a d-dimensional cube of edge-length c. We have implemented the parallelizing components of a compiler using the SUIF compiler system, which accepts a program written in Fortran77 with HPF data distribution and do-independent directives. The output source is an SPMD C program with message-passing routines. We extract semi-regular data partitions and show improvement over HPF regular distributions.