2 ms·

> 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,

> 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.

sdenton4 4y ago
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_algorithm https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...
- throwawaymaths 4y ago
  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.
  - a1369209993 4y ago
    > 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. Well, there are several, but the obvious ones tend to require strange or unrealistic assumptions about the hardware. The most obvious such assumption, IMO, being that the hardware is arranged in 3D space in a manner roughly analogous to a human brain, which tends to be at odds with the common practice of mostly-planar photolithography, and with the preference to be able to change the network topology experimentally without building new hardware.
fulafel 4y ago
It's become a much worse proxy since the memory wall.

sdenton4 4y ago

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_algorithm https://en.wikipedia.org/wiki/Matrix_multiplication_algorith...

throwawaymaths 4y ago
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.
- a1369209993 4y ago
  > 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. Well, there are several, but the obvious ones tend to require strange or unrealistic assumptions about the hardware. The most obvious such assumption, IMO, being that the hardware is arranged in 3D space in a manner roughly analogous to a human brain, which tends to be at odds with the common practice of mostly-planar photolithography, and with the preference to be able to change the network topology experimentally without building new hardware.

fulafel 4y ago

It's become a much worse proxy since the memory wall.