The design and implementation of a runtime system for graph-oriented parallel and distributed programming

Graph has been widely used in modeling, specification, and design of parallel and distributed systems. Many parallel and distributed programs can be expressed as a collection of parallel functional modules whose relationships can be defined by a graph. Often, the basic functions of communication and coordination of the parallel modules are expressed in terms of the underlying graph. Furthermore, parallel/distributed graph algorithms are used to realize various control functions. To facilitate the implementation of these algorithms, it is desirable to have an integrated approach that provides direct support for efficient operations on graphs. We have proposed a graph-oriented programming model, called GOP, which aims at providing high-level abstractions for configuring and programming cooperative parallel processes. GOP enables the programmer to configure the logical structure of a distributed program by using a logical graph and to write the program using communications and synchronization primitives based on the logical structure. In this paper, we describe the design and implementation of a portable run-time system for the GOP framework. The runtime system provides an interface with a library of programming primitives to the low-level facilities required to support graph-oriented communications and synchronization. The implementation is on top of the parallel virtual machine in a local area network of Sun workstations. We focus our discussion on the following four aspects: the software architecture, including the structure of runtime system and interfaces between user programs and the runtime kernel; graph representation; implementation of graph operations; and performance of the run-time in terms of the implementation of graph-oriented communications.