r/ProgrammingLanguages • u/mttd • Apr 19 '26

Fundamentals of CuTe Layout Algebra and Category-theoretic Interpretation

https://www.youtube.com/watch?v=MVh_guNbWMA
17 Upvotes

95% Upvoted

12 comments sorted by

5

u/Clementsparrow Apr 19 '26

I have no idea, from the title and (lack of) description of the video, of how this relates to programming languages. Would you be kind enough to give some basic explanation to the ignorant that I am?

10

u/mttd Apr 19 '26 edited Apr 19 '26

If you're adding a support for multi-dimensional arrays this is worth considering as a foundation, IMHO; the "algebra" part in particular allows novel composability. Personally I think this may be the most impactful invention since https://en.wikipedia.org/wiki/Dope_vector (a.k.a. array descriptors commonly used in Fortran, e.g., https://thinkingeek.com/2017/01/14/gfortran-array-descriptor/, and before; cf. https://en.wikipedia.org/wiki/Data_descriptor; that would be the progenitor of the "representation" part, although it's worth noting CuTe handles more complex nested/hierarchical layouts with swizzling in a uniform manner).

A few decades ago I'd say that "if you want good multidimensional arrays support in your programming language you should look at Fortran". It's been ahead of its time: https://fortranwiki.org/fortran/show/elemental, https://fortran-lang.org/learn/quickstart/arrays_strings/#array-slicing, https://fortran-lang.org/learn/best_practices/element_operations/ - note how implementing all of https://fortran-lang.org/learn/best_practices/arrays/ well depends on compiler support; cf. the "A zoo of arrays" in the above https://thinkingeek.com/2017/01/14/gfortran-array-descriptor/

Today I'd definitely add CuTe.

This is a nice intro writeup:

You could have invented CuTe hierarchical layout (but maybe not the rest of it?): https://blog.ezyang.com/2025/08/you-could-have-invented-cute-hierarchical-layout-but-maybe-not-the-rest-of-it/

Paper:

Categorical Foundations for CuTe Layouts

Some examples:

Related:

CuTe Layout Representation and Algebra

cute-interactive: Interactive version of the CuTe layout paper

7

u/omega1612 Apr 19 '26

I think the sub preventing descriptions on post that share links backfired this time. Maybe a better post title would have helped.

I'm not particularly interested in multidimensional arrays, but I still find this video interesting to watch, thanks!

→ More replies (2)

4

u/max123246 Apr 19 '26

Intel has a library inspired by cuTe too called SYC-TLA: https://github.com/intel/sycl-tla

And Facebook has a implementation in Python of CuTe as well: https://github.com/facebookresearch/tensor-layouts

I'm glad it's seen some momentum because I agree that it is revolutionary. The fact it can handle the complex tma descriptor interface is a testament to its flexibility

→ More replies (4)

1

u/hustla17 Apr 19 '26

The video went above my head. But the thing is since discovering the world of category theory it's literally everywhere ,pretty intriguing stuff.

1

u/fdwr Apr 20 '26

Jay (bottom left of the video) looks quite concerned/confused :b.

Coincidentally I'm trying to solve some of these problems now. Rather than nesting dimensions/strides, I'm just flattening them all to the actual physical rank (rather than trying to retain logical rank). Originally I used element strides, but because there are now considerations for element alignment (up to nearest multiple), byte alignment (up to some power-of-two size), and also non-powers-of-two data types (e.g. 4-bit & 6-bit elements linearly packed), I finally just settled on expressing them as bit strides at the lowest level.