7 ms·
On AlphaTensor’s new matrix multiplication algorithms
- Greg1970 4y ago
- lacker 4y agoIs 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.
- zekrioca 4y agoAlways caution someone who wants to follow in this research: When somebody promotes a fast algorithm there is often a catch. In this case the issue is numerical stability. There is a theorem that states that any algorithm for n-by-n matrix-matrix multiplication that is componentwise forward stable (as good as it gets in this situation) much necessarily use n^3 scalar multiplications. The authors will therefore waste their time if they carry out their plans and try to optimize for stability. The standard algorithm has the nice property and no faster algorithm can have this property. The question of fast matrix multiplication was raised recently on mathoverflow.net, see https://mathoverflow.net/q/421304/110176 https://mathoverflow.net/q/421304/110176 and the answers given there.
- ekelsen 4y agoIn practice you don't need to recurse all the way down. 1 level of Strassen is enough to get real speeedups (if speedups are possible at all) and certainly for deep learning, the instability introduced by a single level will not matter.
- zekrioca 4y agoDo we need forward stability in the componentwise relative sense? This very much depends on the underlying real life application. If we ignore the question of accuracy and stability, then we just might endanger the people who depend on our software.
- ekelsen 4y agoThat's why I specified the application was deep learning.
- KKKKkkkk1 4y agoWe're talking about algorithms for TPUs, which quietly quantize your float32 matrices to bfloat16 behind your back [0]. This is aimed at a crowd that doesn't care about stability. [0] https://cloud.google.com/blog/products/ai-machine-learning/bfloat16-the-secret-to-high-performance-on-cloud-tpus https://cloud.google.com/blog/products/ai-machine-learning/b...
- doubtfuluser 4y agoWhile I agree with other commenters and also with the article, that this is not like „boom, DeepMind magically speeds up everything and you have to look in more detail at numerical stability etc depending on your use case, there is still something big in here: in the past algorithms were an almost exclusive product of long and deep thinking of experts. Now we saw that AI can be used for algorithm discovery. This can actually have quite big impact. All tiny improvements can add up, some improvement in sorting, some in matrix multiplication, some in lookups, you get the point. All that can accumulate to business advantages. So yes I think this is an important first result.
- mattnewport 4y agoProofs are a pretty important part of algorithm development. Proofs of correctness as well as proofs of algorithmic complexity bounds. At the moment that doesn't seem like something this type of approach can do much for, though perhaps it could be combined with work on automated theorem proving.
- alexmolas 4y agobut in this case, it's extremely easy to prove that the algorithm that they propose is correct, or am i missing something?
- eigenket 4y ago"Correct" means different things in different contexts. In a fairly standard application of matrix multiplication you don't multiply matrices A and B to get AB, instead you have some floating point approximation to A, and some floating point approximation to B, and you want something that you can be confident approximates AB with some bounds. The two most important characteristics of an algorithm are the runtime and the error bounds you can prove. Someone smart once said getting the wrong answer in time O(1) is very easy.
- bheadmaster 4y ago
- ncmncm 4y agoPossibly sorting networks could get practical benefit from the Alpha treatment. I think the largest sorting network proven optimal is for a block size in the teens (13?). Analogously to matrix multiplication, it matters most where comparisons are much more expensive than swaps.
- jackmott 4y ago
- verdverm 4y agoI wonder, was/is the ai able to reproduce the best know algorithms we already have? Can it do so reliably? If this Algo is only good for large matrices, can it reproduce the one for small matrices?
- naillo 4y agoSome good critique on this result: https://twitter.com/cHHillee/status/1577713102434361344 https://twitter.com/cHHillee/status/1577713102434361344 TLDR seems like the baseline strassen implementation they used is questionable wrt how really optimal it is in the first place.
- topaz0 4y agoAlso note: a few tweets down in this thread, the tweeter says "you're right, I retract my criticism". So maybe not extremely well thought out critique after all. On twitter of all places.