4 ms·
Is Strassen's algorithm actually used in practice? Oddly enough I find myself doing a lot of matrix multiplication recently. But I am just using cublasCgemm3mSt
by lacker 4y ago
Is Strassen's algorithm actually used in practice? Oddly enough I find myself doing a lot of matrix multiplication recently. But I am just using cublasCgemm3mStridedBatched from Nvidia's cuBLAS library, and it doesn't appear to be public information how it's implemented. Does anyone know if it's actually using Strassen?
Basically the library described at:
https://developer.nvidia.com/blog/cublas-strided-batched-matrix-multiply/ https://developer.nvidia.com/blog/cublas-strided-batched-mat...
I am a bit not-sold-yet on the AlphaTensor stuff because in practice it often seems like shuffling the data around in GPU memory is more expensive than doing the actual multiplications. It takes longer to move values between regular GPU memory and shared memory than it does to do a multiply, right? So all these algorithms that are optimizing the number of arithmetic operations, it isn't even clear to me that they're optimizing the right thing, because they require that you shuffle your data around in weird ways, and they don't generally measure the number of "memory moves" that are needed.
That said, I would be happy to drop in a replacement for cublasCgemm3mStridedBatched and test out if it worked better for me! It doesn't seem like these new AlphaTensor matrix multiplication routines are available as plain old c/c++ libraries yet, though.
- throwawaymaths 4y agoWhy would you just use a warp and do the memory moves on the GPU?
- lacker 4y agoThat is correct, if I understand you correctly, but that doesn't solve the entire optimization problem. You still have to figure out how exactly to handle tiles and transfers to shared memory. This might be a good page for answering this question: https://docs.nvidia.com/deeplearning/performance/dl-performance-matrix-multiplication/index.html https://docs.nvidia.com/deeplearning/performance/dl-performa...
- deleted 4y ago[deleted]
- defrost 4y agoIt's useful enough for the relatively small class of people dealing with matrices of sizes 8192×8192 and above, moreso to those writing backend libraries for targeted computation architectures that can utilise the various weights for moving blocks of data from input source streams between computation nodes, etc. You're correct - the gains come from really knowing the computational architecture and using this approach to find tweaks that optimise operations .. where those operations aren't just atomic mults and adds, but include piped multiply-adds and data moves.
- rpep 4y agoThere’re many people doing larger matrices, but of course they’re mostly sparse and so this isn’t relevant to them.
- deleted 4y ago[deleted]
- lordnacho 4y agoIsn't there some heuristic that uses advanced multiplication algorithms if the matrix is big enough? Perhaps also checking for sparseness if that matters.
- bee_rider 4y agoIIRC, Strassen's algorithm is less stable, so it isn't just a "if the matrix is big enough, go for it" sort of thing, necessarily... although, I've never looked into exactly where the issue shows up. I wonder how well it parallelizes.