Re: clever compilers for linda?

Paul Connolly <eep2pc@ee.surrey.ac.uk> 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
impossible.


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
--

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