Performance analysis of Mul algorithms in the same range

[Lingchuan Meng]

Hi Torbjorn,

Thank you for the reply. The symlink is pointing to the 'gmp-mpara.h'
located in /mpn/x86/k7/ in my case. And after editing,  both files in
the build directory and  /mpn/x86/k7/ have been changed. I've compared
the performances of untuned and tuned library by copying the
thresholds from the tuning program to 'gmp-mpara.h' in the build
folder, and it worked as expected. However, as mentioned in previous
email, editing those thresholds manually to force certain algorithm to
run doesn't deliver the expected result. And the new 'gmp-mpara.h' did
survive the reconfigure and rebuild.

The speed program is great, but, in my case, I'm hoping to get more
information by inserting PAPI codes.


On Sun, Jan 4, 2009 at 5:58 AM, Torbjorn Granlund <tg at swox.com> wrote:
>
> "Lingchuan Meng" <lingchuanmeng at gmail.com> writes:
>
>  I'm new to GMP and trying to measure the performance of the four integer
>  multiplication algorithms. I tried manually modifying the
>  MUL_KARATSUBA_THRESHOLD MUL_TOOM3_THRESHOLD
>  MUL_FFT_THRESHOLD in the 'gmp-mparam.h' as follows:
>
>  #define MUL_KARATSUBA_THRESHOLD          1
>  #define MUL_TOOM3_THRESHOLD              5100
>  ....
>  #define MUL_FFT_THRESHOLD              5100
>
>  Then, I re-ran the configure and make. I expect it to force using
>  Karatsuba when the sizes of operands are in [1, 5100) in terms of limb.
>  However, the outcome doesn't change accordingly. It's more like that the
>  Karatsuba hasn't been forced to be used throughout the testing range.
>
>  Any suggestion is appreciated. Happy belated New Year!
>
> Perhaps your modified gmp-mparam.h didn't survive the new configure?
> Depending on your editor's behaviour, it might have modified just the
> gmp-mparam.h in the build directory, or the file to which that
> gmp-mparam.h symlink is pointing.
>
> Instead of modifying gmp-mparam.h, I would suggest that you use the
> tune/speed program to measure the various functions directly.
>
> $ cd tune
> $ make speed
> [snip]
> $ ./speed -c -s1-500 -f1.4 mpn_mul_basecase mpn_kara_mul_n mpn_toom3_mul_n
> overhead 6.06 cycles, precision 10000 units of 4.56e-10 secs, CPU freq
> king> 2192.19 MHz
>        mpn_mul_basecase mpn_kara_mul_n mpn_toom3_mul_n
> 1              #25.18           n/a           n/a
> 2              #48.34        168.20           n/a
> 3              #79.56        250.84           n/a
> 4             #125.12        259.46           n/a
> 5             #179.32        340.70           n/a
> 7             #288.47        500.67           n/a
> 9             #546.90        762.40           n/a
> 12            #883.00        990.18           n/a
> 16           #1426.75       1440.50           n/a
> 22           #2482.60       2737.00       5593.50
> 30           #4341.00       4390.00       7159.50
> 42            8086.00      #7449.50       9831.00
> 58           14882.00     #12984.00      16218.00
> 81           28120.00     #22529.00      24048.00
> 113          53656.00     #39188.00      39234.00
> 158         103582.00      66951.00     #65582.00
> 221         200328.00     116396.00    #110659.00
> 309         389771.00     199235.00    #184190.00
> 432         757818.00     339379.00    #305710.00
>
> --
> Torbjörn



--
Best regards,

Lingchuan Meng