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

Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

arxiv.org

Post reply on HN
Print view View original

11–20 of 25 posts

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#11

Post by imtringued »

almostgotcaught wrote: post #10
emacs28 wrote: post #6

Earlier quoted context omitted.

First author here. The hardware architectures are realistic - we developed & evaluated real example hardware implementations for them, validated on FPGA, and they achieved state-of-the-art ResNet performance in a deep learning accelerator system implementation compared to prior accelerators evaluated on similar FPGAs. See the associated accelerator system source code here: https://github.com/trevorpogue/algebraic-nnh…

> systolic array designs, an efficient type of hardware design for matrix multiplication (e.g., the Google TPU uses this), as opposed to more SIMD-like vector architectures like GPUs this is wrong. TPUv4 has tensor cores just like NVIDIA has tensor cores just like AMD has tensor cores. no one uses a systolic array because bandwidth/connectivity is much scarcer than compute. the only people that keep talking about the…

https://cloud.google.com/tpu/docs/system-architecture-tpu-vm...

>The primary task for TPUs is matrix processing, which is a combination of multiply and accumulate operations. TPUs contain thousands of multiply-accumulators that are directly connected to each other to form a large physical matrix. This is called a systolic array architecture. Cloud TPU v3, contain two systolic arrays of 128 x 128 ALUs, on a single processor.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#12

Post by robinhouston »

imtringued wrote: post #11
almostgotcaught wrote: post #10

Earlier quoted context omitted.

> systolic array designs, an efficient type of hardware design for matrix multiplication (e.g., the Google TPU uses this), as opposed to more SIMD-like vector architectures like GPUs this is wrong. TPUv4 has tensor cores just like NVIDIA has tensor cores just like AMD has tensor cores. no one uses a systolic array because bandwidth/connectivity is much scarcer than compute. the only people that keep talking about the…

https://cloud.google.com/tpu/docs/system-architecture-tpu-vm... >The primary task for TPUs is matrix processing, which is a combination of multiply and accumulate operations. TPUs contain thousands of multiply-accumulators that are directly connected to each other to form a large physical matrix. This is called a systolic array architecture. Cloud TPU v3, contain two systolic arrays of 128 x 128 ALUs, on a single pro…

I don't see any contradiction between your claim that TPU v3 uses systolic arrays and the parent post's claim that TPU v4 does not.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#13

Post by FL33TW00D »

almostgotcaught wrote: post #10
emacs28 wrote: post #6

Earlier quoted context omitted.

First author here. The hardware architectures are realistic - we developed & evaluated real example hardware implementations for them, validated on FPGA, and they achieved state-of-the-art ResNet performance in a deep learning accelerator system implementation compared to prior accelerators evaluated on similar FPGAs. See the associated accelerator system source code here: https://github.com/trevorpogue/algebraic-nnh…

> systolic array designs, an efficient type of hardware design for matrix multiplication (e.g., the Google TPU uses this), as opposed to more SIMD-like vector architectures like GPUs this is wrong. TPUv4 has tensor cores just like NVIDIA has tensor cores just like AMD has tensor cores. no one uses a systolic array because bandwidth/connectivity is much scarcer than compute. the only people that keep talking about the…

The TPU obviously uses a systolic array: https://jax-ml.github.io/scaling-book/tpus/

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#14

Post by freetonik »

Random anecdote: 15 years ago I was starting an online community for computer science students, and needed to come up with a name. I made a survey for the community members to vote on options, with some boring ones like "CS Hub" and stuff; one of the options was "Karatsuba": I had just learned about the Karatsuba multiplication algorithm, and somehow got this idea into my head that his last name sounds cool and unique, and my online community (later grown into a ed-tech startup) should be named after this Russian mathematician.

Anatoly Karatsuba himself was already dead (he died in 2008). I emailed his daughter Yekaterina (who is also a mathematician, btw) asking for a permission to use their last name. She agreed, but asked to be extra careful about potential implicit affiliations, i.e. to be clear that the content has nothing to do with her father's research.

She also expressed an opinion that in the field of mathematics and computation, at least in Russia, actual researchers are rarely involved in writing textbooks, and the textbooks used in universities often contain conflicting or even wrong information about the authorship of research.

In the end a different name was chosen for the project.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#15

Post by almostgotcaught »

FL33TW00D wrote: post #13
almostgotcaught wrote: post #10

Earlier quoted context omitted.

> systolic array designs, an efficient type of hardware design for matrix multiplication (e.g., the Google TPU uses this), as opposed to more SIMD-like vector architectures like GPUs this is wrong. TPUv4 has tensor cores just like NVIDIA has tensor cores just like AMD has tensor cores. no one uses a systolic array because bandwidth/connectivity is much scarcer than compute. the only people that keep talking about the…

The TPU obviously uses a systolic array: https://jax-ml.github.io/scaling-book/tpus/

Fair enough - my understanding was they moved away from systolic arrays. I stand corrected. I will also say it is well-known they're basically impossible to program/build a compiler for.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#16

Post by godsmokescrack »

The basic idea of reducing 4 multiplications to 3 multiplications

(ax + b)(cx + d) = acx^2 + [(a + b)(c + d) - ac - bd]x + bd

holds pretty generally; there isn't any new math or algorithm here that I can see. Their own complexity analysis (eqns. 7 and 8) shows this performs about the same as using Karatsuba multiplication on the entries of the matrices (instead of on the matrices themselves).

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#17

Post by FL33TW00D »

almostgotcaught wrote: post #15
FL33TW00D wrote: post #13

Earlier quoted context omitted.

The TPU obviously uses a systolic array: https://jax-ml.github.io/scaling-book/tpus/

Fair enough - my understanding was they moved away from systolic arrays. I stand corrected. I will also say it is well-known they're basically impossible to program/build a compiler for.

This is why Google has 500 people working on the TPU compiler team.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#18

Post by gjm11 »

dvasdekis wrote: post #8

Would this work have the potential to speed up encoding/decoding of the PAR2 format[0]? This format is widely used to protect datasets against bitrot and small losses, but is held back because of the significant compute overhead when dealing with large datasets. [0] https://en.wikipedia.org/wiki/Parchive

Unless I am badly misunderstanding the paper, this is about doing matrix multiplication on matrices whose entries are large integers. So far as I can tell, PAR2 doesn't do any large-number arithmetic at all, so I don't think this work will have any relevance for implementations of PAR2.

[EDITED to add:] Reading the paper a bit more carefully, the above isn't exactly right. It is about doing matrix multiplication on matrices whose entries are "large" but they're interested in using the idea for hardware design where "large" may mean not-very-large, building (say) 16-bit multiplies out of 8-bit multipliers.

But for software implementations (and I doubt anyone will be making special-case hardware for PAR2) small multiplications are not generally faster than large ones. Maybe you might be able to do more of them in parallel using SIMD, but I bet the extra additions and subtractions and general overhead would outweigh any gains in that setting.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#19

Post by oofbey »

winterismute wrote: post #5
oofbey wrote: post #3

They're proposing "new hardware architectures" to take advantage of this idea. Anybody with a background in GPU floating point math comment on how realistic this is?

The paper is about integer multiplication, not float

Why would that matter? I understood the point was to speed up matrix multiplication by doing the adds and multiplies in a different order. Shouldn't matter whether the datatype is int, float, complex, whatever.

Re: Karatsuba Matrix Multiplication and Its Efficient Hardware Implementations

#20

Post by sifar »

emacs28 wrote: post #6
oofbey wrote: post #3

They're proposing "new hardware architectures" to take advantage of this idea. Anybody with a background in GPU floating point math comment on how realistic this is?

First author here. The hardware architectures are realistic - we developed & evaluated real example hardware implementations for them, validated on FPGA, and they achieved state-of-the-art ResNet performance in a deep learning accelerator system implementation compared to prior accelerators evaluated on similar FPGAs. See the associated accelerator system source code here: https://github.com/trevorpogue/algebraic-nnh…

I have used Karatsuba's & Winograd's Inner product [0] algorithm in my work for wide multi-simd integer multipliers and matrix multiplication HW for DSPs. The latter cuts down the MACs by half - n^3/2 instead of n^3. I think the paper talks about it's derivative - FFIP.

The issue is memory bandwidth. These techniques indeed help you save multiplier area however the performance is still bandwidth limited - you'd need to be able to feed more data per cycle to increase performance.

One thing the paper doesn't talk about is energy. For DNN, at the network level the energy consumed by integer macs is not that high. Localizing data computation would have a much more impact on energy reduction than optimizing MACs.

[0] https://ieeexplore.ieee.org/document/1687427

Post reply on HN