Questions about layout calculation

[zhujj2008]

Hi，
The document of layout calculation algebra is not complete.
For example, the implementation of the composition function here is inconsistent with what is mentioned in the document ：
https://github.com/NVIDIA/cutlass/blob/main/media/docs/ cute/02_layout_operations.md#composition
It only explained (20:2)o (4,5):(1,4), and did not explain how to calculate (20,2): (16:4)o (4,5):(1,4)。I think this is the key to understanding the calculation of layout。
Is there any more detailed document provided?

[mhoemmen]

Greetings and thanks for your interest in CUTLASS! I'll be happy to add this request to our task list. The next public release of CUTLASS will feature improvements in the documentation.

[mhoemmen]

@zhujj2008 Specifically regarding the layout (20,2):(16:4) o (4,5):(1,4), it's helpful to notice that (4,5):(1,4) is the compact column-major layout for the shape (4,5). Thus, it's equivalent to 20:1.

• (20,2):(16:4) o (4,5):(1,4)
• (20,2):(16:4) o 20:1

20:1 means "take the first 20 consecutive elements of the layout." ("Consecutive" comes from the stride 1.) That's just the first column of (20,2):(16:4), that is, 20:16 (20 elements, with stride 16).

The shape of a composition A o B is the shape of B. Thus, we need to reshape 20:16 to have the required shape (4,5). The stride between consecutive elements in a column is 16, and the stride between consecutive elements in a row is 4 * 16 = 64. Thus, the answer is (4,5) : (16,64).

We get exactly this result if we use compile-time shapes and strides. The following code prints "(_4,_5):(_16,_64)."

using namespace cute;
auto a = make_layout(make_shape(Int<20>{}, _2{}),   make_stride(_16{}, _4{}));
auto b = make_layout(make_shape(_4{},      _5{}), make_stride( _1{}, _4{}));
auto c = composition(a, b);
printf("\n");
print(c);

Results look different (but are the same mathematically) if we use run-time integers. The following prints "((4,1),(5,1)):((16,4),(64,4))."

auto a = make_layout(make_shape(20,2), make_stride(16,4));
auto b = make_layout(make_shape(4, 5), make_stride(1, 4));
auto c = composition(a, b);
printf("\n");
print(c);

((4,1),(5,1)):((16,4),(64,4)) is effectively the same layout as (4,5) : (16,64), because the 1s in the shape don't affect the layout (as a mathematical function from one integer to one integer). CuTe chooses not to simplify layout computations with run-time values in them as much as it could, because simplifications involving run-time values have a run-time cost.

[mhoemmen]

My understanding is that there is a formal theory, but CUTLASS does not have an automatic proof system. It does attempt to move as much computation and checking to compile time as possible. Certain arithmetic operations (e.g., integer division by zero) that are undefined behavior at run time become compiler errors at compile time.

[eatingtomatoes]

Is there any resource describing the theory in a language-indenpendent form?

That may be a good auxiliary material for users to learn CutTe.

[jayhshah]

Hey! I wrote a mathematical note attempting to do just that for complementation and composition (and thus logical division) - available at https://research.colfax-intl.com/a-note-on-the-algebra-of-cute-layouts/. I found these to be the two operations most in need of a rigorous treatment. You might find it helpful.

[eatingtomatoes]

Hey! I wrote a mathematical note attempting to do just that for complementation and composition (and thus logical division) - available at https://research.colfax-intl.com/a-note-on-the-algebra-of-cute-layouts/. I found these to be the two operations most in need of a rigorous treatment. You might find it helpful.

Great! I will read it carefully. Thanks a lot!

[mhoemmen]

FYI, CUTLASS has an extensive CuTe tutorial in media/docs/cute. For the next release of CUTLASS, we plan to expand the CuTe tutorial quite a bit.