41–50 of 53 posts
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?
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…
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?
None. Afaik, all practical implementations of matrix multiplication execute the naive n^3 algorithm because sub-cubic algorithms have too large constant overheads and/or are numerically unstable.
Which one of these algos does Intel/Nvidia/Google use in their AVX/Cuda/TPU implementations?
Simple block partitioning, usually 4x4, with the full ordinary algorithm per block. This is the most numerically-stable and parallel. https://developer.nvidia.com/blog/cutlass-linear-algebra-cud...
Which one of these algos does Intel/Nvidia/Google use in their AVX/Cuda/TPU implementations?
Strassen's method is the only one practical on modern hardware
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…
Theoretical Computer Scientists aren't going to increase the size of your cache, that's just not what they're into or what they know anything about.
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?
None. Afaik, all practical implementations of matrix multiplication execute the naive n^3 algorithm because sub-cubic algorithms have too large constant overheads and/or are numerically unstable.
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…
Quanta has used this graphic in previous articles, and I find it very hard to grok. Time on the y-axis is just strange and confusing. Rotating 90° clockwise makes it much clearer.
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…