Automatic data partitioning for a parallel language

Parallel computing hardware is affordable and accessible, yet parallel programming is not as widespread as one would expect. It is generally accepted that the difficulty lies with current parallel programming languages. This thesis is directed to the goal of making parallel computation easily accessible to a fairly large segment of the scientific community without sacrificing performance. The central contribution is the demonstration that a language and a compiler can be developed which satisfy this goal. The problem domain addressed herein is the class of simulation problems which are statically decomposed, have communication localized to a fixed neighborhood, and have time incremented synchronously after all cells are updated. This language, called Em, both restricts and simplifies the programming interface, and thereby eases the conceptual task of the programmer as well as the analytical task of the compiler. The analytical task of the compiler is to generate an efficient parallel implementation by optimizing the iterative calculations and by optimally partitioning the data across processors. Since the former is well understood, this thesis focuses on automatically generating a Cartesian partition of an n-dimensional, discrete Cartesian space over a given number of processors. The automatic partitioning algorithm has the following advantages: multiple data arrays of any dimension $k \leq n$ are partitioned over one grid; stencils are generalized: neighborhoods are arbitrary, and symmetry is not required; and, different stencils, different data, and different computation loads may exist in different grid positions. The data for the cost model that drives the automatic partitioning is derived from the Em program. Optimization is achieved using simulated annealing