3 ms·
Maddness is their more recent work and yields 100x speedups: https://arxiv.org/pdf/2106.10860.pdf https://arxiv.org/pdf/2106.10860.pdf The code for Maddness is
by cgreerrun 4y ago
Maddness is their more recent work and yields 100x speedups: https://arxiv.org/pdf/2106.10860.pdf 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.
- skohan 4y agoIt'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?
- jacobolus 4y agoFrom 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.
- ffast-math 4y agoThere's definitely a tradeoff between speed and accuracy. We characterize this for various problems in the paper (https://arxiv.org/pdf/2106.10860.pdf 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.