[gambit-list] Computing pi with parallel gambit

Bradley Lucier lucier at math.purdue.edu
Mon Feb 6 22:50:06 EST 2017


> On Feb 6, 2017, at 9:58 PM, Bradley Lucier <lucier at math.purdue.edu> wrote:
> 
> On 12/13/2016 12:38 PM, Marc Feeley wrote:
> 
>> I’d like the bignum code to be reviewed to see if there are any “low hanging fruit” for improving performance on a multiprocessor system.  For example, I would think the karatsuba multiplication algorithm can be parallelized by adding 3 “future” constructs in the recursion.  With a switch, these futures could be removed to get the usual sequential algorithm.
> 
> Basically all the bignum code can be parallelized to a greater or lesser extent.
> 
> gcd, quotient, and integer-sqrt all depend on multiplication for their speed, so you'd parallelize multiplication.  And really, it's only worth parallelizing fft-mul (and karatsuba-mul for arguments that are too large for fft-mul).

Another thing: once karatsuba-mul subdivides its arguments into 1/2 billion bit chunks, which when multiplied by fft-mul yields billion-bit results, each of those billion-bit results requires over 2 GB of RAM to compute.  So you want to be careful about how many of those you fire off in parallel.

Brad


More information about the Gambit-list mailing list