1 # Shapes and Layout 2 3 The XLA `Shape` proto 4 ([xla_data.proto](https://www.tensorflow.org/code/tensorflow/compiler/xla/xla_data.proto)) 5 describes the rank, size, and data type of an N-dimensional array (*array* in 6 short). 7 8 ## Terminology, Notation, and Conventions 9 10 * The rank of an array is equal to the number of dimensions. The *true rank* 11 of an array is the number of dimensions which have a size greater than 1. 12 13 * Dimensions are numbered from `0` up to `N-1` for an `N` dimensional array. 14 The dimension numbers are arbitrary labels for convenience. The order of 15 these dimension numbers does not imply a particular minor/major ordering in 16 the layout of the shape. The layout is determined by the `Layout` proto. 17 18 * By convention, dimensions are listed in increasing order of dimension 19 number. For example, for a 3-dimensional array of size `[A x B x C]`, 20 dimension 0 has size `A`, dimension 1 has size `B` and dimension 2 has size 21 `C`. 22 23 Some utilities in XLA also support negative indexing, similarly to Python; 24 dimension -1 is the last dimension (equivalent to `N-1` for an `N` 25 dimensional array). For example, for the 3-dimensional array described 26 above, dimension -1 has size `C`, dimension -2 has size `B` and so on. 27 28 * Two, three, and four dimensional arrays often have specific letters 29 associated with dimensions. For example, for a 2D array: 30 31 * dimension 0: `y` 32 * dimension 1: `x` 33 34 For a 3D array: 35 36 * dimension 0: `z` 37 * dimension 1: `y` 38 * dimension 2: `x` 39 40 For a 4D array: 41 42 * dimension 0: `p` 43 * dimension 1: `z` 44 * dimension 2: `y` 45 * dimension 3: `x` 46 47 * Functions in the XLA API which take dimensions do so in increasing order of 48 dimension number. This matches the ordering used when passing dimensions as 49 an `initializer_list`; e.g. 50 51 `ShapeUtil::MakeShape(F32, {A, B, C, D})` 52 53 Will create a shape whose dimension size array consists of the sequence 54 `[A, B, C, D]`. 55 56 ## Layout 57 58 The `Layout` proto describes how an array is represented in memory. The `Layout` 59 proto includes the following fields: 60 61 ``` 62 message Layout { 63 repeated int64 minor_to_major = 1; 64 repeated int64 padded_dimensions = 2; 65 optional PaddingValue padding_value = 3; 66 } 67 ``` 68 69 ### Minor-to-major dimension ordering 70 71 The only required field is `minor_to_major`. This field describes the 72 minor-to-major ordering of the dimensions within a shape. Values in 73 `minor_to_major` are an ordering of the dimensions of the array (`0` to `N-1` 74 for an `N` dimensional array) with the first value being the most-minor 75 dimension up to the last value which is the most-major dimension. The most-minor 76 dimension is the dimension which changes most rapidly when stepping through the 77 elements of the array laid out in linear memory. 78 79 For example, consider the following 2D array of size `[2 x 3]`: 80 81 ``` 82 a b c 83 d e f 84 ``` 85 86 Here dimension `0` is size 2, and dimension `1` is size 3. If the 87 `minor_to_major` field in the layout is `[0, 1]` then dimension `0` is the 88 most-minor dimension and dimension `1` is the most-major dimension. This 89 corresponds to the following layout in linear memory: 90 91 ``` 92 a d b e c f 93 ``` 94 95 This minor-to-major dimension order of `0` up to `N-1` is akin to *column-major* 96 (at rank 2). Assuming a monotonic ordering of dimensions, another name we may 97 use to refer to this layout in the code is simply "dim 0 is minor". 98 99 On the other hand, if the `minor_to_major` field in the layout is `[1, 0]` then 100 the layout in linear memory is: 101 102 ``` 103 a b c d e f 104 ``` 105 106 A minor-to-major dimension order of `N-1` down to `0` for an `N` dimensional 107 array is akin to *row-major* (at rank 2). Assuming a monotonic ordering of 108 dimensions, another name we may use to refer to this layout in the code is 109 simply "dim 0 is major". 110 111 #### Default minor-to-major ordering 112 113 The default layout for newly created Shapes is "dimension order is 114 major-to-minor" (akin to row-major at rank 2). 115 116 ### Padding 117 118 Padding is defined in the optional `padded_dimensions` and `padding_value` 119 fields. The field `padded_dimensions` describes the sizes (widths) to which each 120 dimension is padded. If present, the number of elements in `padded_dimensions` 121 must equal the rank of the shape. 122 123 For example, given the `[2 x 3]` array defined above, if `padded_dimension` is 124 `[3, 5]` then dimension 0 is padded to a width of 3 and dimension 1 is padded to 125 a width of 5. The layout in linear memory (assuming a padding value of 0 and 126 column-major layout) is: 127 128 ``` 129 a d 0 b e 0 c f 0 0 0 0 0 0 0 130 ``` 131 132 This is equivalent to the layout of the following array with the same 133 minor-to-major dimension order: 134 135 ``` 136 a b c 0 0 137 d e f 0 0 138 0 0 0 0 0 139 ``` 140 141 ### Indexing into arrays 142 143 The class `IndexUtil` in 144 [index_util.h](https://www.tensorflow.org/code/tensorflow/compiler/xla/index_util.h) 145 provides utilities for converting between multidimensional indices and linear 146 indices given a shape and layout. Multidimensional indices include a `int64` 147 index for each dimension. Linear indices are a single `int64` value which 148 indexes into the buffer holding the array. See `shape_util.h` and 149 `layout_util.h` in the same directory for utilities that simplify creation and 150 manipulation of shapes and layouts. 151
