There's commentary here which seems to be talking about matrix multiplication in general and ignoring real implementations, which are dominated by considerations of the memory hierarchy. They actually introduce operations, like packing for sufficiently large dimensions but not for smaller, and prefetch. Some of that seems only to be tunable empirically for the micro-architecture too. (I don't know how the considerations vary between CPU and GPU.) Fairly recent work on Strassen implementation, talks about that and the normal Goto-type algorithm: https://jianyuhuang.com/papers/sc16.pdf
Discovering faster matrix multiplication algorithms with reinforcement learning
111–116 of 116 posts
Re: Discovering faster matrix multiplication algorithms with reinforcement learning
#112> Leveraging this diversity, we adapted AlphaTensor to specifically find algorithms that are fast on a given hardware, such as Nvidia V100 GPU, and Google TPU v2. These algorithms multiply large matrices 10-20% faster than the commonly used algorithms on the same hardware, which showcases AlphaTensor’s flexibility in optimising arbitrary objectives. 10-20% performance improvement in matrix multiplications is pretty a…
That doesn't say exactly what was run and how. From measurements with nvblas, that difference could be dwarfed by the effect of tile size and pinning buffers or not.
Re: Discovering faster matrix multiplication algorithms with reinforcement learning
#113Always 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 and the answers given there.
Re: Discovering faster matrix multiplication algorithms with reinforcement learning
#114Will this be efficient for sparse matrices ?
Re: Discovering faster matrix multiplication algorithms with reinforcement learning
#115Earlier quoted context omitted.
If you have to process many such matrices, you’re not at O(1). I would imagine that’s what the O is referring to in this case.
If you look at it that way then any algorithm is just o(n) where n is the number of matrices. O does not care about constant factors
There's a better explanation here: https://fgiesen.wordpress.com/2022/10/06/on-alphatensors-new...
This is for matrix multiplication where elements are themselves 4x4 matrices. So yes, indeed this is about multiplying many many 4x4 matrices where N is the size of the outer matrix.
Re: Discovering faster matrix multiplication algorithms with reinforcement learning
#116Machine learning for finding matrix multiplication algorithms is not so new. The problem was solved before with other methods. For example:
https://www.researchgate.net/publication/341942316_Searching...