Has there been much research into slightly flawed matrix multiplications?
If you have a measure of correctness, and a measure of performance. Is there a maximum value of correctness per some unit of processing that exists below a full matrix multiply
Obviously it can be done with precision, since that is what floating point is. But is there anything where you can save x% of computation and have fewer than x% incorrect values in a matrix multiplications?
Gradient descent wouldn't really care about a few (Reliably) dud values.
For semi-random weights you cam get down to 20-30% multiplications/mem reads and maintain ~0.98 cosine similarity output between the approximated and full result.
As far as LLM inference goes, the speedup from removing multiplications is at best comparable to the speedup of quantisation (that is - you get at best similar KL divergence score whether you remove calculations or quantise).
Randomized matrix sketching is one way to get at this (see https://arxiv.org/abs/2302.11474), the problem is hardware is heavily optimized for dense multiplies so what you save in flops doesn't translate to real runtime speeds ups.
Well, approximate computing seems to be a superset of the field you describe here, with many different approaches, including analog computation. As you say, some algorithms care a bit less about precision, especially for LSBs.
Metal support is most welcome (and rare in similar projects)!
Typically, you are not doing a matrix multiplication for the sake of it, but as part of a broader algorithm (e.g. a simulation). Without fusing those other operations into the MatMul kernel, you are leaving performance on the table. How will the Burn devs address this?
Seems kind of CUTLASS-inspired in terms of how its API is designed. I'm curious how they plan to expose more interesting operations, though, since CUTLASS gives you the ability to write custom epilogs and tiling patterns, and I'm not sure their API is expressive enough to do this.
Reminds me of ye olden days when kernel transforms were merely weighted multiplicative and/or additive matrixes applied to every point in the source arriving at pixel data in the target. Blur, sharpen, color channel filter, color swap, invert, etc. An extremely diagonalizable problem suitable for massive parallelism and concurrent calculation because there is little/no dependency on prior calculations.
GPUs came about because of the need for faster float 4x4 and 3x3 matrix, and 3 and 4 vector math ops like multiply, multiply-accumulate, and such, and faster pushing of pixels with things like texture mapping. All hail OpenGL and dual Voodoo2 SLI. ;)
I had bet that matmult would be in transformer-optimized hardware costing a fraction of GPUs first class in torch 2 years ago with no reason to use GPUs any more. Wrong.
The real bottleneck is the memory, optimize your matmul architecture all you like whilst you still have it connected to a big chunk of HBM memory (or whatever your chosen high bandwidth memory is) you can only do so much.
So really GPU v not GPU (e.g. TPU) doesn't matter a whole lot if you've got fundamentally the same memory architecture.
I'm sorry this is a low brow comment but this is the dumbest thing you can do in this space:
> Unit (thread in CUDA, invocation in Vulkan/Wgpu): the smallest execution entity performing computations.
> Plane (warp in CUDA, subgroup in Vulkan/Wgpu): a group of (typically 32) units executing in lockstep and able to share data efficiently through registers.
> Cube (thread block in CUDA, workgroup in Vulkan/Wgpu): a group of units that execute on the same SM, sharing memory and able to synchronize
It's already bad enough that the vendors themselves insisted on different names but why in the bejesus would you rename these concepts and diverge from literally all existing naming conventions when you're providing middleware. Ie when using your tool I'm still going to reference NVIDIA's or AMD's docs to understand how the hardware actually works. Like do you really think otherwise - that your thing is gonna be end of the line???
FYI the word warp isn't random techno babble but is actually a very clever pun that actually fits very well conceptually:
Using the naming from one of the existing API would put too much bias towards that API. It started as a WebGPU project early on, but some features are not present so mixing terms wasn't ideal. We're also working on extending CubeCL to CPU, so we want terms not only tied to the GPU word.
There you go you've hit basically two of 3 completely (AMD and Vulkan) and are close enough to CUDA that people would get it.
I have no idea what a plane connotes and a cube literally gives a distinct enough picture from block that I will be continuously reminding myself of the mapping.
What you did was pointless - you assigned new words to objects that you don't own and now your conceptual framework is askew from the actual underlying (true) conceptual framework.
> CubeCL to CPU
There is zero affinity between GPU programing models and multicore CPU programing models. If you don't believe me go ask the OpenMP people how they're doing supporting GPUs.
Well we can agree to disagree, CubeCL also has the concept of instruction parallelism, which would be used to target simd instructions on CPU. Our algorithms are normally flexible on both the plane size and the line size, adapting to the hardware with comptime logique. You are free to dislike the naming, but imo a mix of multiple APIs is worse than something new.
For people who are interested Kokkos (a C++ library for writing portable kernels) also has a naming scheme for hierarchical parallelism. They use ThreadTeam, Thread (for individual threads within a group), and ThreadVector (for per thread SIMD).
Just commenting to share, personally I have no naming preference but the hierarchal abstractions in general are incredibly useful.
It will make more sense once you start using CubeCL. There's now a CubeCL book available: https://burn.dev/books/cubecl/.
It does come with some mental overhead, but let’s be honest, there’s no objectively “good” choice here without introducing bias toward a specific vendor API.
Learning the core concepts takes effort, but if CubeCL is useful for your work, it’s definitely worth it.
Has there been much research into slightly flawed matrix multiplications?
If you have a measure of correctness, and a measure of performance. Is there a maximum value of correctness per some unit of processing that exists below a full matrix multiply
Obviously it can be done with precision, since that is what floating point is. But is there anything where you can save x% of computation and have fewer than x% incorrect values in a matrix multiplications?
Gradient descent wouldn't really care about a few (Reliably) dud values.
I did research on vector-matrix last year:
https://kolinko.github.io/effort/
For semi-random weights you cam get down to 20-30% multiplications/mem reads and maintain ~0.98 cosine similarity output between the approximated and full result.
As far as LLM inference goes, the speedup from removing multiplications is at best comparable to the speedup of quantisation (that is - you get at best similar KL divergence score whether you remove calculations or quantise).
Randomized matrix sketching is one way to get at this (see https://arxiv.org/abs/2302.11474), the problem is hardware is heavily optimized for dense multiplies so what you save in flops doesn't translate to real runtime speeds ups.
Well, approximate computing seems to be a superset of the field you describe here, with many different approaches, including analog computation. As you say, some algorithms care a bit less about precision, especially for LSBs.
If you do it in 8-bit it's usually 2x as fast as 16 bit on Tensorcores
Metal support is most welcome (and rare in similar projects)!
Typically, you are not doing a matrix multiplication for the sake of it, but as part of a broader algorithm (e.g. a simulation). Without fusing those other operations into the MatMul kernel, you are leaving performance on the table. How will the Burn devs address this?
Seems kind of CUTLASS-inspired in terms of how its API is designed. I'm curious how they plan to expose more interesting operations, though, since CUTLASS gives you the ability to write custom epilogs and tiling patterns, and I'm not sure their API is expressive enough to do this.
One of the author here, don't hesitate if you have any question or comment!
Reminds me of ye olden days when kernel transforms were merely weighted multiplicative and/or additive matrixes applied to every point in the source arriving at pixel data in the target. Blur, sharpen, color channel filter, color swap, invert, etc. An extremely diagonalizable problem suitable for massive parallelism and concurrent calculation because there is little/no dependency on prior calculations.
GPUs came about because of the need for faster float 4x4 and 3x3 matrix, and 3 and 4 vector math ops like multiply, multiply-accumulate, and such, and faster pushing of pixels with things like texture mapping. All hail OpenGL and dual Voodoo2 SLI. ;)
Very interesting, willing to try burn
I had bet that matmult would be in transformer-optimized hardware costing a fraction of GPUs first class in torch 2 years ago with no reason to use GPUs any more. Wrong.
The real bottleneck is the memory, optimize your matmul architecture all you like whilst you still have it connected to a big chunk of HBM memory (or whatever your chosen high bandwidth memory is) you can only do so much.
So really GPU v not GPU (e.g. TPU) doesn't matter a whole lot if you've got fundamentally the same memory architecture.
> matmult would be in transformer-optimized hardware
It is... it's in GPUs lol
> first class in torch
It is
> costing a fraction of GPUs
Why would anyone give you this for cheaper than GPUs lol?
I think they’re referring to hardware like TPUs and other ASICs. Which also exist, of course :)
Sure but GPUs literally have MMA engines now
Could something like this be done in WebGPU?
CubeCL supports WebGPU and can be used with wasm!
burn is awesome
I'm sorry this is a low brow comment but this is the dumbest thing you can do in this space:
> Unit (thread in CUDA, invocation in Vulkan/Wgpu): the smallest execution entity performing computations.
> Plane (warp in CUDA, subgroup in Vulkan/Wgpu): a group of (typically 32) units executing in lockstep and able to share data efficiently through registers.
> Cube (thread block in CUDA, workgroup in Vulkan/Wgpu): a group of units that execute on the same SM, sharing memory and able to synchronize
It's already bad enough that the vendors themselves insisted on different names but why in the bejesus would you rename these concepts and diverge from literally all existing naming conventions when you're providing middleware. Ie when using your tool I'm still going to reference NVIDIA's or AMD's docs to understand how the hardware actually works. Like do you really think otherwise - that your thing is gonna be end of the line???
FYI the word warp isn't random techno babble but is actually a very clever pun that actually fits very well conceptually:
https://en.m.wikipedia.org/wiki/Warp_and_weft
Using the naming from one of the existing API would put too much bias towards that API. It started as a WebGPU project early on, but some features are not present so mixing terms wasn't ideal. We're also working on extending CubeCL to CPU, so we want terms not only tied to the GPU word.
Why unit instead of point?
Unit, plane (as vs train), and cube?
Or point, plane, cube (1d, 2d, 3d)?
I don't recall the reason why, point is a valid name.
Actually, points are zero dimensional, lines are one dimensional.
Thread, group, workgroup.
There you go you've hit basically two of 3 completely (AMD and Vulkan) and are close enough to CUDA that people would get it.
I have no idea what a plane connotes and a cube literally gives a distinct enough picture from block that I will be continuously reminding myself of the mapping.
What you did was pointless - you assigned new words to objects that you don't own and now your conceptual framework is askew from the actual underlying (true) conceptual framework.
> CubeCL to CPU
There is zero affinity between GPU programing models and multicore CPU programing models. If you don't believe me go ask the OpenMP people how they're doing supporting GPUs.
Well we can agree to disagree, CubeCL also has the concept of instruction parallelism, which would be used to target simd instructions on CPU. Our algorithms are normally flexible on both the plane size and the line size, adapting to the hardware with comptime logique. You are free to dislike the naming, but imo a mix of multiple APIs is worse than something new.
For people who are interested Kokkos (a C++ library for writing portable kernels) also has a naming scheme for hierarchical parallelism. They use ThreadTeam, Thread (for individual threads within a group), and ThreadVector (for per thread SIMD).
Just commenting to share, personally I have no naming preference but the hierarchal abstractions in general are incredibly useful.
> Our algorithms are normally flexible on both the plane size and the line size
Congrats - I have no idea what this means lol.
It will make more sense once you start using CubeCL. There's now a CubeCL book available: https://burn.dev/books/cubecl/.
It does come with some mental overhead, but let’s be honest, there’s no objectively “good” choice here without introducing bias toward a specific vendor API.
Learning the core concepts takes effort, but if CubeCL is useful for your work, it’s definitely worth it.
Relevant XKCD: https://xkcd.com/927/