Boost logo

Ublas :

Date view Thread view Subject view Author view

Subject: Re: [ublas] Matrix multiplication performance
From: palik imre (imre_palik_at_[hidden])
Date: 2016-01-24 02:50:30

Hi Michael,

I had a look on your AVX microkernel on my old AMD box. Congratulations, it is twice as fast as what I managed to get out of my optimised C kernel.

I wonder if I can catch up with that using newer gcc + SIMD arrays or intrinsics.

Cheers,

Imre

--------------------------------------------
On Fri, 22/1/16, Michael Lehn <michael.lehn_at_[hidden]> wrote:

 Subject: Re: [ublas] Matrix multiplication performance
 To: "palik imre" <imre_palik_at_[hidden]>
 Cc: "ublas mailing list" <ublas_at_[hidden]>
 Date: Friday, 22 January, 2016, 21:27
 
 Wow Imre!
 
 Ok, that is actually a
 significant difference :-)
 
 I have just added a new version to my site. 
 Unfortunately the computer I used for creating
 the page does not have posix_memalign().  So I
 had to hack my own function for that.  But
 I think for a proof of concept it will do.
 
 But most of all I also added
 micro-kernel that are (fairly) optimised for AVX and FMA. 
 The
 micro-kernel for AVX require MR=4,
 NR=8.  For FMA it requires MR=4, NR=16.  Otherwise
 the reference implementation gets selected. 
 For all parameters default values now can be
 overwritten when compiling, e.g.
 
 Â Â Â  g++ -O3 -Wall
 -std=c++11 -DHAVE_AVX  -DBS_D_MC=512  matprod.cc
 
 The optimised micro kernels
 are only included when compiled with -DHAVE_AVX or
 -DHAVE_FMA
 
 I put all this
 stuff here
 
 Â Â Â  http://www.mathematik.uni-ulm.de/~lehn/test_ublas/session2/page01.html
 
 also the tar-ball
 
 Â Â Â  http://www.mathematik.uni-ulm.de/~lehn/test_ublas/session2.tgz
 
 contains all required
 files:
 
 Â Â Â 
 session2/avx.hpp
 Â Â Â  session2/fma.hpp
 Â Â Â  session2/gemm.hpp
 Â Â Â 
 session2/matprod.cc
 
 Of
 course I would be interested how all this performs on other
 platforms.
 
 
 Cheers,
 
 Michael
 
 
 On 22
 Jan 2016, at 16:20, palik imre <imre_palik_at_[hidden]>
 wrote:
 
> Hi All,
>
> In the meantime I
 enabled avx2 ...
>
>
 Theoretical CPU performance maximum: clock * vector-size *
 ALUs/Core * 2 ~ 69.6GFLOPS
> So it is at
 ~25%
>
> Compiler is
 gcc 4.8.3
>
> vanilla
 run:
> $ g++ -Wall -W -std=gnu++11 -Ofast
 -march=core-avx2 -mtune=core-avx2 -g -DNDEBUG -I gemm -o
 matprod matprod.cc
> $ ./matprod
> #   m     n 
 Â Â Â k  uBLAS:   t1   
 Â Â Â MFLOPS   Blocked:   t2 
 Â    MFLOPS        Diff nrm1
>   100   100   100 
 0.000350402      5707.73      0.00116104     
 1722.59               0
>   200   200   200   0.00445094 
 Â    3594.74      0.00819996      1951.23       
 Â       0
>   300   300   300 
 Â  0.0138515      3898.49       0.0266515 
 Â    2026.15     1.06987e-06
>   400   400   400 
 Â  0.0266447      4803.96       0.0613506 
 Â    2086.37     4.01475e-06
>   500   500   500 
 Â  0.0424372      5891.06        0.119345     
 2094.77     8.99605e-06
>   600   600   600 
 Â  0.0724648      5961.51        0.203187     
 2126.12     1.63618e-05
>   700   700   700 
 Â Â Â 0.115464      5941.25        0.325834 
 Â    2105.36     2.69547e-05
>   800   800   800 
 Â Â Â 0.173003      5918.98        0.480655 
 Â    2130.43     4.09449e-05
>   900   900   900 
 Â Â Â 0.248077       5877.2       
 0.689972      2113.13     5.87376e-05
>  1000  1000  1000      0.33781   
 Â  5920.49        0.930591      2149.17 
 Â Â Â 8.16264e-05
>  1100 
 1100  1100       0.5149      5169.93   
 Â     1.25507         2121 
 Â Â Â 0.000108883
>  1200 
 1200  1200     0.670628      5153.38     
 Â Â Â 1.62732      2123.74 
 Â Â Â 0.000141876
>  1300 
 1300  1300     0.852692      5153.09     
 Â Â Â 2.06708      2125.71 
 Â Â Â 0.000180926
>  1400 
 1400  1400      1.06695      5143.65     
 Â Â Â 2.56183      2142.22 
 Â Â Â 0.000225975
>  1500 
 1500  1500       1.3874   
 Â Â Â 4865.2         3.16532     
 2132.49     0.000278553
> 
 1600  1600  1600      1.77623      4612.03     
 Â    3.8137      2148.05     0.000338106
>  1700  1700  1700   
 Â Â Â 2.3773      4133.26     
 Â Â Â 4.56665      2151.69 
 Â Â Â 0.000404458
>  1800 
 1800  1800      3.06381      3807.03     
 Â Â Â 5.40317      2158.73      0.00048119
>  1900  1900  1900   
 Â Â Â 3.9039      3513.92     
 Â Â Â 6.37295      2152.53 
 Â Â Â 0.000564692
>  2000 
 2000  2000      4.79166      3339.13     
 Â Â Â 7.43399      2152.28 
 Â Â Â 0.000659714
>  2100 
 2100  2100      6.04946      3061.76     
 Â Â Â 8.62429      2147.65 
 Â Â Â 0.000762223
>  2200 
 2200  2200      7.39085       2881.4   
 Â     9.86237      2159.32 
 Â Â Â 0.000875624
>  2300 
 2300  2300      9.00453      2702.42     
 Â Â Â 11.2513      2162.78      0.00100184
>  2400  2400  2400      10.3952   
 Â  2659.68         12.7491      2168.62 
 Â    0.00113563
>  2500  2500  2500 
 Â    12.2283      2555.55     
 Â Â Â 14.4615      2160.92      0.00128336
>  2600  2600  2600      13.8912   
 Â  2530.51         16.1965      2170.34 
 Â    0.00144304
>  2700  2700  2700 
 Â     15.391      2557.72     
 Â Â Â 18.1998      2162.99      0.00161411
>  2800  2800  2800      17.5673   
 Â  2499.19         20.2171      2171.63 
 Â    0.00180035
>  2900  2900  2900 
 Â    19.4621      2506.31     
 Â Â Â 22.5482      2163.28      0.00199765
>  3000  3000  3000      21.4506   
 Â  2517.42         24.9477      2164.53 
 Â    0.00221028
>  3100  3100  3100 
 Â      23.71      2512.95     
 Â Â Â 27.5144      2165.48      0.00243877
>  3200  3200  3200      25.9051   
 Â  2529.85         30.2816      2164.22 
 Â    0.00267766
>  3300  3300  3300 
 Â    28.1949      2549.18          33.176     
 2166.45      0.00293379
>  3400 
 3400  3400      30.7235      2558.56     
 Â Â Â 36.0156      2182.61   
 Â Â Â 0.0032087
>  3500  3500 
 3500      34.0419      2518.95     
 Â Â Â 39.3929      2176.79      0.00349827
>  3600  3600  3600      37.0562   
 Â  2518.12         42.7524      2182.62 
 Â    0.00380447
>  3700  3700  3700 
 Â    39.7885      2546.11     
 Â Â Â 46.4748      2179.81      0.00412621
>  3800  3800  3800      43.6607   
 Â  2513.56         50.2119      2185.62 
 Â     0.0044694
>  3900 
 3900  3900      46.5104      2550.78     
 Â Â Â 54.4822      2177.56      0.00482355
>  4000  4000  4000      50.6098   
 Â  2529.15         58.7686      2178.03 
 Â    0.00520289
>
>
 tuned run:
>
> $ g++
 -Wall -W -std=gnu++11 -Ofast -march=core-avx2
 -mtune=core-avx2 -g -DNDEBUG -I gemm -o matprod2
 matprod2.cc
> $ ./matprod2
> #   m     n 
 Â Â Â k  uBLAS:   t1   
 Â Â Â MFLOPS   Blocked:   t2 
 Â    MFLOPS        Diff nrm1
>   100   100   100 
 0.000351671      5687.13     0.000316612   
 Â  6316.88               0
>   200   200   200   0.00419531 
 Â    3813.78      0.00159044      10060.1       
 Â       0
>   300   300   300 
 Â  0.0141153      3825.62      0.00421113     
 12823.2     1.07645e-06
>   400   400   400 
 Â  0.0291599      4389.59      0.00858138       
 14916     4.00614e-06
>   500   500   500 
 Â  0.0483492      5170.72       0.0166519 
 Â    15013.3     8.96808e-06
>   600   600   600 
 Â  0.0725783      5952.19       0.0279634 
 Â    15448.7     1.63386e-05
>   700   700   700 
 Â Â Â 0.113891      6023.29        0.043077 
 Â      15925     2.69191e-05
>   800   800   800 
 Â Â Â 0.171416      5973.79   
 Â Â Â 0.0627796        16311 
 Â Â Â 4.09782e-05
>   900   900   900 
 Â Â Â 0.243677      5983.32   
 Â Â Â 0.0922766      15800.3 
 Â Â Â 5.88092e-05
>  1000 
 1000  1000     0.335158      5967.33     
 Â  0.123339      16215.5     8.15988e-05
>  1100  1100  1100 
 Â Â Â 0.515776      5161.15     
 Â Â Â 0.16578      16057.5 
 Â Â Â 0.000108991
>  1200 
 1200  1200     0.662706      5214.98     
 Â  0.205989      16777.6     0.000141824
>  1300  1300  1300 
 Â Â Â 0.845952      5194.15     
 Â Â Â 0.27637        15899      0.00018111
>  1400  1400  1400      1.06712   
 Â  5142.82        0.332118      16524.2 
 Â Â Â 0.000225958
>  1500 
 1500  1500      1.38147      4886.11       
 0.409224      16494.6     0.000278265
>  1600  1600  1600      1.72238   
 Â  4756.21        0.492314      16639.8 
 Â Â Â 0.000338095
>  1700 
 1700  1700      2.38508      4119.77       
 0.603566      16279.9     0.000404362
>  1800  1800  1800      3.12034   
 Â  3738.05        0.717409      16258.5 
 Â Â Â 0.000481575
>  1900 
 1900  1900      3.93668      3484.66       
 0.824933      16629.2     0.000564727
>  2000  2000  2000      4.76038   
 Â  3361.07        0.941643      16991.6     
 0.00065862
>  2100  2100  2100     
 5.90627      3135.99         1.12226   
 Â  16504.2     0.000762307
>  2200  2200  2200      7.26419   
 Â  2931.64         1.28213      16609.9 
 Â Â Â 0.000876699
>  2300 
 2300  2300      8.88171      2739.79     
 Â Â Â 1.45247      16753.5      0.00100222
>  2400  2400  2400      10.4956   
 Â  2634.26         1.62705      16992.7 
 Â    0.00113566
>  2500  2500  2500 
 Â     11.913      2623.18     
 Â Â Â 1.87499      16666.7      0.00128371
>  2600  2600  2600      13.7057   
 Â  2564.77          2.1156      16615.6     
 0.00144259
>  2700  2700  2700     
 15.5959      2524.13         2.33957   
 Â  16826.1      0.00161501
>  2800 
 2800  2800      17.1121      2565.67     
 Â Â Â 2.57445      17053.8      0.00179901
>  2900  2900  2900      19.4167   
 Â  2512.16         2.92445      16679.4 
 Â    0.00199764
>  3000  3000  3000 
 Â    21.3239      2532.37     
 Â Â Â 3.18891      16933.7      0.00220999
>  3100  3100  3100      23.5049   
 Â  2534.88          3.5305      16876.4     
 0.00243845
>  3200  3200  3200     
 25.7362      2546.45         3.81708   
 Â  17169.1      0.00267581
>  3300 
 3300  3300      28.4467      2526.62     
 Â Â Â 4.25869        16877      0.00293513
>  3400  3400  3400      30.4607   
 Â  2580.63         4.67999      16796.6 
 Â    0.00320688
>  3500  3500  3500 
 Â    33.7737      2538.96     
 Â Â Â 5.04289      17004.1      0.00349667
>  3600  3600  3600      36.9633   
 Â  2524.45           5.414      17235.3 
 Â    0.00380237
>  3700  3700  3700 
 Â    39.5153      2563.71     
 Â Â Â 6.04875      16748.2      0.00412583
>  3800  3800  3800      42.9412   
 Â  2555.68         6.48985      16910.1 
 Â    0.00446785
>  3900  3900  3900 
 Â    46.5282      2549.81     
 Â Â Â 7.05844        16808      0.00482701
>  4000  4000  4000      50.2218   
 Â  2548.69         7.42442      17240.4 
 Â    0.00520272
>
>
 As the generated machine code is completely different, I
 guess gcc notices the aligned alloc, and uses the alignment
 information for optimisation.
>
> Cheers,
>
> Imre
>
>
> On Friday, 22
 January 2016, 15:09, Michael Lehn <michael.lehn_at_[hidden]>
 wrote:
>
>
> Hi Imre,
>
> thanks for running the benchmarks.  Of
 course you are right that using aligned memory for the
 buffers improves
> performance.  I also
 did not really put any effort in optimising the parameters
 MC, NC, KC, MR and NR.  I will
> compare
 different variants and report them on the website
>
>     http://www.mathematik.uni-ulm.de/~lehn/test_ublas/index.html
>
> I modified my
 benchmark program such that it also computes the FLOPS as
>
>     FLOPS =
 2*m*n*k/time_elpased
>
> See
>
>     http://www.mathematik.uni-ulm.de/~lehn/test_ublas/download/session1/matprod.cc
>
> Could you re-run
 your benchmarks and post the different MFLOPS you get? That
 is important for actually tuning thing.
>
 On my machine my code only reaches 20% of the peak
 performance (about 5 GFLOPS instead of 25.6
 GFLOPS).   So
> a speedup of
 2.5 would be impressive but still far from peak
 performance.
>
>
 Cheers,
>
>
 Michael
>
>
> On 22 Jan 2016, at 11:03, palik imre
 <imre_palik_at_[hidden]>
 wrote:
>
>> Sorry
 for posting twice more or less the same thing.  I got
 confused with javascript interfaces.
>>
>> It seems I
 also forgot to enable avx for my last measurements.  With
 that + my blocking and alignment changes, performance
 according to my tests is something like 250% higher than
 running Michael's original code (with avx).
>>
>> Cheers,
>>
>> Imre
>>
>>
>> On Friday, 22 January 2016, 10:33,
 palik imre <imre_palik_at_[hidden]>
 wrote:
>>
>>
 
>> Hi Michael,
>>
>> your
 blocksizes are far from optimal.  MR & NR should be
 multiples of the L1 cache line size (i.e. 16 for double on
 Intel).  Also, the blocks should be allocated aligned to L1
 cache lines (e.g., via posix_memalign()).
>>
>> This alone
 brought something like 50% speedup for my square matrix
 test.
>>
>> I
 will have a look at the other parameters + the whole thing
 via perf during the weekend.
>>
>> Cheers,
>>
>> Imre
>>
>>
>>
>> On Friday, 22 January 2016, 0:28,
 "ublas-request_at_[hidden]"
 <ublas-request_at_[hidden]>
 wrote:
>>
>>
 
>> Subject: Re: [ublas] Matrix
 multiplication performance
>>
 Message-ID: <7FA49567-4580-4C7F-9B9E-43E08E78E14B_at_[hidden]>
>> Content-Type: text/plain;
 charset="windows-1252"
>>
 
>> Hi Nasos,
>>
 
>> first of all I don?t want to take
 wrong credits and want to point out that this is not my
 algorithm.  It is based on
>>
>>     http://www.cs.utexas.edu/users/flame/pubs/blis2_toms_rev3.pdf
>>
>> 
 Â Â Â https://github.com/flame/blis
>>
>> For a few
 cores (4-8) it can easily made multithreaded.  For
 many-cores like Intel Xeon Phi this is a bit more
>> sophisticated but still not too
 hard.  The demo I posted does not use micro kernels that
 exploit SSE, AVX or
>> FMA
 instructions.  With that the matrix product is on par with
 Intel MKL.  Just like BLIS. For my platforms I wrote
>> my own micro-kernels but the interface
 of function ugemm is compatible to BLIS.
>>
>> Maybe you
 could help me to integrate your code in the benchmark
 example I posted above.
>>
>> About Blaze:  Do they have their own
 implementation of a matrix-matrix product?  It seems to
 require a
>> tuned BLAS implementation
 (?Otherwise you get only poor performance?) for the
 matrix-matrix product.
>> IMHO they
 only have tuned the ?easy? stuff like BLAS Level1 and
 Level2.  In that case it makes more
>> sense to compare the performance with
 the actual underlying GEMM implementation.  But if I am
 wrong,
>> let me know.
>>
>> About the
 block size: In my experience you get better performance if
 you chose them dynamically at runtime
>> depending on the problem size. 
 Depending on the architecture you can just specify ranges
 like 256 - 384 for
>> blocking factor
 MC.  In my code it then also needs to satisfy the
 restriction that it can be divided by factor MR.
>> I know that doing things at compile
 time is a C++ fetish.  But the runtime overhead is
 negligible and having
>> blocks of
 similar sizes easily pays of.
>>
>> Cheers,
>>
>> Michael
>>
 *************************************
>>
>>
>>
>>
>>
 _______________________________________________
>> ublas mailing list
>> ublas_at_[hidden]
>> http://lists.boost.org/mailman/listinfo.cgi/ublas
>> Sent to: michael.lehn_at_[hidden]
>
>
>

Date view Thread view Subject view Author view