3 ms·

Nice idea and write-up! I'm also working in the field of sparsity for neural network inference. Two things come to mind that you should be aware of: - Compared

Nice idea and write-up! I'm also working in the field of sparsity for neural network inference. Two things come to mind that you should be aware of: - Compared with a dense Matrix-Vector Multiply implementation, your algorithm adds algorithmic complexity, but reduces memory traffic. Because Matrix-Vector is usually memory-bound, your throughput increases when you can reduce memory accesses. For batch sizes > 1, the speedup would likely disappear very quickly because you are no longer bottle-necked by memory accesses. (Assuming that's a scenario you are interested in) - As a comparison, I would also like to see another model with an architecture that is 2x faster (so if you apply your method to a 13B parameters LLM at 50% sparsity, how does its performance fare against a 7B parameter LLM? How does it compare to the same LLM quantized to half the baseline bitwidth?). If you could show that your sparse model produces higher fidelity output in the same amount of time (compared to an established inference framework), I'm sure that that would make for an interesting publication. - Because you are omitting multications, your approximation error will likely be biased to have always a smaller absolute value than the true result. If you can add a correction term to compensate for that systematic error, this likely gives you slightly better performance.

kolinko 3y ago
> Compared with a dense Matrix-Vector Multiply implementation, your algorithm adds algorithmic complexity, but reduces memory traffic. Because Matrix-Vector is usually memory-bound, your throughput increases when you can reduce memory accesses. For batch sizes > 1, the speedup would likely disappear very quickly because you are no longer bottle-necked by memory accesses. (Assuming that's a scenario you are interested in) It doesn't really increase an algorithmic complexity. It is O(effrt * inDim * outDim) for multiplications, O(inDim) for calculating dispatch and O(~inDim * log inDim) for finding the cutoff point. O-metric is not great for GPU work, but in this case it roughly holds. The main issue is the architectual limitations of GPUs - the algorithm needs more register / threadgroup / cache memory than the traditional ones, and that would be the main bottleneck then. And the fact that it's not straightforward to parrarelize the work, since every multiplication uses different buckets (just like with MoE models). As for a bigger architecture - I did a lot of testing on Mixtral, which is essentially a 13B model, and my feeling is that it holds way better there. In terms of inference speed per effort it holds as well, and in terms of quality per effort it holds up readable results until 12-16%, not 20-25%. The tests I did were limited, and I broke the Mixtral implementation when I implemented Mistral, so I don't have hard data on this - but will definitely fix it soon. My intuition also is that the bigger the model the more you can shave off from effort. - Ommitting multiplications - that was my guess also, but unintuitively it's not! I have some charts, but didn't manage to prepare them for a release yet. Because the values in the matrix are evenly distributed in positive and in negative numbers, after a certain threshold there is not much drift in the resulting values.

kolinko 3y ago

> Compared with a dense Matrix-Vector Multiply implementation, your algorithm adds algorithmic complexity, but reduces memory traffic. Because Matrix-Vector is usually memory-bound, your throughput increases when you can reduce memory accesses. For batch sizes > 1, the speedup would likely disappear very quickly because you are no longer bottle-necked by memory accesses. (Assuming that's a scenario you are interested in) It doesn't really increase an algorithmic complexity. It is O(effrt * inDim * outDim) for multiplications, O(inDim) for calculating dispatch and O(~inDim * log inDim) for finding the cutoff point. O-metric is not great for GPU work, but in this case it roughly holds. The main issue is the architectual limitations of GPUs - the algorithm needs more register / threadgroup / cache memory than the traditional ones, and that would be the main bottleneck then. And the fact that it's not straightforward to parrarelize the work, since every multiplication uses different buckets (just like with MoE models). As for a bigger architecture - I did a lot of testing on Mixtral, which is essentially a 13B model, and my feeling is that it holds way better there. In terms of inference speed per effort it holds as well, and in terms of quality per effort it holds up readable results until 12-16%, not 20-25%. The tests I did were limited, and I broke the Mixtral implementation when I implemented Mistral, so I don't have hard data on this - but will definitely fix it soon. My intuition also is that the bigger the model the more you can shave off from effort. - Ommitting multiplications - that was my guess also, but unintuitively it's not! I have some charts, but didn't manage to prepare them for a release yet. Because the values in the matrix are evenly distributed in positive and in negative numbers, after a certain threshold there is not much drift in the resulting values.