Tema 4: Aritmètica entera i matrius

13.1 Suma i resta

Problema 13.1 Convertiu a decimal els nombres 0x0D34 i 0xBA1D:

Suposant que representen naturals.
Suposant que representen enters en complement a 2.
Suposant que representen enters en signe-magnitud.

Problema 13.2 Siguin els nombres: $A =$ 0x0D34, $B =$ 0xDD17, $C =$ 0xBA1D, $D =$ 0x3617.

Quant val, en hexadecimal, la suma $A+B$ si representen naturals de 16 bits?
Ídem per a la suma $C+D$.
Quant val, en hexadecimal, la suma $A+B$ si són enters en signe-magnitud de 16 bits?
Ídem per a la suma $C+D$.

Problema 13.3 Siguin els nombres: $A =$ 0xBA7C, $B =$ 0x241A, $C =$ 0xAADF, $D =$ 0x47BE.

Quant val, en hexadecimal, la resta $A-B$ si representen naturals de 16 bits?
Ídem per a la resta $C-D$.
Quant val, en hexadecimal, la resta $A-B$ si són enters en signe-magnitud de 16 bits?
Ídem per a la resta $C-D$.

Problema 13.4 Per a les operacions següents amb naturals de 8 bits, codifiqueu els operands en binari, realitzeu l’operació i indiqueu si s’ha produït ròssec (carry) o, en el cas de la resta, préstec (borrow). Convertiu el resultat a decimal:

$200 + 50$
$25 + 34$
$254 + 3$
$128 - 20$

Problema 13.5 Per a les operacions següents amb enters en Ca2 de 8 bits, codifiqueu els operands en binari, realitzeu l’operació i indiqueu si s’ha produït desbordament (overflow). Convertiu el resultat a decimal:

$(-25) + (-34)$
$(-25) - (-34)$
$(+127) - (-20)$
$(-128) - (-20)$

Vegeu Secció 4.2.1.

Problema 13.6 Donades dues variables naturals de 32 bits emmagatzemades a t1 i t2, escriviu un fragment de codi que calculi la seva suma (t0 = t1 + t2) i determini si s’ha produït ròssec, desant 1 a t3 en cas afirmatiu i 0 altrament. El fragment no ha de contenir cap instrucció de salt.

Indicació: si es produeix ròssec, el resultat t0 és menor que qualsevol dels dos sumands.

Problema 13.7 Donades dues variables enteres de 32 bits emmagatzemades a t1 i t2, escriviu un fragment de codi que calculi la seva suma (t0 = t1 + t2) i determini si s’ha produït desbordament (overflow). El fragment no ha de contenir cap instrucció de salt.

Indicació: hi ha desbordament si i només si els dos sumands tenen el mateix signe i el resultat té signe oposat. A RISC-V, la detecció es fa combinant operacions lògiques bit a bit i desplaçaments sobre els bits de signe.

Vegeu Secció 4.2.3 i Exemple 4.1.

Problema 13.8 Donada la declaració en C:

long long x, y;

Traduïu a assemblador RISC-V les sentències següents (cada variable ocupa dos registres consecutius: part alta i part baixa):

x = x + y;
x = x - y;
if (x > y) x = 1;

13.2 Multiplicació

Vegeu Secció 4.3.

Problema 13.9 Donat el diagrama del multiplicador seqüencial de naturals de 32 bits estudiat a la teoria, que calcula el producte de 64 bits, completeu l’algorisme iteratiu que en descriu el funcionament cicle a cicle, indicant el valor inicial dels registres i les operacions de cada iteració.

Vegeu Algorisme 4.1.

Problema 13.10 Seguint el circuit multiplicador seqüencial, descriviu els passos per a la multiplicació dels naturals de 6 bits $x$ (multiplicand) i $y$ (multiplicador), calculant en cada pas el valor dels registres P, MD i MR en binari:

$x =$ 101000, $y =$ 010011.
$x =$ 110110, $y =$ 000100.

Vegeu Algorisme 4.1 i Exemple 4.3.

Problema 13.11 Seguint el mateix algorisme del circuit multiplicador, i sense usar cap instrucció de multiplicació, escriviu un fragment de codi en assemblador RISC-V que calculi el producte de dos naturals de 32 bits guardats als registres t0 i t2. El resultat de 64 bits s’ha de guardar a t3 (part baixa) i t4 (part alta).

Vegeu Algorisme 4.1.

Problema 13.12 Siguin x, y i z variables de 32 bits emmagatzemades a t1, t2 i t3. Escriviu un fragment de codi en RISC-V que calculi z = x * y i escrigui a t0 el valor 0 si el resultat és correcte o 1 si s’ha produït desbordament. El fragment no ha de fer servir cap instrucció de salt. Considereu:

unsigned int x, y, z;
int x, y, z;

Vegeu Secció 4.3.4.

Problema 13.13 Completeu el contingut que han de tenir els registres operands de les instruccions següents perquè siguin coherents després de la seva execució. Considereu cada instrucció de manera independent:

mul t3, t1, t2 — el resultat als 32 bits de menys pes és 0xFFFFFFFA; t1 = 0x00000002; calculeu el valor de t2.
div t3, t1, t2 (divisió entera, truncament cap a zero) — t1 = 0x00000005, t2 = 0xFFFFFFFE; calculeu el quocient a t3 i el residu.
En quins casos concrets pot produir-se desbordament en una divisió entera?

13.3 Matrius

Vegeu Secció 4.5.

Problema 13.14 Donades les declaracions en C, on NF i NC són constants:

int mat[NF][NC];
int f() {
    int i, j;
    ...
}

Escriviu el codi RISC-V per calcular les adreces dels elements següents, fent servir el nombre mínim d’instruccions i deixant el resultat a a0. Suposeu que i i j estan emmagatzemades a t0 i t1:

mat[3][11]
mat[i][11]
mat[3][j]
mat[i][j]
mat[i+5][j-1]
mat[i*10+4][6]

Vegeu Equació 4.3.

Problema 13.15 Traduïu a assemblador RISC-V la funció del Codi 13.1, on N és una constant:

Codi 13.1: Funció func sobre una matriu de N columnes.

void func(int mat[][N], int i, int j) {
    if (i > j)
        mat[i][j] = mat[j][i];
}

Problema 13.16 Donada la declaració de variable global (on N és una constant):

int M[N][N];

Traduïu a assemblador RISC-V el fragment de codi en C del Codi 13.2, usant el nombre mínim d’instruccions, suposant que i i suma ocupen els registres t0 i t1:

Codi 13.2: Sentència amb dos accessos a la matriu M.

suma += M[i][i+1] - M[i+1][i];

Problema 13.17 Sigui la declaració en C:

char mat[6][10];

Si el registre t0 és un punter que apunta a l’element mat[i][j], és possible modificar t0 amb una sola instrucció perquè apunti a mat[i-3][j+5]? Si la resposta és sí, escriviu-la.

Problema 13.18 Sigui la declaració de la variable global:

long long mat[10][50];

Suposant que inicialment t0 conté l’adreça de l’element mat[4][45], a quin element de la matriu apunta t0 després d’executar la instrucció del Codi 13.3?

Codi 13.3: Instrucció addi sobre t0.

RV32I

        addi    t0, t0, 1384

Problema 13.19 Donades les declaracions en C:

void f(int n) {
    int j;
    int b[8][10];
    ...
    // Aquí va la sentència incògnita
    ...
}

El fragment de codi RISC-V del Codi 13.4 correspon a la traducció de la sentència incògnita. Determineu quina és aquesta sentència i expresseu-la en C, tenint en compte que t0 conté la variable j:

Codi 13.4: Traducció de la sentència incògnita.

RV32IM

        li      t0, 0
bucle:
        li      t1, 10
        bge     t0, t1, final
        li      t1, 10
        mul     t1, t1, a0
        add     t1, t1, t0
        slli    t1, t1, 2
        add     t1, t1, sp
        sw      zero, 0(t1)
        addi    t0, t0, 1
        j       bucle
final:

Problema 13.20 Donades les declaracions en C:

int mati[5][4];

void func(int veci[4]) {
    int j;
    for (j = 0; j < 4; j++)
        veci[j] = j;
}

void main() {
    int *p = &mati[0][0];
    int *fi = &mati[5][0];
    while (p != fi) {
        func(p);
        p += 4;
    }
}

Traduïu a RISC-V la subrutina func amb accés seqüencial al vector veci, suposant que j ocupa t0.
Traduïu a RISC-V la subrutina main amb accés seqüencial a la matriu mati.

13.4 Accés seqüencial

Vegeu Secció 4.6.

Problema 13.21 Donades les declaracions en C (on N és una constant):

void func(int A[N][N]) {
    int i, j, suma = 0;
    ...
}

Traduïu a RISC-V les sentències següents usant accés seqüencial per als accessos a A, suposant que i, j i suma ocupen t0, t1 i t2:

for (i = 0; i < N; i++)
    suma += A[3][i];

for (i = 0; i < N; i++)
    suma += A[i][4];

for (i = 0; i < N; i++)
    suma += A[i][i];

for (i = 0; i < N; i += 3)
    suma += A[i][N-1-i];

Problema 13.22 Donades les declaracions en C:

#define N 100
char      vecchar[N];
int       matint[N][N];
long long matlong[N][N];

void func() {
    int i;
    ...
}

Traduïu a RISC-V les sentències següents usant accés seqüencial, suposant que i ocupa t0:

for (i = 1; i < N; i += 2)
    vecchar[i] = N - i;

for (i = 0; i < N; i++)
    matint[i][0] = 0;

i = 4;
while (matint[3][i] != 0) {
    matint[3][i]--;
    i += 3;
}

for (i = N-1; i >= 0; i--)
    matlong[i][4] = i;

Problema 13.23 Siguin les declaracions en C:

int   z[5][3];
int   vector[4];

void func(int i, int j) {
    int k;
    ...
}

Traduïu a RISC-V la sentència del Codi 13.5, que pertany a func:

Codi 13.5: Sentència de l’apartat a).

vector[i] = z[4][j];

El Codi 13.6, en assemblador RISC-V, s’ha obtingut en traduir el bucle del Codi 13.7 implementant accés seqüencial. Completeu les quatre constants inicials perquè la traducció sigui correcta:

Codi 13.6: Traducció de l’apartat b), amb les quatre constants per completar.

RV32I

.eqv    offset_vector, ?
.eqv    offset_z,      ?
.eqv    max_dist,      ?
.eqv    stride,        ?

func:
        la      t2, vector + offset_vector
        la      t3, z + offset_z
        addi    t6, t3, max_dist
for:
        beq     t3, t6, fifor
        lw      t4, 0(t2)
        lw      t5, 0(t3)
        add     t4, t4, t5
        sw      t4, 0(t2)
        addi    t3, t3, stride
        j       for
fifor:
        ret

Codi 13.7: Bucle de l’apartat b), en C.

for (k = 0; k < 5; k++)
    vector[2] += z[k][2];

Problema 13.24 Donades les declaracions en C:

#define N 10
int mat[N][N];

Traduïu a assemblador RISC-V el codi del Codi 13.8 amb accés seqüencial i un sol punter:

Codi 13.8: Bucle do-while sobre la diagonal de mat.

i = 0;
do {
    mat[i][i]   = mat[i][i+1] - mat[i+1][i];
    i += 2;
} while (i < N);

Problema 13.25 Donades les declaracions en C:

void examen(short p1[100], int p2) {
    int    i;
    short *p;
    ...
}

Traduïu a C, amb una única sentència, el fragment d’assemblador RISC-V del Codi 13.9, sabent que forma part del cos d’examen:

Codi 13.9: Fragment de l’apartat a).

RV32I

        addi    t2, a1, 3
        slli    t2, t2, 1
        add     t2, a0, t2
        sh      zero, 0(t2)

El fragment incomplet de codi C del Codi 13.10 i el de RISC-V del Codi 13.11 pertanyen al cos d’examen i inicialitzen tots els elements de p1 a zero amb accés seqüencial. Completeu les tres sentències que falten en C i les línies corresponents en assemblador, suposant que i i p es guarden a t0 i t1:

Codi 13.10: Fragment incomplet en C de l’apartat b).

p = _______ ;
for (i = 0; i < 100; i++) {
    _______ ;
    _______ ;
}

Codi 13.11: Fragment incomplet en RISC-V de l’apartat b).

RV32I

        li      t0, 0
        li      t2, 100
bucle:
        bge     t0, t2, fibucle
        ___________________
        ___________________
        addi    t0, t0, 1
        j       bucle
fibucle:

Problema 13.26 La funció func recorre la matriu matriu amb un punter. Suposeu que N i M són constants, amb $N \leq M$:

Codi 13.12: Funció func, que recorre matriu amb un punter.

int matriu[N][M];

void func() {
    int  i, *p;
    p = &matriu[0][0];
    for (i = 0; i < N; i++) {
        *p  = i;
        p   = p + M + 1;
    }
}

Enumereu els elements de la matriu que s’escriuen i indiqueu quin valor s’assigna a cada un.
Traduïu a RISC-V el bucle del Codi 13.12 usant accés seqüencial, suposant que i i p ocupen t0 i t1.

Problema 13.27 La funció fila_dispersa escriu els elements de la fila i d’una matriu dispersa, representada pels vectors A, IA i JA, a les posicions corresponents de la matriu global mat:

Codi 13.13: Funció fila_dispersa.

int mat[N][M];

void fila_dispersa(int *A, int *IA, int *JA, int i) {
    int k;
    for (k = IA[i]; k < IA[i+1]; k++)
        mat[i][JA[k]] = A[k];
}

Dels accessos a memòria que fa el bucle del Codi 13.13 (IA[i], IA[i+1], JA[k], mat[i][JA[k]], A[k]), quins es poden traduir amb accés seqüencial i quins només amb accés aleatori?
Traduïu la funció fila_dispersa usant accés seqüencial per als recorreguts que ho permetin, suposant que k es guarda a t0.

Problema 13.28 Donada la versió inicial del bucle del Codi 13.14 (on N és una constant i v és un vector global d’enters):

Codi 13.14: Versió inicial del bucle, sense optimitzar.

RV32I

        li      t0, 0
bucle:
        li      t1, N
        bge     t0, t1, fibucle
        la      t2, v
        slli    t3, t0, 2
        add     t2, t2, t3
        lw      t3, 0(t2)
        add     t4, t4, t3
        addi    t0, t0, 1
        j       bucle
fibucle:

Identifiqueu quantes instruccions s’executen per iteració i calculeu el temps total en cicles per a $N$ iteracions (useu el model de costos: memòria = 4 cicles, salt pres = 2, salt no pres = 1, resta = 1).
Apliqueu l’optimització de condició al final del bucle (do-while). Escriviu la versió optimitzada i calculeu de nou el temps total.
Quina reducció percentual del temps s’obté per a $N = 100$?

Vegeu Secció 4.6.2.

Problema 13.29 Donada la declaració (on N és una constant):

int v[N], w[N];

El bucle for (i = 0; i < N; i++) w[i] = v[i] * 2; es pot optimitzar eliminant la variable d’inducció i.

Escriviu la versió assemblador RISC-V sense cap optimització (usant i explícitament, amb la condició avaluada a l’inici del bucle).
Apliqueu l’eliminació de la variable d’inducció: useu dos punters que avancin directament i elimineu tots els càlculs d’adreça, mantenint la condició avaluada a l’inici. Escriviu la versió optimitzada.
Combineu l’eliminació de la variable d’inducció (b) amb l’avaluació de la condició al final. Quantes instruccions té el cos del bucle resultant?

Vegeu Secció 4.6.1, Secció 4.6.2 i Secció 4.6.3.

13.5 Divisió

Vegeu Secció 4.4.

Problema 13.30 Donat el diagrama del divisor seqüencial de naturals de 32 bits amb restauració estudiat a la teoria, que calcula el quocient i el residu, completeu l’algorisme iteratiu que en descriu el funcionament cicle a cicle.

Vegeu Algorisme 4.2.

Problema 13.31 Seguint el circuit divisor seqüencial amb restauració, descriviu els passos per a la divisió dels naturals de 6 bits $x$ (dividend) entre $y$ (divisor), calculant en cada pas el valor dels registres Q, D i R en binari:

$x =$ 101000, $y =$ 010011.
$x =$ 010101, $y =$ 100100.

Vegeu Algorisme 4.2 i Exemple 4.7.

Problema 13.32 Seguint el mateix algorisme del circuit divisor, i sense usar cap instrucció de multiplicació ni divisió, escriviu un fragment de codi en assemblador RISC-V que calculi el quocient i el residu de la divisió de dos naturals de 32 bits: el dividend al registre t3 i el divisor a t1. El quocient s’ha de guardar a t2 i el residu a t3.

Vegeu Algorisme 4.2.

--- number-sections: true language: crossref-exr-title: "Problema" crossref-exr-prefix: "Problema" --- # {{< var tema4 >}} {#sec-tema-enters-matrius-enunciats} ## Suma i resta *Vegeu @sec-suma-resta-enters i @sec-operacions-ca2.* ::: {#exr-t4-sr-conversio} Convertiu a decimal els nombres `0x0D34` i `0xBA1D`: a) Suposant que representen naturals. b) Suposant que representen enters en complement a 2. c) Suposant que representen enters en signe-magnitud. ::: ::: {#exr-t4-sr-suma-naturals} Siguin els nombres: $A =$ `0x0D34`, $B =$ `0xDD17`, $C =$ `0xBA1D`, $D =$ `0x3617`. a) Quant val, en hexadecimal, la suma $A+B$ si representen naturals de 16 bits? b) Ídem per a la suma $C+D$. c) Quant val, en hexadecimal, la suma $A+B$ si són enters en signe-magnitud de 16 bits? d) Ídem per a la suma $C+D$. ::: ::: {#exr-t4-sr-resta-naturals} Siguin els nombres: $A =$ `0xBA7C`, $B =$ `0x241A`, $C =$ `0xAADF`, $D =$ `0x47BE`. a) Quant val, en hexadecimal, la resta $A-B$ si representen naturals de 16 bits? b) Ídem per a la resta $C-D$. c) Quant val, en hexadecimal, la resta $A-B$ si són enters en signe-magnitud de 16 bits? d) Ídem per a la resta $C-D$. ::: ::: {#exr-t4-sr-overflow-naturals-8bits} Per a les operacions següents amb naturals de 8 bits, codifiqueu els operands en binari, realitzeu l'operació i indiqueu si s'ha produït ròssec (*carry*) o, en el cas de la resta, préstec (*borrow*). Convertiu el resultat a decimal: a) $200 + 50$ b) $25 + 34$ c) $254 + 3$ d) $128 - 20$ ::: ::: {#exr-t4-sr-overflow-enters-8bits} Per a les operacions següents amb enters en Ca2 de 8 bits, codifiqueu els operands en binari, realitzeu l'operació i indiqueu si s'ha produït desbordament (*overflow*). Convertiu el resultat a decimal: a) $(-25) + (-34)$ b) $(-25) - (-34)$ c) $(+127) - (-20)$ d) $(-128) - (-20)$ *Vegeu @sec-condicions-de-sobreeiximent.* ::: ::: {#exr-t4-sr-overflow-deteccio-natural} Donades dues variables naturals de 32 bits emmagatzemades a `t1` i `t2`, escriviu un fragment de codi que calculi la seva suma (`t0 = t1 + t2`) i determini si s'ha produït ròssec, desant 1 a `t3` en cas afirmatiu i 0 altrament. El fragment no ha de contenir cap instrucció de salt. *Indicació:* si es produeix ròssec, el resultat `t0` és menor que qualsevol dels dos sumands. ::: ::: {#exr-t4-sr-overflow-deteccio-enter} Donades dues variables enteres de 32 bits emmagatzemades a `t1` i `t2`, escriviu un fragment de codi que calculi la seva suma (`t0 = t1 + t2`) i determini si s'ha produït desbordament (*overflow*). El fragment no ha de contenir cap instrucció de salt. *Indicació:* hi ha desbordament si i només si els dos sumands tenen el mateix signe i el resultat té signe oposat. A RISC-V, la detecció es fa combinant operacions lògiques bit a bit i desplaçaments sobre els bits de signe. *Vegeu @sec-sobreeiximent-programari i @tip-sobreeiximent-programari.* ::: ::: {#exr-t4-sr-64bits} Donada la declaració en C: ```{.c filename="C"} long long x, y; ``` Traduïu a assemblador RISC-V les sentències següents (cada variable ocupa dos registres consecutius: part alta i part baixa): a) `x = x + y;` b) `x = x - y;` c) `if (x > y) x = 1;` ::: ## Multiplicació *Vegeu @sec-multiplicacio-entera.* ::: {#exr-t4-mul-algorisme} Donat el diagrama del multiplicador seqüencial de naturals de 32 bits estudiat a la teoria, que calcula el producte de 64 bits, completeu l'algorisme iteratiu que en descriu el funcionament cicle a cicle, indicant el valor inicial dels registres i les operacions de cada iteració. *Vegeu @thm-multiplicacio-sequencial.* ::: ::: {#exr-t4-mul-passos} Seguint el circuit multiplicador seqüencial, descriviu els passos per a la multiplicació dels naturals de 6 bits $x$ (multiplicand) i $y$ (multiplicador), calculant en cada pas el valor dels registres P, MD i MR en binari: a) $x =$ `101000`, $y =$ `010011`. b) $x =$ `110110`, $y =$ `000100`. *Vegeu @thm-multiplicacio-sequencial i @tip-seguiment-multiplicacio.* ::: ::: {#exr-t4-mul-programa} Seguint el mateix algorisme del circuit multiplicador, i sense usar cap instrucció de multiplicació, escriviu un fragment de codi en assemblador RISC-V que calculi el producte de dos naturals de 32 bits guardats als registres `t0` i `t2`. El resultat de 64 bits s'ha de guardar a `t3` (part baixa) i `t4` (part alta). *Vegeu @thm-multiplicacio-sequencial.* ::: ::: {#exr-t4-mul-overflow} Siguin `x`, `y` i `z` variables de 32 bits emmagatzemades a `t1`, `t2` i `t3`. Escriviu un fragment de codi en RISC-V que calculi `z = x * y` i escrigui a `t0` el valor 0 si el resultat és correcte o 1 si s'ha produït desbordament. El fragment no ha de fer servir cap instrucció de salt. Considereu: a) `unsigned int x, y, z;` b) `int x, y, z;` *Vegeu @sec-sobreeiximent-en-la-multiplicacio.* ::: ::: {#exr-t4-mul-instruccions} Completeu el contingut que han de tenir els registres operands de les instruccions següents perquè siguin coherents després de la seva execució. Considereu cada instrucció de manera independent: a) `mul t3, t1, t2` — el resultat als 32 bits de menys pes és `0xFFFFFFFA`; `t1 = 0x00000002`; calculeu el valor de `t2`. b) `div t3, t1, t2` (divisió entera, truncament cap a zero) — `t1 = 0x00000005`, `t2 = 0xFFFFFFFE`; calculeu el quocient a `t3` i el residu. c) En quins casos concrets pot produir-se desbordament en una divisió entera? ::: ## Matrius *Vegeu @sec-matrius.* ::: {#exr-t4-matrius-adreces} Donades les declaracions en C, on `NF` i `NC` són constants: ```{.c filename="C"} int mat[NF][NC]; int f() { int i, j; ... } ``` Escriviu el codi RISC-V per calcular les adreces dels elements següents, fent servir el nombre mínim d'instruccions i deixant el resultat a `a0`. Suposeu que `i` i `j` estan emmagatzemades a `t0` i `t1`: a) `mat[3][11]` b) `mat[i][11]` c) `mat[3][j]` d) `mat[i][j]` e) `mat[i+5][j-1]` f) `mat[i*10+4][6]` *Vegeu @eq-acces-aleatori-matriu.* ::: :::: {#exr-t4-matrius-funcio} Traduïu a assemblador RISC-V la funció del @lst-t4-matrius-funcio, on `N` és una constant: ::: {#lst-t4-matrius-funcio} ```{.c filename="C"} void func(int mat[][N], int i, int j) { if (i > j) mat[i][j] = mat[j][i]; } ``` Funció `func` sobre una matriu de `N` columnes. ::: :::: :::: {#exr-t4-matrius-diagonal} Donada la declaració de variable global (on `N` és una constant): ```{.c filename="C"} int M[N][N]; ``` Traduïu a assemblador RISC-V el fragment de codi en C del @lst-t4-matrius-diagonal, usant el nombre mínim d'instruccions, suposant que `i` i `suma` ocupen els registres `t0` i `t1`: ::: {#lst-t4-matrius-diagonal} ```{.c filename="C"} suma += M[i][i+1] - M[i+1][i]; ``` Sentència amb dos accessos a la matriu `M`. ::: :::: ::: {#exr-t4-matrius-punter-offset} Sigui la declaració en C: ```{.c filename="C"} char mat[6][10]; ``` Si el registre `t0` és un punter que apunta a l'element `mat[i][j]`, és possible modificar `t0` amb una sola instrucció perquè apunti a `mat[i-3][j+5]`? Si la resposta és sí, escriviu-la. ::: :::: {#exr-t4-matrius-longlong} Sigui la declaració de la variable global: ```{.c filename="C"} long long mat[10][50]; ``` Suposant que inicialment `t0` conté l'adreça de l'element `mat[4][45]`, a quin element de la matriu apunta `t0` després d'executar la instrucció del @lst-t4-matrius-longlong? ::: {#lst-t4-matrius-longlong} ```{.s filename="RV32I"} addi t0, t0, 1384 ``` Instrucció `addi` sobre `t0`. ::: :::: :::: {#exr-t4-matrius-inversa} Donades les declaracions en C: ```{.c filename="C"} void f(int n) { int j; int b[8][10]; ... // Aquí va la sentència incògnita ... } ``` El fragment de codi RISC-V del @lst-t4-matrius-inversa correspon a la traducció de la sentència incògnita. Determineu quina és aquesta sentència i expresseu-la en C, tenint en compte que `t0` conté la variable `j`: ::: {#lst-t4-matrius-inversa} ```{.s filename="RV32IM"} li t0, 0 bucle: li t1, 10 bge t0, t1, final li t1, 10 mul t1, t1, a0 add t1, t1, t0 slli t1, t1, 2 add t1, t1, sp sw zero, 0(t1) addi t0, t0, 1 j bucle final: ``` Traducció de la sentència incògnita. ::: :::: ::: {#exr-t4-matrius-func-veci} Donades les declaracions en C: ```{.c filename="C"} int mati[5][4]; void func(int veci[4]) { int j; for (j = 0; j < 4; j++) veci[j] = j; } void main() { int *p = &mati[0][0]; int *fi = &mati[5][0]; while (p != fi) { func(p); p += 4; } } ``` a) Traduïu a RISC-V la subrutina `func` amb accés seqüencial al vector `veci`, suposant que `j` ocupa `t0`. b) Traduïu a RISC-V la subrutina `main` amb accés seqüencial a la matriu `mati`. ::: ## Accés seqüencial *Vegeu @sec-optimitzacions-bucle.* ::: {#exr-t4-seq-bucles} Donades les declaracions en C (on `N` és una constant): ```{.c filename="C"} void func(int A[N][N]) { int i, j, suma = 0; ... } ``` Traduïu a RISC-V les sentències següents usant accés seqüencial per als accessos a `A`, suposant que `i`, `j` i `suma` ocupen `t0`, `t1` i `t2`: a) ```{.c filename="C"} for (i = 0; i < N; i++) suma += A[3][i]; ``` b) ```{.c filename="C"} for (i = 0; i < N; i++) suma += A[i][4]; ``` c) ```{.c filename="C"} for (i = 0; i < N; i++) suma += A[i][i]; ``` d) ```{.c filename="C"} for (i = 0; i < N; i += 3) suma += A[i][N-1-i]; ``` ::: ::: {#exr-t4-seq-char-int-long} Donades les declaracions en C: ```{.c filename="C"} #define N 100 char vecchar[N]; int matint[N][N]; long long matlong[N][N]; void func() { int i; ... } ``` Traduïu a RISC-V les sentències següents usant accés seqüencial, suposant que `i` ocupa `t0`: a) ```{.c filename="C"} for (i = 1; i < N; i += 2) vecchar[i] = N - i; ``` b) ```{.c filename="C"} for (i = 0; i < N; i++) matint[i][0] = 0; ``` c) ```{.c filename="C"} i = 4; while (matint[3][i] != 0) { matint[3][i]--; i += 3; } ``` d) ```{.c filename="C"} for (i = N-1; i >= 0; i--) matlong[i][4] = i; ``` ::: :::: {#exr-t4-seq-mixed} Siguin les declaracions en C: ```{.c filename="C"} int z[5][3]; int vector[4]; void func(int i, int j) { int k; ... } ``` a) Traduïu a RISC-V la sentència del @lst-t4-seq-mixed-a, que pertany a `func`: ::: {#lst-t4-seq-mixed-a} ```{.c filename="C"} vector[i] = z[4][j]; ``` Sentència de l'apartat a). ::: b) El @lst-t4-seq-mixed-b, en assemblador RISC-V, s'ha obtingut en traduir el bucle del @lst-t4-seq-mixed-bucle implementant accés seqüencial. Completeu les quatre constants inicials perquè la traducció sigui correcta: ::: {#lst-t4-seq-mixed-b} ```{.s filename="RV32I"} .eqv offset_vector, ? .eqv offset_z, ? .eqv max_dist, ? .eqv stride, ? func: la t2, vector + offset_vector la t3, z + offset_z addi t6, t3, max_dist for: beq t3, t6, fifor lw t4, 0(t2) lw t5, 0(t3) add t4, t4, t5 sw t4, 0(t2) addi t3, t3, stride j for fifor: ret ``` Traducció de l'apartat b), amb les quatre constants per completar. ::: ::: {#lst-t4-seq-mixed-bucle} ```{.c filename="C"} for (k = 0; k < 5; k++) vector[2] += z[k][2]; ``` Bucle de l'apartat b), en C. ::: :::: :::: {#exr-t4-seq-diagonal-do} Donades les declaracions en C: ```{.c filename="C"} #define N 10 int mat[N][N]; ``` Traduïu a assemblador RISC-V el codi del @lst-t4-seq-diagonal-do amb accés seqüencial i un sol punter: ::: {#lst-t4-seq-diagonal-do} ```{.c filename="C"} i = 0; do { mat[i][i] = mat[i][i+1] - mat[i+1][i]; i += 2; } while (i < N); ``` Bucle `do-while` sobre la diagonal de `mat`. ::: :::: :::: {#exr-t4-seq-short} Donades les declaracions en C: ```{.c filename="C"} void examen(short p1[100], int p2) { int i; short *p; ... } ``` a) Traduïu a C, amb una única sentència, el fragment d'assemblador RISC-V del @lst-t4-seq-short-a, sabent que forma part del cos d'`examen`: ::: {#lst-t4-seq-short-a} ```{.s filename="RV32I"} addi t2, a1, 3 slli t2, t2, 1 add t2, a0, t2 sh zero, 0(t2) ``` Fragment de l'apartat a). ::: b) El fragment incomplet de codi C del @lst-t4-seq-short-c i el de RISC-V del @lst-t4-seq-short-s pertanyen al cos d'`examen` i inicialitzen tots els elements de `p1` a zero amb accés seqüencial. Completeu les tres sentències que falten en C i les línies corresponents en assemblador, suposant que `i` i `p` es guarden a `t0` i `t1`: ::: {#lst-t4-seq-short-c} ```{.c filename="C"} p = _______ ; for (i = 0; i < 100; i++) { _______ ; _______ ; } ``` Fragment incomplet en C de l'apartat b). ::: ::: {#lst-t4-seq-short-s} ```{.s filename="RV32I"} li t0, 0 li t2, 100 bucle: bge t0, t2, fibucle ___________________ ___________________ addi t0, t0, 1 j bucle fibucle: ``` Fragment incomplet en RISC-V de l'apartat b). ::: :::: :::: {#exr-t4-seq-diagonal-ptr} La funció `func` recorre la matriu `matriu` amb un punter. Suposeu que `N` i `M` són constants, amb $N \leq M$: ::: {#lst-t4-seq-diagonal-ptr} ```{.c filename="C"} int matriu[N][M]; void func() { int i, *p; p = &matriu[0][0]; for (i = 0; i < N; i++) { *p = i; p = p + M + 1; } } ``` Funció `func`, que recorre `matriu` amb un punter. ::: a) Enumereu els elements de la matriu que s'escriuen i indiqueu quin valor s'assigna a cada un. b) Traduïu a RISC-V el bucle del @lst-t4-seq-diagonal-ptr usant accés seqüencial, suposant que `i` i `p` ocupen `t0` i `t1`. :::: :::: {#exr-t4-seq-dispersa} La funció `fila_dispersa` escriu els elements de la fila `i` d'una matriu dispersa, representada pels vectors `A`, `IA` i `JA`, a les posicions corresponents de la matriu global `mat`: ::: {#lst-t4-seq-dispersa} ```{.c filename="C"} int mat[N][M]; void fila_dispersa(int *A, int *IA, int *JA, int i) { int k; for (k = IA[i]; k < IA[i+1]; k++) mat[i][JA[k]] = A[k]; } ``` Funció `fila_dispersa`. ::: a) Dels accessos a memòria que fa el bucle del @lst-t4-seq-dispersa (`IA[i]`, `IA[i+1]`, `JA[k]`, `mat[i][JA[k]]`, `A[k]`), quins es poden traduir amb accés seqüencial i quins només amb accés aleatori? b) Traduïu la funció `fila_dispersa` usant accés seqüencial per als recorreguts que ho permetin, suposant que `k` es guarda a `t0`. :::: :::: {#exr-t4-opt-condicio-final} Donada la versió inicial del bucle del @lst-t4-opt-condicio-final (on `N` és una constant i `v` és un vector global d'enters): ::: {#lst-t4-opt-condicio-final} ```{.s filename="RV32I"} li t0, 0 bucle: li t1, N bge t0, t1, fibucle la t2, v slli t3, t0, 2 add t2, t2, t3 lw t3, 0(t2) add t4, t4, t3 addi t0, t0, 1 j bucle fibucle: ``` Versió inicial del bucle, sense optimitzar. ::: a) Identifiqueu quantes instruccions s'executen per iteració i calculeu el temps total en cicles per a $N$ iteracions (useu el model de costos: memòria = 4 cicles, salt pres = 2, salt no pres = 1, resta = 1). b) Apliqueu l'optimització de condició al final del bucle (`do-while`). Escriviu la versió optimitzada i calculeu de nou el temps total. c) Quina reducció percentual del temps s'obté per a $N = 100$? *Vegeu @sec-opt-condicio-final.* :::: ::: {#exr-t4-opt-variable-induccio} Donada la declaració (on `N` és una constant): ```{.c filename="C"} int v[N], w[N]; ``` El bucle `for (i = 0; i < N; i++) w[i] = v[i] * 2;` es pot optimitzar eliminant la variable d'inducció `i`. a) Escriviu la versió assemblador RISC-V **sense** cap optimització (usant `i` explícitament, amb la condició avaluada a l'inici del bucle). b) Apliqueu l'eliminació de la variable d'inducció: useu dos punters que avancin directament i elimineu tots els càlculs d'adreça, mantenint la condició avaluada a l'inici. Escriviu la versió optimitzada. c) Combineu l'eliminació de la variable d'inducció (b) amb l'avaluació de la condició al final. Quantes instruccions té el cos del bucle resultant? *Vegeu @sec-opt-acces-sequencial, @sec-opt-condicio-final i @sec-opt-eliminacio-induccio.* ::: ## Divisió *Vegeu @sec-divisio-entera.* ::: {#exr-t4-div-algorisme} Donat el diagrama del divisor seqüencial de naturals de 32 bits amb restauració estudiat a la teoria, que calcula el quocient i el residu, completeu l'algorisme iteratiu que en descriu el funcionament cicle a cicle. *Vegeu @thm-divisio-sequencial-restauracio.* ::: ::: {#exr-t4-div-passos} Seguint el circuit divisor seqüencial amb restauració, descriviu els passos per a la divisió dels naturals de 6 bits $x$ (dividend) entre $y$ (divisor), calculant en cada pas el valor dels registres Q, D i R en binari: a) $x =$ `101000`, $y =$ `010011`. b) $x =$ `010101`, $y =$ `100100`. *Vegeu @thm-divisio-sequencial-restauracio i @tip-seguiment-divisio.* ::: ::: {#exr-t4-div-programa} Seguint el mateix algorisme del circuit divisor, i sense usar cap instrucció de multiplicació ni divisió, escriviu un fragment de codi en assemblador RISC-V que calculi el quocient i el residu de la divisió de dos naturals de 32 bits: el dividend al registre `t3` i el divisor a `t1`. El quocient s'ha de guardar a `t2` i el residu a `t3`. *Vegeu @thm-divisio-sequencial-restauracio.* :::