Re:Discovering faster matrix multiplication algorithms with ...
by throwawaymaths on Wednesday October 05, 2022 @01:05PM
(#33098214)
No, they count multiplications, 47 vs 49 in the 4x4 case. This assumes that multiplications are the heavy lift relative to additions, memory moves, etc. this is not a bad assumption, and is hardware independent, although there are some proposed 'exotic' hardware solutions where addition and multiplication are equally difficult (via lookup table, limited to about 8-bit x 8-bit) or where addition is harder than multiplication (log space number systems) but I don't think these have been deployed
[ Parent
| on HN ]
Re:Discovering faster matrix multiplication algorithms with ...
by lifthrasiir on Wednesday October 05, 2022 @01:35PM
(#33098651)
That assumption didn't age very well. In many if not most modern architectures multiplication still does take more cycles than addition but can have a higher throughput if scheduled well, and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.
Re:Discovering faster matrix multiplication algorithms with ...
by throwawaymaths on Wednesday October 05, 2022 @01:43PM
(#33098774)
> but can have a higher throughput if scheduled well
Unlikely to be true for matrix multiplications, which have well-defined data dependencies.
> and fused multiply-add can be as fast as a single multiplication, essentially giving a free addition.
Yes, this supports the assumption that multiplication is the heavy lift.
Re:Discovering faster matrix multiplication algorithms with ...
by tlb on Wednesday October 05, 2022 @04:27PM
(#33100875)
With sufficiently parallel hardware, you can do an entire mat4 * mat4 multiplication in 3 cycles. First do all 64 multiplications in parallel, then do 32 adds, then 16 adds to get the final answer.
For operations in GF(2) where they claim a result, a multiply is just an AND gate and an add is an XOR gate. So the fully parallel hardware version is 64 AND gates and 48 XOR gates, with a total gate delay of 3. This is a trivial amount of hardware and could easily be an instruction in some alternate universe where it was useful.
Re:Discovering faster matrix multiplication algorithms with ...
by klyrs on Wednesday October 05, 2022 @06:02PM
(#33101759)
You missed the part where the "4x4 matrix multiplication" refers to multiplication of NxN matrices logically partitioned into sixteen blocks of size (N/4)x(N/4), done recursively.