AMI-The language and its implementation

Abstract

Automatic translation of sequential programs to parallel programs which can reasonably exploit distributed memory machines is very difficult and not well-understood. Programming with communication-based statements is very tedious and is often compared with assembly language programming of sequential machines. This thesis attempts an approach which combines advantages of explicitly parallel programming and programming with high-level constructs. We lay emphasis on distributed programming with distributed dynamic data structures. We propose a new programming language AMI. In this thesis, we describe the language and its implementation on a 64-processor PARAM system. The following are the problems faced by a programmer when using dynamic data structures in distributed programs:

Keeping track of distributed pointers, and consistency of distributed dynamic data structures is very difficult for the programmer (if not impossible). All the synchronization and memory allocation/deallocation required for dynamic data structures has to be done explicitly by the programmer, and this is very tedious and error-prone. Optimizations in packing and unpacking data structures during migration cannot be easily taken care of if done explicitly by the programmer. The code taking care of issues in (1) and (2) becomes very huge and unmanageable for debugging and testing. A typical application requires up to 10 times the code that is written in AMI, if programmed with explicit synchronization, etc.

The advantages in using AMI for programming with distributed dynamic data structures are similar to the ones experienced in using a language such as HPF for programming with distributed arrays. The following are the salient features of AMI:

No explicit communication statements; all communications are handled by the runtime system. Unit of data handled is a packet. Packets can be distributed to processors and linked to form dynamic data structures. Packets can be processed in parallel and distributed pointers to other packets are transparent to the programmer. Packets can be allocated and freed dynamically, and in parallel in the processors. Packets can be moved from one processor to another. Packets can be accessed from a process running in any processor. The mechanism to do so is with very simple notation. The notation resembles pointer access. Functions can be accessed with packets and called from other processors to operate on the packet owned by a different processor. Facilities to declare a set of parallel processes (called a platoon), synchronize a platoon, and declare events are provided in AMI.

We have designed and developed a compiler and a runtime system to support AMI programs. This is implemented on a 64-processor distributed memory multiprocessor called PARAM (ACDAC product).