News for hackers. Stuff that matters.
Re:Matrix Multiplication Inches Closer To Mythic Goal by salamanderman on Saturday December 18, 2021 @11:55AM (#29606042)
The part I don't follow is that I thought multiplication used the same number of CPU cycles as addition, so I didn't get the the part where one multiplication replaced with many additions was obviously better. Could someone explain that part? I feel I must be fundamentally misunderstanding something.
Re:Matrix Multiplication Inches Closer To Mythic Goal by teawrecks on Saturday December 18, 2021 @12:34PM (#29606459)
It has nothing to do with clock cycles, it's about how the number of additions and multiplications scale for large matrices.
Re:Matrix Multiplication Inches Closer To Mythic Goal by reportingsjr on Saturday December 18, 2021 @12:26PM (#29606365)
If you look at operations per cycle, in this example for Intel Haswell processors, you'll find that an equivalent add and multiple are quite a bit different.

An add/subtract from a 32 bit register to register is 0.25 cycles per operation.

A multiply from 32 bit register to register is 2 cycles per operation. So a 8x speed difference, not counting for latency, etc.

See page 230 and 231 of this paper: https://www.agner.org/optimize/instruction_tables.pdf

Re:Matrix Multiplication Inches Closer To Mythic Goal by gnufx on Saturday December 18, 2021 @01:12PM (#29606876)
For what it's worth, what counts for normal implementations is the number of multiply-add operations per cycle, typically two on current hardware with FMA.
Re:Matrix Multiplication Inches Closer To Mythic Goal by davidgrenier on Saturday December 18, 2021 @07:20PM (#29610124)
I feel the other answers you got do not directly answer your question for the following reason.

In practice, I believe it is Strassen's algorithm that is used for very large matrix multiplication. Strassen's algorithm improves on both the number of multiplications of scalars as well as addition of scalars which both ends up bound by O(n^(lg 7)).

This is because Strassen's algorithm replaces a single large conventional matrix multiplication consisting of n^3 multiplications and n^3-n^2 additions with 7 recursive application of Strassen's multiplication on matrices of size n/2 along with 15 addition of matrices of size n/2.

The number of additions in a matrix addition is n^2 for a matrix of size n. Thus Strassen's requires 7 recursive calls as well as 15(n/2)^2 additions of scalars.

You win on both fronts if the matrices are sufficiently large and you default to conventional matrix multiplication on a recursive call below a certain threshold.

Re:Matrix Multiplication Inches Closer To Mythic Goal by gameswithgo on Saturday December 18, 2021 @12:37PM (#29606495)
This isn’t about running stuff on hardware. The point is that for a large matrix the number of additions grows much more slowly, such that the represent an increasingly small percentage of operations. So they don’t matter much no matter the hardware at some sufficiently large matrix
Re:Matrix Multiplication Inches Closer To Mythic Goal by Ductapemaster on Saturday December 18, 2021 @12:11PM (#29606215)
The multipliers in CPUs are a mass of logic gates and are challenging to make work in a single cycle. While I believe it is possible with integer multiplication to do so, doing so with other larger data types might take multiple cycles. Division is even more complex, although not part of the question here.

Additions really can be done in 1 cycle, so it's possible to optimize by using them instead of multiplications in operations like this.

Here's a Berkeley EECS lecture on multiplier circuits if you want more info: https://inst.eecs.berkeley.edu/~eecs151/sp18/files/Lecture21...

Re:Matrix Multiplication Inches Closer To Mythic Goal by matbatt38 on Saturday December 18, 2021 @12:14PM (#29606237)
> multiplication used the same number of CPU cycles as addition

Only thanks to lookup table and parallelism. And that's not even true for old computers, where multiplications can take multiple cycles. Also I think complexity is calculated with a pen and paper approach in mind. Number of CPU cycles might vary a from actual complexity when the chips are optimised for certain tasks

Re:Matrix Multiplication Inches Closer To Mythic Goal by saeta on Saturday December 18, 2021 @12:05PM (#29606146)
While that's true for fixed-precision integer arithmetic, this doesn't hold true for floating point multiplication.
Re:Matrix Multiplication Inches Closer To Mythic Goal by Ar-Curunir on Saturday December 18, 2021 @12:49PM (#29606615)
From a complexity perspective, addition is linear time, whereas multiplication is superlinear (nlogn at best)