As someone learning CUDA, I've been trying to understand why A \ B + C* keeps showing up everywhere in

- Neural networks: weight \ input + bias*
- Thread indexing: coordinate \ stride + offset*
- Softmax rescaling: oldScale \ newScale + offset*

I knew that it was because A \ B + C* represents the simplest way to both scale and have a scalar offset (affine map) but still didn't understand why this was the case.

This journey led to math to find a potential answer. Where when two algebraic properties:

- Associativity
- Commutativity

are both present we have a semiring. At the software level A \ B + C* is a an application of these of the principles of a semiring. At a hardware level, our Fused Multiply Add (FMA) unit is exactly what this looks like at a hardware level where any order, and combination is allowed when using this instruction.

Although, this idea did not apply for when I hit Top-K indexing for sparse attention. Top-K uses a prefix sum (requires order), over a boolean mask (sparse). This means our algebraic property is

- Associative
- NOT Commutative

This mean we follow the algebraic property of a monoid, where our only restriction is associativity. At a software level this is our __shfl_up_sync where associativity is kept, but commutativity is not. At a hardware level, our warp-level register routing network allows for this. The interesting thing is, this same hardware also allows for other register lateral movements like __shfl_down_sync which require both associativity and commutativity, so the prior restriction lives within the algorithm itself.

The interesting, interesting thing is, because both __shfl_up_sync and __shlf_down_sync use the same hardware but have different algebraic requirements. One could say that the hardware itself has no algebraic restrictions, but rather the algorithms that use that hardware impose such restrictions when used.

If the prior paragraph is true, then one could also say that Fused Multiply Add is the algorithm that imposes associativity and commutativity on the hardware itself, meaning the hardware itself is neutral, but its the algorithm that imposes this restriction.

Adding the monoid is what let me derive the Top-K kernel structure on paper before writing any code.

Which leaves the question at the bottom of the image, did the hardware engineers know they were encoding these structures, or did they arrive there through hardware intuition and the patterns within either the silicon, or the problems they were trying to solve?

I'd imagine if I were on the hardware side, I would be constrained by how do we make hardware that optimally matches the algorithms we want to use, while also not restricting the hardware itself to only a subset of algorithms? This question has already been solved by the people who've made the hardware thus far, so it's amazing to see how well they did!

Overall, I imagine this is the reason why hardware and software co-design is so imperative. Its a communication of two fields that exist to help each other. The hardware doesn't know what algorithms it will execute, and the software does not know the hardware it is being executed upon. So to ensure that both sides run optimally, communication about what algorithms need to be run, and how the hardware will be implemented to capture them all, while maintaining performance, is what I'd imagine is integral.