I got the latest ooura parallel fft compiled into the bignum multiplication. Supposedly it spawns 4 parallel threads for big enough ffts. Note that in the test below, calculating 3^ {1,000,000,000} shifts back to Karatsuba multiply for really large numbers (> 256 million bits), so it slows down quite a bit.
Somehow it doesn't really seem worth it. It ends up being a little over twice as fast on the parallel Opteron box. I think I'm going to look at less drastic measures to try to speed things up.
Brad
On my 2GHz G5 running 64-bit gambit, nothing else running.
Parallel fft in C (compiled with -O3):
[lindv2:~/programs/gambc40b17/gsi] lucier% ./gsi Gambit Version 4.0 beta 17
(time (* 0 (expt 3 1000000)))
(time (* 0 (expt 3 1000000))) 126 ms real time 143 ms cpu time (119 user, 24 system) 9 collections accounting for 11 ms real time (8 user, 4 system) 10932368 bytes allocated no minor faults no major faults 0
(time (* 0 (expt 3 10000000)))
(time (* 0 (expt 3 10000000))) 1271 ms real time 1492 ms cpu time (1321 user, 171 system) 10 collections accounting for 38 ms real time (9 user, 30 system) 87918968 bytes allocated no minor faults no major faults 0
(time (* 0 (expt 3 100000000)))
(time (* 0 (expt 3 100000000))) 23301 ms real time 29528 ms cpu time (26815 user, 2713 system) 13 collections accounting for 472 ms real time (14 user, 457 system) 1382017064 bytes allocated no minor faults no major faults 0
(time (* 0 (expt 3 1000000000)))
(time (* 0 (expt 3 1000000000))) 379506 ms real time 480968 ms cpu time (423657 user, 57311 system) 24 collections accounting for 19308 ms real time (90 user, 18894 system) 22605836024 bytes allocated no minor faults no major faults 0
Serial fft running in scheme:
[lindv2:~/Desktop/gambc40b17/gsi] lucier% ./gsi Gambit Version 4.0 beta 17
(time (* 0 (expt 3 1000000)))
(time (* 0 (expt 3 1000000))) 176 ms real time 176 ms cpu time (152 user, 24 system) 9 collections accounting for 12 ms real time (8 user, 4 system) 17846160 bytes allocated no minor faults no major faults 0
(time (* 0 (expt 3 10000000)))
(time (* 0 (expt 3 10000000))) 1837 ms real time 1834 ms cpu time (1617 user, 217 system) 21 collections accounting for 67 ms real time (18 user, 48 system) 143777912 bytes allocated no minor faults no major faults 0
(time (* 0 (expt 3 100000000)))
(time (* 0 (expt 3 100000000))) 36836 ms real time 36593 ms cpu time (32865 user, 3728 system) 22 collections accounting for 881 ms real time (25 user, 853 system) 2276689064 bytes allocated no minor faults no major faults 0
(time (* 0 (expt 3 1000000000)))
(time (* 0 (expt 3 1000000000))) 557969 ms real time 548899 ms cpu time (485614 user, 63285 system) 51 collections accounting for 19755 ms real time (219 user, 19231 system) 35132630760 bytes allocated no minor faults no major faults 0
On a 2.2(?) GHz Opteron box with 8 processors (and 8 niced-to-the-max folding@home jobs):
Parallel FFT in C (compiled with -O3):
euler-35% ./gsi Gambit Version 4.0 beta 17
(time (* 0 (expt 3 1000000)))
(time (* 0 (expt 3 1000000))) 126 ms real time 99 ms cpu time (95 user, 4 system) 9 collections accounting for 6 ms real time (6 user, 0 system) 10932000 bytes allocated 2643 minor faults no major faults 0
(time (* 0 (expt 3 10000000)))
(time (* 0 (expt 3 10000000))) 1016 ms real time 1021 ms cpu time (944 user, 77 system) 10 collections accounting for 12 ms real time (4 user, 8 system) 87918968 bytes allocated 21455 minor faults no major faults 0
(time (* 0 (expt 3 100000000)))
(time (* 0 (expt 3 100000000))) 15501 ms real time 22549 ms cpu time (21398 user, 1151 system) 5 collections accounting for 140 ms real time (8 user, 133 system) 1382017064 bytes allocated 338039 minor faults no major faults 0
(time (* 0 (expt 3 1000000000)))
(time (* 0 (expt 3 1000000000))) 235335 ms real time 381121 ms cpu time (361882 user, 19239 system) 24 collections accounting for 2451 ms real time (61 user, 2378 system) 22605836024 bytes allocated 5522936 minor faults no major faults 0
Serial FFT in Scheme:
euler-36% gsi Gambit Version 4.0 beta 17
(time (* 0 (expt 3 1000000)))
(time (* 0 (expt 3 1000000))) 154 ms real time 154 ms cpu time (140 user, 14 system) 11 collections accounting for 7 ms real time (5 user, 0 system) 17843120 bytes allocated 3105 minor faults no major faults 0
(time (* 0 (expt 3 10000000)))
(time (* 0 (expt 3 10000000))) 1635 ms real time 1634 ms cpu time (1522 user, 112 system) 21 collections accounting for 22 ms real time (14 user, 9 system) 143777912 bytes allocated 26433 minor faults no major faults 0
(time (* 0 (expt 3 100000000)))
(time (* 0 (expt 3 100000000))) 30350 ms real time 30340 ms cpu time (28848 user, 1492 system) 22 collections accounting for 142 ms real time (16 user, 124 system) 2276689064 bytes allocated 418349 minor faults no major faults 0
(time (* 0 (expt 3 1000000000)))
(time (* 0 (expt 3 1000000000))) 495749 ms real time 494356 ms cpu time (472253 user, 22103 system) 51 collections accounting for 2578 ms real time (42 user, 2530 system) 35132630760 bytes allocated 6259491 minor faults no major faults 0