|
Function fact takes an integer n and
an output channel as parameters.
The objective is to calculate n!.
To do this the range of numbers [1..n] must be multiplied together.
If the current range, [lo..hi], contains just one number
it is output, opch!hi, and then (->)
the process stops.
If not, the range is divided in two,
[lo..mid] and [mid+1..hi]
and auxiliary processes are created to deal with each part
and return the results on a scratch channel, ch.
When the results are back, ch?x and ch?y,
they are combined and output, opch!x*y.
The auxiliary processes and the combining process
run an parallel (||).
The final result is written to standard output, output.
let
fact = lambda n.
let rec
f = lambda lo. lambda hi. lambda opch.
if lo = hi then
opch!hi -> stop
else {lo < hi}
let mid = (lo+hi)/2,
ch = chan
in {parallel divide and conquer}
f lo mid ch || {small numbers's}
f (mid+1) hi ch || {big numbers's}
ch?x -> ch?y -> opch!x*y {combine} -> stop
in f 1 n output
in fact 10
{\fB Parallel Factorial Program. \fP}
|
e.g. c1993
So if we had lots of processors and
could sensibly spread the processes amongst them
then this would be a parallel divide and conquer.
|
pfl...
| | |
choice |
|| | parallel |
-> | sequence |
? | input act |
! | output act |
chan | new channel |
|
|
|