6 ms·
Show HN: Matrix Multiplication with Half the Multiplications
- halflings 3y agoThis looks pretty cool! What's the catch? e.g. why isn't this already implemented in accelerators, is it really just a forgotten algorithm, or this has some implications on the cost of building the accelerator or else?
- emacs28 3y agoIMHO, for fixed-point MM accelerators, there is no catch, I think it's an overlooked algorithm. It's based on an algorithm by Winograd who coincidentally also proposed another unrelated algorithm that later became very popular for CNN acceleration which would take some visibility away from this other algorithm by Winograd... But that is speculative
- yorwba 3y agoOn the other hand, if you tried it with floating point, you'd lose significant digits. Since the approach is to sum (a[i] + b[i+1])(a[i+1] + b[i]) and subtract the sums of a[i]a[i+1] and b[i]b[i+1] in the end to get a[i]b[i] + a[i+1]b[i+1], you may be taking the difference of two large values to get a small value, losing precision.
- OJFord 3y agoLLM hype and this submission in particular keep making me think of a lecturer I had for Topics in Large Dimensional Data Processing, circa 2016: as I recall he was enthusiastically adamant that the most important thing, breakthroughs etc., in years/decades to come was going to be faster matrix operations. Anyway, I'm pretty sure I recognise FIP (not FFIP of course) from that course. I wish I could remember his name, I believe he left academia after my year and went to work in industry, I'd just be curious to see what he's up to now. I'm not saying it was a particularly novel or prescient comment/attitude, we may not have had quite such ML hype but certainly 'big data' was all the rage at the time, it's just something that's stuck in my mind. One of those areas I always meant to study more, just realistically probably never had the mathematical chops for and certainly those I did have atrophied.
- bee_rider 3y agoMaybe I’m joking, but: our society is just a vehicle for economics at this point, our economy is built around science, our science has mostly been turned into observations about engineering, some time ago we changed all of engineering into differential equations, and differential equations can be solved by discretizing them and doing linear algebra, and most of linear algebra can be done with matrix multiplications (triangular solves and orthonormalizations if you are fancy). All you need is matmul.
- MrYellowP 3y agoSo, what you're saying is ... ... that the Matrix creates the world around us. Thanks.
- SJC_Hacker 3y agoFor life sciences need grad students / postdocs to do the grunt work of pipetting, dissected, plating etc. And whatever the equivalent is in chemistry (titration/GC/mass transfer I guess)? But those tools created by engineers are pretty darn important, and allow plenty of experiments/observations to be performed that were previously out of reach.
- OJFord 3y ago
- mariocesar 3y agoPerhaps it's less of a hidden gem and more of a spotlight moment.
- pclmulqdq 3y agoThere are a lot of matrix multiplication algorithms out there with a lot of pluses and minuses. It's always a balance of accuracy, runtime, and scaling. This one probably has bad accuracy in floating point.
- waynecochran 3y agoThe document said it outputs the exact same values as the conventional method. There is no accuracy trade off here.
- p1esk 3y agoFor floating point? Are you sure?
- deleted 3y ago[deleted]
- waynecochran 3y agoOpening statement of README This repository contains the source code for ML hardware architectures that require nearly half the number of multiplier units to achieve the same performance, by executing alternative inner-product algorithms that trade nearly half the multiplications for cheap low-bitwidth additions, while still producing identical output as the conventional inner product.
- p1esk 3y agoI just looked at the paper: the answer is no, floating point is not supported.
- pclmulqdq 3y agoThe paper cited is about hardware, where there is no accuracy tradeoff because you control the numerical precision completely and use fixed point. In a software implementation, neither is true. There is no chance that you will get the exact same values out of this method that you do out of other FP matmuls.
- lupire 3y agoIt's not just a software algorithm. It's a hardware architecture optimization. To benefit, you have to build hardware that matches the dimensions of the algorithm. That's an expensive commitment.
- SJC_Hacker 3y agoNot so much in FPGA ... although I'm not sure top end FPGAs would beat Nvidia TPUs even with this algorithm, and even if cost were not a consideration.
- emacs28 3y ago> you have to build hardware that matches the dimensions of the algorithm Yes the benefits are realized in custom hardware designs as opposed to software, however, the hardware architectures work for multiplying matrices of arbitrary dimensions by splitting up larger matrices into smaller tiles, then summing up the tile products to form the final larger matrix products (i.e. GEMM)
- adastra22 3y agoI’ve only glanced at it so someone correct me if I’m wrong, but IIUC this is not a replacement for matrix multiplication but rather an approximation that only gives decent-ish results for the types of linear systems you see in AI/ML. But for that use case it is totally fine?
- emacs28 2y agoIt produces identical/bit-equivalent results as conventional/naive matrix multiplication for integer/fixed-point data types
- pbsd 3y agoIt's not quite forgotten. It kind of lives on in the pseudo-dot product Wegman-Carter authenticators like UMAC. See Section 3 of [1] for context. [1] https://cr.yp.to/antiforgery/pema-20071022.pdf https://cr.yp.to/antiforgery/pema-20071022.pdf
- Drakim 3y agoI'm surprised this actually works, usually detecting whether to use multiplication or addition is slower than simply using multiplication. Especially if it's massive amounts of work being done in parallel.
- 1letterunixname 3y agoWonder how well it compares to openblas and cublas.
- barfbagginus 3y agoThis readme does a really poor job of explaining what the improvement is or how they drop half the multiplications. What is the Big O run time on this? Is this shifting the known best bounds? And the diagrams are chaotic and don't really explain anything about why this approach is fast or good. The result is that I'm reluctant to even click-through to the PDF. If you want to improve the project credibility please consider being honest and open about what is actually going on and giving some clear explanations and illustrations, rather than things that may as well be designed to hype people too busy to tell you that you are cranks. It's hard to tell if this is incredibly groundbreaking or just but nothingburger. Sadly I almost feel like that must be an intentional decision motivated by poor merits of work and a desire to exploit AI height. The alternative - which I prefer to believe is the case - is that the author simply needs to revise and better contextualize.
- mariocesar 3y agoIt´s actually fairly clear
- hackyhacky 3y agoNot to everyone. If it's clear to you, you could helpfully explain it.
- VogonPoetry 3y agoThis is an analogy. a^2 - b^2 = aa - bb. This can be factored to (a+b)(a-b). In the first expression there are two multiplies, in the factored version there is only one. However, from a numerical analysis / accuracy standpoint, evaluating the factored expression can result in loss of precision in the result when a is close to b. This is especially true if you repeatedly and sequentially do a lot of these operations. Loss of precision can be a problem in numeral modeling (like climate simulation) -- long term predictions diverge. Given that there is a drive to use greatly reduced precision in ML engines, loss of precision might have an effect on how a model performs. Then again, it might not. I haven't read a lot of papers on ML, but I don't recall seeing ones that try to quantify how sensitive a model is to error propagation. (I am making a distinction between tests where the precision is reduced to see where it breaks down v.s. calculating / understanding what the error level actually is in a model)
- ixaxaar 3y agoMan I remembered something similar I had tried working on in 2018, but gave up after all my PhD applications got rejected. https://github.com/ixaxaar/pytorch-dni https://github.com/ixaxaar/pytorch-dni The concept here goes a bit further and tries to replicate backprop with an external network, arguing that that's probably what the brain actually does.
- yorwba 3y agoI'm not seeing the connection. This work is about low-level optimization of matrix multiplication. The repo you linked seems to be about replacing back-propagated gradients with a cheaper estimate. What's the similarity you see between these two?
- ixaxaar 3y agoCorrect, I think I mistook it as "use a small neural net to approximate matrix multiplication" instead it seems as "use cheaper replacements of matrix mul without much acc loss". Wellll that means I can give dni another try :D
- rollingtide 3y agoUnrelated to the technical discussion but I was wondering what you made that architecture gif with? Looks neat!
- ixaxaar 3y agoI think that image is from the paper and was not created by me. Looks cool indeed!
- jebarker 3y agoThis feels like a "no free lunch" situation. I would imagine that any time saving in approximating the gradients this way would be lost to needing to train for more iterations due to the loss in gradient accuracy. Is that not the case?
- 3y ago
- Lucasoato 3y agoIf you're interested in the mathematical theory behind sub-cubic algorithms for matrix multiplications, you can start from here: https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Sub-cubic_algorithms https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. (Now proven for for 2+j = w = 2.3728596, or j > 0.3728596)
- abeppu 3y agoPredicting that this holds for any j > 0 seems rather bold. Would you care to share your intuition why you think that's the case?
- roflmaostc 3y agoTwo matrices with size NxN each can be multiplied naively with the schoolbook algorithm in O(N^3). It's clear that the algorithm needs at least O(N^2) because to access each element of the matrices once, you need a double for loop, which is O(N^2). for i in rows for j in cols # do something with element matrix1 [i, j], matrix2[i, j],... so it has to be j >= 0
- JohnKemeny 3y agoHis question was: what is the reasoning behind there existing an algorithm running in time n^2+epsilon for really small epsilon.
- abeppu 3y agoYeah, we're agreed that j cannot be less than 0. But your conjecture was about _every j > 0_. Do you have any specific line of reasoning which suggests that j can be arbitrarily close to 0 (0 is the greatest lower bound)? Why do you not think there's some other specific limit k \in (0, 0.3728596] beyond which j cannot be improved?
- gizmo686 3y ago> I conjecture that for every j > 0 in R, a number n exists so that any two n x n matrices can be multiplied together in O(n^(2+j)) steps. Is this stated correctly? Because it seems almost meaningless as stated. You start with "for every j, there exists an n such that...". That would mean that for the rest of the statement, n and j are constant. So you are just saying that you can multiply constant sized matrices in constant time. Technically true, but I feel like you are trying to claim something stronger.
- michelpp 3y agoThis is very cool and a real interesting read! For those in the comments confused about how this is better, the paper is talking about synthesizing matrix multiplication pipelines in hardware, like an FPGA or ASIC. On a CPU or GPU you won't notice because adds and multiplications take the same amount of time generally, but multiplication units takes up many more transistors, so if you can reduce the circuit complexity you can increase the speed and parallel throughput and reduce power and routing complexity. This approach could be particularly useful for efficient sparse matrix multiplication accelerators. Another cool way to eliminate multiplication in matrix multiplication is to use different semirings [1]. The Tropical Semiring [2] for example substitutes addition for multiplication and min (or max) for addition. It's still matrix multiplication but with substituted binary operations. The research in this relatively new field of Tropical Algebra [3] is quite active and rich right now, being used for all kinds of optimization problems and in research for optimizing neural networks [4] . This approach also lends itself to hardware synthesis since most FPGA configurable logical blocks can add/min/max in one clock cycle, whereas efficient multiplication requires fixed dedicated on-chip hardware multipliers. Another way to efficiently remove multiplications with a different but related semiring is to use a Log Semiring [5]. If you have to multiply chains of probabilities (like Markov chains) then the numbers quickly become very small and floating point loses its accuracy to represent the numbers. By scaling the numbers first by taking the log, multiplication becomes addition and addition becomes x + log1p(exp(y - x)). [1] https://en.wikipedia.org/wiki/Semiring https://en.wikipedia.org/wiki/Semiring [2] https://en.wikipedia.org/wiki/Tropical_semiring https://en.wikipedia.org/wiki/Tropical_semiring [3] https://en.wikipedia.org/wiki/Tropical_geometry https://en.wikipedia.org/wiki/Tropical_geometry [4] https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf https://proceedings.mlr.press/v80/zhang18i/zhang18i.pdf [5] https://en.wikipedia.org/wiki/Log_semiring https://en.wikipedia.org/wiki/Log_semiring
- pk-protect-ai 3y ago> By scaling the numbers first by taking the log, multiplication becomes addition and addition becomes x + log1p(exp(y - x)). Isn't this the same approach as in GF(2^x), which has been in use for decades? The only limitation that comes to mind is the field size.
- skykooler 3y agoI find it fascinating that this is using a process invented in 1968 and hasn't been used for this purpose until now!
- pk-protect-ai 3y agoHey, nobody knew what to do with GF(2^x) up until mid last century either... Oh wait, CS was not really a thing almost up until mid last century...