Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!helios!bcm!dimacs.rutgers.edu!seismo!uunet!samsung!emory!hubcap!Steven From: zenith@ensmp.fr (Steven Ericsson Zenith) Newsgroups: comp.parallel Subject: Parallel programming with Ease - Zenith: Ecole des Mines. FRANCE. Message-ID: <12868@hubcap.clemson.edu> Date: 31 Jan 91 22:00:41 GMT Sender: fpst@hubcap.clemson.edu Lines: 423 Approved: parallel@hubcap.clemson.edu --- 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