Linearized Multi-Dimensional Arrays

Linearized Multi-Dimensional Arrays

Contiguous memory blocks are efficient and easy to vectorize, as we found out in the previous sections. Further gains are possible if we can represent the higher-order logic of the AI model in matrices and tensors, but retain the power of sequential address spaces underneath. Rather than thinking of a matrix as rows and columns, or higher dimensions for tensors, we should still think of them as one big chunk of data.

Using dynamic memory to store multi-dimensional arrays is a difficult problem to solve. One idea is to allocated a one-dimensional array, and then “map” a two-dimensional structure on it by using arithmetic with the index offsets. This is what the compiler is doing behind the scenes when it defines the builtin C++ multi-dimensional arrays.

The main difficulty with multi-dimensional arrays of primitive types (e.g. float) is that “new[]” or malloc/calloc return blocks of memory with no structure, and it is difficult to impose the structure of a multi-dimensional array. It is only legal to use one dimension of indexing on the pointer to this block of memory.

For example, if we wish to declare an array similar to arr[5][3] on the heap, we cannot allocate 15 integers, pass the address to a pointer and then use two levels of brackets on the pointer variable such as ptr[i][j]. Instead, it is necessary to map the two indices, x and y, to a single index, i. For the array arr[5][3] the mapping is:

    i = x * 3 + y;
    val = ptr[i];

Note that this is pointer arithmetic based on the size of the array's data, not the number of bytes.

More generally, a macro for defining the mapping for two-dimensional arrays, using the indices and the number of rows and columns, is shown below:

    #define MAP2(x1, x2, size1, size2) (x1 * size2 + x2)

Note that the size1 macro parameter is not actually used, but is left there to avoid confusion (or maybe to create it). The size of the first dimension is not needed in any linearized index calculations.

The MAP2 macro can be used for multi-dimensional dynamic arrays, as below. Unfortunately, the MAP2 macro must be used for every array reference. The code fragment below allocates a two-dimensional dynamic array and then uses the MAP2 macro to set all elements to zero.

    int num_rows = 5, num_columns = 3;
    int *p = calloc(num_rows * num_columns, sizeof(int));
    for (int i = 0; i < num_rows; i++)
        for (int j = 0; j < num_columns; j++)
            p[MAP2(i, j, num_rows, num_columns)] = 0; // p[i][j]=0 

Similarly, macros can be defined for mapping three-dimensional and higher dimensional arrays to the one-dimensional array index. The macros for dimensions three and four are shown below, and macros for higher dimensions can be devised by following the pattern.

    #define MAP3(x1, x2, x3, size1, size2, size3) \
        (x1 * size2 * size3 + x2 * size3 + x3)
    #define MAP4(x1, x2, x3, x4, size1, size2, size3, size4) \
        (x1 * size2 * size3 * size4 + x2 * size3 * size4 \
        + x3*size4 + x4)

• Next: • Up: Table of Contents • Buy: Generative AI in C++: Coding Transformers and LLMs

The new AI programming book by Aussie AI co-founders: AI coding in C++ Transformer engine speedups LLM models Phone and desktop AI Code examples Research citations Get your copy from Amazon: Generative AI in C++