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
