KONA Notes: layout_padded

Padded Layouts

Motivation

• padding multi dimensional arrays helps with
  • enable use of instructions which require over-alignment
  • cache line access optimization
    • for mdspan<double, dextents<int, 2>> A(ptr, N, 7); the code below will exhibit false sharing on cachelines of 64 byte

magic_index_range range(N);
for_each(execution::par, range.begin(), range.end(), [=](int i) {
  for(int j=0; j<M; j++) A[i, j] = i*100 + j;
});

• often submdspan of layout_left or layout_right only needs a single stride in addition to extents
  • used by BLAS (leading dimension)
  • important in image processing libraries (pitch of a row)
  • also: submdspan layout_left_padded and layout_right_padded rank-2 mdspan can always preserve layout type

Proposal

• add two new layouts: layout_left_padded and layout_padded_right
• we "pad" the stride-1 dimension
  • that means the padding stride is stride(1) for layout_left_padded and stride(rank()-2) for layout_right_padded
• the padding is specified via a template argument:

template<size_t Padding>
struct layout_padded_left;

• Padding == dynamic_extent indicates using a runtime padding
• the padding stride is the smallest multiple of Padding larger then the corresponding extent
  • this supports the "cacheline" alignment by providing Padding computed from cacheline size and scalar size
  • this supports submdspan usecase by simply passing the actual stride of a given dimension

layout_left_padded<4>::mapping map(extents<int, 7,5>());
// map.stride(0) == 1
// map.stride(1) == 8

layout_right_padded<4>::mapping map(extents<int, 7,5>());
// map.stride(0) == 8
// map.stride(1) == 1

layout_right_padded<dynamic_extent>::mapping 
  map(extents<int, 7,5>(), 4);
// map.stride(0) == 8
// map.stride(1) == 1

layout_right_padded<dynamic_extent>::mapping
  map(extents<int, 7,5>(), 13);
// map.stride(0) == 13
// map.stride(1) == 1

Why not use layout_stride for these usecases

• the padded layouts have a number of advantages:
  • one stride is still statically known to be 1: critical for good vectorization
  • only needs to store a single stride - if that stride is not compile time known
    • layout_stride always has runtime stored strides for each dimension

Integration with submdspan

• we want for submdspan of layout_left and layout_right to return padded layouts instead of layout_stride where possible
• this would be a breaking change for submdspan if introduced later

mdspan<int, dextents<int, 3>, layout_left> A(ptr, N, M, K);

auto sub_1 = submdspan(A, pair(x,y), full_extent, 5);
// sub_1 without P2642: layout_stride, proposed: layout_left_padded

auto sub_2= submdspan(A, pair(x,y), pair(z,p), 5);
// sub_2 layout_stride (unchanged)

auto sub_3 = submdspan(A, 5, full_extent, full_extent);
// sub_3 layout_stride (unchanged)

auto sub_4 = submdspan(A, full_extent, pair(x,y), 5);
// sub_4 layout_left (unchanged)

Why not a layout_stride with compile time strides

• this question gets asked a bit, but it doesn't work
• consider this submdspan case:

mdspan<int, extents<int, dynamic_extents,3,4,5>, layout_left> A(ptr, N);

auto sub_A = submdspan(A, pair(x,y), full_extent, full_extent, full_extent);

• with layout_stride we would need to store 3-runtime strides:
  • stride(0) == 1 - static
  • stride(1) == N - dynamic
  • stride(2) == N*3 - dynamic
  • stride(3) == N*3*4 - dynamic

Start by reviewing the proposed layout_left_padded and layout_right_padded mappings, including their static and dynamic padding behavior and the submdspan integration examples. No files, tests, or entry points are identified in the issue. Done would require an agreed design covering the layouts, mapping semantics, and compatibility impact.