| Multicomputers, such as the Intel Paragon and the IBM SP-2 offer significant advantages over shared-memory multiprocessors in terms of cost and scalability. However, due to the absence of a uniform global address space, they are a very difficult programming model in which the user has to decide how data and computation are to be partitioned across processors, and to specify how to transfer those sections of data among processors. To overcome this difficulty, significant research effort has been aimed at source-to-source parallelizing compilers for multicomputers that relieve the programmer from the task of program partitioning and communication generation.;Compiling for distributed memory requires efficient ways to describe data and iterations that are partitioned across processors. Previous work in this area has used descriptors that do not include processor information. Thus, when the resulting partitions have different sizes and/or shapes, a separate descriptor is used for each case, leading to inefficient multiversion code. In this dissertation, we present a new descriptor that is parameterized by processor coordinates and show how it is used to compile efficiently for BLOCK distributions. For the more general CYCLIC(k) distributions, most current research efforts concentrate on the special case of array expressions using enumeration techniques. Unfortunately, these techniques are not applicable to general DO loops. To compile for the most general case, the work in this dissertation uses techniques based on Fourier-Motzkin elimination. Therefore, by using the former technique to compile efficiently for the simplest and most frequent cases, and the latter to cover the difficult, general cases, we are able to handle a large range of programs.;These techniques have been implemented as part of the PARADIGM project at the University of Illinois. The complete system aims at providing an automated means to parallelize sequential programs to obtain high performance on a wide variety of multicomputers. |
