Bolt: Faster matrix and vector operations that run on compressed data • Hacker News Board

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

#41

Post by a-dub » Sun, Jun 19, 2022, 3:44 PM UTC

ffast-math wrote: post #33

a-dub wrote: post #31

any thoughts on trying to build a sort of vq-blas?

IMO it would be super cool and I hope someone does it. There are a lot of interesting tradeoffs around which techniques to use for which matrix sizes and under which assumptions about read vs write ratios, what you have a training set for, whether you can fuse compression intro previous ops, etc.

hm... so maybe a better place would be one of these toolkits like jax where the entire computation is known at optimization time where a blas would potentially have to do some heroic heuristics to try and fully optimize underneath the blas interface.

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

#42

Post by nynx » Sun, Jun 19, 2022, 5:57 PM UTC

ffast-math wrote: post #22

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…

Fascinating, might try implementing this on an FPGA.

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

#43

Post by ffast-math » Mon, Jun 20, 2022, 2:01 AM UTC

fragmede wrote: post #40

ta_tunestub wrote: post #35

Earlier quoted context omitted.

Are you aware of any code/projects that convert something like a fully trained resnet50 model into a maddness optimized, approximate model? An approximate but speedier resnet inference model that runs on a CPU would be useful even if it’s not quite as fast/accurate as a GPU inference model, since currently the cost to run a GPU is typically higher than CPUs.

Not to distract from the clearly good technical work you've done here, but why name it Bolt when there's a Fintech startup with the same name. Among other brand confusion issues (Like the Chevy Bolt).

I named it this in 2017 and was only worried about name collisions with other GitHub repos and ML algorithms. Also it's a backronym for Based On Lookup Tables + sounds at least somewhat evocative of going fast, so it was the best name for an algorithm I could come up with.