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.
[ Parent
| on HN ]
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.