[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
- To: adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
- Subject: PARALLEL RECURSION
- From: Per Brinch Hansen <pbh@xxxxxxxxxxxxxxx>
- Date: Sun, 23 May 1999 22:04:49 -0400
- 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
- Organization: Syracuse University
CC: b.m.cook@xxxxxxxxxxxxxx, greeny@xxxxxxxxx,
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 .
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 :
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
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 .)
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;
if depth > 0 then
tree(depth - 1, left)|
tree(depth - 1, right)|
root(bottom, left, right)
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)
p = 1
p > 1
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],
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 . 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.
Per Brinch Hansen
P.S. I am sending you copies of the following papers by regular mail:
 Brinch Hansen, P., Efficient parallel recursion. SIGPLAN
Notices 30, 12 (December 1995), 9-16.
 Brinch Hansen, P., SuperPascal - a publication language for
parallel scientific computing. Concurrency - Practice and
Experience 6, 5 (August 1994), 461-483.
 Brinch Hansen, P., Java's insecure parallelism. ACM SIGPLAN
Notices 34, 4 (April 1999), 38-45.