Layout

Mathematically, a Layout represents a function that maps a logical coordinate to a 1-D index space that can be used to index into an array. It consists of a shape and a stride, wherein the shape determines the domain, and the stride establishes the mapping through an inner product. shape and stride are both defined by (recursive) tuples of integers.

For example, we can construct a vector with stride 2 

julia> using MoYe
julia> struct StrideVector
          data
          layout
       end
julia> Base.getindex(x::StrideVector, i) = x.data[x.layout(i)]
julia> a = StrideVector(collect(1:8), Layout(4, 2))Main.StrideVector([1, 2, 3, 4, 5, 6, 7, 8], 4:2)
julia> @show a[1] a[2] a[3] a[4];a[1] = 1
a[2] = 3
a[3] = 5
a[4] = 7

Fundamentals

julia> using MoYe
julia> layout_2x4 = Layout((2, (2, 2)), (4, (1, 2)))(2, (2, 2)):(4, (1, 2))
julia> print("Shape: ", shape(layout_2x4))Shape: (2, (2, 2))
julia> print("Stride: ", stride(layout_2x4))Stride: (4, (1, 2))
julia> print("Size: ", size(layout_2x4)) # the domain is (1,2,...,8)Size: 8
julia> print("Rank: ", rank(layout_2x4))Rank: 2
julia> print("Depth: ", depth(layout_2x4))Depth: 2
julia> print("Cosize: ", cosize(layout_2x4))Cosize: 8
julia> layout_2x4 # this can be viewed as a row-major matrix(2, (2, 2)):(4, (1, 2))

Compile-time-ness of values

You can also use static integers:

julia> static_layout = @Layout (2, (2, 2)) (4, (1, 2))(_2, (_2, _2)):(_4, (_1, _2))
julia> typeof(static_layout)StaticLayout{2, Tuple{StaticInt{2}, Tuple{StaticInt{2}, StaticInt{2}}}, Tuple{StaticInt{4}, Tuple{StaticInt{1}, StaticInt{2}}}} (alias for Layout{2, Tuple{Static.StaticInt{2}, Tuple{Static.StaticInt{2}, Static.StaticInt{2}}}, Tuple{Static.StaticInt{4}, Tuple{Static.StaticInt{1}, Static.StaticInt{2}}}})
julia> sizeof(static_layout)0

Different results from static Layout vs dynamic Layout

It is expected to get results that appears to be different when the layout is static or dynamic. For example,

julia> layout = @Layout (2, (1, 6)) (1, (6, 2))(_2, (_1, _6)):(_1, (_6, _2))
julia> print(coalesce(layout))_12:_1

is different from

julia> layout = Layout((2, (1, 6)), (1, (6, 2)))(2, (1, 6)):(1, (6, 2))
julia> print(coalesce(layout))(2, 1, 6):(1, 6, 2)

But they are mathematically equivalent. Static information allows us to simplify the result as much as possible, whereas dynamic layouts result in dynamic checking hence type instability.

Coordinate space

The coordinate space of a Layout is determined by its Shape. This coordinate space can be viewed in three different ways:

  1. h-D coordinate space: Each element in this space possesses the exact hierarchical structure as defined by the Shape. Here h stands for "hierarchical".
  2. 1-D coordinate space: This can be visualized as the colexicographically flattening of the coordinate space into a one-dimensional space.
  3. R-D coordinate space: In this space, each element has the same rank as the Shape, but each mode (top-level axis) of the Shape is colexicographically flattened into a one-dimensional space. Here R stands for the rank of the layout.
julia> layout_2x4(2, (1, 2)) # h-D coordinate7
julia> layout_2x4(2, 3) # R-D coordinate7
julia> layout_2x4(6) # 1-D coordinate7

Layout Algebra

Concatenation

A layout can be expressed as the concatenation of its sublayouts.

julia> layout_2x4[2] # get the second sublayout(2, 2):(1, 2)
julia> tuple(layout_2x4...) # splatting a layout into sublayouts(2:4, (2, 2):(1, 2))
julia> make_layout(layout_2x4...) # concatenating sublayouts(2, (2, 2)):(4, (1, 2))
julia> for sublayout in layout_2x4 # iterating a layout
          @show sublayout
       endsublayout = 2:4
sublayout = (2, 2):(1, 2)

Complement

Let's assume that we are dealing with a vector of 24 elements. Our goal is to partition this vector into six tiles, each consisting of four elements, following a specific pattern: gather every 4 elements at even indices to a tile.

This operation creates a new layout where we collect every second element until we have four elements, and then repeat this process for the rest of the vector.

The resulting layout would resemble:

       1    2    3    4    5    6
    +----+----+----+----+----+----+
 1  |  1 |  2 |  9 | 10 | 17 | 18 |
    +----+----+----+----+----+----+
 2  |  3 |  4 | 11 | 12 | 19 | 20 |
    +----+----+----+----+----+----+
 3  |  5 |  6 | 13 | 14 | 21 | 22 |
    +----+----+----+----+----+----+
 4  |  7 |  8 | 15 | 16 | 23 | 24 |
    +----+----+----+----+----+----+

complement computes the first row of this new layout. 

julia> print_layout(complement(@Layout(4,2), 24))(_2, 3):(_1, _8)
       1    2    3 
    +----+----+----+
 1  |  1 |  9 | 17 |
    +----+----+----+
 2  |  2 | 10 | 18 |
    +----+----+----+

The layout Layout(4,2) and it complement gives us the desired new layout.

julia> print_layout(make_layout(@Layout(4, 2),complement(@Layout(4, 2), 24)))(_4, (_2, 3)):(_2, (_1, _8))
       1    2    3    4    5    6 
    +----+----+----+----+----+----+
 1  |  1 |  2 |  9 | 10 | 17 | 18 |
    +----+----+----+----+----+----+
 2  |  3 |  4 | 11 | 12 | 19 | 20 |
    +----+----+----+----+----+----+
 3  |  5 |  6 | 13 | 14 | 21 | 22 |
    +----+----+----+----+----+----+
 4  |  7 |  8 | 15 | 16 | 23 | 24 |
    +----+----+----+----+----+----+

Product

Logical product

julia> tile = @Layout((2,2), (1,2));
julia> print_layout(tile)(_2, _2):(_1, _2)
      1   2 
    +---+---+
 1  | 1 | 3 |
    +---+---+
 2  | 2 | 4 |
    +---+---+
julia> matrix_of_tiles = @Layout((3,4), (4,1));
julia> print_layout(matrix_of_tiles)(_3, _4):(_4, _1)
       1    2    3    4 
    +----+----+----+----+
 1  |  1 |  2 |  3 |  4 |
    +----+----+----+----+
 2  |  5 |  6 |  7 |  8 |
    +----+----+----+----+
 3  |  9 | 10 | 11 | 12 |
    +----+----+----+----+
julia> print_layout(logical_product(tile, matrix_of_tiles))((_2, _2), (_3, _4)):((_1, _2), (_16, _4))
       1    2    3    4    5    6    7    8    9   10   11   12 
    +----+----+----+----+----+----+----+----+----+----+----+----+
 1  |  1 | 17 | 33 |  5 | 21 | 37 |  9 | 25 | 41 | 13 | 29 | 45 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 2  |  2 | 18 | 34 |  6 | 22 | 38 | 10 | 26 | 42 | 14 | 30 | 46 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 3  |  3 | 19 | 35 |  7 | 23 | 39 | 11 | 27 | 43 | 15 | 31 | 47 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 4  |  4 | 20 | 36 |  8 | 24 | 40 | 12 | 28 | 44 | 16 | 32 | 48 |
    +----+----+----+----+----+----+----+----+----+----+----+----+

Blocked product

julia> print_layout(blocked_product(tile, matrix_of_tiles))((_2, _3), (_2, _4)):((_1, _16), (_2, _4))
       1    2    3    4    5    6    7    8 
    +----+----+----+----+----+----+----+----+
 1  |  1 |  3 |  5 |  7 |  9 | 11 | 13 | 15 |
    +----+----+----+----+----+----+----+----+
 2  |  2 |  4 |  6 |  8 | 10 | 12 | 14 | 16 |
    +----+----+----+----+----+----+----+----+
 3  | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 |
    +----+----+----+----+----+----+----+----+
 4  | 18 | 20 | 22 | 24 | 26 | 28 | 30 | 32 |
    +----+----+----+----+----+----+----+----+
 5  | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 |
    +----+----+----+----+----+----+----+----+
 6  | 34 | 36 | 38 | 40 | 42 | 44 | 46 | 48 |
    +----+----+----+----+----+----+----+----+

Raked product

julia> print_layout(raked_product(tile, matrix_of_tiles))((_3, _2), (_4, _2)):((_16, _1), (_4, _2))
       1    2    3    4    5    6    7    8 
    +----+----+----+----+----+----+----+----+
 1  |  1 |  5 |  9 | 13 |  3 |  7 | 11 | 15 |
    +----+----+----+----+----+----+----+----+
 2  | 17 | 21 | 25 | 29 | 19 | 23 | 27 | 31 |
    +----+----+----+----+----+----+----+----+
 3  | 33 | 37 | 41 | 45 | 35 | 39 | 43 | 47 |
    +----+----+----+----+----+----+----+----+
 4  |  2 |  6 | 10 | 14 |  4 |  8 | 12 | 16 |
    +----+----+----+----+----+----+----+----+
 5  | 18 | 22 | 26 | 30 | 20 | 24 | 28 | 32 |
    +----+----+----+----+----+----+----+----+
 6  | 34 | 38 | 42 | 46 | 36 | 40 | 44 | 48 |
    +----+----+----+----+----+----+----+----+

Division

Logical division

julia> raked_prod = raked_product(tile, matrix_of_tiles);
julia> subtile = (Layout(2,3), Layout(2,4));
julia> print_layout(logical_divide(raked_prod, subtile))ERROR: MethodError: no method matching _complement(::Tuple{Int64}, ::Tuple{Int64}, ::Static.StaticInt{6})

Closest candidates are:
  _complement(::Tuple{Vararg{Union{Int32, Int64, Tuple, Static.StaticInt}, R}}, ::Tuple{Vararg{Union{Tuple{Vararg{Union{Tuple, Static.StaticInt}}}, Static.StaticInt}, R}}, ::Union{Int32, Int64, Static.StaticInt}) where R
   @ MoYe ~/work/MoYe.jl/MoYe.jl/src/layout.jl:640
  _complement(::Union{Int32, Int64, Static.StaticInt}, ::Static.StaticInt{0}, ::Union{Int32, Int64, Static.StaticInt})
   @ MoYe ~/work/MoYe.jl/MoYe.jl/src/layout.jl:634
  _complement(::Union{Int32, Int64, Static.StaticInt}, ::Union{Int32, Int64, Static.StaticInt}, ::Union{Int32, Int64, Static.StaticInt})
   @ MoYe ~/work/MoYe.jl/MoYe.jl/src/layout.jl:637

Zipped division

julia> print_layout(zipped_divide(raked_prod, subtile))ERROR: MethodError: no method matching _complement(::Tuple{Int64}, ::Tuple{Int64}, ::Static.StaticInt{6})

Closest candidates are:
  _complement(::Tuple{Vararg{Union{Int32, Int64, Tuple, Static.StaticInt}, R}}, ::Tuple{Vararg{Union{Tuple{Vararg{Union{Tuple, Static.StaticInt}}}, Static.StaticInt}, R}}, ::Union{Int32, Int64, Static.StaticInt}) where R
   @ MoYe ~/work/MoYe.jl/MoYe.jl/src/layout.jl:640
  _complement(::Union{Int32, Int64, Static.StaticInt}, ::Static.StaticInt{0}, ::Union{Int32, Int64, Static.StaticInt})
   @ MoYe ~/work/MoYe.jl/MoYe.jl/src/layout.jl:634
  _complement(::Union{Int32, Int64, Static.StaticInt}, ::Union{Int32, Int64, Static.StaticInt}, ::Union{Int32, Int64, Static.StaticInt})
   @ MoYe ~/work/MoYe.jl/MoYe.jl/src/layout.jl:637