8 ms·

I'm super 100% out of my depth on this on the math side of things, so bear with me. But isn't matrix multiplication one of the core basis assumptions of GPU ba

by Fordec 6y ago

I'm super 100% out of my depth on this on the math side of things, so bear with me. But isn't matrix multiplication one of the core basis assumptions of GPU based computing architectures, in particular for AI? That doing math in parallel (which matrices fit into like a glove) gets the fastest result? Does this imply that a new future architecture could be, at least in theory, get the natural advantage over what we have at the moment? Because if the answer is yes or even a "possibly, too early to tell, requires more R&D", then the existing GPU manufacturers suddenly have a long term problem and we're very likely about to see a decade of a new arms race in computing architecture.

cambalache 6y ago
You are confusing the efficiency of an algorithm with its implementation. Worth repeating the famous Dijkstra's dictum here : “Computer Science is no more about computers than astronomy is about telescopes.”
- Fordec 6y ago
  I don't believe I am confused actually. I get this is just an algorithm hypothetical being answered right now. I just care about the telescopes way more than the astronomy and am thinking steps ahead about the meta game of the telescope market. Just as I personally would care far more about the real world implications of P=NP far more than the act of solving it.
  - gtr32x 6y ago
    I understand that the answer is no here. Because this method is only suitable for the class of linear system thats the equivalent of sparse matrices. GPUs on the other hand are more optimized for the general purpose matrix multiplication here. Unless it can be shown that there are certain economically high-usage scenarios of this class of problems (e.g. the usage magnitude of bitcoin mining), the investment into this specific research does not seem warranted.
    - sdenton4 6y ago
      Completely ridiculous. Firstly, faster solutions in fundamental problems can eventually lead to hardware that supports it. Secondly, this is already happening for sparse matrix multiplication: the nvidia A100 has some sparsity support, to allow making better use of pruned neutral networks, for example. Thirdly, sparse enough systems, even without the A100, can run faster on cpu than gpu. If you find yourself with one of these problems, you can just choose the correct piece of hardware for the job. Without a sparse algorithm, you are still stuck with the slower dense solution. Fourthly, giant sparse systems do indeed arise constantly. Just to make one up, consider weather measurements. Each row is a set of measurements from a specific weather station, but there are thousands of stations: it's a sparse set of observations, with some nearby dependencies. Evolving the state in time will often involve solving a giant linear system. (See other comments on the thread about pdes.) It is absolutely worthwhile research, regardless of how applicable it is to fscking bitcoin.
xxpor 6y ago
My question is why did GPGPU stuff take so long to take off then? Computer graphics is basically applied linear algebra aka matrix math
- volta83 6y ago
  computer graphics is doing a lot of very small (4x4 matrices) linear algebra GPGPU is often about doing few (or one) very big (10^9 x 10^9) matrix op. You can split big matrix op into smaller ones, but with a big matrix you need to combine the results; with independent smaller matrices you don't.
  - xxpor 6y ago
    Ah interesting, that does make a lot of sense.
kernelmethod 6y ago
You (and apparently a few of the other commenters here) have some misconceptions about what this article is about. The paper this article is based on is about solving a linear system (i.e. solve for x in the equation Ax = b), not matrix multiplication, which is completely different. From what I can tell, the authors of the paper just claim that their method for solving a certain class of linear systems is faster than the asymptotic cost of the fastest known matrix-matrix multiplication algorithm.
- _nalply 6y ago
  Perhaps it is possible to go backwards from solving to matrix multiplication. Your example Ax = b can be solved using a matrix multiplication with the inverse matrix: x = A^-1 b. So if one can solve a linear system faster than by matrix multiplication, one could try to use the same algorithm for matrix multiplication.
  - FartyMcFarter 6y ago
    When solving a linear system, x and b only have one column. So unless the algorithm is general enough to not have that limitation, it won't be applicable to general matrix multiplication.
    - rightbyte 6y ago
      > When solving a linear system, x and b only have one column Isn't it linear for whatever amount of columns?
    - conjectures 6y ago
      The extension to matrix-matrix is trivial, since a matrix is just a concatenation of columns.
      - FartyMcFarter 6y ago
        A matrix is a concatenation of columns yes, but how does that help us multiply matrices by using a sparse linear-system solver? Perhaps it's trivial but I don't see it.
Someone 6y ago
As others mentioned, this algorithm isn’t matrix multiplication. Even if it were, as the article mentions, we don’t even know what the optimal (in terms of basic operations on numbers) algorithm for multiplying matrices is. See https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm for a starting point. (“Optimal in time” is a different problem. For fixed-size matrices, as often used in computer graphics, that may be known, but even then, there’s the effect of caching, time needed to move data to and from the GPU, etc) Also, Strassen multiplication and its improvements have a “somewhat reduced numerical stability, and the algorithm also requires significantly more memory compared to the naive algorithm” (https://en.wikipedia.org/wiki/Numerical_stability https://en.wikipedia.org/wiki/Numerical_stability) This algorithm may have some of the same problems. Being random, it likely also will have varying running times. That can be bad for GPUs if they are used to generate real-time graphics. In total, I don’t see GPU manufacturers being worried about this. They already live with the worry that somebody will discover an O(n²) matrix multiplication algorithm that’s implementable in hardware and more efficient for small n, and I don’t think they lose sleep over that.

by Fordec 6y ago

cambalache 6y ago

You are confusing the efficiency of an algorithm with its implementation. Worth repeating the famous Dijkstra's dictum here : “Computer Science is no more about computers than astronomy is about telescopes.”

Fordec 6y ago
I don't believe I am confused actually. I get this is just an algorithm hypothetical being answered right now. I just care about the telescopes way more than the astronomy and am thinking steps ahead about the meta game of the telescope market. Just as I personally would care far more about the real world implications of P=NP far more than the act of solving it.
- gtr32x 6y ago
  I understand that the answer is no here. Because this method is only suitable for the class of linear system thats the equivalent of sparse matrices. GPUs on the other hand are more optimized for the general purpose matrix multiplication here. Unless it can be shown that there are certain economically high-usage scenarios of this class of problems (e.g. the usage magnitude of bitcoin mining), the investment into this specific research does not seem warranted.
  - sdenton4 6y ago
    Completely ridiculous. Firstly, faster solutions in fundamental problems can eventually lead to hardware that supports it. Secondly, this is already happening for sparse matrix multiplication: the nvidia A100 has some sparsity support, to allow making better use of pruned neutral networks, for example. Thirdly, sparse enough systems, even without the A100, can run faster on cpu than gpu. If you find yourself with one of these problems, you can just choose the correct piece of hardware for the job. Without a sparse algorithm, you are still stuck with the slower dense solution. Fourthly, giant sparse systems do indeed arise constantly. Just to make one up, consider weather measurements. Each row is a set of measurements from a specific weather station, but there are thousands of stations: it's a sparse set of observations, with some nearby dependencies. Evolving the state in time will often involve solving a giant linear system. (See other comments on the thread about pdes.) It is absolutely worthwhile research, regardless of how applicable it is to fscking bitcoin.

xxpor 6y ago

My question is why did GPGPU stuff take so long to take off then? Computer graphics is basically applied linear algebra aka matrix math

volta83 6y ago
computer graphics is doing a lot of very small (4x4 matrices) linear algebra GPGPU is often about doing few (or one) very big (10^9 x 10^9) matrix op. You can split big matrix op into smaller ones, but with a big matrix you need to combine the results; with independent smaller matrices you don't.
- xxpor 6y ago
  Ah interesting, that does make a lot of sense.

kernelmethod 6y ago

You (and apparently a few of the other commenters here) have some misconceptions about what this article is about. The paper this article is based on is about solving a linear system (i.e. solve for x in the equation Ax = b), not matrix multiplication, which is completely different. From what I can tell, the authors of the paper just claim that their method for solving a certain class of linear systems is faster than the asymptotic cost of the fastest known matrix-matrix multiplication algorithm.

_nalply 6y ago
Perhaps it is possible to go backwards from solving to matrix multiplication. Your example Ax = b can be solved using a matrix multiplication with the inverse matrix: x = A^-1 b. So if one can solve a linear system faster than by matrix multiplication, one could try to use the same algorithm for matrix multiplication.
- FartyMcFarter 6y ago
  When solving a linear system, x and b only have one column. So unless the algorithm is general enough to not have that limitation, it won't be applicable to general matrix multiplication.
  - rightbyte 6y ago
    > When solving a linear system, x and b only have one column Isn't it linear for whatever amount of columns?
  - conjectures 6y ago
    The extension to matrix-matrix is trivial, since a matrix is just a concatenation of columns.
    - FartyMcFarter 6y ago
      A matrix is a concatenation of columns yes, but how does that help us multiply matrices by using a sparse linear-system solver? Perhaps it's trivial but I don't see it.

Someone 6y ago

As others mentioned, this algorithm isn’t matrix multiplication. Even if it were, as the article mentions, we don’t even know what the optimal (in terms of basic operations on numbers) algorithm for multiplying matrices is. See https://en.wikipedia.org/wiki/Strassen_algorithm https://en.wikipedia.org/wiki/Strassen_algorithm for a starting point. (“Optimal in time” is a different problem. For fixed-size matrices, as often used in computer graphics, that may be known, but even then, there’s the effect of caching, time needed to move data to and from the GPU, etc) Also, Strassen multiplication and its improvements have a “somewhat reduced numerical stability, and the algorithm also requires significantly more memory compared to the naive algorithm” (https://en.wikipedia.org/wiki/Numerical_stability https://en.wikipedia.org/wiki/Numerical_stability) This algorithm may have some of the same problems. Being random, it likely also will have varying running times. That can be bad for GPUs if they are used to generate real-time graphics. In total, I don’t see GPU manufacturers being worried about this. They already live with the worry that somebody will discover an O(n²) matrix multiplication algorithm that’s implementable in hardware and more efficient for small n, and I don’t think they lose sleep over that.