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

61–70 of 116 posts

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#61

Post by chillee »

Quoting myself on twitter:

https://twitter.com/cHHillee/status/1577713102434361344

I'm quite suspicious about their hardware benchmarks. They're not writing custom kernels, they're relying on a graph compiler like XLA to automatically fuse their decomposed matmuls (and my guess is that XLA will not be very good at this).

Moreover, as far as I can tell, they don't report absolute performance numbers anywhere. In other words, I suspect that a naive N^3 matrix multiplication would absolutely smoke them in performance.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#62

Post by throwawaymaths »

sdenton4 wrote: post #58
throwawaymaths wrote: post #51

Earlier quoted context omitted.

> the number of operations This is a very good proxy for actual real world speed. It's pretty much "as good as it gets" for most straight computational tasks, though sometimes memory movement is your real bottleneck.

This is questionable... The 'best' algorithms for matrix multiplication are galactic algorithms that provide no actual benefit. Raw operation counts are a good proxy for speed, but the big-O complexity that people actually chase hasn't been especially helpful for this problem in the last twenty+ years. https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...

Probably the most common matrix multiplication is (nx9) x (9xm) (9 = 3x3 cells from a convnet) . If you can optimize the shit out of those you might be in business for something interesting.

Though to be honest the real slow step in machine learning is training and the slow step in training is the outer product of two matrices.... I don't believe there is an algorithmic way out of that one.

For non-ml/non-GF purposes, you might also worry about numerical stability of these matrix multiplications, which is not addressed in this paper.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#63

Post by lifthrasiir »

throwawaymaths wrote: post #47
svnt wrote: post #15

The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…

No, they count multiplications, 47 vs 49 in the 4x4 case. This assumes that multiplications are the heavy lift relative to additions, memory moves, etc. this is not a bad assumption, and is hardware independent, although there are some proposed 'exotic' hardware solutions where addition and multiplication are equally difficult (via lookup table, limited to about 8-bit x 8-bit) or where addition is harder than multipl…

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.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#64

Post by throwawaymaths »

lifthrasiir wrote: post #63
throwawaymaths wrote: post #47

Earlier quoted context omitted.

No, they count multiplications, 47 vs 49 in the 4x4 case. This assumes that multiplications are the heavy lift relative to additions, memory moves, etc. this is not a bad assumption, and is hardware independent, although there are some proposed 'exotic' hardware solutions where addition and multiplication are equally difficult (via lookup table, limited to about 8-bit x 8-bit) or where addition is harder than multipl…

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.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#65

Post by jeffbee »

danuker wrote: post #3
a-dub wrote: post #2

this is cool. i suppose it's only a matter of time until we see optimizing compilers that use transformer-rl style searches for subsets of their optimization and codegen.

Will also generate some fun bugs!

Superoptimizers are already extremely good at discovering latent flaws in high level source code, and in compilers.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#66

Post by chrchang523 »

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.

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.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#67

Post by Ar-Curunir »

svnt wrote: post #15

The big claim turns out to be a little overstated. The claim: > AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. reduces to: > AlphaTensor discovers algorithms that outperform the Strassen-square algorithm, which is a fast algorithm for large square matrices31,32. Although the discovered algorithm has the same theoretical comple…

You’re wrong. They discovered an algorithm with fewer multiplications for 4x4 matrices.

They also discovered better algorithms for other dimensions.

Re: Discovering faster matrix multiplication algorithms with reinforcement learning

#68

Post by fulafel »

throwawaymaths wrote: post #51
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…

> the number of operations This is a very good proxy for actual real world speed. It's pretty much "as good as it gets" for most straight computational tasks, though sometimes memory movement is your real bottleneck.

It's become a much worse proxy since the memory wall.
Post reply on HN