3 ms·
> Compared with a dense Matrix-Vector Multiply implementation, your algorithm adds algorithmic complexity, but reduces memory traffic. Because Matrix-Vector is
by 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.