9 ms·

Matrix multiplication using only addition

233 points by daniel-cussen 3y ago

Hi HN, this paper is my first proper academic publication, it's on arxiv only for now--this is a pre-print--but is being considered for publication by peer-reviewed journals concurrently. Open-access journals, of course. I'm totally disinterested in tenure or academic recognition. For my goals being a Stanford dropout is better than any other amount of academic recognition. So i don't care about journals uh prestige numbers the impact factors i know that term but anything paywalled is bad for what i do care about, which is my business, fgemm. Means Fast/Faster/Fastest GEneral Matrix-Matrix multiplication. gemm is an acronym already used in BLAS libraries, Basic Linear Algebra Subprograms, which is what most of the time n money spent on ML goes to. I'm going to be available to answer questions insofar as i can.

daniel-cussen 3y ago
Hi HN, this paper is my first proper academic publication, it's on arxiv only for now--this is a pre-print--but is being considered for publication by peer-reviewed journals concurrently. Open-access journals, of course. I'm totally disinterested in tenure or academic recognition. For my goals being a Stanford dropout is better than any other amount of academic recognition. So i don't care about journals uh prestige numbers the impact factors i know that term but anything paywalled is bad for what i do care about, which is my business, fgemm. Means Fast/Faster/Fastest GEneral Matrix-Matrix multiplication. gemm is an acronym already used in BLAS libraries, Basic Linear Algebra Subprograms, which is what most of the time n money spent on ML goes to. I'm going to be available to answer questions insofar as i can.
- unlikelymordant 3y ago
  Could you adapt this to finding fast inverses?
  - daniel-cussen 3y ago
    I looked at that, i concluded yes because the bottleneck of inverting a matrix is matrix multiplication. Spesh since fgemm targets 32-bit floating-point format, n has high accuracy (not saying how high but much better than Strassen, at least as good as naive matrix multiplication).
- quickthrower2 3y ago
  Hi Daniel. Thanks for the inspiration. Something I have thought about too is sticking some papers out there without needing to go through expensive gates (PhD etc.).
  - daniel-cussen 3y ago
    It's brutally hard. I had an easier time buying skylinesort.com n posting the skylinesort algorithm there, than publishing through professors n academia. Typically not feasible for undergraduates, least of all anybody not paying tuition. Same way professors are expected to have an undergraduate degree at the very least (4 profs at Stanford have just an undergraduate degree), a Master's degree (a handful have that and no more), but typically a PhD is required (literally all the other professors have PhD's). Is required. Who requires it? Who says, "I require a PhD."? Is expected? Who expects it? Who says, "I expect a PhD."? Passive voice is typical in academia. Very rare to get around the gatekeeping, frankly. I couldn't publish on arxiv for years because of lack of academic affiliation alone. Took years to get to this point in terms of the effort I dedicate to getting recognition for my work.
    - Vasniktel 3y ago
      Thanks Daniel. Could you expand on this comment? What did you have to do to be able to publish a paper on arxiv?
      - daniel-cussen 3y ago
        At the time, i needed academic affiliation, meaning be in college or more likely have a professor vouch for me. What i ended up doing was return to Stanford undergrad n take classes related to algorithms, show my algorithm portfolio in office hours, then get referred to other profs, one of them being Jeffrey Ullman, in 2019. N then after emails back n forth we met in person in the Gates building, it went from there. Very happy to have met Professor Jeffrey Ullman.
  - jmhimara 3y ago
    Not sure if this is what you're talking about, but you don't typically pay to get a PhD (in fact you get paid in the US).
- blast 3y ago
  This is cool! How did you end up working with Ullman? I guess "being a Stanford dropout" explains how you met him, but there must be an interesting story here. Can you share how that happened and what the process was?
- henistein 3y ago
  Is there any python implementation of it? I would really like to try it out
- bishop77 3y ago
  How does this compare to Strassen's algorithm? Could you please provide a reference implementation?
brucethemoose2 3y ago
This is a fascinating idea. Any real acedemic critique is over my head (and I hope others chime in), but some random thoughts: - "logarithm LUT then add" seems delightfully simple, especially at low precision. I am going to have to read that paper too... - The concerns about GPU style parallelism may not be as bad in "alternative" architectures. For instance, Centaur came up with a single, serial, but hilariously wide 32,768-bit SIMD core for inference: https://fuse.wikichip.org/news/3256/centaur-new-x86-server-processor-packs-an-ai-punch/ https://fuse.wikichip.org/news/3256/centaur-new-x86-server-p... - The silicon simplification also seems relevant to Samsung's in memory computing effort: https://www.servethehome.com/samsung-hbm2-pim-and-aquabolt-xl-at-hot-chips-33/ https://www.servethehome.com/samsung-hbm2-pim-and-aquabolt-x... - I wonder if this would be relevant to llama.cpp's CPU inference?
- daniel-cussen 3y ago
  Well so one issue w both GPUs n CPUs which make them bad platforms for this algorithm is that, in both, FLOPS are such an important metric for sales that multiplication is highly subsidized in both those chip types. So huge amounts of area is dedicated to floating point multiplication, meaning the advantage of fgemm (the name of the algorithm is the same as the name of the company) is purely one of energy. Which is great because if it were software it would be impossible to protect the IP. USPTO is very clear in that sense, i believe in both in re Bilski and in the Alice Corp. case which reached SCOTUS, that algorithms need to be implemented physically, typically meaning in a chip, to be patentable. So because it needs a chip to work, it is good business, if it did not it would be bad business. A chip provides every form of IP protection, all four forms, trade secret, copyright, patent, n even trademark. No other medium has that to my knowledge. So if you have a CPU or a GPU n want it to do more work in the same amount of time, this paper promises nothing, n it keeps that promise. Nonetheless i'm advancing rapidly to the point of creating the hardware that can cut off 70% of the cost of GEMM. I considered 50% off, same thing at half the price, but it wouldn't be fair to the consumer w my economics. You see 50% discounts all the time, who cares? 70% off, you don't see that all the time. On something you actually want? Especially on a commodity, n it's still good business for me as the lowest-cost producer.
pkoird 3y ago
Didn't look too deep into the paper but can I just say that I LOVE this style of academic writing? Accessible, full of examples, and in a conversing tone. Most of the math papers I come across jump right into the "Let $X \in F be ring of S^1$ and etc. I secretly believe that people heap abstractions after abstractions to purposefully shield the fact that the meat of what they've written is actually quite simple. Either that, or I've failed to understand that some ideas can't just be explained without invoking arcane symbols.
- nathan_compton 3y ago
  > secretly believe Apparently not so secretly.
- sublinear 3y ago
  > I secretly believe that people heap abstractions after abstractions to purposefully shield the fact that the meat of what they've written is actually quite simple. It usually is pretty simple, but what they're going for is rigor and concision. Maybe a few papers are overconstrained and could drop a few unnecessary details, but I don't think that's all that common after enough review.
  - cinntaile 3y ago
    Sometimes people just want their work to sound more impressive than it actually is. Using in-words is a pretty standard technique, their peers don't mind because they speak the same language. To outsiders it sounds difficult. Quite common in academia.
- l33t233372 3y ago
  I think it’s just that what’s being talked about is so precise and so deep in the weeds of nested definitions that you generally need to talk like that, or at least you have to be a truly gifted communicator to write a math paper without it.
  - mathisfun123 3y ago
daniel-cussen 3y ago
One thing I highly recommend is trying it for yourself, just with pen and paper. Think of ten two-digit numbers under 40 for it to work nicely. Just numbers under 40, 1-100 would require like 20 numbers for it to work as well as it does in realistic examples. Write them in one line, then write them sorted on the next line, with lines connecting them to where they were before. Then underneath each number write down the difference between that number n the one before it, this is called taking the first differences. Repeat the sorting followed by taking first differences until you have only two numbers, two being an arbitrary limit. You may then pretend the row and column are the same, so expand with the same vector using the lines drawn, and prefix sum where first difference was performed. So: 11 39 23 28 31 19 32 05 01 09 sort 01 05 09 11 19 23 28 31 32 39 first differences 1 4 4 2 8 4 5 3 1 7 sort and remove duplicates 1 2 3 4 5 7 8 first differences 1 1 1 1 1 2 1 sort and remove duplicates 1 2 reduction complete
- smlacy 3y ago
  Writing 'n' instead of 'and' when discussing mathematics is generally a very bad idea. Your example is a good one, but your use of abbreviations in your writing is horrid.
  - daniel-cussen 3y ago
    I think you're right in this case. Alright I'll edit if I still can. I don't use any variables anyway in my post. EDIT: alright I fixed all the single letter abbreviations.
    - svnt 3y ago
      almost: > Then underneath each number write down the difference between that number n the one before it
      - daniel-cussen 3y ago
        True. Too late to edit. Yeah that is confusing, guess I gotta write differently when discussing that. I just shave characters for character counts, which are often a problem particularly on Twitter. It's not because I don't like typing out the whole word, I generally refrain from that sort of abbreviation. It is also stylistically unique--I use a unique style for the same reason as, and vindicating, Auguste Rodin who faced problems due to his statues being too literal.
kragen 3y ago
apparently the fgemm future of artificial intelligence is... a versatrig slide rule? wait, this actually doesn't use logarithms at all, it's more of a difference engine really
- daniel-cussen 3y ago
  Yeh, it bears many resemblances to Babbage's difference engine.
  - kragen 3y ago
    yeah, sorry for making the slide rule joke before even reading the abstract
hdhsjsbv 3y ago
What is the algorithmic complexity (Big O) of this? And thank you for great submission. I skimmed it and I enjoyed it. But didn’t read the cost function section with much attention.
KETpXDDzR 3y ago
I'm unsure if this yields any computational benefits over classic multiplication. "In real arithmetic, multiplication may be faster for the following reason: When two real numbers are multiplied, the mantissae are multiplied together and the exponents are added, and these operations can be carried out in parallel. When two real numbers are added, first the mantissa of the smaller number must be shifted so that the exponents match (a process termed normalisation). Then the mantissae must be added. The result of the addition may overflow the original word length by 1 bit, or it may generate any number of leading zeros. Therefore the result must be normalised again. There are therefore 3 steps and they must be done in series." - https://www.researchgate.net/post/Is-multiplication-slower-than-addition-on-modern-CPUs https://www.researchgate.net/post/Is-multiplication-slower-t...
- daniel-cussen 3y ago
  One addition and one move replacing one multiplication? Absolutely makes things much cheaper.
  - kragen 3y ago
    well, probably. it likely depends on how the move works; muxes aren't free and driving long wires isn't either but the confusion in the comment you are replying to is that it thinks you are deriving a floating-point matrix multiply algorithm, when in fact you are deriving an integer matrix multiply algorithm floating-point adds are slightly more expensive than floating-point multiplies integer multiplies are enormously more expensive than integer adds (in power and area, though not in time)
- KETpXDDzR 3y ago
  To support this: "ADDSS/SUBSS take 1–3 cycles while MULSS takes 0.5–5 cycles." - http://www.agner.org/optimize/ http://www.agner.org/optimize/
Drunk_Engineer 3y ago
As a chip designer, I'm dubious of this claim: "The advantage of performing matrix multiplication using only addition for arithmetic is that it then becomes feasible to build special- purpose chips with no multiplier circuits. Such chips will take up less space per on-chip processor." Perhaps that is true in a toy design, but in real-world chips the multiplier uses only a very tiny fraction of chip real-estate. And even if the matrix-multiply can be eliminated, there are other uses for multiply operations. I once attended a chip design conference where NVidia discussed its latest GPU. In one of the slides showing block layout, the designers pointed out how barely any silicon was being used for actual floating operations -- the vast majority was for pipelining and moving bits around.
- brigade 3y ago
  That’s because CPUs and GPUs are useful for more than just matrix multiplication. TPUs aren’t; they assume highly regular data movement in and out of the ALUs.
- hedgehog 3y ago
  It of course depends on workload but I know more than a little about this specific problem space and reducing the space+energy cost of the multipliers is useful. If the idea proposed worked well enough it might be a useful block in a camera ISP chip, audio interface for wake word and speech preprocessing, and similar applications where the models are small and energy is precious.
  - creato 3y ago
    I don’t know, sorting requires a lot of moving data around, which is expensive for energy too. Maybe this will be used for vectors of small fixed/bounded size, but then you don’t get to amortize the cost of the logs as much either.
- imtringued 3y ago
  I once saw a professor show me their latest taped out CPU (multi project wafer of course) and it had one tiny core that is supposed to control the wake-up of the larger processor. The sleep controller has no memory and is a thin slice that is barely visible. Meanwhile the primary processor is much larger but it too is completely dwarfed by the memory it is being surrounded by. The idea of throwing out parts of the ALU is ridiculous. The only situation where this would make sense is in some kind of processing in memory situation where your logic process does not permit large CPUs and you expect to have hundreds of cores per chip with multiple chips on a single DIMM.
jiggawatts 3y ago
Instead of sorting, just count the occurrences of the distinct values. For 8-bit values, this requires only 256 registers, each with a relatively small number of bits. E.g.: if the maximum matrix size is 16K*16K, then only 14 bits per accumulator is required. This is just Radix sort and is very easy to implement in digital circuits. It can even reuse the same adder circuits.
- daniel-cussen 3y ago
  Sorting is very fast since i designed a sorting algorithm tailor-made for this problem, which is about as fast as your approach. Difference being the numbers are 32-bit, so iterating through the entire array of all possible 24-bit mantissas (i know they're 23 bit, but the implicit initial 1 of normal (vs denormal) values is explicit here) would be way too slow. Otherwise you'd be right, 8-bit values you can just use counting-sort, no problem. Or 14 bits, same deal. Now also notice there's a difference between the matrix size and the mantissa size, we care about the mantissa size, so it's 24 bits.
sabhiram 3y ago
Fascinating paper. We design an inference accelerator which more or less accomplishes this by quantizing input tensors into logarithmic space. This allows the multiplication (in convolution especially), to be optimized into very simple adders. This (and a few other tricks) has a very dramatic impact on how much compute density we achieve while keeping power very low. We keep the tensors in our quantized space throughout the layers of the network and convert the outputs as required on the way out of the ASIC. We achieve impressive task level performance, but this requires some specialized training and model optimizations. Very cool to see ideas like this propagate more into the mainstream.
- KRAKRISMOTT 3y ago
  Isn't matrix multiplication already a convolution? You are rotating the right hand side matrix anti clockwise 90 degrees and then convolving it upon the LHS matrix from top to bottom.
  - sabhiram 3y ago
    The point above regarding convolution had to do specifically with accelerating 3x3 and above convolutional operations, as the product and the accumulation can be done in a few clock cycles if setup with care and love.
  - kragen 3y ago
    no, it is not, and i am not discrete convolution is cₙ = Σᵢaᵢbₙ₋ᵢ there is no way in which the indexes into the input matrices in a matrix multiplication are formed from sums or differences of indices and dummy variables however, convolution is a matrix multiplication, specifically multiplication by the circulant matrix of the convolution kernel hth, hand
    - KRAKRISMOTT 3y ago
      Sure it doesn't sum the whole matrix but it does sum row by row. Also how did you type out LaTeX in HN? Or is that a font?
daniel-cussen 3y ago
Unfortunately i cannot answer questions as unlike i chip i must now sleep. It's 2:42 AM here. First thing in the morning i'll be on it.
Vasniktel 3y ago
Thanks for the paper Daniel. Very easy to read and understand. I believe I might have found a minor typo that made me scratch my head for a second. On page 3 in the part where you describe the "follow pointers" part of the algorithm you wrote vi=sj and then cpi=csj whereas I believe you meant cvi=csj and that we can now replace vi with csj to make it cvi. Let me know if I'm misunderstanding something here.
- daniel-cussen 3y ago
  Thanks, help finding typos is appreciated! It'll make things easier for when this gets published in a peer-reviewed journal, which is in the works.
Roark66 3y ago
I learned (assembly)programming on a chip that had no multiplication instruction. It was 6510 (a version of popular 6502) and I fail to see the benefit. Back then every multiplication had to be done via addition in loop and division with subtract/compare(except certain numbers like powers of 2 where one could bit shift). You can imagine how slow it was. I was envious of my friends with Amigas (68k cpu) who had chips that were capable of multiplication in hardware. It seems obvious that a properly tuned hardware implementation is always going to be faster than doing the same thing in software. Taken to the extreme this is the crux of the old RISC vs CISC debate.
- LovinFossilFuel 3y ago
  [dead]
- imtringued 3y ago
  This also reminds me of the days when division was not implemented in hardware on ARM chips.
inglor 3y ago
Did the comments here actually read the paper? It just does "russian peasant" multiplication simulating multiplication with addition. There is no new math discovered as far as I understand. It's basically "we know how to do multiplication with a lot of additions". If this was effective rather than just "simulate multiplication with a lot of additions" it would have been super interesting for parallelization of multiplications and communication bounds.
- mathisfun123 3y ago
  > Did the comments here actually read the paper? It just does "russian peasant" multiplication simulating multiplication with addition. Hate to break it to you but often not even the reviewers actually read the paper.
- lang4d 3y ago
  The main content of the paper is trying to minimize the number of “russian peasant” multiplications that need to be performed. I would say those are the interesting parts. Section 2.3 claims dropping the number of additions by a factor of 6 from the naive algorithm. Seems like doing the sorting, recursion, and alignment would have a nontrivial performance penalty, but it’s still a pretty interesting idea.
- kragen 3y ago
  this is not correct probably it would improve the paper to remove the russian-peasant-multiplication references entirely, or reduce them to a throwaway aside in one place in part this is because you surely won't be the last person careless enough to make this obvious error but also it's because russian-peasant multiplication is a totally normal way for hardware multipliers to work, and the main content of the paper is totally decoupled from whether the final multiplication at the end of all the reductions are done with russian-peasant multiplication or (as would probably be a better idea) something like a dadda multiplier or a booth multiplier
hamilyon2 3y ago
I rarely let myself a negative comment, but core of article is authors realising that n-bit multiplication is n additions. So, absolutely nothing interesting or new
- peepeepoopoo16 3y ago
  From what I can tell, it memoizes the intermediate additions and then uses that to amortize the adds across multiple array elements and achieve speedups.
  - kragen 3y ago
    neither of these comments is correct
    - peepeepoopoo16 3y ago
      Mind offering an explanation?
      - kragen 3y ago
        there is a perfectly clear explanation in the paper
- daniel-cussen 3y ago
  Uh, you clearly didn't get the proof. N-bit multiplications performed with a single addition and a single move. Proof involves showing superiority over the number of additions in Russian Peasants.
nabla9 3y ago
Wow. Jeffrey Ullman? Turing Award, Neumann medal etc. He is now 80 years old. Ullman is of the authors of several legendary computer science books Dragon Book (Compilers: Principles, Techniques, and Tools) the Cinderella Book (Introduction to Automata Theory, Languages, and Computation), Green Dragon Book (Principles of Compiler Design) He was the thesis advisor for Sergey Brin, Ravi Sethi, Surajit Chaudhuri
- giovannibonetti 3y ago
  His book about Standard ML is very interesting, too. It is a great introduction to strongly-typed functional languages like Haskell, Ocaml and F#.
rustybolt 3y ago
Sounds like bullshit to me? The 1x1 case reduces to multiplication so it's multiplication without multiplication?
amelius 3y ago
Multiplication in binary is just addition of various shifted versions of one of the operands. So it should not be surprising that this is possible or perhaps even efficient.
mratsim 3y ago
At a glance this sounds like a re-discovery of addition chains and using them to construct Pippenger algorithm. But applied to matrices instead of group elements. See: https://github.com/mratsim/constantine/issues/37 https://github.com/mratsim/constantine/issues/37
- kragen 3y ago
  i don't think that is the case but i don't really understand pippenger's algorithm. what would pippenger's buckets correspond to in this 'fgemm' thing?
scscsc 3y ago
Does anyone know anything about the affiliation of the first author, "Fgemm SPA"?
- daniel-cussen 3y ago
  Fgemm SpA, coming soon.
jhj 3y ago
This feels very disconnected from the realities of hardware to the point of impracticality. More energy is typically burned on RAMs/flops (storing bits and shuffling them around) than the combinational logic portion (adders/multipliers/etc) doing the arithmetic on real designs these days. Sorting, computing differences and the like involves a lot of data movement and likely temporary storage for buffering as well. I've evaluated fixed-function sorting in ASIC designs, it's not cheap at all. This feels like the authors had some ideas of circuit design concerns from the 1980s ("hardware multipliers are very expensive!") and trying to port that to the present.
- daniel-cussen 3y ago
  No comment.
amai 3y ago
See also „Multiplying and Dividing on the 6502“ , which was an early microprocessor without multiplier unit https://news.ycombinator.com/item?id=31911655 https://news.ycombinator.com/item?id=31911655

233 points by daniel-cussen 3y ago

daniel-cussen 3y ago

unlikelymordant 3y ago
Could you adapt this to finding fast inverses?
- daniel-cussen 3y ago
  I looked at that, i concluded yes because the bottleneck of inverting a matrix is matrix multiplication. Spesh since fgemm targets 32-bit floating-point format, n has high accuracy (not saying how high but much better than Strassen, at least as good as naive matrix multiplication).
quickthrower2 3y ago
Hi Daniel. Thanks for the inspiration. Something I have thought about too is sticking some papers out there without needing to go through expensive gates (PhD etc.).
- daniel-cussen 3y ago
  It's brutally hard. I had an easier time buying skylinesort.com n posting the skylinesort algorithm there, than publishing through professors n academia. Typically not feasible for undergraduates, least of all anybody not paying tuition. Same way professors are expected to have an undergraduate degree at the very least (4 profs at Stanford have just an undergraduate degree), a Master's degree (a handful have that and no more), but typically a PhD is required (literally all the other professors have PhD's). Is required. Who requires it? Who says, "I require a PhD."? Is expected? Who expects it? Who says, "I expect a PhD."? Passive voice is typical in academia. Very rare to get around the gatekeeping, frankly. I couldn't publish on arxiv for years because of lack of academic affiliation alone. Took years to get to this point in terms of the effort I dedicate to getting recognition for my work.
  - Vasniktel 3y ago
    Thanks Daniel. Could you expand on this comment? What did you have to do to be able to publish a paper on arxiv?
    - daniel-cussen 3y ago
      At the time, i needed academic affiliation, meaning be in college or more likely have a professor vouch for me. What i ended up doing was return to Stanford undergrad n take classes related to algorithms, show my algorithm portfolio in office hours, then get referred to other profs, one of them being Jeffrey Ullman, in 2019. N then after emails back n forth we met in person in the Gates building, it went from there. Very happy to have met Professor Jeffrey Ullman.
- jmhimara 3y ago
  Not sure if this is what you're talking about, but you don't typically pay to get a PhD (in fact you get paid in the US).
blast 3y ago
This is cool! How did you end up working with Ullman? I guess "being a Stanford dropout" explains how you met him, but there must be an interesting story here. Can you share how that happened and what the process was?
henistein 3y ago
Is there any python implementation of it? I would really like to try it out
bishop77 3y ago
How does this compare to Strassen's algorithm? Could you please provide a reference implementation?

brucethemoose2 3y ago

This is a fascinating idea. Any real acedemic critique is over my head (and I hope others chime in), but some random thoughts: - "logarithm LUT then add" seems delightfully simple, especially at low precision. I am going to have to read that paper too... - The concerns about GPU style parallelism may not be as bad in "alternative" architectures. For instance, Centaur came up with a single, serial, but hilariously wide 32,768-bit SIMD core for inference: https://fuse.wikichip.org/news/3256/centaur-new-x86-server-processor-packs-an-ai-punch/ https://fuse.wikichip.org/news/3256/centaur-new-x86-server-p... - The silicon simplification also seems relevant to Samsung's in memory computing effort: https://www.servethehome.com/samsung-hbm2-pim-and-aquabolt-xl-at-hot-chips-33/ https://www.servethehome.com/samsung-hbm2-pim-and-aquabolt-x... - I wonder if this would be relevant to llama.cpp's CPU inference?

daniel-cussen 3y ago
Well so one issue w both GPUs n CPUs which make them bad platforms for this algorithm is that, in both, FLOPS are such an important metric for sales that multiplication is highly subsidized in both those chip types. So huge amounts of area is dedicated to floating point multiplication, meaning the advantage of fgemm (the name of the algorithm is the same as the name of the company) is purely one of energy. Which is great because if it were software it would be impossible to protect the IP. USPTO is very clear in that sense, i believe in both in re Bilski and in the Alice Corp. case which reached SCOTUS, that algorithms need to be implemented physically, typically meaning in a chip, to be patentable. So because it needs a chip to work, it is good business, if it did not it would be bad business. A chip provides every form of IP protection, all four forms, trade secret, copyright, patent, n even trademark. No other medium has that to my knowledge. So if you have a CPU or a GPU n want it to do more work in the same amount of time, this paper promises nothing, n it keeps that promise. Nonetheless i'm advancing rapidly to the point of creating the hardware that can cut off 70% of the cost of GEMM. I considered 50% off, same thing at half the price, but it wouldn't be fair to the consumer w my economics. You see 50% discounts all the time, who cares? 70% off, you don't see that all the time. On something you actually want? Especially on a commodity, n it's still good business for me as the lowest-cost producer.

pkoird 3y ago

Didn't look too deep into the paper but can I just say that I LOVE this style of academic writing? Accessible, full of examples, and in a conversing tone. Most of the math papers I come across jump right into the "Let $X \in F be ring of S^1$ and etc. I secretly believe that people heap abstractions after abstractions to purposefully shield the fact that the meat of what they've written is actually quite simple. Either that, or I've failed to understand that some ideas can't just be explained without invoking arcane symbols.

nathan_compton 3y ago
> secretly believe Apparently not so secretly.
sublinear 3y ago
> I secretly believe that people heap abstractions after abstractions to purposefully shield the fact that the meat of what they've written is actually quite simple. It usually is pretty simple, but what they're going for is rigor and concision. Maybe a few papers are overconstrained and could drop a few unnecessary details, but I don't think that's all that common after enough review.
- cinntaile 3y ago
  Sometimes people just want their work to sound more impressive than it actually is. Using in-words is a pretty standard technique, their peers don't mind because they speak the same language. To outsiders it sounds difficult. Quite common in academia.
l33t233372 3y ago
I think it’s just that what’s being talked about is so precise and so deep in the weeds of nested definitions that you generally need to talk like that, or at least you have to be a truly gifted communicator to write a math paper without it.
- mathisfun123 3y ago

daniel-cussen 3y ago

One thing I highly recommend is trying it for yourself, just with pen and paper. Think of ten two-digit numbers under 40 for it to work nicely. Just numbers under 40, 1-100 would require like 20 numbers for it to work as well as it does in realistic examples. Write them in one line, then write them sorted on the next line, with lines connecting them to where they were before. Then underneath each number write down the difference between that number n the one before it, this is called taking the first differences. Repeat the sorting followed by taking first differences until you have only two numbers, two being an arbitrary limit. You may then pretend the row and column are the same, so expand with the same vector using the lines drawn, and prefix sum where first difference was performed. So: 11 39 23 28 31 19 32 05 01 09 sort 01 05 09 11 19 23 28 31 32 39 first differences 1 4 4 2 8 4 5 3 1 7 sort and remove duplicates 1 2 3 4 5 7 8 first differences 1 1 1 1 1 2 1 sort and remove duplicates 1 2 reduction complete

smlacy 3y ago
Writing 'n' instead of 'and' when discussing mathematics is generally a very bad idea. Your example is a good one, but your use of abbreviations in your writing is horrid.
- daniel-cussen 3y ago
  I think you're right in this case. Alright I'll edit if I still can. I don't use any variables anyway in my post. EDIT: alright I fixed all the single letter abbreviations.
  - svnt 3y ago
    almost: > Then underneath each number write down the difference between that number n the one before it
    - daniel-cussen 3y ago
      True. Too late to edit. Yeah that is confusing, guess I gotta write differently when discussing that. I just shave characters for character counts, which are often a problem particularly on Twitter. It's not because I don't like typing out the whole word, I generally refrain from that sort of abbreviation. It is also stylistically unique--I use a unique style for the same reason as, and vindicating, Auguste Rodin who faced problems due to his statues being too literal.

kragen 3y ago

apparently the fgemm future of artificial intelligence is... a versatrig slide rule? wait, this actually doesn't use logarithms at all, it's more of a difference engine really

daniel-cussen 3y ago
Yeh, it bears many resemblances to Babbage's difference engine.
- kragen 3y ago
  yeah, sorry for making the slide rule joke before even reading the abstract

hdhsjsbv 3y ago

What is the algorithmic complexity (Big O) of this? And thank you for great submission. I skimmed it and I enjoyed it. But didn’t read the cost function section with much attention.

KETpXDDzR 3y ago

I'm unsure if this yields any computational benefits over classic multiplication. "In real arithmetic, multiplication may be faster for the following reason: When two real numbers are multiplied, the mantissae are multiplied together and the exponents are added, and these operations can be carried out in parallel. When two real numbers are added, first the mantissa of the smaller number must be shifted so that the exponents match (a process termed normalisation). Then the mantissae must be added. The result of the addition may overflow the original word length by 1 bit, or it may generate any number of leading zeros. Therefore the result must be normalised again. There are therefore 3 steps and they must be done in series." - https://www.researchgate.net/post/Is-multiplication-slower-than-addition-on-modern-CPUs https://www.researchgate.net/post/Is-multiplication-slower-t...

daniel-cussen 3y ago
One addition and one move replacing one multiplication? Absolutely makes things much cheaper.
- kragen 3y ago
  well, probably. it likely depends on how the move works; muxes aren't free and driving long wires isn't either but the confusion in the comment you are replying to is that it thinks you are deriving a floating-point matrix multiply algorithm, when in fact you are deriving an integer matrix multiply algorithm floating-point adds are slightly more expensive than floating-point multiplies integer multiplies are enormously more expensive than integer adds (in power and area, though not in time)
KETpXDDzR 3y ago
To support this: "ADDSS/SUBSS take 1–3 cycles while MULSS takes 0.5–5 cycles." - http://www.agner.org/optimize/ http://www.agner.org/optimize/

Drunk_Engineer 3y ago

As a chip designer, I'm dubious of this claim: "The advantage of performing matrix multiplication using only addition for arithmetic is that it then becomes feasible to build special- purpose chips with no multiplier circuits. Such chips will take up less space per on-chip processor." Perhaps that is true in a toy design, but in real-world chips the multiplier uses only a very tiny fraction of chip real-estate. And even if the matrix-multiply can be eliminated, there are other uses for multiply operations. I once attended a chip design conference where NVidia discussed its latest GPU. In one of the slides showing block layout, the designers pointed out how barely any silicon was being used for actual floating operations -- the vast majority was for pipelining and moving bits around.

brigade 3y ago
That’s because CPUs and GPUs are useful for more than just matrix multiplication. TPUs aren’t; they assume highly regular data movement in and out of the ALUs.
hedgehog 3y ago
It of course depends on workload but I know more than a little about this specific problem space and reducing the space+energy cost of the multipliers is useful. If the idea proposed worked well enough it might be a useful block in a camera ISP chip, audio interface for wake word and speech preprocessing, and similar applications where the models are small and energy is precious.
- creato 3y ago
  I don’t know, sorting requires a lot of moving data around, which is expensive for energy too. Maybe this will be used for vectors of small fixed/bounded size, but then you don’t get to amortize the cost of the logs as much either.
imtringued 3y ago
I once saw a professor show me their latest taped out CPU (multi project wafer of course) and it had one tiny core that is supposed to control the wake-up of the larger processor. The sleep controller has no memory and is a thin slice that is barely visible. Meanwhile the primary processor is much larger but it too is completely dwarfed by the memory it is being surrounded by. The idea of throwing out parts of the ALU is ridiculous. The only situation where this would make sense is in some kind of processing in memory situation where your logic process does not permit large CPUs and you expect to have hundreds of cores per chip with multiple chips on a single DIMM.

jiggawatts 3y ago

Instead of sorting, just count the occurrences of the distinct values. For 8-bit values, this requires only 256 registers, each with a relatively small number of bits. E.g.: if the maximum matrix size is 16K*16K, then only 14 bits per accumulator is required. This is just Radix sort and is very easy to implement in digital circuits. It can even reuse the same adder circuits.

daniel-cussen 3y ago
Sorting is very fast since i designed a sorting algorithm tailor-made for this problem, which is about as fast as your approach. Difference being the numbers are 32-bit, so iterating through the entire array of all possible 24-bit mantissas (i know they're 23 bit, but the implicit initial 1 of normal (vs denormal) values is explicit here) would be way too slow. Otherwise you'd be right, 8-bit values you can just use counting-sort, no problem. Or 14 bits, same deal. Now also notice there's a difference between the matrix size and the mantissa size, we care about the mantissa size, so it's 24 bits.

sabhiram 3y ago

Fascinating paper. We design an inference accelerator which more or less accomplishes this by quantizing input tensors into logarithmic space. This allows the multiplication (in convolution especially), to be optimized into very simple adders. This (and a few other tricks) has a very dramatic impact on how much compute density we achieve while keeping power very low. We keep the tensors in our quantized space throughout the layers of the network and convert the outputs as required on the way out of the ASIC. We achieve impressive task level performance, but this requires some specialized training and model optimizations. Very cool to see ideas like this propagate more into the mainstream.

KRAKRISMOTT 3y ago
Isn't matrix multiplication already a convolution? You are rotating the right hand side matrix anti clockwise 90 degrees and then convolving it upon the LHS matrix from top to bottom.
- sabhiram 3y ago
  The point above regarding convolution had to do specifically with accelerating 3x3 and above convolutional operations, as the product and the accumulation can be done in a few clock cycles if setup with care and love.
- kragen 3y ago
  no, it is not, and i am not discrete convolution is cₙ = Σᵢaᵢbₙ₋ᵢ there is no way in which the indexes into the input matrices in a matrix multiplication are formed from sums or differences of indices and dummy variables however, convolution is a matrix multiplication, specifically multiplication by the circulant matrix of the convolution kernel hth, hand
  - KRAKRISMOTT 3y ago
    Sure it doesn't sum the whole matrix but it does sum row by row. Also how did you type out LaTeX in HN? Or is that a font?

daniel-cussen 3y ago

Unfortunately i cannot answer questions as unlike i chip i must now sleep. It's 2:42 AM here. First thing in the morning i'll be on it.

Vasniktel 3y ago

Thanks for the paper Daniel. Very easy to read and understand. I believe I might have found a minor typo that made me scratch my head for a second. On page 3 in the part where you describe the "follow pointers" part of the algorithm you wrote vi=sj and then cpi=csj whereas I believe you meant cvi=csj and that we can now replace vi with csj to make it cvi. Let me know if I'm misunderstanding something here.

daniel-cussen 3y ago
Thanks, help finding typos is appreciated! It'll make things easier for when this gets published in a peer-reviewed journal, which is in the works.

Roark66 3y ago

I learned (assembly)programming on a chip that had no multiplication instruction. It was 6510 (a version of popular 6502) and I fail to see the benefit. Back then every multiplication had to be done via addition in loop and division with subtract/compare(except certain numbers like powers of 2 where one could bit shift). You can imagine how slow it was. I was envious of my friends with Amigas (68k cpu) who had chips that were capable of multiplication in hardware. It seems obvious that a properly tuned hardware implementation is always going to be faster than doing the same thing in software. Taken to the extreme this is the crux of the old RISC vs CISC debate.

LovinFossilFuel 3y ago
[dead]
imtringued 3y ago
This also reminds me of the days when division was not implemented in hardware on ARM chips.

inglor 3y ago

Did the comments here actually read the paper? It just does "russian peasant" multiplication simulating multiplication with addition. There is no new math discovered as far as I understand. It's basically "we know how to do multiplication with a lot of additions". If this was effective rather than just "simulate multiplication with a lot of additions" it would have been super interesting for parallelization of multiplications and communication bounds.

mathisfun123 3y ago
> Did the comments here actually read the paper? It just does "russian peasant" multiplication simulating multiplication with addition. Hate to break it to you but often not even the reviewers actually read the paper.
lang4d 3y ago
The main content of the paper is trying to minimize the number of “russian peasant” multiplications that need to be performed. I would say those are the interesting parts. Section 2.3 claims dropping the number of additions by a factor of 6 from the naive algorithm. Seems like doing the sorting, recursion, and alignment would have a nontrivial performance penalty, but it’s still a pretty interesting idea.
kragen 3y ago
this is not correct probably it would improve the paper to remove the russian-peasant-multiplication references entirely, or reduce them to a throwaway aside in one place in part this is because you surely won't be the last person careless enough to make this obvious error but also it's because russian-peasant multiplication is a totally normal way for hardware multipliers to work, and the main content of the paper is totally decoupled from whether the final multiplication at the end of all the reductions are done with russian-peasant multiplication or (as would probably be a better idea) something like a dadda multiplier or a booth multiplier

hamilyon2 3y ago

I rarely let myself a negative comment, but core of article is authors realising that n-bit multiplication is n additions. So, absolutely nothing interesting or new

peepeepoopoo16 3y ago
From what I can tell, it memoizes the intermediate additions and then uses that to amortize the adds across multiple array elements and achieve speedups.
- kragen 3y ago
  neither of these comments is correct
  - peepeepoopoo16 3y ago
    Mind offering an explanation?
    - kragen 3y ago
      there is a perfectly clear explanation in the paper
daniel-cussen 3y ago
Uh, you clearly didn't get the proof. N-bit multiplications performed with a single addition and a single move. Proof involves showing superiority over the number of additions in Russian Peasants.

nabla9 3y ago

Wow. Jeffrey Ullman? Turing Award, Neumann medal etc. He is now 80 years old. Ullman is of the authors of several legendary computer science books Dragon Book (Compilers: Principles, Techniques, and Tools) the Cinderella Book (Introduction to Automata Theory, Languages, and Computation), Green Dragon Book (Principles of Compiler Design) He was the thesis advisor for Sergey Brin, Ravi Sethi, Surajit Chaudhuri

giovannibonetti 3y ago
His book about Standard ML is very interesting, too. It is a great introduction to strongly-typed functional languages like Haskell, Ocaml and F#.

rustybolt 3y ago

Sounds like bullshit to me? The 1x1 case reduces to multiplication so it's multiplication without multiplication?

amelius 3y ago

Multiplication in binary is just addition of various shifted versions of one of the operands. So it should not be surprising that this is possible or perhaps even efficient.

mratsim 3y ago

At a glance this sounds like a re-discovery of addition chains and using them to construct Pippenger algorithm. But applied to matrices instead of group elements. See: https://github.com/mratsim/constantine/issues/37 https://github.com/mratsim/constantine/issues/37

kragen 3y ago
i don't think that is the case but i don't really understand pippenger's algorithm. what would pippenger's buckets correspond to in this 'fgemm' thing?

scscsc 3y ago

Does anyone know anything about the affiliation of the first author, "Fgemm SPA"?

daniel-cussen 3y ago
Fgemm SpA, coming soon.

jhj 3y ago

This feels very disconnected from the realities of hardware to the point of impracticality. More energy is typically burned on RAMs/flops (storing bits and shuffling them around) than the combinational logic portion (adders/multipliers/etc) doing the arithmetic on real designs these days. Sorting, computing differences and the like involves a lot of data movement and likely temporary storage for buffering as well. I've evaluated fixed-function sorting in ASIC designs, it's not cheap at all. This feels like the authors had some ideas of circuit design concerns from the 1980s ("hardware multipliers are very expensive!") and trying to port that to the present.

daniel-cussen 3y ago
No comment.

amai 3y ago

See also „Multiplying and Dividing on the 6502“ , which was an early microprocessor without multiplier unit https://news.ycombinator.com/item?id=31911655 https://news.ycombinator.com/item?id=31911655