zenith@ensmp.fr (Steven Ericsson Zenith) (02/01/91)
--- oO0Oo ---
Parallel programming with Ease
- A brief description of the model -
January 1991
Steven Ericsson Zenith
Chef du projet - Projet Ease
Center for Research in Computer Science - Centre de Recherche en Informatique
CRI - Ecole Nationale Superieure des Mines de Paris
--- oO0Oo ---
Copyright 1990, Steven Ericsson Zenith
Permission is granted to make verbatim copies of this text provided the
copyright notice and this permission notice is preserved on all copies.
--- oO0Oo ---
*Introduction - programming with efficiency and Ease*
Ease is a simple new model for parallel and distributed programming.
An Ease program is described as a collection of processes which execute
concurrently, constructing and interacting via strictly typed shared
data structures called "contexts".
Ease is simpler and more efficient to use than than either generalized
message passing or Linda.
Message passing has proven to be a difficult addendum to conventional
programming practices, since it compels the programmer to be concerned
about issues of data distribution. Further, experience reveals that
managing that distribution of data incurs performance overheads (in the
form of repeated copying of the same data) which are difficult to keep
track of in large programs. The apparent simplicity of the message
model hides subtle complexities.
The Linda model at first appears to provide an elegant high level
solution to the data distribution issue. It has a rich expressive power
which arises from its greater abstraction. However, performance of real
Linda programs is difficult to predict. Linda programming is heavily
dependent on program optimization, so much so that it leads programmers
to develop techniques and conventions founded on an understanding of the
behavior of a particular optimizer or underlying matching protocol.
Linda programs written in this way possess hidden performance semantics
(see my earlier notes).
Implementation of the Ease model provides greater efficiency than either
generalized message passing or Linda. This efficiency is due to the
reduced number of copy operations required to implement data exchange.
This reduces the total load on the machine i.e. generally on both the
computation unit and the memory subsystem.
Copy operations are prevalent in generalized message passing and Linda
models, and are very often the cause of reduced efficiency on parallel
machines. In Ease the copying of data can be limited to data movements
between disjoint memory spaces.
The model is independent of machine memory architecture, yet is
efficient when compiled for either shared or distributed memory
machines.
Ease provides simple and symmetric operators (read and write, get and put).
Provides constructions for both cooperative and subordinate concurrency
and a mechanism (combinations) for building statically reusable and virtual
resources on parallel and distributed machines.
The examples in this note use the syntax of C-with-Ease and not pure
Ease. The Ease keywords which appear in C programs begin with an "escape"
character (generally %) to distinguish them from the names used in the
standard C function library - see the example at the end. It is not the
purpose of this note to present the full definition of C-with-Ease, and
there are several aspects of that definition not presented here.
*Contexts - shared data structures*
A "context" is a shared data structure. The simplest context is
SHARE type name
For example, the C-with-Ease statement
%share int bag ;
creates a "bag", named "bag", which is an unordered set of integers.
That is, integers placed in this "bag" can be read and retrieved but the
order of the values returned cannot be determined by the order in which
they where placed in the bag.
A more ordered data structure can be constructed. The context
SHARE STREAM type name
orders the data values in the context such that values read or retrieved
will be those least recently placed in the context. So, if only two
processes are involved, one producer and one consumer, values consumed
will be strictly in the order the values were produced. Where there are
many consumers a value consumed will be one of the least recently
produced. That is, a stream will not offer a process a value produced
before any other value in the stream.
For example, the C-with-Ease statement
%share %stream int channel ;
creates a "stream" called "channel".
A strict order may be placed on a context by the creation of "singletons".
The context
SHARE [n] type name
creates "n slots" in a context for values of the specified type. So, for
example, the C-with-Ease statement
%share [1] int number ;
creates a context which is a single integer. Singletons can be addressed
by subscription. Operations on this context behave as for the other
forms except that a value placed in the context at a specified subscript
overwrites the previous value at that subscript. A further example
should make the functionality clear. The C-with-Ease statement
%share [3][3] int number ;
creates a shared matrix.
Contexts can be more general than those simple examples described above,
and since a context is a real data object a context type may be
described and manipulated like any other data type. So, for example
CONTEXT name type
specifies a name for a context type, which may subsequently be used in a
context allocation. For example, the C-with-Ease statement
%context integers int ;
specifies a context type with the name "integers" for values of type
int, and can be used in a context allocation in a statement directly
equivalent to our first example. So that, given these specifications
%share integers bag ;
is equivalent to
%share int bag ;
It is now possible to describe contexts of context type. The C-with-Ease
statements
%context bag_of_integers integers ;
%share [n] bag_of_integers box ;
specify a context named "bag_of_integers" which is, itself, able to hold
contexts of type "integers". The second statement in the example
allocates n slots for such contexts (singletons in this example are used
simply to allow the contexts to be distinguished - they are not required).
With the above exception the "context" keyword has, thus far, been used
simply in place of type definition. However, contexts can build more
complex gatherings of data. For example
struct point {
int x;
int y;
} ;
%context space {
[n] point ;
%stream integers ;
bag_of_integers ;
} ;
This gives a single name to a shared "space", operations on this space
are type associative (name equivalent). That is, they are valid if the
type of their operand is one of the types specified for the context.
*Operations - actions on shared data*
There are four simple, symmetric, operations on contexts. They are
o write (c, e) - copies the value of the expression e to the context c.
o read (c, v) - copies a value from the context c to a variable v.
o put (c, n) - moves the value associated with the name n to the context c.
o get (c, n) - moves a value from the context c to associate with the name n.
Write and read are copy operations. Put and get are binding operators.
The synchronization characteristics of the operations are similarly
symmetric
o get and read block if data is not existent
o write and put are non-blocking.
Consider how these operations change the state of a program.
Write changes the state of a context, leaving the local state
unchanged. Read changes the local state whilst leaving the context
state unchanged.
Put changes both the context state and local state, i.e. subsequently
the value associated with the variable name used in the operation is
undefined. Get also changes both the context state and the local state,
i.e. the value bound to the variable name used in the operation is
removed from the context.
*Combinations - uniformly building and using resources*
The construction of and interaction with resources has special
requirements. To enable the simple and uniform view of resources in
parallel and distributed environments, Ease provides "combinations".
A "combination" provides guaranteed call-reply semantics via some
context. That is, a process which outputs a request to some resource
which has access to a shared context is guaranteed to receive the reply
to this "request". Thus two particular processes synchronize.
A combination consists of two associated operations. A "call"
CALL c e v
behaves like a write of the value of expression e followed by a get to
the variable v on the context c. A "reply"
RESOURCE c v REPLY f(v)
behaves like a get and a subsequent write of the value returned from the
associated function, where the value written is guaranteed to satisfy
the associated call. For example, the C-with-Ease statement
%call (trees, "oak", tree) ;
writes the value "oak" to the context "trees" and blocks. If a parallel
process executes a corresponding statement
%resource (trees, tree_name) %reply find_tree (tree_name) ;
the value of "tree_name" becomes "oak". The value returned from
"find_tree" is written to context "trees" but is guaranteed to satisfy
the associated blocked call and thus the value is given to "tree" and
the call unblocks.
This call-reply guarantee is important and allows the simple creation of
"statically reusable" and "virtual resources".
A "virtual resource" is a process which "pretends" to be the actual
resource. For example, a disc cache can be considered to provide
"virtual resource" since it returns to the user immediately as though
the requested action had been completed on the actual resource.
A "statically reusable" resource is a process which manages direct
access to the actual resource. For example, a vector processor may be
considered a "statically reusable" resource since the user process must
await its turn before use - a simulation of the resource's behavior may
not be useful.
The context type
type REPLY type
defines the types of call and reply values involved in a combination.
For example, the C-with-Ease statement
%share {string %reply tree_struct} trees ;
allocates a context named "trees". Only combination operations are valid
on such types.
An brief aside: In fact, there is a special array type for use in
contexts in C-with-Ease (arrays must be "counted" or fixed size). Types
used in contexts in an X-with-Ease language (e.g. C-with-Ease and
FORTRAN-with-Ease) must state equivalence to the types specified in the
reference language. Thus there are constraints on pointers in
C-with-Ease not mentioned here.
*Processes - Intro*
Ease provides two forms of process creation which differ in their
synchronization characteristics and the rules for access to local
data.
In C-with-Ease a process is a non-recursive "void" function which meets
the specified rules for access to non-local variables.
*Processes - (1) cooperation*
The first form of process creation, a cooperation, creates some number
of "cooperating" parallel processes. For example
COOPERATE p() q()
creates two processes ($p()$ and $q()$ - in fact there could be any
number of processes. The cooperation blocks until all the processes have
terminated. Processes in a cooperation may use free variables in their
body provided the value of the free variable is not changed or otherwise
written to. If a free variable is changed or otherwise written to in the
body of one process it may not appear in the body of any of the others.
A special shorthand allows many similar processes to be created:
COOPERATE (i = 0 for n) p(i)
This statement creates a cooperation of $n$ processes where each has an
index $i$ in its scope.
For example, the C-with-Ease statement
%cooperate {p(); q();}
creates two processes. The statement
%cooperate (i = 0 for n) p(i) ;
creates n processes, each of which has an argument index i with a
distinct value from 0 to n-1.
*Processes - (2) subordination*
The second form of process creation, a subordination, creates one
"subordinate" process. For example
SUBORDINATE p()
creates a single process (p()). Unlike cooperation, subordination does
not block - the process is created and the parent continues. A
subordinate process inherits access to all context names in its scope,
but may not include references to any non-local (automatic) variables.
Again, a special shorthand allows many similar processes to be created:
SUBORDINATE (i = 0 for n) p(i)
For example, the C-with-Ease statement
%subordinate p() ;
creates a single process, whilst
%subordinate (i = 0 for n) p(i) ;
creates n processes, each of which has an argument index i with a
distinct value from 0 to n-1.
Since subordinate processes are "cut free" from the parent process and
continue with a disjoint scope. An attempt by a subordinate to interact
with a context who's parallel scope has terminated (because the process
which defined the scope has terminated) causes the subordinate to
terminate.
This mechanism is useful since it enables reasoning about speculative
computation and provides the automatic release of allocated resources.
*One final point*
Although Ease is not a message passing model it has be defined with CSP
as its mathematical basis. In CSP mathematics a context may be regarded
as a process with a well defined behavior - just as, in the CSP model,
variables may be defined in this way.
This point, however, need not directly concern the application
programmer - except to reassure her or him that the Ease definition is
well formed, understood, and that Ease programs are malable by formal
techniques.
*Example: "Result parallelism"*
The following example is adapted directly from "How to write parallel
programs: a guide to the perplexed" where it is given as an example of
"result parallelism" (not of prime finding).
void main()
{
int i, ok;
%share [LIMIT] int prime;
%write (prime[2], 1);
%cooperate (i = 3 for LIMIT) prime(i);
for(i = 2; i <= LIMIT; ++i) {
%get (primes[i], ok);
if (ok) printf("%d\n", i);
}
}
void prime(n)
int n;
{
int i, limit, ok;
double function sqrt();
limit = sqrt((double) me) + 1;
for (i = 2; i < limit; ++i) {
%read (primes[i], ok);
if (ok && (me%i == 0)) %write(prime[n], 0);
}
%write(prime[n], 1);
}
It is left as an exercise for the reader to explain why this program
works and why the version presented in the paper by Carriero and
Gelernter [ACM Comp.Surveys Sept89] deadlocks ;-).
--
Steven Ericsson Zenith * Email: zenith@ensmp.fr * Fax:(1)64.69.47.09
| Francais:(1)64.69.47.08 | Office:(1)64.69.48.52
Center for Research in Computer Science - Centre de Recherche en Informatique
CRI - Ecole Nationale Superieure des Mines de Paris
35 rue Saint-Honore 77305 Fontainebleau France
"All see beauty as beauty only because they see ugliness" LaoTzu