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.

Took years to get to this point in terms of the effort I dedicate to getting recognition for my work.

Very happy to have met Professor Jeffrey Ullman.

The general public wants something simple and useful.

The writers want recognition.

I learnt that when I wrote my own thesis. I tried to be simple and useful but I discovered something else when thinking about the subject: I wanted to make sure that my thesis gets good grades.

Now I’m currently doing research on a niche statistics topic and I would be lost without papers.

How does one figure out “this is what we currently understand about x” without research papers and plundering scihub?

So there are very few results you can expand upon. Lexical priming turned out to be reproducible and usable as a tool, the Stroop effect too. But those are exceptions. However, they don't explain the underlying mechanism. E.g., the Stroop effect is 90 years old, and there's no explanation of how it works. So if you read text books that explain you the state of the art of around 1980, you're practically up to date as far as real knowledge is concerned. The rest is infighting and publishing for its own sake.

And psycho-linguistics at least has some experimental standards, because it is a fairly limited topic and it is suited to lab settings. Other fields don't even have that. Social psychology is a joke. Articles are based on questionnaires and introspection.

That's why articles in those fields are not well read. They get read by a small audience, mostly people in the same school of thought, and mostly to add to the citation section. But not for knowledge.

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.

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)

If you want to learn deep stuff with clarity, those old books are still the way to go.

i know a lot of math (hence the name) - basically lots of stuff scattered around analysis, geometry, and complexity theory, at varying levels between senior undergrad and research level (MIP and SAT and SMT). this basically tracks my academic progression (from math undergrad to cs phd student).

the stuff that i can explain the best is the research level stuff. why? because i can explain it in the same relatable terms that i learned it through, since i learned it when i needed it - through relatable examples that clearly motivate the ideas. i've done it many times - often a junior phd student will ask me what i work on and i start telling a story that starts with some really common thing that gives a foothold ("how would you figure out which variables in a for loop are reused") and then step by step you "follow your nose" to the ideas behind the proofs and techniques and etc.

what's my point? lots of academic math is useless frippery that couldn't be motivated in this way and so it can't be articulated except formally.

It doesn’t work so much for proofs in a lot of mathematics, especially because the “common ground” you speak pf starting at would be hours of explanation behind what you’re trying to say.

count = 0

for x in list:

  if x == 1:

    count +=1

  return 3

  return 1

if you want to see how cryptic it is: https://arxiv.org/abs/2103.07510

Apparently not so secretly.

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

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

- The silicon simplification also seems relevant to Samsung's in memory computing effort: https://www.servethehome.com/samsung-hbm2-pim-and-aquabolt-x...

- I wonder if this would be relevant to llama.cpp's CPU inference?

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.

I'm having trouble understanding this. Are you saying that GPUs invest area on floating-point multipliers because FLOPS are an important marketing metric? The only thing that mattered to us was: how can we make these operations faster within the area and power constraints we have? Reducing energy consumption was thus a major goal.

I wish you luck. If I were in your shoes, I would approach NVidia or Google -- and expect to be hammered with tough questions.

Yes. That is precisely what i'm saying. If i'm mistaken in saying that that's one thing, but as far as it being what i'm saying, it very much is. It's been an important guiding principle for some time now in the project, that recent chips--including FPGA's--tend to have hard IP for floating point multiplication.

Now spending a lot of chip area on getting more FLOPS is not necessarily a bad decision if there is no alternative for achieving fast matrix multiplication. Almost any method is sensible if there was no better alternative available when the decision to use that method was made. In addition, fgemm only really makes sense when matrices contain over 1000 elements per row or column, not sure how much more than 1000 per vector but more than that. Small and in particular small and dense matrices are still best multiplied exactly the way GPUs multiply them, with many floating-point multiplier circuits in parallel. It's not stupid in the least.

Yeah so NVidia n Google have the same business model i'm going for, Google having TPUs in its datacenters that do work that cannot be reverse engineered. Google does not sell TPUs. You can use them by sending Google the work, and you'll benefit from much lower cost and faster speed. NVidia has a similar offering, just not as well-known. That's the correct business model in my analysis, and what fgemm will sell. Sell the work.

Help me understand: TPUs cannot be reverse engineered because the user doesn't have access to the physical device, but other devices like GPUs can?

Can you show some examples of reverse-engineering of GPUs that has been performed on the basis of having physical access to the dies? Are you aware of any reverse engineering done on them using other means? How much has this reverse engineering prevented e.g. NVidia from being financially successful? Finally, since patents are freely available to the public once they have been granted, does that nullify some concerns regarding reverse engineering?

I'm not an entrepeneur, so take this with a fistful of salt, but having worked at places like NVidia, I would never try to compete head to head with them, as a startup. Very few semiconductor startups achieve any success, and the ones that do start by finding a very particular market niche where the established players aren't even trying to play.

Again, I wish you good luck.

Also the claims about huge amounts of area being dedicated to multiplication are false. ALU size is mostly irrelevant.

IANAL, but I do not believe semiconductor masks are copyrightable under US law (my limited understanding is that there is essentially due to the fact that the mask is inherently functional and/or aspects of the merger doctrine). There is a separate sui generis mask work protection via 17 U.S.C. §§ 901-914.

Edit: Moreover, I'm unsure how you figure a chip itself is protected by trade secret, since reverse engineering an IC is not terribly difficult.

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.

Seems like doing the sorting, recursion, and alignment would have a nontrivial performance penalty, but it’s still a pretty interesting idea.

Hate to break it to you but often not even the reviewers actually read the paper.

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

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

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

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)

- http://www.agner.org/optimize/

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.

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

i typed special characters with the compose key; cf. https://github.com/kragen/xcompose

not as easy as latex but more compatible

See: https://github.com/mratsim/constantine/issues/37

wait, this actually doesn't use logarithms at all, it's more of a difference engine really

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.

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.

This is just Radix sort and is very easy to implement in digital circuits. It can even reuse the same adder circuits.

https://news.ycombinator.com/item?id=31911655

And thank you for great submission. I skimmed it and I enjoyed it. But didn’t read the cost function section with much attention.

So it should not be surprising that this is possible or perhaps even efficient.

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

EDIT: alright I fixed all the single letter abbreviations.

> Then underneath each number write down the difference between that number n the one before it

   (-⟜»∘⍷∧)⍟(1+↕3) 11‿39‿23‿28‿31‿19‿32‿5‿1‿9

   -⟜»∘⍷∧ vec

   +´-⟜»∘⍷∧ vec

   ⍷∧ vec

   +`-⟜»∘⍷∧ vec

like, if after 7 iterations, we have

1 2 3 7 9 12 18 23 27 57 72 95 129 680 718 994 2631 10770 18047 785265

that gets down to four items after 14 iterations

1 54 2814 716356

but because that's roughly exponential it takes a beastly number of iterations to get down to 2 items

i guess i should read the paper

Yeah hey the paper will not be that painful to read if you can already perform the reduction steps. I'll answer further questions.

Yeah so for floating point an exponential distribution is bounded in how many elements it can contain for a given exponent, so it works out quite nicely. It does not work on bignums.

Nice to see someone use lower-case i like i do!

unless i fucked it up, it looks like you can insert a separate renormalization step before the sorting where you shift each number to the left by a variable amount, like a floating-point unit always does with the mantissa (except subnormals), and that seems to solve the exponential distribution problem; it always seems to get down to a single item from 10000 34-bit items in about 15 steps

no wait, it doesn't really solve it, because a vector of the first 1000 fibonacci numbers still takes 485 iterations. but the last number in that vector is a 694-bit number. it does seem to improve it enormously

i thought this might make it work much worse (because in a sense it's adding bits to the numbers: what used to be a 1-bit number might now have n-bit-wide differences with the numbers before and after it) but at least in random tests it seems to make a huge improvement

just to clarify, what i'm doing (with unsigned integers) is

    def normalize(v):
        for vi in v:
            while vi < 2**34:
                vi *= 2
            yield vi

    def nreductions(v):
        while True:
            v = list(sortu(normalize(v)))
            yield v
            v = list(diffs(v))

the shifts of course have to be undone in the other direction, just like the permutations, but i don't think that's a problem?

(oh, now i see that in §3.1 'alignment' you are already doing something like this, except that you're shifting right to reduce the number of duplicates and eliminate one extra bit of differencing per iteration, not left to reduce the dynamic range of the data. for smallish numbers that seems to be roughly as effective, but left-shift normalizing works a lot better than right-shift aligning for 256-bit numbers)

i haven't tried doing any actual vector multiplies with this algorithm yet so if i did fuck it up i wouldn't have noticed

this is a pretty exciting algorithm, thanks for sharing

First thing in the morning i'll be on it.