Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #59559

Re: matrix multiplication

Show all headers | View raw

krishna.myneni@ccreweb.org writes:
>On Wednesday, May 17, 2017 at 5:13:50 PM UTC-5, krishna...@ccreweb.org wrot=
>e:
>> ... I spent an hour writing a full matrix multiplier for an integrated st=
>ack system, source below. ...
>
>The row offsets may be precomputed for the two matrices to be multiplied. T=
>he revised Forth source is given below.

I took this code, replaced occurences of A@ with @ and replaced

>        J I df_mul_r1c2 2 pick f!
>        dfloat+

with

        J I rot >r df_mul_r1c2 r@ f!
        r> dfloat+

and the result seems to be working; I did not find this replacement
trivial, BTW.  I also produced a version of the inner loop that works
only on separate-stack systems (i.e., Forth-2012):

Forth-94                            Forth-2012
nc1 @ 0 DO                          nc1 @ 0 DO        
  2dup 2>r >r f@ r> f@ f* f+          2dup f@ f@ f* f+
  2r> roffs2 @ + >r                   roffs2 @ + >r   
  dfloat+ r>                          dfloat+ r>      
LOOP                                LOOP              

Results for a 500x500 matrix multiply on a Core i5-6600K:

Forth-94 Forth-2012 Forth-2012 Forth-94 Forth-94 
Myneni  Myneni/Ertl     Ertl   Rees/Ertl   pahihu 
109966M     107831M    1046M       1202M    1517M vfxlin Ndp387.fth
  2986M       2260M    2220M       2945M    2764M gforth-fast
  4028M       4076M    4844M       5067M    5017M SwiftForth HW stack, no WAIT

I don't know what in this code slows down VFX so much.  It does not
appear to be the classical code-close-to-written-data problem (the
inner loop does not write data close to the code, and the number of
icache misses (2.8M) is not high enough to explain such a big number
of cycles).  The code generated by VFX (see below) for the inner loop
looks inconspicuous to me.

SwiftForth benefits from having only 5 (instead of 8 for the other
variants) FP words (i.e., call-return pairs) in the inner loop.

Here's the code that VFX generates for the inner loop

( 080C6E60    DB2B )                  FLD       TBYTE 0 [EBX]
( 080C6E62    8B5500 )                MOV       EDX, [EBP]
( 080C6E65    DB2A )                  FLD       TBYTE 0 [EDX]
( 080C6E67    DEC9 )                  FMULP     ST(1), ST
( 080C6E69    DEC1 )                  FADDP     ST(1), ST
( 080C6E6B    031D70340A08 )          ADD       EBX, [080A3470]
( 080C6E71    53 )                    PUSH      EBX
( 080C6E72    8B5D00 )                MOV       EBX, [EBP]
( 080C6E75    83C308 )                ADD       EBX, 08
( 080C6E78    5A )                    POP       EDX
( 080C6E79    83042401 )              ADD       [ESP], 01
( 080C6E7D    8344240401 )            ADD       [ESP+04], 01
( 080C6E82    895D00 )                MOV       [EBP], EBX
( 080C6E85    8BDA )                  MOV       EBX, EDX
( 080C6E87    71D7 )                  JNO       080C6E60

Finally, Gforth also contains a primitive V* that fits the inner loop
of your matrix multiplication:

v* ( f_addr1 nstride1 f_addr2 nstride2 ucount -- r )

I implemented a variant of your inner word that uses V*:

: df_mul_r1c2 ( row1 col2 -- rsum )
    df_r1c2>a1a2 [ 1 floats ] literal swap roffs2 @ nc1 @ v* ;

Let's compare the version that uses V* with the version that uses FAXPY:

cycles
  faxpy       v*
   316M     562M  500x500
19.168M 120.710M 2000x2000

For the 500x500 case, the V* version is slower because the latency of
the F+ is a lower bound for the performance per iteration of V*,
because each F+ depends on the result of the F+ of the previous
iteration; by contrast, in faxpy the floating-point operations of each
iteration are independent of other iterations.

For the 2000x2000 case, the V* version is slower because it has no
spatial locality when accessing the column, so for each element of the
column, we see a cache miss, while the FAXPY version accesses
everything in a spatially local way; hmm, swapping the middle and the
outer loop around might help, by providing at least temporal locality
for the column.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2017: http://www.euroforth.org/ef17/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

matrix multiplication krishna.myneni@ccreweb.org - 2017-05-17 15:13 -0700
  Re: matrix multiplication stephen@mpeforth.com (Stephen Pelc) - 2017-05-17 22:31 +0000
    Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-17 15:39 -0700
      Re: matrix multiplication rickman <gnuarm@gmail.com> - 2017-05-18 03:22 -0400
        Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-18 00:29 -0700
          Re: matrix multiplication rickman <gnuarm@gmail.com> - 2017-05-18 03:48 -0400
          Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-18 08:42 +0000
  Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-18 00:25 -0700
    Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-19 15:13 +0000
      Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-19 17:26 +0000
        Re: matrix multiplication Alex <alex@rivadpm.com> - 2017-05-19 18:56 +0100
        Re: matrix multiplication Paul Rubin <no.email@nospam.invalid> - 2017-05-19 21:48 -0700
        Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-20 10:21 +0000
          Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-20 06:12 -0700
          Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-20 09:47 -0700
            Re: matrix multiplication Paul Rubin <no.email@nospam.invalid> - 2017-05-20 15:31 -0700
              Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-21 04:46 -0700
                Re: matrix multiplication mhx@iae.nl - 2017-05-21 13:41 -0700
                Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-21 15:32 -0700
            Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-21 07:19 +0000
              Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-21 05:10 -0700
                Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-21 14:29 +0000
                Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-21 09:17 -0700
      Re: matrix multiplication stephen@mpeforth.com (Stephen Pelc) - 2017-05-19 20:54 +0000
      Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-19 14:33 -0700
        Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-19 16:12 -0700
        Re: matrix multiplication anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2017-05-20 14:48 +0000
    Re: matrix multiplication krishna.myneni@ccreweb.org - 2017-05-19 18:38 -0700

csiph-web