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

Groups > comp.lang.forth > #59653

Re: matrix multiplication

Show all headers | View raw

krishna.myneni@ccreweb.org writes:
>On Sunday, May 21, 2017 at 2:51:44 AM UTC-5, Anton Ertl wrote:
>> krishna...org writes:
>> >A next step could be to do the computations in parallel on a multi-core =
>system, following the example I posted earlier:
>> >
>> >ftp://ccreweb.org/software/kforth/examples/parallel-mm.4th
>> >
>> >Do gforth, vfxlin, and swift forth provide fork and mmap syscalls, or eq=
>uivalents?
>>=20
>> There is multi-threading support in these systems (for Gforth in the
>> development version) that you could use; then you also don't need to
>> share the memory with mmap.
>>=20
>
>But I think the idea of forking the process, rather than using threads has =
>some potentially significant benefits to the programmer. The child process(=
>es) inherit a copy of all the code and data memory of the parent, and this =
>eliminates a lot of worries about code re-entrancy and mutexes. The big dat=
>a would be held in shared memory, and, for some cases, mutexes for the shar=
>ed memory may be required, but not for matrix multiplication. Each process =
>writes into a separate area of the shared memory even when the output matri=
>x is contiguous.

Use user variables for the stuff you don't want to be shared, and you
are fine.

>> However, my next step would be to implement cache blocking.  While the
>> slowdown from going beyond the cache is (to me) surprisingly low for
>> the FAXPY-based version, that is on a system that is otherwise idle
>> (interestingly both on my PC and on the Odroid C2).  If the system
>> makes more use of its multiple cores, and especially if you want to
>> have several instances of matrix multiply running on them,using less
>> main memory bandwidth by using cache blocking should help.
>>=20
>
>Dealing with the processor cache is one area in which I'm not well versed. =
>Are there instructions for blocking and unblocking the cache? I assumed the=
> cache was largely independent of programmer control.

Cache blocking means that you process the data in blocks that fit in
the cache.  There are no special instructions for it.  The cache is
handled mostly transparently (apart from performance) by the CPU, but
programmers who know how they work can make use of that knowledge to
get better performance.

In the present case, if we look at your inner-product-based matrix
multiplication, you compute

C[i,j] = A[i,.] * B[.,j]

B[.,j] makes good use of spatial locality (typically, 8 elements of
B[.,j] fit in one cache line), A[i,.] doesn't.

But if we assume that all elements of A[i,.] fit in the cache level of
interest here, you can reuse the elements of A[i,.] by first computing
several elements of C[i,.] before changing the i.

However, if you compute all elements of C[i,.] before changing the i,
the whole B matrix will be read, so you have no temporal locality on
B.  So let's compute several elements of C[i,0..15] first, then
C[i+1,0..15] etc. until C[i+15,0..15]; in this way you need only
A[i..i+15,.] and B[.,0..15] in the cache, for computing 256 elements
of C.  Then compute the next 256 elements of C, e.g.,
C[i..i+15,16..31]; this will reuse the data from A, but load the next
block of B data into the cache.

The block sizes can be adapted to the cache sizes, or you can use
recursion to have blocking at a lot of sizes (some of which will be
good fits for the cache sizes).

>Isn't explicit use of the SSE2 instructions considered vectorization?=20

If you are using SIMD/vector instructions (e.g., MULPD), yes.  If you
are using scalar instructions (e.g., MULSD), no.

- 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