Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Matrix Multiplication Inches Closer To Mythic Goal

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 53 posts

Re: Matrix Multiplication Inches Closer To Mythic Goal

#31

Post by Ductapemaster »

salamanderman wrote: post #29

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.

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

#32

Post by matbatt38 »

salamanderman wrote: post #29

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.

> 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

#33

Post by reportingsjr »

salamanderman wrote: post #29

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.

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

#34

Post by 1024core »

Just for reference: a Google TPU can multiply a 256x256 matrix in 1 clock cycle[1]. That seems astonishingly fast, considering the TPU operates at 700MHz:

The TPU Matrix Multiplication Unit has a systolic array mechanism that contains 256 × 256 = total 65,536 ALUs. That means a TPU can process 65,536 multiply-and-adds for 8-bit integers every cycle. Because a TPU runs at 700MHz, a TPU can compute 65,536 × 700,000,000 = 46 × 1012 multiply-and-add operations or 92 Teraops per second (92 × 1012) in the matrix unit.

[1] https://cloud.google.com/blog/products/ai-machine-learning/a...

Re: Matrix Multiplication Inches Closer To Mythic Goal

#35

Post by teawrecks »

salamanderman wrote: post #29

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.

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

#36

Post by gameswithgo »

e-dant wrote: post #17

This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on increasing the size and efficiency of our cache and stack . MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abs…

this article isn’t at all about doing it faster on actual hardware, and everyone has worried a lot about cache for decades now.

Re: Matrix Multiplication Inches Closer To Mythic Goal

#37

Post by gameswithgo »

salamanderman wrote: post #29

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.

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

#38

Post by Ar-Curunir »

salamanderman wrote: post #29

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.

From a complexity perspective, addition is linear time, whereas multiplication is superlinear (nlogn at best)

Re: Matrix Multiplication Inches Closer To Mythic Goal

#39

Post by mensetmanusman »

It would be interesting to put this in perspective in regards to total energy savings.

Since so much of computation is matrix multiplication, how much computational power integrated over the next decade would we say that the exponent going from 3->2.3 has saved?

Re: Matrix Multiplication Inches Closer To Mythic Goal

#40

Post by gnufx »

e-dant wrote: post #17

This thought has been churning around in my mind for some years now — we focus too much on processing speed and reductions in time complexity and not enough on increasing the size and efficiency of our cache and stack . MM (especially MM on large type numbers like e.g. hashing algorithms) are very reliant on the cache because you can’t always fit that big of a number into a register. Side note, I was reading some Abs…

Not relevant to the article, but well-written single and double precision floating point large matrix GEMM on mainstream CPUs is basically computation-bound -- look at performance figures -- and is relatively unusual in that. (You probably need to worry about prefetching to get there, though.)
Post reply on HN