Re:Bolt: Faster matrix and vector operations that run on com...
by jacobolus on Saturday June 18, 2022 @03:54PM
(#31793213)
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 com...
by ffast-math on Saturday June 18, 2022 @11:51PM
(#31796007)
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.
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?