[gambit-list] Computing pi with parallel gambit
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.
More information about the Gambit-list