zenith@uunet.UU.NET (Steven Zenith) (12/10/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 ** busalacc@cs.umn.edu (Perry J. Busalacchi) (02/10/89)
We are currently in the process of implementing Linda on both the NCUBE hypercube and the Butterfly GP1000. The NCUBE implementation is currently being tested and benchmarked. The Butterfly implementation is still under development. I would be happy to moderate a Linda news group if no one else would prefer to do it. I would also be happy to supply anyone with information on our Linda implementations and our plans for future research. Perry Busalacchi University of Minnesota (busalacc@umn-cs.cs.umn.edu)
andrewn%SYMA.SUSSEX.AC.UK@CUNYVM.CUNY.EDU (Andrew D Nimmo) (04/10/89)
[ If anyone has a canned bibliography, please post it. I'll keep a
version here and then we won't have to burden the net with bib. request.
---- Steve
]
I am searching for information and articles on Linda, covering
the concepts and applications (e.g. the Cogent XTM Transputer-based
computer, Linda C, Linda Postscript etc) available. Any information,
book details etc. would be appreciated.
Thanks - Andrew D. Nimmo
VLSI and Graphics Research Group
EAPS II
University of Sussex
Falmer
BRIGHTON
East Sussex
BN1 9QT
United Kingdom
andrewn@uk.ac sussex.syma JANETscott@cs.rochester.edu (Michael Scott) (05/13/89)
As followup to my recent posting about Linda, let me say that I consider
Gelernter and Carriero's work on Linda to be a significant contribution to
the state of the art. I have some concerns about the language/model that
are long-standing and that I belive the Linda people understand. My posting
was simply in response to Carriero's claim that efficiency concerns had
been proven "irrelevant". I continue to assert that this is not the case.
I have a great deal of respect for the Linda group and its work.
I believe it is in everyone's interest to keep Linda in perspective and
to appreciate it without attempting to sell it as the answer to
everyone's problems. I agree that the discussion in this newsgroup has
run its course and should die out for a while.
--
Michael L. Scott
University of Rochester (716) 275-7745
scott@cs.rochester.edu scott%rochester@CSNET-RELAY
{decvax, allegra, cmcl2}!rochester!scotthall@uunet.UU.NET (Craig Hall) (08/22/90)
Hello all, I have heard of a network programming interface called Linda. Does anyone have or know of someone who has ported a PD version of Linda to SunOS, maybe even to the 386i? I would greatly appreciate any clues. Thanks in advance, Craig Hall System Administrator, Computer Graphics Lab Eastern Washington University Cheney, WA 99004 UUCP: ...!uunet!isc-br!ewu!hall Internet: hall@ewu%uunet.uu.net
surfer@dcs.qmw.ac.uk (Osborne) (04/21/91)
I am interested in the Linda concurrent programming model, and would like
to know of any ftp sites holding any reports on Linda.
Thanks in advance....
Michael Osborne
--
=========================== MODERATOR ==============================
Steve Stevenson {steve,fpst}@hubcap.clemson.edu
Department of Computer Science, comp.parallel
Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell