ERCIM News No.35 - October 1998
The Coordination Language Manifold
by Farhad Arbab
The proper functioning of many of todays applications depends on the mutual cooperation and interaction of (one or more) computers and human users. Special coordination languages have been designed, in which one can specify, analyze and control the cooperation between the various system components. An important application of such languages is in the parallelization of computation intensive sequential programs. Experimental research on coordination started at CWI in 1990. The major result of these efforts so far has been the development of the coordination language MANIFOLD, based on a novel model for control-oriented coordination (IWIM). The language has found several licensees in Europe as well as the USA.
Computers nowadays do much more than mere computing. They also act as facilitators, mediators, and coordinators enabling the collaboration of other computers (or computer programs), sensors and actuators that involve their real world environment, or human beings. This requires computers to interact with these agents, as expressed in the concept of Interaction Machine, proposed by P. Wegner in 1995. An Interaction Machine is an extension of a Turing Machine that can interact with its environment with new input and output primitive actions. Interaction Machines can represent the behaviour of many interesting real systems.
The goal of coordination is to manage the interaction among concurrent programs. Analogous to the way in which topology abstracts away the metric details of geometry and focuses on the invariant properties of (seemingly very different) shapes, coordination abstracts away the details of computation in Interaction Machines, and focuses on the invariant properties of (seemingly very different) programs. As such, coordination focuses on program patterns that specifically deal with interaction.
Coordination is relevant in the design, development, debugging, maintenance, and reuse of all concurrent systems. The primary concern in the design of a concurrent application must be how its various active entities are to cooperate with each other. A number of software platforms and libraries are presently popular for easing the development of concurrent applications. Such systems, eg, PVM, MPI, CORBA, etc., are sometimes called middleware. Coordination languages can be thought of as their linguistic counterpart.
The coordination language MANIFOLD, developed at CWI during the 1990s, is a control-oriented language, directed to aspects such as processing or the flow of control, rather than large-scale data handling, and is suited to, eg, applications involving work-flow in organizations, or multi-phase applications where the content, format, and/or modality of information substantially changes from one phase to the next. Its primitives support coordination of entities from without, so that the coordination modules are separated from the computation modules and, hence, can be reused in other applications. For example, the same MANIFOLD coordinator program that was developed for a parallel/distributed bucket sort algorithm, was used at CWI in a quite different research field to perform function evaluation and numerical optimization using domain decomposition. MANIFOLD manages complex, dynamically changing inter-connections among sets of independent, concurrent, cooperating processes.
Whereas computation processes can be written in any conventional programming language, coordinator processes are written in the MANIFOLD language. The language is based on the IWIM model (Idealized Worker Idealized Manager), which is a generic, abstract communication model that separates computation (worker) from communication and cooperation (manager) modules.
MANIFOLD is a strongly-typed, block-structured, event-driven language, in which, semantically, there is no need for computational entities or constructs like integers, floats, strings, arithmetic expressions, sequential composition, conditional statements, loops, etc. MANIFOLD only recognizes processes, ports, events, and streams (which are asynchronous channels), and its only control structure is an event-driven state transition mechanism. Programming in MANIFOLD is a game of dynamically creating process instances and (re)connecting the ports of some processes via streams, in reaction to observed event occurrences. Any coordinator process can also be used as a meta-coordinator, to build a sophisticated hierarchy of coordination protocols. Such higher-level coordinators are not possible in most other coordination languages and models.
MANIFOLDs coordination modules construct and maintain a dynamic data-flow graph where each node is a process. These modules only change the graph topology, by changing the connections among various processes in the application. The computation modules cannot possibly change the graph topology. This separation makes both sets of modules easier to verify and more reusable.
The MANIFOLD system runs on multiple platforms and consists of a compiler, a run-time system library, a number of utility programs, and libraries of built-in and predefined processes of general interest. Presently, it runs on IBM RS6000 AIX, IBM SP1/2, Solaris, Linux, Cray, and SGI IRIX. A MANIFOLD application consists of a (potentially very large) number of processes running on a network of heterogeneous hosts, some of which may be parallel systems. Processes in the same application may be written in different programming languages and some of them may not know anything about MANIFOLD, nor the fact that they are cooperating with other processes through MANIFOLD in a concurrent application.
MANIFOLD has been successfully used at CWI to implement parallel and distributed versions of a semi-coarsened multi-grid Euler solver algorithm. This represents a real-life heavy-duty Computational Fluid Dynamics application where MANIFOLD enabled restructuring of existing sequential Fortran code using pure coordination protocols that allow it to run on parallel and distributed platforms. The results of this work are very favourable: no modification to the computational Fortran 77 code, simple, small, reusable MANIFOLD coordination modules, and linear speed-up of total execution time with respect to the number of processors (eg, from almost 9 to over 2 hours). Other applications of MANIFOLD include its use in modelling cooperative information systems, coordination of loosely-coupled genetic algorithms on parallel and distributed platforms, coordination of multiple solvers in a concurrent constraint programming system, and a distributed propositional theorem checker.
Information on the web at:
- http://wwwdbs.cwi.nl/cwwwi/owa/cwwwi.print_projects?ID=57, and ID=58
Farhad Arbab - CWI
Tel: +31 20 592 4056