6 ms·

Another technique is to transpose the left matrix so each dot product is scanned in row-order and hence more cache friendly. Another one I tried ages ago is to

Another technique is to transpose the left matrix so each dot product is scanned in row-order and hence more cache friendly. Another one I tried ages ago is to use a single loop counter and "de-interleave" the bits to get what would normally be 3 distinct loop variables. For this you need to modify the entry in the result matrix rather than having it write-only. It has the effect of accessing like a z-order curve but in 3 dimensions. It's a bit of overhead, but you can also unroll say 8 iterations (2x2x2) which helps make up for it. This ends up making good use of both caches and even virtual memory if things don't fit in RAM. OTOH it tends to prefer sizes that are a power of 2.

dralley 5y ago
The compiler will sometimes do this transpose for you, but as with all compiler optimizations it might sometimes break.
- melissalobos 5y ago
  That sounds very interesting, is the anywhere I can read more about this optimization? I didn't know any compiler could do optimizations like that.
  - kanaffa12345 5y ago
    there is no way a general purpose compiler will figure this out. op is probably talking about something like halide or tvm or torchscript jit.
    - deleted 5y ago
      [deleted]
    - astrange 5y ago
      https://polly.llvm.org https://polly.llvm.org is a research project that could possibly maybe do this.
      - kanaffa12345 5y ago
        a polyhedral compiler wouldn't find this either - polyhedral compilation is for finding optimal schedules for loop nests i.e., the order in which independent (wrt dataflow) iterations run. as far as i know you, a transpose can't be expressed in the polyhedral model.
        astrange 5y ago
        Hmm I thought GCC's polyhedral optimizations had a loop transposition, but it turned out I was remembering an old "-floop-transpose" flag that seems to be only in old Apple GCC to get a SPEC win…
- phkahler 5y ago
  The transpose is irrelevant after moving on to z-order access patterns and the 3d equivalent. Not quite as possible to reach peak sustained performance but well worth the trade in simplicity IMO.
cerved 5y ago
You can get extremely creative in optimizing matrix mulplication for cache and SIMD.
- jacobolus 5y ago
  For contexts like the web, also check out cache-oblivious matrix multiplication https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2 https://dspace.mit.edu/bitstream/handle/1721.1/80568/4355819...
gfd 5y ago
I really like these set of lecture notes for optimizing matrix multiplication: https://ppc.cs.aalto.fi/ch2/v7/ https://ppc.cs.aalto.fi/ch2/v7/ (The transpose trick is used in v1)
- progbits 5y ago
  This deserves it's own submission, wonderful resource!
- eigenvalue 5y ago
  I find it surprising that, even after using all those tricks, they are still only to achieve around 50% of the theoretical peak performance of the chip in terms of GFLOPS. And that's for matrix multiplication, which is a nearly ideal case for these techniques.
  - gfd 5y ago
    Hmm where did you see that? In the graph at the bottom of v7, it got "93% of the theoretical maximum performance"
mynameismon 5y ago
Another very very interesting optimisation can be found in these lecture slides [0]. (Scroll to slide 28, although the entire slide deck is amazing) [0]: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-slides/MIT6_172F18_lec1.pdf https://ocw.mit.edu/courses/electrical-engineering-and-compu...
- infogulch 5y ago
  Loop order and in-memory striding choice in general is a pretty interesting. I worked on an old voxel-based game engine that used a very complicated on-disk storage format. It seemed.. unnecessary, so I experimented with very simplified strategy of literally writing out voxel color bytes to a stream and gzipping it, which turned out to be both faster and smaller in my application. iirc it was like 10x smaller but only if I used the right striding order. I knew that the striding order benefits would only work on voxel data similar to the data I was testing on, and I wanted to generalize it so that it could be configured dynamically so each dataset could use the best striding order for that particular data. I tried setting up numpy ndarray so that you could configure the memory striding order independently of the array indices so that my code wouldn't have to change if the striding order changed, but I could never get it to work and unfortunately I wasn't able to convince numpy folks I interacted with that this feature would be helpful.
3836293648 5y ago
Assuming you're only using the left matrix once, surely the action of transposing it would slow it down so much that any gains are lost
- kanaffa12345 5y ago
  you don't transpose it before the matmul, you always have it transposed (i.e., when you print the weights of a linear layer in pytorch, you're actually seeing (A^t)^t and what's stored is A^t.
- hddqsb 5y ago
  Matrix multiplication is O(n^3), while transposing is O(n^2). So for a large matrix, transposing will only take a tiny fraction of the time spent in multiplication. (But the loop reordering trick mentioned in @mynameismon's link is a very nice alternative.)

dralley 5y ago

The compiler will sometimes do this transpose for you, but as with all compiler optimizations it might sometimes break.

melissalobos 5y ago
That sounds very interesting, is the anywhere I can read more about this optimization? I didn't know any compiler could do optimizations like that.
- kanaffa12345 5y ago
  there is no way a general purpose compiler will figure this out. op is probably talking about something like halide or tvm or torchscript jit.
  - deleted 5y ago
    [deleted]
  - astrange 5y ago
    https://polly.llvm.org https://polly.llvm.org is a research project that could possibly maybe do this.
    - kanaffa12345 5y ago
      a polyhedral compiler wouldn't find this either - polyhedral compilation is for finding optimal schedules for loop nests i.e., the order in which independent (wrt dataflow) iterations run. as far as i know you, a transpose can't be expressed in the polyhedral model.
      - astrange 5y ago
        Hmm I thought GCC's polyhedral optimizations had a loop transposition, but it turned out I was remembering an old "-floop-transpose" flag that seems to be only in old Apple GCC to get a SPEC win…
phkahler 5y ago
The transpose is irrelevant after moving on to z-order access patterns and the 3d equivalent. Not quite as possible to reach peak sustained performance but well worth the trade in simplicity IMO.

cerved 5y ago

You can get extremely creative in optimizing matrix mulplication for cache and SIMD.

jacobolus 5y ago
For contexts like the web, also check out cache-oblivious matrix multiplication https://dspace.mit.edu/bitstream/handle/1721.1/80568/43558192-MIT.pdf;sequence=2 https://dspace.mit.edu/bitstream/handle/1721.1/80568/4355819...

gfd 5y ago

I really like these set of lecture notes for optimizing matrix multiplication: https://ppc.cs.aalto.fi/ch2/v7/ https://ppc.cs.aalto.fi/ch2/v7/ (The transpose trick is used in v1)

progbits 5y ago
This deserves it's own submission, wonderful resource!
eigenvalue 5y ago
I find it surprising that, even after using all those tricks, they are still only to achieve around 50% of the theoretical peak performance of the chip in terms of GFLOPS. And that's for matrix multiplication, which is a nearly ideal case for these techniques.
- gfd 5y ago
  Hmm where did you see that? In the graph at the bottom of v7, it got "93% of the theoretical maximum performance"

mynameismon 5y ago

Another very very interesting optimisation can be found in these lecture slides [0]. (Scroll to slide 28, although the entire slide deck is amazing) [0]: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/lecture-slides/MIT6_172F18_lec1.pdf https://ocw.mit.edu/courses/electrical-engineering-and-compu...

infogulch 5y ago
Loop order and in-memory striding choice in general is a pretty interesting. I worked on an old voxel-based game engine that used a very complicated on-disk storage format. It seemed.. unnecessary, so I experimented with very simplified strategy of literally writing out voxel color bytes to a stream and gzipping it, which turned out to be both faster and smaller in my application. iirc it was like 10x smaller but only if I used the right striding order. I knew that the striding order benefits would only work on voxel data similar to the data I was testing on, and I wanted to generalize it so that it could be configured dynamically so each dataset could use the best striding order for that particular data. I tried setting up numpy ndarray so that you could configure the memory striding order independently of the array indices so that my code wouldn't have to change if the striding order changed, but I could never get it to work and unfortunately I wasn't able to convince numpy folks I interacted with that this feature would be helpful.

3836293648 5y ago

Assuming you're only using the left matrix once, surely the action of transposing it would slow it down so much that any gains are lost

kanaffa12345 5y ago
you don't transpose it before the matmul, you always have it transposed (i.e., when you print the weights of a linear layer in pytorch, you're actually seeing (A^t)^t and what's stored is A^t.
hddqsb 5y ago
Matrix multiplication is O(n^3), while transposing is O(n^2). So for a large matrix, transposing will only take a tiny fraction of the time spent in multiplication. (But the loop reordering trick mentioned in @mynameismon's link is a very nice alternative.)