liveBook · Manning

Row-major order

As explained in Grokking GPU Programming

Row-major order is a multidimensional array layout in which elements of each row are contiguous in memory.

A matrix may look like a grid, but its elements occupy a linear stretch of memory. In row-major order, the elements of each row are contiguous: the first row comes first, followed by the second, and so on. C and C++ use this layout for 2D arrays. section 10.10

Flattening a matrix

The 2×3 matrix [[a, b, c], [d, e, f]] is stored as [a, b, c, d, e, f]. For a matrix with width N, element (row, col) has index row * N + col: multiplying by N skips whole rows, and adding col selects an element within the row. section 12.12

Figure 10.8 Row-major layout. Consecutive 1D indices fill each row before moving to the next. Each cell shows the 1D array index where that matrix element lives: row 0 holds [0] through [m−1], row 1 holds [m] through [2m−1], and so on, ending at [nm−1] in the bottom-right. The numbered arrows give the traversal order: across the columns first (1), then down to the next row (2).

Follow the indices across each row, then down to the next row. section 10.10

Column-major order instead stores each column contiguously. Mixing its indexing arithmetic with row-major data can produce structured but incorrect results. For a square matrix, the result may look transposed; check indexing with a small matrix whose answer you can verify by hand. section 10.10 section 12.12

For GPU performance, look at the addresses a warp accesses at the same moment, not just the path of one thread. If each thread sums a different row, each thread walks contiguously, but simultaneous reads are a row width apart. If each thread sums a different column, simultaneous reads can touch consecutive elements of one row and coalesce. These two assignments compute different sums, so choose an access pattern that also produces the result you need. section 10.10

Row width also matters in shared memory. In a 32-bank example, reading a column of a 32×32 row-major tile sends all 32 accesses to the same bank. Adding a spacer column makes the physical row width 33, spreading those accesses across banks at the cost of 3.125% more shared memory. section 11.8

Figure 11.8 The padding trick on a toy 4-bank GPU: without padding (arr[4][4]), row-major storage places every column-0 element at a multiple-of-4 address, so all four land in bank 0 (a 4-way conflict). Adding one padding column (arr[4][5]) shifts each row’s start by one, moving the four accesses into four different banks, so the conflict disappears.

A four-bank model shows how an extra column shifts row starts and avoids a column-access conflict. section 11.8

Layout is a convention, not a CUDA requirement. Classic cuBLAS defaults to column-major storage; for tightly packed row-major matrices, its multiplication call can swap the operands and use the transposed view without copying data. Padding or submatrices require attention to the actual leading dimensions. cuBLASLt accepts other layouts. section 10.10 section 12.9

How Grokking GPU Programming covers it

How deep it goes
Works through flattening, indexing errors, warp access patterns, shared-memory padding, and the cuBLAS transpose trick.
Examples
Uses a 2×3 matrix, row and column sums, padded shared-memory tiles, and a cuBLAS matrix multiplication call.
What you can do after
Diagnose/debug indexing and access-pattern problems using row-major offsets and small hand-checked matrices.
How it connects
Connects matrix indexing with column-major order, memory coalescing, shared-memory bank conflicts, and matrix multiplication.

Also explained in

Compare how 2 books explain row-major order →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.