Laboratori 4: Matrius i subrutines

Lliuraments

Cal lliurar les respostes als exercicis següents al campus virtual abans de l’inici de la sessió de laboratori:

Exercici	Nom i format del fitxer
Exercici 31.1	`s4_1_1.s`
Exercici 31.2	`s4_2_1.md`
Exercici 31.3	`s4_2_2.md` i `s4_2_2.s`
Exercici 31.4	`s4_3_1.md` i `s4_3_1.s`

Lectura prèvia

Abans de fer la sessió, cal haver llegit i entès els continguts següents:

Concepte	On trobar-ho
Declaració de matrius en memòria (`.space`, `.word`, `.align`)	Secció 4.5.1, RISC-V 2.31
Càlcul de l’adreça d’un element `mat[i][j]`	Equació 4.3, Secció 4.5.2
Instruccions de lectura i escriptura (`lw`, `sw`, `lb`, `sb`, `lbu`)	RISC-V 2.29
`long long` en RV32I: dos registres per valor de 64 bits	Essencial 2.11
Instrucció de multiplicació entera (`mul`)	RISC-V 4.2
Pas de matrius per referència com a paràmetre	Exemple 4.13
Subrutines multinivell: registres segurs i bloc d’activació	Secció 3.9.4, RISC-V 3.20
Accés seqüencial i stride	Secció 4.6.1, Equació 4.4

31.1 Declaració de matrius

Les matrius multidimensionals s’emmagatzemen en memòria en ordre de files (row-major order): primer tots els elements de la fila 0, després els de la fila 1, i així successivament fins a la darrera fila (Secció 4.5.1). La mida total d’una matriu de NF files, NC columnes i elements de $T$ bytes és $\texttt{NF} \cdot \texttt{NC} \cdot T$ bytes.

Exercici 31.1 (s4_1_1.s) Declareu al segment .data les variables globals del Codi 31.1. Useu .eqv per a les dimensions de cada matriu (EC 4.1). Garantiu l’alineació correcta de cada variable amb la directiva .align on calgui.

Codi 31.1: Quatre matrius globals de tres tipus.

int       mat1[5][6];
char      mat2[3][5];
long long mat3[2][2];
int       mat4[2][3] = {{2, 3, 1}, {2, 4, 3}};

Recordeu que en C els elements d’una matriu es guarden per files, i que en RV32I:

int ocupa 4 bytes (alineació a 4 bytes, .align 2).
char ocupa 1 byte (sense restricció d’alineació).
long long ocupa 8 bytes (alineació a 8 bytes, .align 3); calen dos registres per operar-hi (Essencial 2.11).

Solució 31.1.

s4_1_1.s

.eqv NF1, 5
.eqv NC1, 6
.eqv NF2, 3
.eqv NC2, 5
.eqv NF3, 2
.eqv NC3, 2
.eqv NF4, 2
.eqv NC4, 3

.data
        .align 2
mat1:   .space  120               # int mat1[5][6]: NF1*NC1*4 = 120 bytes

mat2:   .space  15                # char mat2[3][5]: NF2*NC2*1 = 15 bytes (sense alineació)

        .align 3
mat3:   .space  32            # long long mat3[2][2]: NF3*NC3*8 = 32 bytes

        .align 2
mat4:   .word   2, 3, 1, 2, 4, 3  # int mat4[2][3] inicialitzada per files

.text
        li      a7, 93
        li      a0, 0
        ecall

La mida de cada .space s’escriu com a literal ja calculat, amb l’expressió aritmètica al comentari, perquè RARS no avalua expressions als operands (RISC-V 2.11); per això, tot i estar definides amb .eqv, les dimensions NF/NC no es poden multiplicar dins .space (NF1*NC1*4): una constant .eqv sola sí que hi és vàlida, però no una expressió.

mat2 és de tipus char (1 byte), de manera que no requereix cap directiva .align. Tot i així, la variable següent (mat3) necessita alineació a 8 bytes: la directiva .align 3 just abans de mat3 garanteix que comença en una adreça múltiple de 8, independentment de quants bytes ocupa mat2.

mat4 s’inicialitza amb .word llistant els elements per files: primer la fila 0 (2, 3, 1) i després la fila 1 (2, 4, 3). La directiva .align 2 és explícita a títol documental: com que mat3 comença en una adreça múltiple de 8 i ocupa 32 bytes, l’adreça següent (la de mat4) ja és múltiple de 4.

31.2 Accés a elements

L’adreça d’un element mat[i][j] d’una matriu de NC columnes i elements de $T$ bytes es calcula com (Equació 4.3):

\[@\texttt{mat[i][j]} = @\texttt{mat[0][0]} + (i \cdot \texttt{NC} + j) \cdot T\]

Exercici 31.2 (s4_2_1.md) Donades les variables globals declarades a Solució 31.1, calculeu l’adreça de memòria de cada un dels elements següents en funció de l’adreça base de la matriu corresponent:

@mat1[4][3]
@mat2[2][4]
@mat3[1][0]
@mat4[0][2]

Solució 31.2. Aplicant la fórmula $@\texttt{mat[i][j]} = @\texttt{mat[0][0]} + (i \cdot \texttt{NC} + j) \cdot T$:

Element	`NC`	$T$	Càlcul	Resultat
`mat1[4][3]`	6	4	`@mat1 + (4·6 + 3)·4`	`@mat1 + 108`
`mat2[2][4]`	5	1	`@mat2 + (2·5 + 4)·1`	`@mat2 + 14`
`mat3[1][0]`	2	8	`@mat3 + (1·2 + 0)·8`	`@mat3 + 16`
`mat4[0][2]`	3	4	`@mat4 + (0·3 + 2)·4`	`@mat4 + 8`

Per a mat3, $T = 8$ perquè cada element és de tipus long long (64 bits). L’element mat3[1][0] ocupa les adreces @mat3 + 16 (paraula baixa) i @mat3 + 20 (paraula alta), en ordre little-endian (Secció 2.5.1).

Exercici 31.3 (s4_2_2.md i s4_2_2.s) Traduïu a RV32IM el programa C del Codi 31.2. El programa principal crida subr dues vegades; subr accedeix a mat1 per índexs variables.

Codi 31.2: Programa que crida dues vegades la funció subr.

int mat1[5][6];
int mat4[2][3] = {{2, 3, 1}, {2, 4, 3}};
int col = 2;

void main() {
    mat1[4][3] = subr(mat4, mat4[0][2], col);
    mat1[0][0] = subr(mat4, 1, 1);
}

int subr(int x[][3], int i, int j) {
    mat1[j][5] = x[i][j];
    return i;
}

subr rep una matriu per referència (x és l’adreça base) i accedeix a x[i][j] i a mat1[j][5] amb índexs variables: cal usar mul (RISC-V 4.2).

Abans d’escriure cap instrucció:

Determineu si subr és uninivell o multinivell i per què.
Determineu si el programa principal fa crides i quines conseqüències té per a la gestió del context. Tingueu en compte que és el punt d’entrada del programa —és el primer bloc del segment .text—: no és cridat per cap altra subrutina i acaba amb ecall (RISC-V 3.23).
Per a cada funció, identifiqueu quines dades es generen abans d’una crida i s’usen després (Secció 3.9.4). Assigneu-les a registres segurs.
Dibuixeu el bloc d’activació de cada funció amb els desplaçaments de cada element.

Un cop escrit, poseu un punt de ruptura a l’inici de subr, executeu fins a aquest punt i anoteu els valors (en hexadecimal) dels registres a0, a1, a2 i ra en cadascuna de les dues crides.

Comproveu que, en acabar, mat1[0][0] = 1, mat1[1][5] = 4, mat1[2][5] = 3 i mat1[4][3] = 1.

Solució 31.3. Pas 1. subr: uninivell o multinivell.

subr és uninivell: no fa cap crida. No cal preservar ra ni cap registre segur per a valors que travessen una crida; tots els temporals van a registres t i el bloc d’activació queda buit.

Pas 2. El programa principal: gestió del context.

El programa principal fa dues crides a subr, però és el punt d’entrada: com que és el primer bloc del segment .text, no és la funció cridada per cap altra subrutina, i acaba amb ecall (sortida), no amb ret. Per tant, no ha de preservar ra ni cap registre segur per a ningú, i no li cal bloc d’activació. Sí que ha d’usar registres segurs (s0–s11) per a les dades pròpies que han de sobreviure a les crides: com que subr és responsable de restaurar-los abans de retornar (Essencial 3.11), el seu valor es conserva a través de cada crida.

Pas 3. Registres segurs del programa principal.

Entre la primera crida a subr i la segona, el programa principal necessita les adreces de mat1 i mat4. Com que aquests valors travessen les crides, s’assignen a registres segurs:

Dada	Registre
`@mat1`	`s0`
`@mat4`	`s1`

Pas 4. Blocs d’activació.

Cap de les dues rutines no necessita bloc d’activació: subr és uninivell i sense variables locals, i el programa principal no ha de preservar cap registre. Tots dos BA són buits.

s4_2_2.s

.eqv NF1, 5
.eqv NC1, 6
.eqv NF4, 2
.eqv NC4, 3

.data
        .align 2
mat1:   .space  120            # int mat1[5][6]: NF1*NC1*4 = 120 bytes
        .align 2
mat4:   .word   2, 3, 1, 2, 4, 3  # int mat4[2][3]
col:    .word   2

.text

        la      s0, mat1          # s0 = @mat1 (segur: travessa les crides)
        la      s1, mat4          # s1 = @mat4 (segur: travessa les crides)

        # mat1[4][3] = subr(mat4, mat4[0][2], col)
        mv      a0, s1            # arg0: @mat4
        lw      a1, 8(s1)         # arg1: mat4[0][2] = @mat4 + 8 → 1
        la      t0, col
        lw      a2, 0(t0)         # arg2: col = 2
        jal     ra, subr          # a0 = subr(@mat4, 1, 2) → retorna 1

        # @mat1[4][3] = @mat1 + (4*NC1 + 3)*4 = @mat1 + 108
        sw      a0, 108(s0)

        # mat1[0][0] = subr(mat4, 1, 1)
        mv      a0, s1            # arg0: @mat4
        li      a1, 1             # arg1: i = 1
        li      a2, 1             # arg2: j = 1
        jal     ra, subr          # a0 = subr(@mat4, 1, 1) → retorna 1

        # @mat1[0][0] = @mat1 + 0
        sw      a0, 0(s0)

        li      a7, 93
        li      a0, 0
        ecall

# subr(int x[][3], int i, int j)
# a0 = @x, a1 = i, a2 = j
# retorna i (a0)
# uninivell: a2 = j és vàlid durant tot el cos (cap crida el destrueix)
subr:
        # t0 = x[i][j] = Mw[@x + (i*NC4 + j)*4]
        li      t1, NC4
        mul     t0, a1, t1        # t0 = i * NC4
        add     t0, t0, a2        # t0 = i*NC4 + j
        slli    t0, t0, 2         # t0 = (i*NC4 + j) * 4
        add     t0, a0, t0        # t0 = @x[i][j]
        lw      t0, 0(t0)         # t0 = x[i][j]

        # mat1[j][5] = x[i][j]
        # @mat1[j][5] = @mat1 + (j*NC1 + 5)*4
        la      t1, mat1
        li      t2, NC1
        mul     t3, a2, t2        # t3 = j * NC1
        addi    t3, t3, 5         # t3 = j*NC1 + 5
        slli    t3, t3, 2         # t3 = (j*NC1 + 5) * 4
        add     t1, t1, t3        # t1 = @mat1[j][5]
        sw      t0, 0(t1)         # mat1[j][5] = x[i][j]

        mv      a0, a1            # return i
        ret

Comprovació pràctica

Els quatre elements de l’enunciat són a @mat1 + 0, @mat1 + 44, @mat1 + 68 i @mat1 + 108. Per localitzar-los a la vista de dades de RARS, calculeu l’adreça absoluta sumant el desplaçament a l’adreça base de mat1 (visible al panell Labels).

31.3 Accés seqüencial

Quan un bucle recorre els elements d’una matriu i la distància en bytes entre dos elements consecutius del recorregut és constant, es pot aplicar la tècnica d’accés seqüencial (Secció 4.6.1): en lloc de recalcular l’adreça a cada iteració, es manté un punter p que s’incrementa sumant-li l’stride (Equació 4.4):

\[\text{stride} = @X_{i+1} - @X_i = \text{constant}\]

L’stride depèn del patró de recorregut. Per a una matriu d’elements de mida $T$ bytes i NC columnes (Secció 4.6.4):

Recorregut	Stride
Una fila (elements consecutius)	$T$
Una columna (salt entre files)	$\texttt{NC} \cdot T$

Exercici 31.4 (s4_3_1.md i s4_3_1.s) Considereu la matriu i el programa C del Codi 31.3:

Codi 31.3: Matriu mat i programa que en suma una columna.

int mat[4][6] = { {0, 0, 2, 0, 0, 0},
                  {0, 0, 4, 0, 0, 0},
                  {0, 0, 6, 0, 0, 0},
                  {0, 0, 8, 0, 0, 0} };
int resultat;

void main() {
    resultat = suma_col(mat);
}

int suma_col(int m[][6]) {
    int i, suma = 0;
    int *p;
    p = &m[0][2];       // inicialitzar el punter
    for (i = 0; i < 4; i++) {
        suma += *p;     // accés a m usant el punter
        p += 6;         // incrementar el punter
    }
    return suma;
}

Abans d’escriure cap instrucció, responeu al fitxer s4_3_1.md:

Calculeu l’adreça de m[i][2] en funció de @m i i.
Calculeu l’stride per recórrer la columna 2 (distància en bytes entre m[i][2] i m[i+1][2]).
Expliqueu per què p += 6 al codi C correspon, en assemblador, a sumar l’stride calculat a l’apartat anterior (aritmètica de punters).
Determineu si suma_col és uninivell o multinivell i assigneu cada variable a un registre.
Determineu si el programa principal fa alguna crida i quines conseqüències té per a la gestió del context. Recordeu que és el punt d’entrada del programa —el primer bloc de .text— i que acaba amb ecall.

A continuació, traduïu el programa a RV32IM usant la tècnica d’accés seqüencial per recórrer la columna i eliminant la variable d’inducció (Secció 4.6.3).

Comproveu que, en acabar, la variable global resultat conté 20 (la suma dels elements de la columna 2: $2 + 4 + 6 + 8$).

Solució 31.4. Pas 1. Adreça de m[i][2].

\[@\texttt{m[i][2]} = @\texttt{m} + (i \cdot 6 + 2) \cdot 4 = @\texttt{m} + i \cdot 24 + 8\]

Pas 2. Stride.

\[\text{stride} = @\texttt{m[i+1][2]} - @\texttt{m[i][2]} = 24 \text{ bytes}\]

Pas 3. Aritmètica de punters.

En C, p és de tipus int *. Un increment d’una unitat (p += 1) equival a sumar la mida de l’element apuntat en bytes (4 bytes per a int). Per tant, p += 6 equival a sumar $6 \cdot 4 = 24$ bytes en assemblador, que coincideix exactament amb l’stride calculat.

Pas 4. Assignació de registres de suma_col.

suma_col és uninivell: no fa cap crida. Tots els temporals van a registres t; BA buit.

Variable	Registre
`p` (punter, inicialitzat a `@m[0][2]`)	`t0`
`suma`	`t1`
sentinella (`@m[NF][2]`)	`t2`
stride (24)	`t3`
`*p` (valor llegit a cada iteració)	`t4`

El registre t4 es reutilitza abans del bucle com a temporal per calcular la sentinella (NF), i dins del bucle per contenir *p; no hi ha conflicte perquè els dos usos no coincideixen en el temps.

Com que el recorregut elimina la variable d’inducció i i controla el bucle comparant el punter amb una sentinella (Secció 4.6.3), la comparació es fa entre adreces, que són naturals: per això s’usa bgeu/bltu en lloc de bge/blt (Essencial 4.4).

Pas 5. Gestió del context del programa principal.

El programa principal crida suma_col, però és el punt d’entrada: com que és el primer bloc del segment .text, no és la funció cridada per cap altra subrutina, i acaba amb ecall. Per tant, no ha de preservar ra ni cap registre segur, i no li cal bloc d’activació. A més, no hi ha cap valor propi que hagi de travessar la crida (el resultat es desa directament a resultat en retornar), de manera que no necessita cap registre segur.

s4_3_1.s

.eqv NF, 4
.eqv NC, 6

.data
        .align 2
mat:    .word   0, 0, 2, 0, 0, 0
        .word   0, 0, 4, 0, 0, 0
        .word   0, 0, 6, 0, 0, 0
        .word   0, 0, 8, 0, 0, 0
        .align 2
resultat: .word 0

.text

        la      a0, mat
        jal     ra, suma_col    # a0 = suma_col(mat)

        la      t0, resultat
        sw      a0, 0(t0)       # resultat = a0

        li      a7, 93
        li      a0, 0
        ecall

# suma_col(int m[][6])
# a0 = @m
# retorna suma (a0)
suma_col:
        li      t1, 0           # suma = 0
        li      t3, 24          # stride = NC*4 = 6*4 = 24
        addi    t0, a0, 8       # p = @m[0][2] = @m + (0*NC + 2)*4 = @m + 8
        li      t4, NF
        mul     t2, t4, t3
        add     t2, t0, t2      # sentinella = @m[NF][2] = p + NF*stride
for:
        bgeu    t0, t2, fifor   # salta si p >= sentinella
        lw      t4, 0(t0)       # t4 = *p = m[i][2]
        add     t1, t1, t4      # suma += *p
        add     t0, t0, t3      # p += stride
        j       for
fifor:
        mv      a0, t1          # return suma
        ret

Comprovació pràctica

Per verificar l’accés seqüencial, poseu un punt de ruptura a la instrucció lw t4, 0(t0) del bucle. A cada pulsació de Run → Go (F5), observeu com t0 avança 24 bytes i t4 pren successivament els valors 2, 4, 6 i 8.

Aprofundiment 31.1: L’stride i la memòria cau

L’stride determina l’eficiència d’ús de la memòria cau. Recórrer una fila (amb un stride de 4 bytes) és eficient: elements consecutius comparteixen el mateix bloc. Recórrer una columna (amb un stride de 24 bytes, en aquest cas) salta entre files i pot provocar moltes més fallades de memòria cau (cache misses), especialment si NC és gran.

A Capítol 33 s’analitza quantitativament aquest efecte.

--- number-sections: true --- # {{< var sessio4 >}} {#sec-sessio-matrius-subrutines} ### Lliuraments {.unnumbered} Cal lliurar les respostes als exercicis següents al campus virtual abans de l'inici de la sessió de laboratori: | Exercici | Nom i format del fitxer | | :--- | :--- | | @exr-declaracio-matrius | `s4_1_1.s` | | @exr-adreces-matrius | `s4_2_1.md` | | @exr-subr-matrius | `s4_2_2.md` i `s4_2_2.s` | | @exr-suma-columna | `s4_3_1.md` i `s4_3_1.s` | : {.striped .hover} ### Lectura prèvia {.unnumbered} Abans de fer la sessió, cal haver llegit i entès els continguts següents: | Concepte | On trobar-ho | | :--- | :--- | | Declaració de matrius en memòria (`.space`, `.word`, `.align`) | @sec-matrius-declaracio, @nte-directives-align-space | | Càlcul de l'adreça d'un element `mat[i][j]` | @eq-acces-aleatori-matriu, @sec-matrius-acces-aleatori | | Instruccions de lectura i escriptura (`lw`, `sw`, `lb`, `sb`, `lbu`) | @nte-load-store | | `long long` en RV32I: dos registres per valor de 64 bits | @cau-long-long-2-regs | | Instrucció de multiplicació entera (`mul`) | @nte-rv32im-instruccions-multiplicacio | | Pas de matrius per referència com a paràmetre | @tip-matriu-pas-referencia | | Subrutines multinivell: registres segurs i bloc d'activació | @sec-multinivell-pila, @nte-abi-variables-locals | | Accés seqüencial i *stride* | @sec-opt-acces-sequencial, @eq-stride | : {.striped .hover} ## Declaració de matrius Les matrius multidimensionals s'emmagatzemen en memòria en ordre de files (*row-major order*): primer tots els elements de la fila 0, després els de la fila 1, i així successivament fins a la darrera fila (@sec-matrius-declaracio). La mida total d'una matriu de `NF` files, `NC` columnes i elements de $T$ bytes és $\texttt{NF} \cdot \texttt{NC} \cdot T$ bytes. --- :::: {#exr-declaracio-matrius} ## `s4_1_1.s` Declareu al segment `.data` les variables globals del @lst-declaracio-matrius. Useu `.eqv` per a les dimensions de cada matriu (@imp-eqv-dimensions). Garantiu l'alineació correcta de cada variable amb la directiva `.align` on calgui. ::: {#lst-declaracio-matrius} ```{.c filename="C"} int mat1[5][6]; char mat2[3][5]; long long mat3[2][2]; int mat4[2][3] = {{2, 3, 1}, {2, 4, 3}}; ``` Quatre matrius globals de tres tipus. ::: Recordeu que en C els elements d'una matriu es guarden per files, i que en RV32I: - `int` ocupa 4 bytes (alineació a 4 bytes, `.align 2`). - `char` ocupa 1 byte (sense restricció d'alineació). - `long long` ocupa 8 bytes (alineació a 8 bytes, `.align 3`); calen **dos registres** per operar-hi (@cau-long-long-2-regs). :::: --- ::: {#sol-declaracio-matrius} ```{.s filename="s4_1_1.s"} .eqv NF1, 5 .eqv NC1, 6 .eqv NF2, 3 .eqv NC2, 5 .eqv NF3, 2 .eqv NC3, 2 .eqv NF4, 2 .eqv NC4, 3 .data .align 2 mat1: .space 120 # int mat1[5][6]: NF1*NC1*4 = 120 bytes mat2: .space 15 # char mat2[3][5]: NF2*NC2*1 = 15 bytes (sense alineació) .align 3 mat3: .space 32 # long long mat3[2][2]: NF3*NC3*8 = 32 bytes .align 2 mat4: .word 2, 3, 1, 2, 4, 3 # int mat4[2][3] inicialitzada per files .text li a7, 93 li a0, 0 ecall ``` La mida de cada `.space` s'escriu com a **literal ja calculat**, amb l'expressió aritmètica al comentari, perquè RARS no avalua expressions als operands (@nte-rars-operands-literals); per això, tot i estar definides amb `.eqv`, les dimensions `NF`/`NC` no es poden multiplicar dins `.space` (`NF1*NC1*4`): una constant `.eqv` sola sí que hi és vàlida, però no una expressió. `mat2` és de tipus `char` (1 byte), de manera que no requereix cap directiva `.align`. Tot i així, la variable **següent** (`mat3`) necessita alineació a 8 bytes: la directiva `.align 3` just abans de `mat3` garanteix que comença en una adreça múltiple de 8, independentment de quants bytes ocupa `mat2`. `mat4` s'inicialitza amb `.word` llistant els elements **per files**: primer la fila 0 (`2, 3, 1`) i després la fila 1 (`2, 4, 3`). La directiva `.align 2` és explícita a títol documental: com que `mat3` comença en una adreça múltiple de 8 i ocupa 32 bytes, l'adreça següent (la de `mat4`) ja és múltiple de 4. ::: ## Accés a elements L'adreça d'un element `mat[i][j]` d'una matriu de `NC` columnes i elements de $T$ bytes es calcula com (@eq-acces-aleatori-matriu): $$@\texttt{mat[i][j]} = @\texttt{mat[0][0]} + (i \cdot \texttt{NC} + j) \cdot T$$ --- ::: {#exr-adreces-matrius} ## `s4_2_1.md` Donades les variables globals declarades a @sol-declaracio-matrius, calculeu l'adreça de memòria de cada un dels elements següents en funció de l'adreça base de la matriu corresponent: - `@mat1[4][3]` - `@mat2[2][4]` - `@mat3[1][0]` - `@mat4[0][2]` ::: --- ::: {#sol-adreces-matrius} Aplicant la fórmula $@\texttt{mat[i][j]} = @\texttt{mat[0][0]} + (i \cdot \texttt{NC} + j) \cdot T$: | Element | `NC` | $T$ | Càlcul | Resultat | | :--- | ---: | ---: | :--- | :--- | | `mat1[4][3]` | 6 | 4 | `@mat1 + (4·6 + 3)·4` | `@mat1 + 108` | | `mat2[2][4]` | 5 | 1 | `@mat2 + (2·5 + 4)·1` | `@mat2 + 14` | | `mat3[1][0]` | 2 | 8 | `@mat3 + (1·2 + 0)·8` | `@mat3 + 16` | | `mat4[0][2]` | 3 | 4 | `@mat4 + (0·3 + 2)·4` | `@mat4 + 8` | : {.striped .hover} Per a `mat3`, $T = 8$ perquè cada element és de tipus `long long` (64 bits). L'element `mat3[1][0]` ocupa les adreces `@mat3 + 16` (paraula baixa) i `@mat3 + 20` (paraula alta), en ordre *little-endian* (@sec-endianness). ::: --- :::: {#exr-subr-matrius} ## `s4_2_2.md` i `s4_2_2.s` Traduïu a RV32IM el programa C del @lst-subr-matrius. El programa principal crida `subr` dues vegades; `subr` accedeix a `mat1` per índexs variables. ::: {#lst-subr-matrius} ```{.c filename="C"} int mat1[5][6]; int mat4[2][3] = {{2, 3, 1}, {2, 4, 3}}; int col = 2; void main() { mat1[4][3] = subr(mat4, mat4[0][2], col); mat1[0][0] = subr(mat4, 1, 1); } int subr(int x[][3], int i, int j) { mat1[j][5] = x[i][j]; return i; } ``` Programa que crida dues vegades la funció `subr`. ::: `subr` rep una matriu per referència (`x` és l'adreça base) i accedeix a `x[i][j]` i a `mat1[j][5]` amb índexs variables: cal usar `mul` (@nte-rv32im-instruccions-multiplicacio). Abans d'escriure cap instrucció: 1. Determineu si `subr` és uninivell o multinivell i per què. 2. Determineu si el programa principal fa crides i quines conseqüències té per a la gestió del context. Tingueu en compte que és el punt d'entrada del programa —és el primer bloc del segment `.text`—: no és cridat per cap altra subrutina i acaba amb `ecall` (@nte-punt-entrada-etiqueta). 3. Per a cada funció, identifiqueu quines dades es generen **abans** d'una crida i s'usen **després** (@sec-multinivell-pila). Assigneu-les a registres segurs. 4. Dibuixeu el bloc d'activació de cada funció amb els desplaçaments de cada element. Un cop escrit, poseu un punt de ruptura a l'inici de `subr`, executeu fins a aquest punt i anoteu els valors (en hexadecimal) dels registres `a0`, `a1`, `a2` i `ra` en cadascuna de les dues crides. Comproveu que, en acabar, `mat1[0][0]` = 1, `mat1[1][5]` = 4, `mat1[2][5]` = 3 i `mat1[4][3]` = 1. :::: --- ::: {#sol-subr-matrius} **Pas 1. `subr`: uninivell o multinivell.** `subr` és **uninivell**: no fa cap crida. No cal preservar `ra` ni cap registre segur per a valors que travessen una crida; tots els temporals van a registres `t` i el bloc d'activació queda buit. **Pas 2. El programa principal: gestió del context.** El programa principal fa dues crides a `subr`, però és el **punt d'entrada**: com que és el primer bloc del segment `.text`, no és la funció cridada per cap altra subrutina, i acaba amb `ecall` (sortida), no amb `ret`. Per tant, **no ha de preservar `ra` ni cap registre segur** per a ningú, i no li cal bloc d'activació. Sí que ha d'usar registres **segurs** (`s0`–`s11`) per a les dades pròpies que han de sobreviure a les crides: com que `subr` és responsable de restaurar-los abans de retornar (@cau-regla-registres-segurs), el seu valor es conserva a través de cada crida. **Pas 3. Registres segurs del programa principal.** Entre la primera crida a `subr` i la segona, el programa principal necessita les adreces de `mat1` i `mat4`. Com que aquests valors travessen les crides, s'assignen a registres segurs: | Dada | Registre | | :--- | :--- | | `@mat1` | `s0` | | `@mat4` | `s1` | : {.striped .hover} **Pas 4. Blocs d'activació.** Cap de les dues rutines no necessita bloc d'activació: `subr` és uninivell i sense variables locals, i el programa principal no ha de preservar cap registre. Tots dos BA són buits. ```{.s filename="s4_2_2.s"} .eqv NF1, 5 .eqv NC1, 6 .eqv NF4, 2 .eqv NC4, 3 .data .align 2 mat1: .space 120 # int mat1[5][6]: NF1*NC1*4 = 120 bytes .align 2 mat4: .word 2, 3, 1, 2, 4, 3 # int mat4[2][3] col: .word 2 .text la s0, mat1 # s0 = @mat1 (segur: travessa les crides) la s1, mat4 # s1 = @mat4 (segur: travessa les crides) # mat1[4][3] = subr(mat4, mat4[0][2], col) mv a0, s1 # arg0: @mat4 lw a1, 8(s1) # arg1: mat4[0][2] = @mat4 + 8 → 1 la t0, col lw a2, 0(t0) # arg2: col = 2 jal ra, subr # a0 = subr(@mat4, 1, 2) → retorna 1 # @mat1[4][3] = @mat1 + (4*NC1 + 3)*4 = @mat1 + 108 sw a0, 108(s0) # mat1[0][0] = subr(mat4, 1, 1) mv a0, s1 # arg0: @mat4 li a1, 1 # arg1: i = 1 li a2, 1 # arg2: j = 1 jal ra, subr # a0 = subr(@mat4, 1, 1) → retorna 1 # @mat1[0][0] = @mat1 + 0 sw a0, 0(s0) li a7, 93 li a0, 0 ecall # subr(int x[][3], int i, int j) # a0 = @x, a1 = i, a2 = j # retorna i (a0) # uninivell: a2 = j és vàlid durant tot el cos (cap crida el destrueix) subr: # t0 = x[i][j] = Mw[@x + (i*NC4 + j)*4] li t1, NC4 mul t0, a1, t1 # t0 = i * NC4 add t0, t0, a2 # t0 = i*NC4 + j slli t0, t0, 2 # t0 = (i*NC4 + j) * 4 add t0, a0, t0 # t0 = @x[i][j] lw t0, 0(t0) # t0 = x[i][j] # mat1[j][5] = x[i][j] # @mat1[j][5] = @mat1 + (j*NC1 + 5)*4 la t1, mat1 li t2, NC1 mul t3, a2, t2 # t3 = j * NC1 addi t3, t3, 5 # t3 = j*NC1 + 5 slli t3, t3, 2 # t3 = (j*NC1 + 5) * 4 add t1, t1, t3 # t1 = @mat1[j][5] sw t0, 0(t1) # mat1[j][5] = x[i][j] mv a0, a1 # return i ret ``` ::: {.callout-tip title="Comprovació pràctica"} Els quatre elements de l'enunciat són a `@mat1 + 0`, `@mat1 + 44`, `@mat1 + 68` i `@mat1 + 108`. Per localitzar-los a la vista de dades de RARS, calculeu l'adreça absoluta sumant el desplaçament a l'adreça base de `mat1` (visible al panell *Labels*). ::: ::: ## Accés seqüencial Quan un bucle recorre els elements d'una matriu i la distància en bytes entre dos elements consecutius del recorregut és constant, es pot aplicar la tècnica d'**accés seqüencial** (@sec-opt-acces-sequencial): en lloc de recalcular l'adreça a cada iteració, es manté un punter `p` que s'incrementa sumant-li l'***stride*** (@eq-stride): $$\text{stride} = @X_{i+1} - @X_i = \text{constant}$$ L'*stride* depèn del patró de recorregut. Per a una matriu d'elements de mida $T$ bytes i `NC` columnes (@sec-matrius-recorreguts): | Recorregut | *Stride* | | :--- | :--- | | Una fila (elements consecutius) | $T$ | | Una columna (salt entre files) | $\texttt{NC} \cdot T$ | : {.striped .hover} --- :::: {#exr-suma-columna} ## `s4_3_1.md` i `s4_3_1.s` Considereu la matriu i el programa C del @lst-suma-columna: ::: {#lst-suma-columna} ```{.c filename="C"} int mat[4][6] = { {0, 0, 2, 0, 0, 0}, {0, 0, 4, 0, 0, 0}, {0, 0, 6, 0, 0, 0}, {0, 0, 8, 0, 0, 0} }; int resultat; void main() { resultat = suma_col(mat); } int suma_col(int m[][6]) { int i, suma = 0; int *p; p = &m[0][2]; // inicialitzar el punter for (i = 0; i < 4; i++) { suma += *p; // accés a m usant el punter p += 6; // incrementar el punter } return suma; } ``` Matriu `mat` i programa que en suma una columna. ::: Abans d'escriure cap instrucció, responeu al fitxer `s4_3_1.md`: 1. Calculeu l'adreça de `m[i][2]` en funció de `@m` i `i`. 2. Calculeu l'*stride* per recórrer la columna 2 (distància en bytes entre `m[i][2]` i `m[i+1][2]`). 3. Expliqueu per què `p += 6` al codi C correspon, en assemblador, a sumar l'*stride* calculat a l'apartat anterior (aritmètica de punters). 4. Determineu si `suma_col` és uninivell o multinivell i assigneu cada variable a un registre. 5. Determineu si el programa principal fa alguna crida i quines conseqüències té per a la gestió del context. Recordeu que és el punt d'entrada del programa —el primer bloc de `.text`— i que acaba amb `ecall`. A continuació, traduïu el programa a RV32IM usant la tècnica d'accés seqüencial per recórrer la columna i eliminant la variable d'inducció (@sec-opt-eliminacio-induccio). Comproveu que, en acabar, la variable global `resultat` conté `20` (la suma dels elements de la columna 2: $2 + 4 + 6 + 8$). :::: --- ::: {#sol-suma-columna} **Pas 1. Adreça de `m[i][2]`.** $$@\texttt{m[i][2]} = @\texttt{m} + (i \cdot 6 + 2) \cdot 4 = @\texttt{m} + i \cdot 24 + 8$$ **Pas 2. Stride.** $$\text{stride} = @\texttt{m[i+1][2]} - @\texttt{m[i][2]} = 24 \text{ bytes}$$ **Pas 3. Aritmètica de punters.** En C, `p` és de tipus `int *`. Un increment d'una unitat (`p += 1`) equival a sumar la mida de l'element apuntat en bytes (4 bytes per a `int`). Per tant, `p += 6` equival a sumar $6 \cdot 4 = 24$ bytes en assemblador, que coincideix exactament amb l'*stride* calculat. **Pas 4. Assignació de registres de `suma_col`.** `suma_col` és **uninivell**: no fa cap crida. Tots els temporals van a registres `t`; BA buit. | Variable | Registre | | :--- | :--- | | `p` (punter, inicialitzat a `@m[0][2]`) | `t0` | | `suma` | `t1` | | sentinella (`@m[NF][2]`) | `t2` | | *stride* (24) | `t3` | | `*p` (valor llegit a cada iteració) | `t4` | : {.striped .hover} El registre `t4` es reutilitza abans del bucle com a temporal per calcular la sentinella (`NF`), i dins del bucle per contenir `*p`; no hi ha conflicte perquè els dos usos no coincideixen en el temps. Com que el recorregut elimina la variable d'inducció `i` i controla el bucle comparant el punter amb una sentinella (@sec-opt-eliminacio-induccio), la comparació es fa entre **adreces**, que són naturals: per això s'usa `bgeu`/`bltu` en lloc de `bge`/`blt` (@cau-opt3-eliminacio-induccio). **Pas 5. Gestió del context del programa principal.** El programa principal crida `suma_col`, però és el **punt d'entrada**: com que és el primer bloc del segment `.text`, no és la funció cridada per cap altra subrutina, i acaba amb `ecall`. Per tant, no ha de preservar `ra` ni cap registre segur, i no li cal bloc d'activació. A més, no hi ha cap valor propi que hagi de travessar la crida (el resultat es desa directament a `resultat` en retornar), de manera que no necessita cap registre segur. ```{.s filename="s4_3_1.s"} .eqv NF, 4 .eqv NC, 6 .data .align 2 mat: .word 0, 0, 2, 0, 0, 0 .word 0, 0, 4, 0, 0, 0 .word 0, 0, 6, 0, 0, 0 .word 0, 0, 8, 0, 0, 0 .align 2 resultat: .word 0 .text la a0, mat jal ra, suma_col # a0 = suma_col(mat) la t0, resultat sw a0, 0(t0) # resultat = a0 li a7, 93 li a0, 0 ecall # suma_col(int m[][6]) # a0 = @m # retorna suma (a0) suma_col: li t1, 0 # suma = 0 li t3, 24 # stride = NC*4 = 6*4 = 24 addi t0, a0, 8 # p = @m[0][2] = @m + (0*NC + 2)*4 = @m + 8 li t4, NF mul t2, t4, t3 add t2, t0, t2 # sentinella = @m[NF][2] = p + NF*stride for: bgeu t0, t2, fifor # salta si p >= sentinella lw t4, 0(t0) # t4 = *p = m[i][2] add t1, t1, t4 # suma += *p add t0, t0, t3 # p += stride j for fifor: mv a0, t1 # return suma ret ``` ::: {.callout-tip title="Comprovació pràctica"} Per verificar l'accés seqüencial, poseu un punt de ruptura a la instrucció `lw t4, 0(t0)` del bucle. A cada pulsació de *Run → Go* (F5), observeu com `t0` avança 24 bytes i `t4` pren successivament els valors `2`, `4`, `6` i `8`. ::: ::: {#wrn-stride-memoria-cau .callout-warning collapse="true"} ## L'*stride* i la memòria cau L'*stride* determina l'eficiència d'ús de la memòria cau. Recórrer una **fila** (amb un *stride* de 4 bytes) és eficient: elements consecutius comparteixen el mateix bloc. Recórrer una **columna** (amb un *stride* de 24 bytes, en aquest cas) salta entre files i pot provocar moltes més fallades de memòria cau (*cache misses*), especialment si `NC` és gran. A @sec-sessio-mc s'analitza quantitativament aquest efecte. ::: :::