Bolt: Faster matrix and vector operations that run on compressed data
1–10 of 43 posts
Re: Bolt: Faster matrix and vector operations that run on compressed data
#2This 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.
Re: Bolt: Faster matrix and vector operations that run on compressed data
#3Wow, this is fascinating. I wonder if hardware could be designed to do this really efficiently.
Re: Bolt: Faster matrix and vector operations that run on compressed data
#4Maddness 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.
Re: Bolt: Faster matrix and vector operations that run on compressed data
#5Maddness 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?
Re: Bolt: Faster matrix and vector operations that run on compressed data
#6Wow, this is fascinating. I wonder if hardware could be designed to do this really efficiently.
It already is right? A GPU is basically a purpose-built linear algebra machine.
Re: Bolt: Faster matrix and vector operations that run on compressed data
#7This 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.
Re: Bolt: Faster matrix and vector operations that run on compressed data
#8THis 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?
Re: Bolt: Faster matrix and vector operations that run on compressed data
#9Maddness 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?
From what I can tell, this is a machine learning based approximation to matrix multiplication by a particular matrix (which it was trained on). It trades accuracy for speed. If you need to multiply many (many!) vectors by a static matrix and you have loose enough error tolerance, this can provide up to 100x speedup.
Re: Bolt: Faster matrix and vector operations that run on compressed data
#10THis 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?
In almost all practical uses of matrix multiplication, we have rounding errors. For example, in 3D it is hard to reverse exactly a rotation and get the exact initial position back.
I don't know what amount of losses we are talking about but in deep learning, several operations don't require a crazy level of compression, and it led to some lightweight float implementations (bfloat, on 16 bits, being the most common but there are also 8 bits floats for extreme cases)
If that's really a 10-100x speed increase at the cost of a bit of loss, I am sure machine learning will love it.