Parallel Factorial

LA home
 FP,  λ
 Logic,  π


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.

  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.

window on the wide world:

Computer Science Education Week

free op. sys.
free office suite,
ver 3.4+

~ free photoshop
web browser
like it says!

|   choice
|| parallel
-> sequence
? input act
! output act
chan new channel

© L. Allison   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Sunday, 29-Mar-2015 09:10:46 EST.