PARALLEL RECURSION

[Per Brinch Hansen <pbh@xxxxxxxxxxxxxxx>]

To:   adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
From: pbh@xxxxxxxxxxxxxxx   
CC:   b.m.cook@xxxxxxxxxxxxxx, greeny@xxxxxxxxx,
      Alfred_Hartmann@xxxxxxxx, tholm@xxxxxxxxxxxx,
      ingargiola@xxxxxxxxxxxxxxxxxxx, jmk@xxxxxxxxxxxxxxxx,
      KKrishna@xxxxxxxxxxxxxxxxxx, lewis@xxxxxxxxxxxxxxx,
      r.mckeag@xxxxxxxxx, ohearn@xxxxxxxxxxxxx,
      reynolds@xxxxxxxxxx, johan.sunter@xxxxxxxxxxx,
      oyvind.teig@xxxxxxxxxxxx, h.thimbleby@xxxxxxxxx,
      java-threads@xxxxxxxxx, occam-com@xxxxxxxxx,
      pbh@xxxxxxxxxxxxxxx  
Date: 23 May 1999
Subject: PARALLEL RECURSION

Dear Adrian Lawrence,

No, I have not solved the unsolvable problem of "bounded memory
consumption" in the presence of parallel recursion. Since recursion,
is unbounded, that would have been a miracle. I have, however, found a
memory allocation scheme for parallel recursion that is about as fast as
the traditional stack discipline for sequential languages [1].

There will always be a conflict between our intellectutal desire to
write programs in a notation with as few restrictions as possible and
the more practical need to run such programs efficiently and reliably
in fixed-size memories.

In a 1994 paper, I wrote the following [2]:

  Since the 1960s, computer scientists have recognized the distinction
  between publication languages that emphasize clarity of concepts,
  and implementation languages that reflect pragmatic concerns and
  historical traditions.
  .....
  occam was an invaluable inspiration for SuperPascal. Years ahead of
  its time, occam set a standard of simplicity and security against
  which future parallel languages will be measured. The parallel
  features of SuperPascal are a subset of occam2 with the added
  generality of dynamic process arrays and recursive parallel
  processes. This generality enables you to write parallel algorithms
  that cannot be expressed in occam.

(Needless to say, if you compare Java's parallelism to occam2, it's a
bitter cup of coffee indeed [3].)

In my own work on computational science, I used SuperPascal as a
publication language and occam2 as an implementation language.
SuperPascal enabled me to write elegant recursive algorithms for
parallel versions of Quicksort and the Fast Fourier Transform. I then
rewrote these programs in occam2 using process trees with fixed depths
and tested their performance on a Computing Surface.

The difference between the two notations was striking. Here is the
SuperPascal definition of a binary process tree:

  procedure tree(depth: integer; bottom: channel);
  var left, right: channel;
  begin
    if depth > 0 then
      begin
        open(left, right);
        parallel
          tree(depth - 1, left)|
          tree(depth - 1, right)|
          root(bottom, left, right)
        end
      end
    else leaf(bottom)
  end;

The occam2 version is a notational clutter that has no place in a
thinking tool or a published algorithm:

  PROC NODE(VAL INT no, CHAN OF ITEMS bottom1, bottom2,
    left1, left2, right1, right2)
  ...
  INT p:
  SEQ
    bottom1?CASE param;p
    IF
      p = 1
        leaf(bottom1, bottom2)
      p > 1
        SEQ
          PAR
            left1!param;(p - 1)/2
            right1!param;(p - 1)/2
          root(bottom1, bottom2, left1, left2, right1, right2)
  :

  PLACED PAR i = 0 For p
    PROCESSOR i + 2 T8
      VAL left IS (2*i) + 1:
      VAL right IS left + 1:
      PLACE up[i] AT inp0:
      PLACE down[i] AT out0:
      PLACE down[left] AT inp1:
      PLACE up[left] AT out1:
      PLACE down[right] AT inp2:
      PLACE up[right] AT out2:
      NODE(i, up[i], down[i], up[left], down[left],
        up[right], down[right])

Even as I retype this 1991 program piece, I have to proofread it as
carefully as assembler language. When you have figured out how the tree
nodes and channels are numbered, you will appreciate that the need for
process and channel arrays is due solely to the limitations of the
programming notation: the absence of recursion.

It hardly matters that occam has changed since then, considering that
the occam community still shies away from parallel recursion. So I
have a simple suggestion to offer:

Develop a publication language that extends occam with parallel
recursion using the memory allocation scheme described in [1]. Since
this would be a publication language only, it is sufficient to
implement a platform-independent version for uniprocessor PCs with a
portable compiler and interpreter written in occam (or even in Java).

It may amuse you to know that I tested my parallel SuperPascal programs
on an IBM PC with only 64 kbytes of memory. When the parallel programs
worked, I rewrote them in occam2, changed a few constants, and used them
to solve much larger problems on a Computing Surface with 48 transputers
and 48 Mbytes of distributed memory. The manual translation of correct
readable SuperPascal programs into occam was a trivial task.

Since it is no problem to rewrite a model program in another language,
it is not particularly important to be able to use publication and
implementation languages on the same computer.

Best regards,

Per Brinch Hansen


P.S. I am sending you copies of the following papers by regular mail:

[1] Brinch Hansen, P., Efficient parallel recursion. SIGPLAN
    Notices 30, 12 (December 1995), 9-16.

[2] Brinch Hansen, P., SuperPascal - a publication language for
    parallel scientific computing. Concurrency - Practice and
    Experience 6, 5 (August 1994), 461-483.

[3] Brinch Hansen, P., Java's insecure parallelism. ACM SIGPLAN
    Notices 34, 4 (April 1999), 38-45.