Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Discovering faster matrix multiplication algorithms with reinforcement learning

nature.com

Post reply on HN
Print view View original

81–90 of 116 posts

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#81

Post by fulafel »

psychphysic wrote: post #36
atty wrote: post #29

Earlier quoted context omitted.

On the other hand, real world performance is really the only useful metric for matrix multiplication. I don’t really care about the theoretical performance, or the number of operations. Not disagreeing with your take that the claim is grandiose, just pointing out that finding a generalizable way to automate the improvement of what is almost certainly the most important mathematical operation a computer can do is wort…

Surely theoretical improvement begets real world, especially in the context of highly specialised hardware. It was with theoretical performance improvement that motivated the creation of SIMD and led to real world speed ups.

It's interesting how both SIMD and big-o have had so different reasons for being of limited but still significant relevance.

SIMD, and vector processors like it was called in the 70s, delivered practical speedups in simple benchmarks right away but most applications dont't take advantage because of SW engineering reasons. Whereas big-O improvement ignores important components of performance per unit of time (memory access and constant factors) and is purely theoretical in an essential sense.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#82

Post by vlovich123 »

Nihmie wrote: post #77
boole1854 wrote: post #27

Earlier quoted context omitted.

This is not a correct summary of the results of the paper. First, you cut out the initial part of the sentence about improving on Strassen's two-level algorithm. Here is the complete sentence: > Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. That is,…

To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1). Talking about scaling for a problem that has no scaling factor is a bit odd.

If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#83

Post by HarHarVeryFunny »

chrchang523 wrote: post #66
psychphysic wrote: post #36

Earlier quoted context omitted.

Surely theoretical improvement begets real world, especially in the context of highly specialised hardware. It was with theoretical performance improvement that motivated the creation of SIMD and led to real world speed ups.

Sometimes. In the case of matrix multiplication, there is a pretty large backlog of "galactic algorithms" going down to ~O(n^2.373) that haven't yet led to real-world improvements. Strassen's ~O(n^2.807) algorithm is only considered over the basic O(n^3) strategy for n>1000.

Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#85

Post by tlb »

throwawaymaths wrote: post #64
lifthrasiir wrote: post #63

Earlier quoted context omitted.

That assumption didn't age very well. In many if not most modern architectures multiplication still does take more cycles than addition but can have a higher throughput if scheduled well, and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.

> but can have a higher throughput if scheduled well Unlikely to be true for matrix multiplications, which have well-defined data dependencies. > and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition. Yes, this supports the assumption that multiplication is the heavy lift.

With sufficiently parallel hardware, you can do an entire mat4 * mat4 multiplication in 3 cycles. First do all 64 multiplications in parallel, then do 32 adds, then 16 adds to get the final answer.

For operations in GF(2) where they claim a result, a multiply is just an AND gate and an add is an XOR gate. So the fully parallel hardware version is 64 AND gates and 48 XOR gates, with a total gate delay of 3. This is a trivial amount of hardware and could easily be an instruction in some alternate universe where it was useful.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#87

Post by WFHRenaissance »

optimalsolver wrote: post #44

Now, were these algorithms discovered, or invented? I.e., have they always been there, just sitting in Platonic space waiting for a conscious mind to stumble across them, or have they just now popped into existence?

Discovered. I'd go as far to say that all "invention" is actually just discovery that we find useful.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#88

Post by chrchang523 »

HarHarVeryFunny wrote: post #83
chrchang523 wrote: post #66

Earlier quoted context omitted.

Sometimes. In the case of matrix multiplication, there is a pretty large backlog of "galactic algorithms" going down to ~O(n^2.373) that haven't yet led to real-world improvements. Strassen's ~O(n^2.807) algorithm is only considered over the basic O(n^3) strategy for n>1000.

Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.

My understanding is that the Winograd minimal filtering algorithms used in cuDNN are different from the O(n^2.37) Coppersmith-Winograd-descended matrix multiplication algorithms. But I acknowledge that these can be considered cousins, produced by the same line of research.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#89

Post by HarHarVeryFunny »

chrchang523 wrote: post #88
HarHarVeryFunny wrote: post #83

Earlier quoted context omitted.

Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.

My understanding is that the Winograd minimal filtering algorithms used in cuDNN are different from the O(n^2.37) Coppersmith-Winograd-descended matrix multiplication algorithms. But I acknowledge that these can be considered cousins, produced by the same line of research.

I'm pretty sure there's no difference. It does seem to be pretty hard to turn the theoretical win into a practical one - the GPU kernel needs to be coded extremely efficiently to match the underlying hardware. AFAIK it's only a win for 3x3 - maybe for one other size too. Originally Winograd wasn't supported by cuDNN on NVidia's Tensor Cores (matmul-specific hardware on more recentish GPUs), vs CUDA cores, but a Google search seems to indicate it can be done - not sure if that's in cuDNN though.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#90

Post by cochne »

vlovich123 wrote: post #82
Nihmie wrote: post #77

Earlier quoted context omitted.

To be pedantic about this complexity estimate for the 4 x 4 case, both of them reduce to a O(1). If N == 4, it's a constant, so we have O(4^2.778) == O(4^2.8074) == O(1). Talking about scaling for a problem that has no scaling factor is a bit odd.

If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.

If you look at it that way then any algorithm is just o(n) where n is the number of matrices. O does not care about constant factors
Post reply on HN