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

Bolt: Faster matrix and vector operations that run on compressed data

github.com

Post reply on HN
Print view View original

21–30 of 43 posts

Re: Bolt: Faster matrix and vector operations that run on compressed data

#21

Post by ffast-math »

skohan wrote: post #5
cgreerrun wrote: post #4

Maddness is their more recent work and yields 100x speedups: https://arxiv.org/pdf/2106.10860.pdf The code for Maddness is in the same github repo if you search for "Mithral". SIMD instructions can work wonders in the right context.

It's incredible that there's actually this much room to improve. How does this compare to GPU implementations? Also it looks like the optimization is related to running operations on a compressed representation, for the 10x vs 100x speedup, is there a tradeoff between speed and accuracy, or is that extra degree of magnitude just from bringing SIMD into the picture?

There's definitely a tradeoff between speed and accuracy. We characterize this for various problems in the paper (https://arxiv.org/pdf/2106.10860.pdf), but tl;dr is that it speeds things up more at a given level of error when there's more redundancy in your matrices.

Back-of-the-envelope calculation suggests that this won't beat tensor cores on NVIDIA GPUs. This is basically because ~half the die is an ASIC for dense (and 2:4 sparse) matmuls, with no support for the sparsity structure we induce. If 1:16 sparsity were supported or there were a batched warp_shuffle instruction, we'd get similar speedups for GPUs as we do on CPUs.

Re: Bolt: Faster matrix and vector operations that run on compressed data

#22

Post by ffast-math »

nynx wrote: post #3

Wow, this is fascinating. I wonder if hardware could be designed to do this really efficiently.

Definitely. On CPUs, you could make this 2x faster pretty easily with just another execution port for vpshufb / vtbl and a 4bit lo and hi unpack instruction.

Though the real speedup would be allowing dense matmul ASICs to operate on 16-byte tables and 4-bit indices as operands. The reason Bolt and MADDNESS end up so fast is that they produce "sparse" representations that are still contiguous, strided arrays in memory. So the kernels and access patterns are just like those of dense GEMMs (and therefore vectorize-able, etc), but with lookup-adds instead of multiply-adds.

Hopefully-clarifying image: https://imgur.com/a/trOB69U

Re: Bolt: Faster matrix and vector operations that run on compressed data

#23

Post by ffast-math »

anderskaseorg wrote: post #7
raxxorraxor wrote: post #2

This looks good. Why do the vectors have to be dense? Just because of overhead/speed gain being the lowest? Just asking if you could use it universally for all operations if I don't know the density.

If your data is represented as sparse vectors, that sparse representation is already compressed. You wouldn’t want to decompress it to a dense representation just to apply a different, less effective, lossy compression algorithm. That would be like taking a screenshot of a paragraph of text so you can post a JPEG of it to Twitter. Oh, wait.

Exactly. You can run it on sparse inputs. It's just that our implementation doesn't exploit the sparsity, so we don't claim that it will work better.

Re: Bolt: Faster matrix and vector operations that run on compressed data

#24

Post by outlace »

ffast-math wrote: post #20

Author here. Ask me anything--happy to answer questions. Also, if you like this kind of work, you might like what I've been building for the past year: Composer [1]. It speeds up neural net training by a lot (e.g., 7x faster for ResNet-50) [2] and, in contrast to Bolt/MADDNESS, is polished, documented code you can get working in [1] https://github.com/mosaicml/composer [2] https://www.mosaicml.com/blog/mosaic-resnet

I see it noted that this could speed up machine learning inference, but any hope of this being extended to also speed up training? I imagine with 100x speedup in matmuls, albeit approximate matmuls, one could plausibly train on a CPU.

Re: Bolt: Faster matrix and vector operations that run on compressed data

#25

Post by ffast-math »

bee_rider wrote: post #15

I guess the naive approach, if we wanted to do a quick lossy matrix multipy, would be to take the truncated SVD and use that. How does this library compare to the boring strategy, I wonder?

We found sparse, truncated PCA to be the most competitive baseline. We beat it by a lot (see the paper [1]), but the other big drawback is that trading off the rank vs sparsity was an ugly hyperparameter tuning problem. By ugly, I mean that the results were really sensitive to getting this right, it wasn't easy to set a priori, and took a while to iterate on because the sparse PCA trained much more slowly than any other practical alternative.

There are situations where PCA/SVD is the right approach though. Namely, if you need really little error, our method often can't do that, whereas throwing away dims that explain almost no variance can. Also it's just easier to implement.

[1] https://arxiv.org/pdf/2106.10860.pdf

Re: Bolt: Faster matrix and vector operations that run on compressed data

#26

Post by ffast-math »

outlace wrote: post #24
ffast-math wrote: post #20

Author here. Ask me anything--happy to answer questions. Also, if you like this kind of work, you might like what I've been building for the past year: Composer [1]. It speeds up neural net training by a lot (e.g., 7x faster for ResNet-50) [2] and, in contrast to Bolt/MADDNESS, is polished, documented code you can get working in [1] https://github.com/mosaicml/composer [2] https://www.mosaicml.com/blog/mosaic-resnet

I see it noted that this could speed up machine learning inference, but any hope of this being extended to also speed up training? I imagine with 100x speedup in matmuls, albeit approximate matmuls, one could plausibly train on a CPU.

Yes. It's another research project to make this happen, but I think it would be fairly straightforward. The issue is that you can't backprop through the assignment step, so you get no gradient with respect to the input. This mandates a progressive layer freezing strategy. I don't think it would be too hard to get working though; you'd likely just need to train for longer, or start with a pretrained model and fine-tune it as you freeze + approximate the layers.

Re: Bolt: Faster matrix and vector operations that run on compressed data

#27

Post by febin »

ffast-math wrote: post #20

Author here. Ask me anything--happy to answer questions. Also, if you like this kind of work, you might like what I've been building for the past year: Composer [1]. It speeds up neural net training by a lot (e.g., 7x faster for ResNet-50) [2] and, in contrast to Bolt/MADDNESS, is polished, documented code you can get working in [1] https://github.com/mosaicml/composer [2] https://www.mosaicml.com/blog/mosaic-resnet

Thank you for your efforts. I came across your paper/code and posted it here. I was looking to find a technique to cost optimise transformer based question and answering. Presently I am using CPU and getting a GPU is too costly on AWS.

Since I use high level code I don't understand the maths completely. However, I was wondering if your techniques can be beneficial on CPUs?

If I were to use this to improve transformer based architecture what should be my approach?

Re: Bolt: Faster matrix and vector operations that run on compressed data

#28

Post by amitport »

jansan wrote: post #8

THis sounds and looks impressive, but this part struck me: "If you ... and can tolerate lossy compression" What does this mean? I wouldn't have thought that matrix operations can be lossy. Does anybody know to what extend they are lossy and where this would be acceptable?

Neural networks generally tolerate lossy compression. So they are OK here provided that they have demonstrated that their compressed op networks still manage to reach comparable accuracy.

Unfortunately, AFAIKT, the experiments are not very comprehensive. So I wouldn't be surprised to find a good lossy compression for this use case, but I'm not sure if this is such.

Re: Bolt: Faster matrix and vector operations that run on compressed data

#29

Post by ffast-math »

febin wrote: post #27
ffast-math wrote: post #20

Author here. Ask me anything--happy to answer questions. Also, if you like this kind of work, you might like what I've been building for the past year: Composer [1]. It speeds up neural net training by a lot (e.g., 7x faster for ResNet-50) [2] and, in contrast to Bolt/MADDNESS, is polished, documented code you can get working in [1] https://github.com/mosaicml/composer [2] https://www.mosaicml.com/blog/mosaic-resnet

Thank you for your efforts. I came across your paper/code and posted it here. I was looking to find a technique to cost optimise transformer based question and answering. Presently I am using CPU and getting a GPU is too costly on AWS. Since I use high level code I don't understand the maths completely. However, I was wondering if your techniques can be beneficial on CPUs? If I were to use this to improve transformer…

Thanks for posting it!

It should be possible to get large speedups on CPUs, but the trick will be gradually approximating each of the layers in the model (see my reply to sibling comment). It's not conceptually difficult, but will require a fair amount of C++ work to port the code to GPUs* for training; and it will probably go slower than dense ops on modern GPUs due to tensor cores not supporting our memory layout.

I think of this paper as the first in a two-part series, where the next one takes these fast ops and gets them working in full neural nets. (If anyone wants to do this project, happy to coadvise you / talk about it whenever; I won't have bandwidth to do it myself for the foreseeable future).

*Someone recently started doing this as part of their master's thesis: https://github.com/joennlae/halutmatmul

Re: Bolt: Faster matrix and vector operations that run on compressed data

#30

Post by febin »

ffast-math wrote: post #29
febin wrote: post #27

Earlier quoted context omitted.

Thank you for your efforts. I came across your paper/code and posted it here. I was looking to find a technique to cost optimise transformer based question and answering. Presently I am using CPU and getting a GPU is too costly on AWS. Since I use high level code I don't understand the maths completely. However, I was wondering if your techniques can be beneficial on CPUs? If I were to use this to improve transformer…

Thanks for posting it! It should be possible to get large speedups on CPUs, but the trick will be gradually approximating each of the layers in the model (see my reply to sibling comment). It's not conceptually difficult, but will require a fair amount of C++ work to port the code to GPUs* for training; and it will probably go slower than dense ops on modern GPUs due to tensor cores not supporting our memory layout.…

Thank you, I will try to take this up. What would be the best way to reach out to you?
Post reply on HN