Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Multiplying Matrices Without Multiplying

arxiv.org

Post reply on HN
Print view View original

41–50 of 124 posts

Re: Multiplying Matrices Without Multiplying

#41

Post by thwoeri2324 »

infogulch wrote: post #36

I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML. [0]: https:/…

Quick note: the exp does not work the way it does with scalars.

https://en.wikipedia.org/wiki/Matrix_exponential#Elementary_...

Re: Multiplying Matrices Without Multiplying

#42

Post by ffast-math »

yangjunpro wrote: post #16

An interesting work, with some to-be-addressed questions: 1.The paper only covers the GEMM part with small-scale experiments(CIFAR-10/100), not covering convolution, not covering GEMM part in more popular network such as Transformer/BERT, etc. 2. It is still an approximating method, meaning potential accuracy loss. So I think this method is less attractive to training acceleration scenario, maybe potentially as a com…

Great observations. I see this paper as the first in a three-part series. The second part is specializing it for convolution (which has additional structure to exploit), and the third is hooking these approximate ops into deep neural nets the way people currently do with scalar quantization / pruning.

I'm not optimistic about beating tensor cores when running on GPUs, at least until/unless we get similar hardware support.*

Barring better hardware support, the killer app is probably CPU inference--once there are Conv implementations and the necessary GPU kernels to train the network.

*Aside: this support would be pretty doable since the kernels look almost identical to GEMM kernels--you just need a multiplex-add rather than a multiply-add. On an x86 machine, all it would take is a vpshufb-add and a 4-bit unpack instruction.

Re: Multiplying Matrices Without Multiplying

#43

Post by criticaltinker »

yangjunpro wrote: post #16

An interesting work, with some to-be-addressed questions: 1.The paper only covers the GEMM part with small-scale experiments(CIFAR-10/100), not covering convolution, not covering GEMM part in more popular network such as Transformer/BERT, etc. 2. It is still an approximating method, meaning potential accuracy loss. So I think this method is less attractive to training acceleration scenario, maybe potentially as a com…

> I think this method is less attractive to training acceleration scenario

The proposed hash based encoding function is not differentiable, so it doesn’t appear this method can be used for training at all.

I’m not aware of any hash functions that are analytically differentiable, so to support efficient back-propagation I suspect that some fundamental changes to this method would be necessary.

Re: Multiplying Matrices Without Multiplying

#44

Post by ffast-math »

infogulch wrote: post #36

I wonder how much alternative number representations have been studied for use in matrices. Like, storing the log of values instead so that multiplication can be done by just adding. Or something like Zech's logarithm. Or even, take the log of whole matrices (which is a thing apparently [0]), then adding them to compute their multiplication. I wonder if the logarithm of a matrix can be computed using ML. [0]: https:/…

There's been some work on doing adds instead of multiplies (e.g., https://arxiv.org/abs/2012.03458). And I think float8 will roughly be doing this under the hood.

Personally, I'm not sure whether this is the path to go down or not. Doing everything in log space could help from a hardware perspective, since multiply-adds are much more complex than adds. But it 1) doesn't reduce the number of operations being performed, 2) might increase the necessary bit width for a given level of fidelity (depending on your input distribution and other factors), and 3) might make accumulate operations expensive, since these aren't cleanly expressed in the log domain.

Re: Multiplying Matrices Without Multiplying

#45

Post by ffast-math »

leecarraher wrote: post #22

For some reason they run all their tests single threaded. Seems like parallelism is where all computing hardware is inevitably going. I also wish they had run time comparisons to more recent matrix sketching and multiplication method such as frequent directions, newer FJLT implementations, and RIP matrices based on hashing.

We compared to several frequent directions variants, Fast Johnson–Lindenstrauss, some other hashing-based methods, and a bunch of other approximate matrix multiplication approaches. We had to omit some of them from the results section though because they were 10-100x worse than exact matrix products and they ruined the plots. More info in appendix E5.

As far as single threaded, there's a simple answer and a subtle one. The simple answer is that we consider the core subroutine a single thread would run in a multithreaded context, not how to do the multithreading. These are basically orthogonal issues since matrix multiplication is embarrassingly parallel and our method would parallelize just like any other. More details in appendix E2.

The subtler answer is that we could do even better in the multithreaded context if you could fuse the encoding step with whatever earlier code produces the larger matrix. This is a result of matrix products becoming memory-bandwidth-bound in the limit of sufficient cores, combined with our approach reducing the size of the matrix by a huge amount.

Re: Multiplying Matrices Without Multiplying

#46

Post by robotresearcher »

mhh__ wrote: post #39
Ar-Curunir wrote: post #26

Earlier quoted context omitted.

Computer Science doesn't mean empirical stuff only, nor does it mean evaluations with code. Theory has its place, and so does systems work. No need to denigrate one or the other.

I was trying to be clear that I was referring to papers which are talking about code they wrote. If you wrote (say) a program to predict the throughput of machine code, then I want to be able to reproduce the results you claim - thats a real example, no hint of any source yet and I've been looking. If we can't reproduce it isn't really science. I know academics often write bad code and don't like to publish their dir…

Did you ask them for their code?

Re: Multiplying Matrices Without Multiplying

#47

Post by ltbarcly3 »

antonzabirko wrote: post #33
honie wrote: post #20

Earlier quoted context omitted.

I don't disagree with you on the potential financial burdens faced by PhD students but, in this case, and if I haven't missed anything, the infrastructural barrier is not high: > All experi-ments use a single thread on a Macbook Pro with a 2.6GHz Intel Core i7-4960HQ processor. Unless stated otherwise, all timing results use five trials, with each trial reporting the fastest among 20 executions. It may also be worth…

I meant learning barrier. If i had the money i likely would go for it though!

I really don't know how to respond other than to say:

"I would have done this years ago if I knew how to do it" is fantastically narcissistic.

Re: Multiplying Matrices Without Multiplying

#48

Post by davesque »

cs702 wrote: post #31

Every element of a matrix multiplication is a dot-product of two vectors. The dot-product of two vectors quantifies their similarity -- in fact, we call it "dot-product similarity" in a nearest-neighbors context: If the dot product > 0, the vectors point in similar directions; if It's not too hard to imagine that it might be possible to learn representative K-means clusters of training vectors and then, at run-time,…

Thanks for your succinct summary of the result.

Just the other day, I was thinking about how useful clusterings seem in summarizing the landscape of a set of points in any number of dimensions. This work seems to be built on top of the same insight as well as the innovation of using hashing to speed up the similarity checks.

Re: Multiplying Matrices Without Multiplying

#49

Post by m00x »

ltbarcly3 wrote: post #47
antonzabirko wrote: post #33

Earlier quoted context omitted.

I meant learning barrier. If i had the money i likely would go for it though!

I really don't know how to respond other than to say: "I would have done this years ago if I knew how to do it" is fantastically narcissistic.

Another form of: "I could totally have built Google or Amazon if I wanted to, I'm just a lazy genius."
Post reply on HN