[gambit-list] Floating-point codes for testing register allocation

Bradley Lucier lucier at math.purdue.edu
Tue Apr 3 11:38:31 EDT 2007


Marc:

I've included below two files that I hope will eventually replace the  
fft bignum multiplication routines in _num.scm.  (The advantage of  
the new approach is that it is provably correct; I'm waiting to see  
if there are any disadvantages.)

The main loops in direct-fft-recursive and inverse-fft-recursive are  
scheduled to take 122 and 96 cycles, respectively, on my G5 using  
CC='gcc -mcpu=970 -m64' with the official Apple gcc 4.0.1; most of  
the time is taken in constantly reloading W and a from the stack.  
(You can find this information by passing -dR to gcc. BTW, why does  
b21 erase the .c file after compiling something with -dynamic?  It's  
almost as if you're embarrassed by the C code that gsc generates ;-)   
If the number of registers are increased so that W and a are kept in  
registers, then these two loops are each scheduled in about 31  
cycles, the same as a hand rewrite of the code in C.

Please see whether some type of SSA form for GVM variables used in a  
basic block improves performance the same way that generating SSA- 
type code for F64 variables in each basic block helped the floating- 
point code.

Some trivial timing comparisons with the existing code are given  
below.  I hope that when I'm done the new code will be faster than  
the old.  (For example, the new code is more "cache-oblivious" than  
the old.)

Brad

> [descartes:~/programs/gambc40b17/fftmul] lucier% gsc -:m100000
> Gambit Version 4.0 beta 21
>
> > (load "fftmul-fast")
> "/Users/lucier/programs/gambc40b17/fftmul/fftmul-fast.o2"
> > (define a (expt 3 10000000))
> > (define b (expt 3 10000000))
> > (define c (time (* a a)))
> (time (* a a))
>     2193 ms real time
>     2090 ms cpu time (1948 user, 142 system)
>     1 collection accounting for 22 ms real time (3 user, 19 system)
>     110229552 bytes allocated
>     no minor faults
>     no major faults
> > (define d (time (fft-mul a a)))
> (time (fft-mul a a))
>     2621 ms real time
>     2431 ms cpu time (2203 user, 228 system)
>     1 collection accounting for 44 ms real time (4 user, 40 system)
>     112555696 bytes allocated
>     no minor faults
>     no major faults
> > (define e (time (* a b)))
> (time (* a b))
>     3659 ms real time
>     3002 ms cpu time (2777 user, 225 system)
>     1 collection accounting for 77 ms real time (3 user, 74 system)
>     171743360 bytes allocated
>     no minor faults
>     no major faults
> > (define f (time (fft-mul a b)))
> (time (fft-mul a b))
>     4007 ms real time
>     3585 ms cpu time (3219 user, 366 system)
>     1 collection accounting for 64 ms real time (3 user, 61 system)
>     183596720 bytes allocated
>     no minor faults
>     no major faults
> > (= c d)
> #t
> > (= e f)
> #t


-------------- next part --------------
A non-text attachment was scrubbed...
Name: fftluts.scm
Type: application/octet-stream
Size: 126315 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20070403/6cca7390/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fftmul-fast.scm
Type: application/octet-stream
Size: 16352 bytes
Desc: not available
URL: <http://mailman.iro.umontreal.ca/pipermail/gambit-list/attachments/20070403/6cca7390/attachment-0001.obj>


More information about the Gambit-list mailing list