[gambit-list] Computing pi with parallel gambit

Marc Feeley feeley at iro.umontreal.ca
Tue Dec 13 10:47:54 EST 2016


I have tried the “cond-future” idea on an improved chud-parallel.scm that exposes some more parallelism.  The run time drops from 9 to 7 seconds.  There are still many idle processors at the end of the computation due to the sequential final “quotient” (which takes about 1.8 seconds).  Note that globally the processors are active only 52% of the time (length of the lowest green horizontal bar), so if the algorithm was perfectly parallel the run time would be about 3.5 seconds or roughly a factor of 4.5x faster than on 1 processor.

I’ve attached the new code and activity log.

Marc


-------------- next part --------------
A non-text attachment was scrubbed...
Name: chud-parallel.scm
Type: application/octet-stream
Size: 3061 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20161213/c83bd5f4/attachment.obj>
-------------- next part --------------


-------------- next part --------------
A non-text attachment was scrubbed...
Name: PastedGraphic-1.png
Type: image/png
Size: 40068 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20161213/c83bd5f4/attachment.png>
-------------- next part --------------


> On Dec 12, 2016, at 6:30 PM, Marc Feeley <feeley at iro.umontreal.ca> wrote:
> 
> 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