Mathemagix

[Bernard Mourrain <address@concealed>]

Hi Joris,

Impressive results.

Can you explain the two columns below?

B.

> Hi all,
>
> I just finished a new (raw) FFT multiplication for lengths of the form n=2^p.
> The implementation uses SIMD instructions and multi-threading.
> Here are benchmarks on my bipro :
>
> ---> Complexify Double
>
> [vdhoeven@localhost algebramix]$ fft_bench
>          4 :            7.67037 ns         6.1363e-05 ms
>          8 :            6.13164 ns        0.000147159 ms
>         16 :            4.65555 ns        0.000297955 ms
>         32 :            4.11272 ns        0.000658035 ms
>         64 :            4.13011 ns         0.00158596 ms
>        128 :            3.69123 ns         0.00330735 ms
>        256 :            3.43379 ns         0.00703241 ms
>        512 :            3.44551 ns          0.0158769 ms
>       1024 :            3.51524 ns           0.035996 ms
>       2048 :            3.85681 ns          0.0868862 ms
>       4096 :            3.83977 ns           0.188732 ms
>       8192 :            3.46781 ns           0.369308 ms
>      16384 :            3.44088 ns           0.789255 ms
>      32768 :            3.44783 ns            1.69468 ms
>      65536 :            4.36525 ns             4.5773 ms
>     131072 :             5.9592 ns            13.2784 ms
>     262144 :            5.37996 ns            25.3858 ms
>     524288 :            5.52765 ns            55.0635 ms
>    1048576 :            5.18983 ns            108.839 ms
>    2097152 :            5.16801 ns              227.6 ms
>    4194304 :            4.98821 ns            460.286 ms
>    8388608 :            6.22998 ns               1202 ms
>   16777216 :            9.44982 ns               3805 ms
>
> ---> Modular P, P= 3*2^30+1
>
> [vdhoeven@localhost mmx]$ fft_bench
>          4 :            13.3117 ns        0.000106494 ms
>          8 :            14.8151 ns        0.000355562 ms
>         16 :            16.2274 ns         0.00103855 ms
>         32 :            17.2079 ns         0.00275326 ms
>         64 :            17.8119 ns         0.00683977 ms
>        128 :             18.418 ns          0.0165025 ms
>        256 :            18.6565 ns          0.0382086 ms
>        512 :            18.4581 ns          0.0850551 ms
>       1024 :            18.5203 ns           0.189648 ms
>       2048 :            18.6802 ns           0.420828 ms
>       4096 :            18.9043 ns           0.929182 ms
>       8192 :            19.0554 ns            2.02933 ms
>      16384 :            19.1279 ns            4.38748 ms
>      32768 :            8.85069 ns            4.35029 ms
>      65536 :            8.95706 ns            9.39216 ms
>     131072 :            8.61178 ns             19.189 ms
>     262144 :            8.73949 ns            41.2381 ms
>     524288 :            8.82756 ns            87.9355 ms
>    1048576 :            8.97725 ns            188.267 ms
>    2097152 :            8.81662 ns            388.286 ms
>    4194304 :            8.85039 ns            816.667 ms
>    8388608 :            8.76102 ns            1690.33 ms
>   16777216 :            8.84881 ns               3563 ms
>
> A few notes:
>
>   - We are about twice as slow as FFTW3 for complex doubles,
>     due to the fact that we don't use codelets for the moment.
>   - The jump in efficiency for Modular P in at n=32768 is due
>     to the fact that we start multi-threading at this point.
>   - Multi-threading gives a clean gain by a factor 2 in the case
>     of Modular P and only a gain of about 1.5 in the case of
>     Complexify Double.
>   - Modular P does not make use of SIMD instructions.
>     It should be possible to compute w.r.t. two moduli with
>     about the same speed.
>   - For large n, integer multiplication based on four Ps
>     might be competitive to integer multiplication based on FFTW3.
>   - The TFT transform still has to be re-implemented.
>
> Best wishes, Joris
>