[gambit-list] Computing pi with parallel gambit

Marc Feeley feeley at iro.umontreal.ca
Mon Dec 12 18:30:30 EST 2016


I’m thinking it would be nice if _num.scm was improved to implement parallel algorithms when a configuration option is used.  This could be based on the “future” and “touch” parallelism constructs.  Just a quick reminder

   (future expr)

conceptually spawns a new thread that computes expr and returns a representative of the result (a “placeholder”), and

   (touch placeholder)

waits for the result to be available and returns the result.  So the idiom

   (let* ((a (future EXPR1))
          (b EXPR2))
     (combine (touch a) b))

will compute EXPR1 and EXPR2 in parallel and call “combine” when the two results are available.

These forms can be implemented easily with Gambit threads:

  (define-macro (future expr)
    `(thread-start! (make-thread (lambda () ,expr))))

  (define (touch x)
    (thread-join! x))

Since most parallel fork/join algorithms will probably want to fork threads for numbers of a certain size, it is interesting to consider a “conditional” future construct that takes a condition as argument:

  (define-macro (cond-future test expr)
    `(if ,test (thread-start! (make-thread (lambda () ,expr))) ,expr))

  (define (cond-touch x)
    (if (thread? x) (thread-join! x) x))

That way a parallel algorithm would do:

   (let* ((a (cond-future (> (size data) 1000) EXPR1))
          (b EXPR2))
     (combine (cond-touch a) b))

A sequential version would be obtained by defining

  (define-macro (cond-future test expr)
    expr)

  (define (cond-touch x)
    x)

Brad, do you think these forms would be a good basis for implementing parallel algorithms for arithmetic?

Marc


> On Dec 12, 2016, at 4:52 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
> 
> On 12/12/2016 04:39 PM, Marc Feeley wrote:
>> 
>>> On Dec 11, 2016, at 9:53 PM, Bradley Lucier <lucier at math.purdue.edu
>>> <mailto:lucier at math.purdue.edu>> wrote:
>>> 
>>> Is there a way for me to try to run it in parallel?
>>> 
>>> Brad
>>> 
>>> <chud-parallel.scm>
>> 
>> I tried your program on my working copy of Gambit (rather brittle, but
>> good enough to run simple tests like this).
> 
> Thanks, it looks very interesting!
> 
>> When I review the source code, I think the first 2000 ms are used to
>> compute sequentially the square root of a 2 million digit bignum, and
>> after the 5000 ms mark, the program computes sequentially (quotient (* p
>> ch-C sqrt-C) (* ch-D (+ q (* p ch-A)))) with large bignums.
>> 
>> So to improve the performance, it would be necessary to improve the
>> parallelism in those two parts.
> 
> Absolutely.
> 
>> The square root could probably be done
>> concurrently with the main computation (for a small number of
>> processors, otherwise a parallel square root algorithm needs to be
>> devised).
> 
> Yes, the computation to the square root should be carried out in parallel with the computation of gpg.
> 
>> The tail part of the computation might be improved by
>> parallel algorithms for multiplication and division.
> 
> The two arguments to
> 
>            (quotient (* p ch-C sqrt-C) (* ch-D (+ q (* p ch-A)))))))
> 
> can be computed in parallel.
> 
> I appreciate you trying this experiment.  The activity log is a pretty good tool!
> 
> Brad




More information about the Gambit-list mailing list