ERCIM News No.36 - January 1999
ERCIM News No.36 - January 1999
Using Co-ordination to Parallelize Existing Sequential Programs
by Farhad Arbab, Kees Everaars and Barry Koren
The co-ordination language MANIFOLD, developed during the 1990s at CWI, has important applications in the parallelization of computation intensive sequential programs. The language is based on a novel model for control-oriented coordination (IWIM).
Programming in MANIFOLD (see ERCIM News 35, page 33) is a game of dynamically creating process instances and (re)connecting the ports of some processes via streams (asynchronous channels), in reaction to observed event occurrences. This style reflects the way one programmer might discuss his interprocess communication application with another programmer by telephone (let process a connect process b with process c so that c can get its input; when process b receives event e, broadcast by process c, react on that by doing this and that; etc.).
As is already clear from this phone call, processes in MANIFOLD do not explicitly send a message to or receive a message from another process. Processes in MANIFOLD are treated as black-box workers that can only read or write through the openings (called ports) in their own bounding walls. Always a third party - a coordinator process called ‘manager’? - is responsible for setting up the communication channel between the output port of one process and the input port of another process, so that data can flow through it.
This setting up of the communication from the outside is very typical for MANIFOLD and has several advantages. An important advantage is that it results in a clear separation between the modules responsible for computation and those responsible for co-ordination, and therefore also strengthens the modularity and enhances the re-usability of both types of modules.
MANIFOLD has been successfully used at CWI to restructure a sequential existing implementation of a real-life heavy-duty Computational Fluid Dynamics application (with a semi-coarsened multi-grid Euler solver algorithm). The sequential version of this software was created in the framework of contract research financed by the European Union (BRITE/EURAM). For the restructuring of the sequential application into a parallel application we used a master/worker protocol implemented in MANIFOLD.
The idea is simple. In a coordinator process we create and activate a master process that embodies the computations of the main program of the sequential version. When we arrive in the ‘master’? at some work that could be parallelized (in our case the pre- or post-relaxation on the different grids), the master does not perform these computations itself but delegates it to a number of ‘worker’? processes. Each time the master needs a worker to delegate some work to, it raises an event to signal the coordinator to create a worker. In this way a pool of workers is working for the master, each worker performing pre- or post-relaxation.
When the workers have finished their relaxations (this creates a synchronization point in the application), the master proceeds its sequential work until it again arrives at a point where it wants to use a pool of workers to delegate the relaxations to. The Figure shows the dynamically created pools of workers during a semi-sparse multigrid run. Here we can see for example that for level 6 there are 268 pools of workers created, in which a total of 1838 (ie, the total of the heights in this histogram) workers did their relaxation work. In the sparse-grid-of-grids approach this simple master/worker implemented in MANIFOLD was able to improve the execution time from almost 9 to over 2 hours on a 4-processor machine.
The modularity of MANIFOLD also enables the introduction of concurrency step by step. We can therefore proceed as follows. We initially plug a block of code as a monolithic computing process into a concurrent structure, in order to obtain a running parallel/distributed application. As more experience is gained through running the new application, computation bottlenecks may be identified. This may lead to replacing some such monolithic blocks of code with more MANIFOLD modules that coordinate the activity of smaller blocks of computation code, in a new concurrent sub-structure.
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.
For more information, see website http://dbs.cwi.nl/cwwwi/owa/cwwwi.print_projects?ID=57, and http://dbs.cwi.nl/cwwwi/owa/cwwwi.print_projects?ID=58.Please contact:
Farhad Arbab, Kees Everaars (MANIFOLD) and Barry Koren (CFD) - CWI
Tel: +31 20 592 4056
E-mail: {Farhad.Arbab, Kees.Everaars, Barry.Koren}@cwi.nl