Communication Spaces II
=======================

Linda and Friends
=================
Gelernter, Yale university

Machine-independent and portable parallel programming model
Bindings to various languages
Implementations on various architectures (parallel, distributed)
Rather popular a few years ago

Central notions:
----------------

Tuple: Ordered set of values

  ('a', 17, "abc")
  (3.14, [1, 2, 3])

Tuple space: multiset of tuples

  { ("a", 7), ("b", 3.14), ("a", 7) }

Linda programs operate on a central tuple store
- logical shared memory
- associative access ("pattern matching")

- add tuple

  out("P", 5, false) 

  => add ("P", 5, false) to TS

- remove tuple

  int i; bool b;
  in("P", ?i, ?b)

  => block process until matching tuple available
     ("P", <any int>, <any bool>)
  => withdraw tuple from tuple space
  => bind i and b to corresponding components

  multiple tuples matching => non-deterministic choice

- read tuple

  rd("P", ?i, ?b)
  success = rdp("P", ?i, ?b)

  => read matching tuple but do not remove it from TS
     rd: blocks until matching tuple availabe
     rdp: immediately returns and signal success

- parallel processes

  eval("P", f(x), g(y))

  => start process computing tuple components
  => on termination, process issues out("P", r1, r2)

  unification of data and processes
  "live data structures"

Example: data parallelism
--------

main()
{
  get(task, tasks);                     /* initialize tasks */

  for (i = 0; i < tasks; i++)           /* start tasks */
    eval("task", j, process(j, task[j]));

  init(result)                          /* collect results */
  for (i = 0; i < tasks; i++)
    {
      in("task", ?j, ?res);
      result = combine(result, j, res)
    }
  print(result)
}

Example: manager worker solution
--------

manager()
{
  for (i = 0; i < workers; i++)		/* start workers */
    eval(worker(i))

  get(task, tasks);			/* initialize tasks */
  for (j = 0; j < tasks; j++)		/* issue tasks */
    out("task", j, task[j])

  init(result)				/* collect results */
  for (j = 0; j < tasks; j++)
  {
    in("result", ?k, >res)
    combine(result, k, res)
  }
  print(result)				/* print results */
}

int worker(int p)
{
  while (1)
  {
    in("task", ?i, ?task)
    out("result", i, process(i, task))
  }
  return(0)
}

Example: "functional" solution
-------

div_and_conq(i, x)
{
  if (base(x)) return(f(x))

  split(x, x1, x2)

  eval(2*i, div_and_conq(2*i, x1));
  eval(2*i+1, div_and_conq(2*i+1, x1));

  in(2*i, ?res1);
  in(2*i+1, ?res2);

  return(combine(res1, res2));
}

solve(x) 
{
  return(div_and_conq(1, x));
}

Extension: multiple tuple spaces
--------------------------------
- use tuple space as first argument in operations
- distribution of TS in disjoint classes

TupleSpace workspc, taskspc, resultspc;

manager()
{
  for (i = 0; i < workers; i++)		/* start workers */
    workspc.eval(worker(i))

  get(task, tasks);			/* initialize tasks */
  for (j = 0; j < tasks; j++)		/* issue tasks */
    taskspc.out(j, task[j])

  init(result)				/* collect results */
  for (j = 0; j < tasks; j++)
  {
    resultspc.in(?k, >res)
    combine(result, k, res)
  }
  print(result)				/* print results */
}

- better efficiency (less search required)
- restriction of communication capabilities
  (cf. message passing in MPI vs Fortran M)
       
Extension: tuple spaces as fields of a tuple
--------------------------------------------
- tuple spaces as first order objects

TupleSpace t;
...
while (...)
 {
   TupleSpace *s = new TupleSpace;
   t.out(i, s);
 }
...

- Forwarding communication capabilities
  (cf. ports sent via messages in Fortran M)

Comparison to Message Passing
-----------------------------

MP: point-to-point messages
- message directed to some receiver
- only receivers can read it, message destroyed

Linda: tuples
- data objects in own right
- any number of processes can read it, tuples potentially live forever

MP: processes
- defined by interaction with other processes

Linda: "live tuples"
- result implicitly created in tuple store

Applications
------------
- High-level parallel programming
- System-level parallelism
  (Kernel Linda, parallel operating systems)
- "Mirror worlds"
  (book by Gelernter in 1990, forecast of WWW 
   as a world-wide tuple space in which Linda agents operate)

Lasting influence
-----------------
Separation of issues

- computation language: C++, Modula-2, ...
  in charge of sequential core computations

- coordination language: Linda, MPI, ...
  in charge of coordinating sequential processes

No need for new computation language
when defining a coordination model!