Matrices: dos índices, una dirección

Matrices: dos índices, una dirección

Una matriz es una cuadrícula de números dispuestos en filas y columnas. Una fila es una línea horizontal de la cuadrícula, que se lee de izquierda a derecha. Una columna es una línea vertical de la cuadrícula, que se lee de arriba a abajo. La memoria no tiene concepto de filas ni columnas. Es una sola línea larga de bytes, el mismo tipo de vector tratado en la lección anterior. Para almacenar una matriz, sus filas y columnas deben colocarse una tras otra en esa única línea. La elección habitual es el orden row-major (por filas): almacenar cada número de la primera fila, luego cada número de la segunda fila, y continuar hasta que se haya colocado cada fila.

Dos índices, una dirección

La posición de un elemento en una matriz viene dada por dos índices: el índice de fila, que indica a qué fila pertenece, y el índice de columna, que indica a qué columna pertenece. El conteo de ambos comienza en 0, igual que funcionaban los índices en la lección de vectores. La memoria contiene una única secuencia plana de números, por lo que los dos índices deben combinarse primero en un único índice aplanado: multiplicar el índice de fila por el número de columnas de la matriz y luego sumar el índice de columna. A partir de ahí, el índice aplanado se convierte en una dirección de byte de la misma manera que lo hace el índice de un vector: address = base + index * 4.

Aplanar una fila y una columna en una dirección
mul  t4, t1, t3 # t4 = índice de fila * número de columnas
add  t4, t4, t2 # t4 = that + índice de columna (el índice aplanado)
slli t4, t4, 2 # t4 = desplazamiento en bytes = índice * 4
add  t5, t0, t4 # t5 = dirección del elemento en esa fila y columna
lw   t5, 0(t5) # t5 = valor en esa dirección

multiplica el índice de fila por el número de columnas. En la lección de vectores la multiplicación podía hacerse con un desplazamiento porque 4 es una potencia de dos, pero el número de columnas de una matriz normalmente no lo es, así que aquí se usa en lugar de . Se suma el índice de columna y el resultado se escala por 4 con otro (4 es una potencia de dos, así que un desplazamiento sigue funcionando para esta parte). Eso produce el desplazamiento en bytes del elemento en la fila y columna dadas.

Indexación por filas
índice=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

Fila 0, columna 0 se asigna al índice 0.

La cuadrícula de la izquierda muestra cómo se dibuja una matriz en papel. La única fila de la derecha muestra cómo se disponen esos mismos números en memoria. El resaltado recorre la cuadrícula en orden de lectura: fila 0 de izquierda a derecha, luego fila 1, luego fila 2. En el mismo momento el mismo elemento se ilumina en la fila aplanada de abajo, porque multiplicar el índice de fila por el número de columnas y sumar el índice de columna da la dirección de ese elemento, que coincide con el valor hexadecimal mostrado en ambos lados. RISC-V trabaja únicamente con la línea aplanada de la derecha. La cuadrícula es una forma que la disposición .data de tu programa y tu propia lectura de ella imponen sobre esa única línea, usando la aritmética , y mostrada arriba. Una vez que la cuadrícula y la fila aplanada se entienden como una sola cosa mostrada dos veces, el mismo patrón cubre cualquier cuadrícula de datos: las filas de píxeles de una imagen, un tablero de juego o una hoja de cálculo. Cada una es un array, al que se accede con una multiplicación adicional.

Suma de una matriz

Suma todos los elementos de una matriz de 3 por 3
.data
m: .word 1, 2, 3, 4, 5, 6, 7, 8, 9 # matriz 3x3, almacenada fila por fila
.text
la  t0, m # dirección base
li  t1, 3 # número de filas
li  t2, 3 # número de columnas
li  t3, 0 # índice de fila actual, empieza en 0
li  s0, 0 # total acumulado
row_loop:
  beq t3, t1, row_done
  li  t4, 0 # índice de columna actual, empieza en 0
col_loop:
  beq t4, t2, col_done
  mul  t5, t3, t2 # índice de fila * número de columnas
  add  t5, t5, t4 # + índice de columna = índice aplanado
  slli t5, t5, 2 # desplazamiento en bytes = índice * 4
  add  t6, t0, t5 # dirección del elemento en esa fila y columna
  lw   t6, 0(t6) # valor en esa dirección
  add  s0, s0, t6 # total += elemento
  addi t4, t4, 1 # avanza a la siguiente columna
  j col_loop
col_done:
  addi t3, t3, 1 # avanza a la siguiente fila
  j row_loop
row_done:
  mv a0, s0 # imprime el total: 1+2+...+9 = 45
  li a7, 1
  ecall
  li a7, 10
  ecall

Dos bucles anidados indexan la matriz. El bucle externo selecciona una fila y el bucle interno selecciona una columna dentro de esa fila. multiplica el índice de fila por el número de columnas. Sumar el índice de columna y escalar por 4 da la dirección de ese elemento. El valor almacenado en esa dirección se carga y se suma al total acumulado. Cuando el bucle interno termina una fila, el bucle externo pasa a la siguiente fila, hasta que se hayan procesado las 3 filas.

ℹ
El orden fila-prioritario almacena todos los números de la primera fila, luego todos los números de la segunda fila, y continúa en ese patrón. Esto es una convención más que una regla. Otros lenguajes, Fortran entre ellos, usan el orden columna-prioritario: todos los números de la primera columna, luego todos los números de la segunda columna, y así sucesivamente. El escritor de los datos y el lector de los datos deben acordar qué disposición se utilizó. RISC-V lee y escribe en la dirección que tú calcules.
Abrir en Litessera Lux, el ensamblador RISC-VCómprame un café