Re: clever compilers for linda? (Ed Segall)
Thu, 3 Feb 1994 04:11:26 GMT

          From comp.compilers

Related articles
clever compilers for linda? (1994-01-30)
Re: clever compilers for linda? (1994-02-03)
| List of all articles for this month |

Newsgroups: comp.compilers,comp.parallel
From: (Ed Segall)
Keywords: parallel
Organization: School of Computer Science, Carnegie Mellon
References: 94-01-126
Date: Thu, 3 Feb 1994 04:11:26 GMT

Paul Connolly <> wrote:
> I remember reading (comms ACM?) that clever compilers can optimize
>linda operations on the tuple space into point-to-point message passing.
>Can someone confirm this, or is my memory failing? Can anyone name a
>C-linda compiler that does this optimization?

Yes. This technique is used in distributed (network) as well as parallel
implementations, done at both Yale and SCA and possibly elsewhere. It's
often called "hash-to-rendezvous". (Database folks call a closely related
technique "horizontal partitioning".)

Basically, the compiler first partitions Tuple Space into independent
subspaces, and then within each subspace, chooses a key to index tuples by
(when possible). This key must consist of information present in all
potentially matching tuple/antituple pairs. If a non-trivial key exists,
it is mapped to a processor (the rendezvous processor), and tuples and
antituples meet up there. Runtime optimization can often ensure that the
rendezvous processor is the actual destination processor, so that only one
message is needed. Obviously, there are cases that will make this

Read Carriero's, Bjornson's, and/or Leichter's dissertations from Yale for
more information.

You can read mine, too (from Rutgers), if you want to order it from UMI
(that's University Microfilms, Inc). I haven't released it as a TR yet,
so if you ask me or Rutgers for copies, you may wait a while.

--Edward Segall

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.