[Patch, libgfortran] PR21468 Vectorizing matmul, other perf improvements

[Janne Blomqvist]

On Sun, Nov 13, 2005 at 08:48:55PM +0100, Thomas Koenig wrote:
> On Sun, Nov 13, 2005 at 05:52:37PM +0200, Janne Blomqvist wrote:
> 
> > I have looked at PR21468, "Vectorizing libgfortran". The attached
> > patch enables vectorizing the main loop for matmul in case of unit
> > stride. It doesn't change the code much, only adds const and restrict
> > appropriately to the type declarations, so that the vectorizer can
> > safely vectorize the main loop. 
> 
> This is OK.  You can commit this part.

Thanks; I'll do that tomorrow evening, unless somebody objects before
then.

> > Another thing that it does is enabling -funroll-loops for matmul_* and
> > matmull_*. This is actually a bigger performance booster than
> > vectorizing, almost doubling performance.
> 
> I fear that this may be platform-dependant.  Loop unrolling may
> be a big win for architectures with many registers, while on
> architectures with few registers, such as i686, it may cause
> performance degradation.

Yes, but I tested on i686. I don't think we'll find a more register
starved architecture than that in widespread use. ;-) Well, embedded
is of course an entire world on its own, but they can surely compile
with -Os if they ever want libgfortran.

But you're of course right that testing on other platforms, and even
different x86/x86-64 cpu:s, would be nice to have.

> Maybe this needs to become platform-dependent.  I think we need
> some more benchmarks here.

I wrote a small benchmark to test matmul performance at different
sizes, attached to this mail. Unfortunately that benchmark failed to
prove my point that unrolling almost doubles performance (which I
somehow managed to see in another even more ad hoc benchmark). Oh, the
joys of benchmarking. Anyway, there is still quite a speedup:

Results on Athlon 1200 MHz, 256 KB cache.

With -funroll-loops:

 Matrix side size    Speed (Gflops/s)    Loop count
 =================================================
    2               0.063                 33333333
    4               0.238                  3571428
    8               0.453                   416666
   16               0.658                    50403
   32               0.768                     6200
   64               0.850                      768
  128               0.775                       95
  256               0.509                       11
  512               0.158                        1
 1024               0.157                        1

Without loop unrolling:

 Matrix side size    Speed (Gflops/s)    Loop count
 =================================================
    2               0.059                 33333333
    4               0.226                  3571428
    8               0.486                   416666
   16               0.470                    50403
   32               0.593                     6200
   64               0.663                      768
  128               0.682                       95
  256               0.466                       11
  512               0.152                        1
 1024               0.151                        1

At small sizes, the execution speed is dimished due to overhead, and
with larger sizes the performance is memory bound. For 128x128 the
matrices still fit onto L2 cache. As libgfortran matmul isn't blocked,
the performance rapidly drops as it spills into main memory. At
intermediate sizes, we see the advantage of -funroll-loops, for 16x16,
32x32 and 64x64 there is a speedup of 40%, 30% and 28%, respectively.

-- 
Janne Blomqvist
-------------- next part --------------
program matmul_bench
  implicit none

  integer, parameter :: wp = selected_real_kind(4), &
       dp = selected_real_kind(15)

  call runbench (1500)

contains

  ! Run matrix mult benchmark with different sized arrays.
  subroutine runbench (nmax)
    integer, intent(in) :: nmax
    real(wp), allocatable, dimension(:,:) :: a, b, res
    integer :: n, loop
    real(dp) :: time, flops

    print *, 'Matrix side size    Speed (Gflops/s)    Loop count'
    print *, '================================================='
    n = 2
    do
       allocate (a(n,n), b(n,n), res(n,n))
       call random_number (a)
       call random_number (b)
       ! matmul for square matrix is (2n-1)*n**2 flops. Assuming on
       ! average 1 gflop/s cpu, 4e8 flops takes about 0.4 seconds and
       ! should be enough.
       flops = (2 * n - 1) * n**2
       loop = max (int (4.0e8_dp / flops), 1)
       call matmul_timing (a, b, res, loop, time)
       print '(I5,14X,F6.3,15X,I10)', n, flops * real(loop, dp) / time / 1.0e9_dp, loop
       deallocate (a, b, res)
       n = n * 2
       if (n > nmax) exit
    end do
  end subroutine runbench

  ! Actual routine, and timing.
  subroutine matmul_timing (a, b, res, loop, time)
    real(wp), intent(in), dimension(:, :) :: a, b
    real(wp), intent(inout) :: res(:,:)
    integer, intent(in) :: loop
    real(dp), intent(out) :: time
    real(dp) :: t1, t2
    integer :: i

    call cpu_time (t1)
    do i = 1, loop
       res = matmul (a, b)
    end do
    call cpu_time (t2)
    time = t2 - t1
  end subroutine matmul_timing

    
end program matmul_bench
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 185 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20051113/46a95a4e/attachment.sig>