[gambit-list] Computing pi with parallel gambit

Bradley Lucier lucier at math.purdue.edu
Mon Feb 6 21:58:39 EST 2017


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).

The subroutines for fft-mul, together with their complexity in with 
N-bit arguments, with annotations EP (for embarrassingly parallel):

make-w: O(N), EP
make-w-rac: O(N), EP
bignum->f64vector-rac: O(N), EP
componentwise-rac-multiply: O(N), EP
componentwise-rac-multiply-conjugate: O(N), EP
componentwise-complex-multiply: O(N), EP
f64vector-rac->bignum: O(N), EP + a cleanup to propagate carries if 
necessary.
direct-fft-recursive-4: O(N log N), EP
inverse-fft-recursive-4: O(N log N), EP

plus

cleanup: O(N), EP + a cleanup to propagate borrows if necessary.

The routines direct-fft-recursive-4 and inverse-fft-recursive-4 are 
surprisingly efficient (about 1/2 the speed of FFTW), so even though the 
other steps are O(N) and the FFTs are O(N log N), the O(N) steps take an 
unexpectedly (at least to me) large fraction of the time for the total 
routine.

BTW, the results of make-w can be reused for arguments of the same or 
smaller sizes, so they should be cached.

To parallelize most of the O(N) routines you'd need to turn the basic 
loops into kernels with parameters and then break up the arguments 
accordingly.

Here's the time to compute (square x) where x is (expt 3 100000000), 
with the timings for all the component subroutines.

(time (##make-f64vector (##fx* two^n 2)))
     2 ms real time
     0 ms cpu time (0 user, 0 system)
     1 collection accounting for 2 ms real time (0 user, 0 system)
     no bytes allocated
     320 minor faults
     no major faults
(time (make-w (##fx- log-two^n 1)))
     63 ms real time
     64 ms cpu time (52 user, 12 system)
     no collections
     36320 bytes allocated
     640 minor faults
     no major faults
(time (make-w-rac log-two^n))
     58 ms real time
     56 ms cpu time (44 user, 12 system)
     no collections
     48608 bytes allocated
     640 minor faults
     no major faults
(time (bignum->f64vector-rac x a))
     97 ms real time
     96 ms cpu time (84 user, 12 system)
     no collections
     no bytes allocated
     767 minor faults
     no major faults
(time (componentwise-rac-multiply a rac-table))
     82 ms real time
     80 ms cpu time (80 user, 0 system)
     no collections
     no bytes allocated
     no minor faults
     no major faults
(time (direct-fft-recursive-4 a table))
     1402 ms real time
     1404 ms cpu time (1404 user, 0 system)
     no collections
     80 bytes allocated
     no minor faults
     no major faults
(time (componentwise-complex-multiply a a))
     90 ms real time
     92 ms cpu time (92 user, 0 system)
     no collections
     no bytes allocated
     no minor faults
     no major faults
(time (inverse-fft-recursive-4 a table))
     1293 ms real time
     1292 ms cpu time (1292 user, 0 system)
     no collections
     80 bytes allocated
     no minor faults
     no major faults
(time (componentwise-rac-multiply-conjugate a rac-table))
     85 ms real time
     84 ms cpu time (84 user, 0 system)
     no collections
     no bytes allocated
     no minor faults
     no major faults
(time (f64vector-rac->bignum a result result-length))
     233 ms real time
     232 ms cpu time (232 user, 0 system)
     no collections
     128 bytes allocated
     no minor faults
     no major faults
(time (cleanup x y result))
     0 ms real time
     0 ms cpu time (0 user, 0 system)
     no collections
     no bytes allocated
     no minor faults
     no major faults
(time (* a a))
     3411 ms real time
     3412 ms cpu time (3364 user, 48 system)
     1 collection accounting for 2 ms real time (0 user, 0 system)
     180384 bytes allocated
     2843 minor faults
     no major faults

This result has 39,624,064 "fdigits" or 316,992,512 bits.

So the FFTs take only about 2700ms of 3400ms total time, all the rest of 
the stuff takes about 700ms.  It's hard to get much speedup here without 
writing a lot of new code.

Brad



More information about the Gambit-list mailing list