Matrices: two indices, one address

Matrices: two indices, one address

A matrix is a grid of numbers arranged in rows and columns. A row is one horizontal line of the grid, read from left to right. A column is one vertical line of the grid, read from top to bottom. Memory has no concept of rows or columns. It is one long line of bytes, the same kind of vector covered in the previous lesson. To store a matrix, its rows and columns must be placed one after another in that single line. The usual choice is row-major order: store every number of the first row, then every number of the second row, and continue until every row has been placed.

Two indices, one address

An element's position in a matrix is given by two indices: the row index, which row it belongs to, and the column index, which column it belongs to. Counting for both starts at 0, the same way indices worked in the vectors lesson. Memory holds a single flat sequence of numbers, so the two indices must first be combined into one flattened index: multiply the row index by the number of columns in the matrix, then add the column index. From there the flattened index becomes a byte address the same way a vector's index does: address = base + index * 4.

Flattening a row and column into an address
mul  t4, t1, t3 # t4 = row index * number of columns
add  t4, t4, t2 # t4 = that + column index (the flattened index)
slli t4, t4, 2 # t4 = byte offset = index * 4
add  t5, t0, t4 # t5 = address of the element at this row and column
lw   t5, 0(t5) # t5 = value at that address

multiplies the row index by the number of columns. In the vectors lesson the multiplication could be done with a shift because 4 is a power of two, but the number of columns in a matrix usually is not, so is used here instead of . The column index is added, and the result is scaled by 4 with another (4 is a power of two, so a shift still works for this part). That produces the byte offset of the element at the given row and column.

Row-major indexing
index=0× 3 +0=0
1
0x10010000
2
0x10010004
3
0x10010008
4
0x1001000c
5
0x10010010
6
0x10010014
7
0x10010018
8
0x1001001c
9
0x10010020
01
0x10010000
12
0x10010004
23
0x10010008
34
0x1001000c
45
0x10010010
56
0x10010014
67
0x10010018
78
0x1001001c
89
0x10010020

Row 0, column 0 maps to index 0.

The grid on the left shows how a matrix is drawn on paper. The single row on the right shows how those same numbers are laid out in memory. The highlight moves through the grid in reading order: row 0 from left to right, then row 1, then row 2. At the same moment the same element lights up in the flattened row below, because multiplying the row index by the number of columns and adding the column index gives that element's address, which matches the hex value shown on both sides. RISC-V works only with the flattened line on the right. The grid is a shape that your program's .data layout and your own reading of it impose on that single line, using the , , and arithmetic shown above. Once the grid and the flattened row are understood as one thing shown twice, the same pattern covers any grid of data: an image's rows of pixels, a game board, or a spreadsheet. Each is one array, reached with one extra multiplication.

Summing a matrix

Add every element of a 3 by 3 matrix
.data
m: .word 1, 2, 3, 4, 5, 6, 7, 8, 9 # 3x3 matrix, stored row by row
.text
la  t0, m # base address
li  t1, 3 # number of rows
li  t2, 3 # number of columns
li  t3, 0 # current row index, starts at 0
li  s0, 0 # running total
row_loop:
  beq t3, t1, row_done
  li  t4, 0 # current column index, starts at 0
col_loop:
  beq t4, t2, col_done
  mul  t5, t3, t2 # row index * number of columns
  add  t5, t5, t4 # + column index = flattened index
  slli t5, t5, 2 # byte offset = index * 4
  add  t6, t0, t5 # address of the element at this row and column
  lw   t6, 0(t6) # value at that address
  add  s0, s0, t6 # total += element
  addi t4, t4, 1 # move to the next column
  j col_loop
col_done:
  addi t3, t3, 1 # move to the next row
  j row_loop
row_done:
  mv a0, s0 # print total: 1+2+...+9 = 45
  li a7, 1
  ecall
  li a7, 10
  ecall

Two nested loops index the matrix. The outer loop selects a row and the inner loop selects a column within that row. multiplies the row index by the number of columns. Adding the column index and scaling by 4 gives the address of that element. The value stored at that address is loaded and added to the running total. When the inner loop finishes a row, the outer loop moves to the next row, until all 3 rows have been processed.

ℹ
Row-major order stores all the numbers of the first row, then all the numbers of the second row, and continues in that pattern. This is a convention rather than a rule. Other languages, Fortran among them, use column-major order: all the numbers of the first column, then all the numbers of the second column, and so on. The writer of the data and the reader of the data must agree on which layout was used. RISC-V reads and writes at whatever address you compute.
Open in Litessera Lux, the RISC-V AssemblerBuy me a coffee