Supporting fine-grain computation on distributed memory parallel computers
David Socha · 1991
This dissertation addresses the issues of efficiently programming distributed memory parallel computers. In particular, it concentrates on the language, compiler and data partitioning support needed to easily program efficient solutions to data parallel applications such as iterative numerical solution techniques (finite difference equations), recurrence equations and many imaging processing applications. We introduce a language model that is close to this application domain and that allows the programmer to easily express these algorithms without worrying about the implementation details associated with distributed memory, communication, scalability and portability. We also introduce compiler techniques to efficiently implement this language model on distributed memory parallel computers and show that it performs well. The same techniques can be used to execute sets of recurrence equations that have been compiled into systolic arrays. This is the first such implementation of systolic arrays for general purpose distributed memory parallel computers. The central data structure for these applications is a regular two-dimensional grid of points usually corresponding to some physical space. This dissertation discusses the importance and difficulties of finding good mappings of these points to the memories of the processing elements (PEs) of the distributed memory parallel computer. An allocation refers to the points mapped to a single PE. We introduce a new mapping algorithm that improves upon previous algorithms by balancing the load among the PEs, when each allocation is greater than about 2 $\times$ 10 points, and by positioning adjacent allocations so that a PE has to communicate with fewer other PEs (at most six) for many important applications.