zenith@uunet.UU.NET (Steven Zenith) (12/08/88)
Further to requests for me to post a summary of the Linda model
in comp.os.research (this is also submitted to comp.parallel).
The following is extracted from a note on the subject.
The Simplicity of Linda
Steven Ericsson Zenith
7th December 1988
Architecture Group
INMOS Limited, Bristol, UK.
Copyright INMOS Limited, 1988.
Linda is a parallel processing paradigm based on the concept of
*generative communication, which unifies the concepts of
process creation and communication. Linda is elegant and easy to
understand, so let's keep it simple.
Linda utilises a concept known as *tuple space*. Think of
tuple space as a kind of global associative memory. Tuple space
stores objects called *tuples*. A tuple consists of a
sequence of typed fields, for example
("foo", 6, 23.5)
is a tuple which is a sequence of values; a string "foo",
an integer value 6, and a floating point value 23.5. It is
distinct from the following tuples
("foo", 6, 23.5, 32.5)
(6, 23.5, "foo")
(4, 5)
These are passive tuples i.e. passive data objects.
A tuple may also contain fields which are process types evaluated
subsequent to entering tuple space. These are known as active tuples.
It may be easier at this stage to simply think of tuple space as
a bag of objects. Linda provides four basic primitive operations
which act upon tuple space:
out(t) to put tuple t into tuple space (i.e. to put an object into the bag).
in(t) to get tuple t from tuple space (i.e. to pick an object from the bag).
rd(t) to read tuple t in tuple space (i.e. to look at an object without
removing it from the bag).
eval(t) to evaluate tuple $t$ (i.e. put an object into the bag for evaluation).
out(t) and eval(t) place a tuple (t) into tuple space and then terminate.
in(t) removes some tuple t from tuple space and then terminates.
rd(t) reads the value of some tuple t and then terminates.
This definition naturally implies that if there is no tuple which
initially matches t present in tuple space then the primitive
in or rd will not terminate until it acquires a tuple t subsequently
added to tuple space.
eval(t) acts like out(t), except that t is evaluated subsequent to
its entry to tuple space and will typically transform into a passive
data tuple, for example
eval (P, Q)
creates processes P and Q which are placed in tuple space and
are evaluated concurrently. Any results are left (as tuples) in
tuple space. Thus is born the term "generative communication".
Tuples have no physical or virtual *address* in tuple
space. A tuple is selected by in or rd by associative matching.
The field of a tuple may contain an *actual* or *formal*, for example,
if N is a variable of integer type
(6, ?N)
contains a formal N and will match with any of the
following tuples
(6, 7)
(6, 8)
(6, 1024)
The input in(6, ?N) will select a matching tuple from
tuple space, and perform the actual to formal assignment. If
several matching tuples exist in tuple space then an arbitrary
selection is made.
Similarly, the output out(6, ?N) will place a tuple in
tuple space, and may be selected by an input which has an actual
of integer type in the place of the formal,
e.g. in(?I, 11) or in(6, 23).
More recently Linda has acquired two variant forms of in
and rd. These are the primitives inp and rdp, which are predicate
functions which test for presence, for example
if inp(t) then tuplefound else tupleNOTfound
inp(t) attempts to remove some tuple t from
tuple space and then terminates. rd(t) attempts
to read the value of some tuple t and then terminates. In both
cases the predicate is true if the function succeeds in its
attempt and false otherwise.
The semantics of these two predicates seem sloppy, for example,
it's not clear how presence is tested. Is a full search of tuple
space guaranteed? There are temporal problems i.e. its result may
not be correct at termination, since (in the time taken to return
the results) several tuples of the required type may have entered
tuple space.
This test for presence (I believe) is a mistake. The test would
be more meaningful as a test for readiness as in the Occam model,
for example
alt
in (t1)
P
in (t2)
Q
Let's use some buzz words to describe the Linda paradigm. This is
a) fun and b) helps us to understand why Linda is liked so much.
So Linda features
* a easy to use concept
* automatically scalable algorithms
* portable applications programming (architecture independent)
* the same model on different parallel architectures
* a unified process and communications model
* an integral persistent storage concept
* Linda is easily added to existing sequential languages to
create parallel variants of the original language (e.g. C-Linda,
Lisp-Linda, Postscript Linda, Modula-Linda exist currently).
Any model of communication at a higher level than direct
point-to-point communication will see degraded performance, even in
the case of simple through routing. Linda performance will
naturally be system dependent. A good choice of implementation
strategy can produce interesting results however. As an example,
the Modula-Linda implementation completed by Siemens on the
Parwell machine[2] showed a ten percent improvement on
local communication and twenty percent improvement on global
communication when compared with the native message passing
system (at low traffic).
The Linda model of communication is a higher level model than the
Occam model of message passing. In some respects the communication model
is more like a
system facility than the direct simplicity of point-to-point
process communication. In a distributed environment the tuple
space passive data model alone can play a role equivalent to that
fulfilled by the filing system on conventional machines. Many
implementations use Linda simply in that role, ignoring the
implementation of eval. But this is to miss the point.
Linda is a new and complete parallel processing paradigm worthy
of attention.
[1] David Gelernter,
Generative Communication in Linda, ACM Trans. Jan. 1985.
[2] Borrmann, Herdieckerhoff, Klien,
Implementation of the Linda Concept on a Hierarchical
Multiprocessor, Conpar88 Proceedings, 1988.
Copyright INMOS Limited. All rights reserved.
* Steven Ericsson Zenith Snail mail: INMOS Limited, 1000 Aztec West,
| zenith@inmos.uucp Almondsbury, Bristol BS12 4SQ. UK.
zenith@inmos.co.uk Voice: (UK)0454 616616x513
** All can know beauty as beauty only because there is ugliness **