Re:Discovering faster matrix multiplication algorithms with ...
by fulafel on Wednesday October 05, 2022 @04:04PM
(#33100622)
It's interesting how both SIMD and big-o have had so different reasons for being of limited but still significant relevance.
SIMD, and vector processors like it was called in the 70s, delivered practical speedups in simple benchmarks right away but most applications dont't take advantage because of SW engineering reasons. Whereas big-O improvement ignores important components of performance per unit of time (memory access and constant factors) and is purely theoretical in an essential sense.
Re:Discovering faster matrix multiplication algorithms with ...
by chrchang523 on Wednesday October 05, 2022 @01:49PM
(#33098855)
Sometimes. In the case of matrix multiplication, there is a pretty large backlog of "galactic algorithms" going down to ~O(n^2.373) that haven't yet led to real-world improvements. Strassen's ~O(n^2.807) algorithm is only considered over the basic O(n^3) strategy for n>1000.
Re:Discovering faster matrix multiplication algorithms with ...
by HarHarVeryFunny on Wednesday October 05, 2022 @04:05PM
(#33100637)
Winograd O(n^2.37) is a win for 3x3 convolutions in cuDNN, so it can be implemented efficiently.
Re:Discovering faster matrix multiplication algorithms with ...
by chrchang523 on Wednesday October 05, 2022 @04:46PM
(#33101060)
My understanding is that the Winograd minimal filtering algorithms used in cuDNN are different from the O(n^2.37) Coppersmith-Winograd-descended matrix multiplication algorithms. But I acknowledge that these can be considered cousins, produced by the same line of research.
Re:Discovering faster matrix multiplication algorithms with ...
by HarHarVeryFunny on Wednesday October 05, 2022 @05:01PM
(#33101210)
I'm pretty sure there's no difference. It does seem to be pretty hard to turn the theoretical win into a practical one - the GPU kernel needs to be coded extremely efficiently to match the underlying hardware. AFAIK it's only a win for 3x3 - maybe for one other size too. Originally Winograd wasn't supported by cuDNN on NVidia's Tensor Cores (matmul-specific hardware on more recentish GPUs), vs CUDA cores, but a Google search seems to indicate it can be done - not sure if that's in cuDNN though.
It was with theoretical performance improvement that motivated the creation of SIMD and led to real world speed ups.