Tema 4: Aritmètica entera i matrius

22.1 Suma i resta

Exemple 22.1: Solució: conversió a decimal en tres representacions

Codificació en binari dels dos nombres de 16 bits:

Codificació

0x0D34 = 0000 1101 0011 0100
0xBA1D = 1011 1010 0001 1101

El bit de més pes (bit 15) és 0 per a 0x0D34 i 1 per a 0xBA1D: les tres interpretacions coincideixen per al primer nombre i divergeixen per al segon.

0x0D34: com que el bit 15 és 0, el valor és el mateix en les tres representacions:

\[0 \cdot 16^3 + 13 \cdot 16^2 + 3 \cdot 16 + 4 = 3380\]

0xBA1D:

Natural: $11 \cdot 16^3 + 10 \cdot 16^2 + 1 \cdot 16 + 13 = 47\,645$.
Enter en Ca2 (Secció 1.5.1): el bit 15 val 1, per tant, el nombre és negatiu. El valor absolut s’obté fent el complement a 2: 0xBA1D → invertir bits → 0x45E2 → sumar 1 → 0x45E3 $= 17\,891$. Resultat: $-17\,891$. Comprovació: $47\,645 - 2^{16} = -17\,891$ ✓
Enter en signe-magnitud (Secció 1.5.3): bit de signe 1 (negatiu) i magnitud als 15 bits restants: 0x3A1D $= 14\,877$. Resultat: $-14\,877$.

Resum:

	a) Natural	b) Ca2	c) Signe-magnitud
`0x0D34`	$3380$	$+3380$	$+3380$
`0xBA1D`	$47\,645$	$-17\,891$	$-14\,877$

Exemple 22.2: Solució: desbordament en enters Ca2 de 8 bits

Enunciat: Problema 13.5.

El rang dels enters en Ca2 de 8 bits és $[-128, 127]$. Es produeix desbordament quan els dos operands tenen el mateix signe i el resultat en té de diferent.

a) $(-25) + (-34)$

Codificació: $-25 =$ 1110 0111, $-34 =$ 1101 1110.

Càlcul

  1110 0111   (-25)
+ 1101 1110   (-34)
-----------
1 1100 0101   (descartant el ròssec de sortida: 0xC5)

El resultat truncat a 8 bits és 1100 0101 = $-59_{10}$ en Ca2. Els dos operands són negatius i el resultat també és negatiu: no hi ha desbordament. El resultat és correcte: $-25 + (-34) = -59$.

b) $(-25) - (-34) = (-25) + 34$

Codificació: $-25 =$ 1110 0111. El subtrahend, $-34 =$ 1101 1110, es nega complementant-lo i sumant-hi 1 (Secció 1.6.2): 0010 0001 + 1 = 0010 0010 ($+34$).

Càlcul

  1110 0111   (-25)
+ 0010 0010   (+34)
-----------
1 0000 1001   (descartant el ròssec de sortida: 0x09)

Resultat: 0000 1001 = $+9_{10}$. Els operands tenen signes oposats: no hi ha desbordament. Correcte: $-25 + 34 = +9$.

c) $(+127) - (-20) = (+127) + 20$

Codificació: $+127 =$ 0111 1111. El subtrahend, $-20 =$ 1110 1100, es nega: 0001 0011 + 1 = 0001 0100 ($+20$).

Càlcul

  0111 1111   (+127)
+ 0001 0100   (+20)
-----------
  1001 0011   (0x93)

Resultat: 1001 0011 = $-109_{10}$ en Ca2. Tots dos operands eren positius, però el resultat és negatiu: hi ha desbordament. El resultat correcte seria $+147$, que no és representable amb 8 bits en Ca2.

d) $(-128) - (-20) = (-128) + 20$

Codificació: $-128 =$ 1000 0000. El subtrahend negat és, com a c), $+20 =$ 0001 0100.

Càlcul

  1000 0000   (-128)
+ 0001 0100   (+20)
-----------
  1001 0100   (0x94)

Resultat: 1001 0100 = $-108_{10}$ en Ca2. Els operands tenien signes oposats: no hi ha desbordament. Correcte: $-128 + 20 = -108$.

Exemple 22.3: Solució: detecció del ròssec sense salts

Enunciat: Problema 13.6.

En sumar dos naturals de 32 bits, el resultat es trunca mòdul $2^{32}$. Si hi ha ròssec (carry, $c = 1$), el valor retornat és $S = A + B - 2^{32}$ i, com que $B < 2^{32}$, es compleix $S < A$ (i, simètricament, $S < B$). Si no n’hi ha, $S = A + B \geq A$. Per tant:

\[c = 1 \iff S <_u A\]

que és exactament la indicació de l’enunciat. La comparació sense signe es fa amb sltu (Secció 3.3.1), que deixa el resultat booleà (0 o 1) directament en un registre, sense cap salt:

RV32I

        add     t0, t1, t2      # t0 = t1 + t2  (truncat a 32 bits)
        sltu    t3, t0, t1      # t3 = 1 si t0 < t1 (sense signe): hi ha ròssec

Dues instruccions en total. Comparar el resultat amb qualsevol dels dos sumands és equivalent; s’ha triat t1.

Exemple 22.4: Solució: detecció de desbordament d’enters sense salts

Enunciat: Problema 13.7.

Les variables t1 i t2 contenen els sumands; el resultat ha d’anar a t0 i l’indicador de desbordament a t3 (1 si hi ha desbordament, 0 altrament), sense cap instrucció de salt.

La condició de desbordament en la suma de dos enters és: els operands tenen el mateix signe i el resultat té signe diferent (Equació 4.2):

\[v = \overline{(A_{31} \oplus B_{31})} \land (A_{31} \oplus S_{31})\]

RV32I

        add     t0, t1, t2      # t0 = t1 + t2  (resultat truncat a 32 bits)
        xor     t3, t1, t2      # t1 XOR t2: bit 31 = 0 si mateix signe
        not     t3, t3          # NOT(t1 XOR t2): bit 31 = 1 si mateix signe
        xor     t4, t1, t0      # t1 XOR resultat: bit 31 = 1 si signes diferents
        and     t3, t3, t4      # condició de desbordament als 32 bits
        srli    t3, t3, 31      # desplaça el bit 31 a la posició 0
                                # t3 = 1 si desbordament, 0 altrament

Anàlisi pas a pas:

xor t3, t1, t2: el bit 31 és 0 si t1 i t2 tenen el mateix signe, 1 si en tenen de diferent.
not t3, t3: el bit 31 passa a ser 1 si els operands tenien el mateix signe.
xor t4, t1, t0: el bit 31 és 1 si el signe del resultat és diferent del de t1.
and t3, t3, t4: el bit 31 és 1 si i només si es compleixen les dues condicions simultàniament: mateix signe als operands i signe diferent al resultat.
srli t3, t3, 31: posa el bit de condició a la posició 0.

El programa no conté cap instrucció de salt: totes les operacions són aritmètiques o lògiques de cost $\mathcal{O}(1)$.

22.2 Multiplicació

Exemple 22.5: Solució: seguiment del circuit multiplicador seqüencial

Enunciat: Problema 13.10.

El circuit treballa amb naturals. Per a operands de 6 bits, els registres P i MD tenen 12 bits i MR en té 6. A cada iteració:

Si MR[0] == 1: P = P + MD.
MD = MD << 1.
MR = MR >> 1.

Convenció de la taula: cada fila mostra l’estat final de la iteració; les columnes MR[0] i Acció indiquen el que s’ha executat en aquella iteració (decidit amb el valor de MR[0] abans del desplaçament); la fila inicial porta «—».

a) $x =$ 101000 ($40_{10}$), $y =$ 010011 ($19_{10}$). Resultat esperat: $760_{10}$.

Iter.	P (12 bits)	MD (12 bits)	MR (6 bits)	MR[0]	Acció
inicial	`000000 000000`	`000000 101000`	`010011`	—	—
1	`000000 101000`	`000001 010000`	`001001`	1	suma
2	`000001 111000`	`000010 100000`	`000100`	1	suma
3	`000001 111000`	`000101 000000`	`000010`	0	no suma
4	`000001 111000`	`001010 000000`	`000001`	0	no suma
5	`001011 111000`	`010100 000000`	`000000`	1	suma
6	`001011 111000`	`101000 000000`	`000000`	0	no suma

Resultat: $P =$ 001011 111000$_2 = 760_{10}$ ✓

b) $x =$ 110110 ($54_{10}$), $y =$ 000100 ($4_{10}$). Resultat esperat: $216_{10}$.

Iter.	P (12 bits)	MD (12 bits)	MR (6 bits)	MR[0]	Acció
inicial	`000000 000000`	`000000 110110`	`000100`	—	—
1	`000000 000000`	`000001 101100`	`000010`	0	no suma
2	`000000 000000`	`000011 011000`	`000001`	0	no suma
3	`000011 011000`	`000110 110000`	`000000`	1	suma
4	`000011 011000`	`001101 100000`	`000000`	0	no suma
5	`000011 011000`	`011011 000000`	`000000`	0	no suma
6	`000011 011000`	`110110 000000`	`000000`	0	no suma

Resultat: $P =$ 000011 011000$_2 = 216_{10}$ ✓

Exemple 22.6: Solució: coherència d’operands de mul i div

Enunciat: Problema 13.13.

a) mul t3, t1, t2 amb resultat baix 0xFFFFFFFA i t1 = 0x00000002

mul calcula els 32 bits de menys pes del producte, és a dir, el producte mòdul $2^{32}$ (RISC-V 4.2). Cal trobar un t2 tal que:

\[2 \cdot \texttt{t2} \equiv \texttt{0xFFFFFFFA} \pmod{2^{32}}\]

Com que el factor $2$ i el mòdul ($2^{32}$) no són coprimers, la solució no és única: n’hi ha exactament dues, separades per $2^{31}$:

t2 = 0xFFFFFFFD: interpretant els valors com a enters, $2 \times (-3) = -6 =$ 0xFFFFFFFA ✓
t2 = 0x7FFFFFFD: interpretant-los com a naturals, $2 \times 2\,147\,483\,645 = 4\,294\,967\,290 =$ 0xFFFFFFFA ✓

Totes dues són coherents amb l’enunciat: els 32 bits de menys pes del producte són idèntics tant si els operands s’interpreten com a enters com si s’interpreten com a naturals — per això hi ha una única instrucció mul, mentre que per a la part alta cal distingir la interpretació amb mulh/mulhu/mulhsu (Secció 4.3.4 i Aprofundiment 4.7).

b) div t3, t1, t2 amb t1 = 0x00000005 i t2 = 0xFFFFFFFE

$\texttt{t2} =$ 0xFFFFFFFE $= -2$. La divisió entera trunca cap a zero (Essencial 4.3):

\[q = \operatorname{trunc}\!\left(\frac{5}{-2}\right) = \operatorname{trunc}(-2{,}5) = -2 \qquad \Rightarrow \qquad \texttt{t3} = \texttt{0xFFFFFFFE}\]

El residu té el signe del dividend i satisfà la identitat $x = y \cdot q + r$:

\[r = 5 - (-2) \times (-2) = 5 - 4 = +1\]

c) Casos de desbordament en la divisió entera

Un únic cas: $-2^{31} \div (-1)$, el resultat matemàtic del qual ($+2^{31}$) no és representable en Ca2 de 32 bits. RISC-V no genera cap excepció: div retorna $-2^{31}$ i rem retorna $0$ (Secció 4.4.3.1). La divisió per zero no és un cas de desbordament, sinó un cas especial amb resultat definit (div → $-1$, rem → dividend).

22.3 Matrius

Nota: les solucions deixen les expressions aritmètiques als operands (NC*4, mat + 3*NC*4, mat + (3*NC + 11)*4) per fer visible l’invariant de cada càlcul d’adreces, tal com s’admet a la teoria i als exàmens (EC 2.3).

Exemple 22.7: Solució: càlcul d’adreces en una matriu

Enunciat: Problema 13.14.

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

L’adreça de mat[i][j] és $@\texttt{mat} + (i \cdot \texttt{NC} + j) \cdot 4$.

a) mat[3][11] — fila i columna constants: tot és invariant.

RV32I

        la      a0, mat + (3*NC + 11)*4

b) mat[i][11] — fila variable, columna constant.

RV32IM

        la      a0, mat + 11*4      # @mat + 11*4 (invariant)
        li      t2, NC*4            # NC*4 (invariant)
        mul     t3, t0, t2          # i*NC*4
        add     a0, a0, t3          # @mat + i*NC*4 + 11*4

c) mat[3][j] — fila constant, columna variable.

RV32I

        la      a0, mat + 3*NC*4    # @mat + 3*NC*4 (invariant)
        slli    t2, t1, 2           # j*4
        add     a0, a0, t2          # @mat + 3*NC*4 + j*4

d) mat[i][j] — fila i columna variables.

RV32IM

        la      a0, mat             # @mat (invariant)
        li      t2, NC              # NC (invariant)
        mul     t3, t0, t2          # i*NC
        add     t3, t3, t1          # i*NC + j
        slli    t3, t3, 2           # (i*NC + j)*4
        add     a0, a0, t3          # @mat + (i*NC + j)*4

e) mat[i+5][j-1]

Equivalent a mat[i'][j'] amb i' = i+5 i j' = j-1. Incorporant les constants als invariants:

RV32IM

        la      a0, mat + (5*NC - 1)*4   # @mat + (5*NC - 1)*4 (invariant)
        li      t2, NC                    # NC (invariant)
        mul     t3, t0, t2               # i*NC
        add     t3, t3, t1               # i*NC + j
        slli    t3, t3, 2                # (i*NC + j)*4
        add     a0, a0, t3               # @mat + (i*NC + j)*4 + (5*NC-1)*4

f) mat[i*10+4][6]

La fila és i*10+4, la columna és la constant 6. La fila ja conté una multiplicació per 10 que no és potència de 2; les dues multiplicacions es fusionen en una: l’invariant 10*NC*4 permet resoldre-ho amb un únic mul.

RV32IM

        la      a0, mat + 4*NC*4 + 6*4  # @mat + (4*NC + 6)*4 (invariant)
        li      t2, 10*NC*4              # 10*NC*4 (invariant)
        mul     t3, t0, t2              # i*10*NC*4
        add     a0, a0, t3              # @mat + (i*10*NC + 4*NC + 6)*4

Exemple 22.8: Solució: elements veïns de la diagonal amb un sol mul

Enunciat: Problema 13.16.

Adreces dels dos elements segons l’Equació 4.3 (amb NC = N i $T = 4$), reagrupant els termes:

\[@\texttt{M[i][i+1]} = @\texttt{M} + (i \cdot N + i + 1) \cdot 4 = @\texttt{M} + 1 \cdot 4 + i \cdot (N+1) \cdot 4\]

\[@\texttt{M[i+1][i]} = @\texttt{M} + ((i+1) \cdot N + i) \cdot 4 = @\texttt{M} + N \cdot 4 + i \cdot (N+1) \cdot 4\]

Les dues adreces comparteixen el terme variable $i \cdot (N+1) \cdot 4$: amb un únic mul n’hi ha prou. La part restant de cada adreça és un invariant que s’integra a la la corresponent:

RV32IM

        # t0 = i, t1 = suma
        li      t4, (N+1)*4
        mul     t4, t0, t4          # d = i*(N+1)*4  (comú a les dues adreces)
        la      t2, M + 1*4         # invariant: @M[0][1]
        add     t2, t2, t4          # @M[i][i+1]
        lw      t2, 0(t2)           # M[i][i+1]
        la      t3, M + N*4         # invariant: @M[1][0]
        add     t3, t3, t4          # @M[i+1][i]
        lw      t3, 0(t3)           # M[i+1][i]
        sub     t2, t2, t3          # M[i][i+1] - M[i+1][i]
        add     t1, t1, t2          # suma += M[i][i+1] - M[i+1][i]

Deu instruccions i una sola multiplicació. La traducció directa (calcular cada adreça per separat amb l’Equació 4.3) necessitaria dues multiplicacions i més instruccions.

Exemple 22.9: Solució: func i main amb accés seqüencial

Enunciat: Problema 13.20.

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) Traducció de func amb accés seqüencial a veci

func és uninivell. El paràmetre veci arriba per a0 (adreça base del vector). j s’assigna a t0.

L’stride del recorregut per fila és 4 bytes (mida d’un int). El bucle es controla amb el punter; la variable j es manté, perquè se’n necessita el valor (veci[j] = j).

RV32I

func:
        # a0 = @veci
        mv      t1, a0              # t1 = p = @veci[0]
        addi    t2, a0, 4*4         # t2 = sentinella = @veci[4]
        li      t0, 0               # j = 0
        bgeu    t1, t2, fibucle1    # comprovació inicial (longitud 4 > 0: mai no salta)
bucle1:
        sw      t0, 0(t1)           # veci[j] = j
        addi    t1, t1, 4           # p += stride (4 bytes)
        addi    t0, t0, 1           # j++
        bltu    t1, t2, bucle1      # salta si p < sentinella
fibucle1:
        ret

b) Traducció de main amb accés seqüencial a mati

main és multinivell (crida func). Com que p i fi han de sobreviure a la crida i func (apartat a) utilitza t0–t2, cal desar-los en registres segurs (s0, s1) en lloc de t0/t1: p → s0, fi → s1. Cal desar ra, s0 i s1 al bloc d’activació.

RV32I

main:
        addi    sp, sp, -12
        sw      ra, 8(sp)
        sw      s1, 4(sp)
        sw      s0, 0(sp)

        la      s0, mati            # s0 = p = @mati[0][0]  (segur: sobreviu a la crida)
        addi    s1, s0, 5*4*4       # s1 = fi = @mati[5][0]
        bgeu    s0, s1, fibucle2    # comprovació inicial (5 > 0: mai no salta)
bucle2:
        mv      a0, s0              # a0 = p
        jal     ra, func
        addi    s0, s0, 4*4         # p += 4  (4 ints = 16 bytes)
        bltu    s0, s1, bucle2
fibucle2:
        lw      s0, 0(sp)
        lw      s1, 4(sp)
        lw      ra, 8(sp)
        addi    sp, sp, 12
        ret

22.4 Accés seqüencial

Nota: com a la secció anterior, les solucions deixen les expressions aritmètiques als operands (N*4, (N+1)*4, 3*(N-1)*4, i també les directives .eqv) per fer visible l’stride de cada recorregut, tal com s’admet a la teoria i als exàmens (EC 2.3).

Exemple 22.10: Solució: recorreguts per fila, columna i diagonal

Enunciat: Problema 13.21.

void func(int A[N][N]) {
    int i, j, suma = 0;  // i a t0, j a t1, suma a t2
    ...
}

A arriba per a0. N és una constant. Es demana accés seqüencial: les variables d’índex desapareixen de la traducció (el control es fa amb el punter i la sentinella), tret de l’apartat d, on i es conserva com a comptador. suma ocupa t2.

a) Suma de la fila 3: for (i = 0; i < N; i++) suma += A[3][i]

L’stride del recorregut per fila és 4 bytes.

L’adreça del primer element és @A[3][0] = @A + 3*N*4.

RV32I

        # a0 = @A, t2 = suma (inicialitzada prèviament a 0)
        li      t3, 3*N*4
        add     t3, a0, t3          # t3 = p = @A[3][0]
        li      t4, N*4
        add     t4, t3, t4          # t4 = sentinella = @A[3][N]
        bgeu    t3, t4, fibucle     # comprovació inicial
bucle:
        lw      t5, 0(t3)           # A[3][i]
        add     t2, t2, t5          # suma += A[3][i]
        addi    t3, t3, 4           # p += stride (4 bytes)
        bltu    t3, t4, bucle
fibucle:

b) Suma de la columna 4: for (i = 0; i < N; i++) suma += A[i][4]

L’stride del recorregut per columna és N*4 bytes.

L’adreça del primer element és @A[0][4] = @A + 4*4.

La sentinella és @A[N][4] = @A[0][4] + N*(N*4). Com que N és una constant, el desplaçament N*N*4 també ho és, i va directament a l’operand de li (EC 2.3): no cal mul.

RV32I

        # a0 = @A, t2 = suma (inicialitzada prèviament a 0)
        addi    t3, a0, 4*4         # t3 = p = @A[0][4]
        li      t5, N*4             # stride = N*4
        li      t4, N*N*4           # N²*4
        add     t4, t3, t4          # t4 = sentinella = @A[N][4]
        bgeu    t3, t4, fibucle     # comprovació inicial
bucle:
        lw      t6, 0(t3)           # A[i][4]
        add     t2, t2, t6          # suma += A[i][4]
        add     t3, t3, t5          # p += stride (N*4 bytes)
        bltu    t3, t4, bucle
fibucle:

c) Suma de la diagonal principal: for (i = 0; i < N; i++) suma += A[i][i]

D’un element A[i][i] al següent A[i+1][i+1] hi ha $N + 1$ elements de distància: l’stride és (N+1)*4 bytes (fila «diagonal principal» de la taula de strides de Secció 4.6.4).

El primer element és @A[0][0] = @A, i la sentinella, @A + N*((N+1)*4): com a l’apartat b, el desplaçament és constant i va a l’operand de li.

RV32I

        # a0 = @A, t2 = suma (inicialitzada prèviament a 0)
        mv      t3, a0              # t3 = p = @A[0][0]
        li      t5, (N+1)*4         # stride = (N+1)*4
        li      t4, N*(N+1)*4       # N * (N+1)*4
        add     t4, t3, t4          # t4 = sentinella
        bgeu    t3, t4, fibucle     # comprovació inicial
bucle:
        lw      t6, 0(t3)           # A[i][i]
        add     t2, t2, t6          # suma += A[i][i]
        add     t3, t3, t5          # p += stride ((N+1)*4 bytes)
        bltu    t3, t4, bucle
fibucle:

d) Diagonal secundària saltant de 3 en 3: for (i = 0; i < N; i += 3) suma += A[i][N-1-i]

Entre dos elements accedits consecutivament, A[i][N-1-i] i A[i+3][N-1-(i+3)], la distància en elements és $3N - 3 = 3(N-1)$: l’stride és constant, 3*(N-1)*4 bytes, i l’accés seqüencial és aplicable al càlcul d’adreces.

Ara bé, el nombre d’iteracions és $\lceil N/3 \rceil$ i l’adreça de la sentinella no té una expressió senzilla. En aquest cas és més net conservar i com a comptador del bucle (la variable d’inducció sobreviu per al control) i avançar el punter només per a l’accés a A:

RV32I

        # a0 = @A, t0 = i, t2 = suma (inicialitzada prèviament a 0)
        li      t0, 0               # i = 0
        li      t3, (N-1)*4
        add     t3, a0, t3          # t3 = p = @A[0][N-1]
        li      t5, 3*(N-1)*4       # stride = 3*(N-1)*4
        li      t4, N               # invariant
        bge     t0, t4, fibucle     # comprovació inicial
bucle:
        lw      t6, 0(t3)           # A[i][N-1-i]
        add     t2, t2, t6          # suma += A[i][N-1-i]
        add     t3, t3, t5          # p += stride
        addi    t0, t0, 3           # i += 3
        blt     t0, t4, bucle
fibucle:

Contrast entre els recorreguts per fila i per columna (apartats a i b): el recorregut per fila (apartat a) té stride 4, el recorregut per columna (apartat b) té stride N*4. Per a valors grans de N, el recorregut per columna genera moltes fallades de memòria cau, ja que cada accés aterra en una línia de memòria cau diferent. El recorregut per fila aprofita molt millor la localitat espacial (aquests conceptes s’estudien a Capítol 7).

Exemple 22.11: Solució: accessos mixtos a matriu i vector

Enunciat: Problema 13.23.

a) vector[i] = z[4][j]

Els paràmetres arriben per a0 (i) i a1 (j). La fila de z[4][j] és constant: l’invariant @z[4][0] = @z + 4*3*4 s’integra a la la (com a Exemple 4.11) i només cal escalar j. L’adreça de vector[i] s’obté escalant i:

RV32I

        la      t0, z + 4*3*4       # invariant: @z[4][0]
        slli    t1, a1, 2           # j*4
        add     t0, t0, t1          # @z[4][j]
        lw      t0, 0(t0)           # z[4][j]
        la      t1, vector          # invariant: @vector
        slli    t2, a0, 2           # i*4
        add     t1, t1, t2          # @vector[i]
        sw      t0, 0(t1)           # vector[i] = z[4][j]

b) Constants del recorregut seqüencial

El bucle accedeix sempre a vector[2] (posició fixa) i recorre la columna 2 de z (int z[5][3]):

offset_vector: distància de @vector a @vector[2] → 2*4 = 8.
offset_z: distància de @z al primer element del recorregut, z[0][2] → 2*4 = 8.
stride: d’un element z[k][2] al següent, z[k+1][2], hi ha una fila sencera (3 int) → 3*4 = 12.
max_dist: la sentinella t6 s’assoleix (beq) després de les 5 iteracions → 5 vegades l’stride → 5*3*4 = 60.

RV32I

.eqv    offset_vector, 2*4     # 8
.eqv    offset_z,      2*4     # 8
.eqv    max_dist,      5*3*4   # 60
.eqv    stride,        3*4     # 12

Exemple 22.12: Solució: vector de short — traducció i inicialització

Enunciat: Problema 13.25.

a) Traducció a C del fragment

Els paràmetres arriben per a0 (@p1) i a1 (p2). El fragment calcula t2 = p2 + 3, l’escala per la mida d’un short ($T = 2$; per això slli t2, t2, 1), el suma a la base @p1 i hi escriu un zero de 16 bits (sh):

p1[p2 + 3] = 0;

b) Inicialització de p1 amb accés seqüencial

Sentències que falten (i a t0, p a t1):

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

Al fragment d’assemblador, els dos buits del cos del bucle són l’escriptura i l’avanç del punter. L’stride és $T = 2$ bytes (mida d’un short): p++ es tradueix per addi t1, t1, 2, i l’escriptura de 16 bits, per sh:

RV32I

        mv      t1, a0              # p = p1  (prèvia al fragment mostrat)
        li      t0, 0
        li      t2, 100
bucle:
        bge     t0, t2, fibucle
        sh      zero, 0(t1)         # *p = 0
        addi    t1, t1, 2           # p++  (2 bytes)
        addi    t0, t0, 1
        j       bucle
fibucle:

Nota: la inicialització p = p1 (mv t1, a0) no apareix al fragment de l’enunciat, que comença a li t0, 0; s’ha inclòs aquí per completesa.

Exemple 22.13: Solució: optimització #2 — avaluació de la condició al final

Enunciat: Problema 13.28.

Versió inicial:

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:

a) Cost de la versió inicial

10 instruccions per iteració: les pseudoinstruccions es compten per les instruccions reals, i la en són dues, auipc i addi. Cost per iteració (model de costos: lw = 4, salt pres = 2, salt no pres = 1, resta = 1):

Instrucció	Cost
`li t1, N`	1
`bge` (no pres, $N$ vegades)	1
`la t2, v` (`auipc` + `addi`)	2
`slli t3`	1
`add t2`	1
`lw t3`	4
`add t4`	1
`addi t0`	1
`j bucle` (pres)	2
Total per iteració	14

Inicialització: li t0, 0 = 1 cicle.

Última comprovació ($i = N$): li t1, N (1) + bge pres (2) = 3 cicles.

Total: $1 + 14N + 3 = 14N + 4$ cicles.

b) Versió optimitzada (condició al final)

Es pot fer la comprovació inicial una sola vegada (si N > 0 sempre es compleix, es pot ometre si es pot garantir). Per ser fidel a la semàntica del while original:

RV32I

        li      t0, 0
        li      t1, N
        la      t2, v               # extracció d'invariants fora del bucle
        bge     t0, t1, fibucle     # comprovació inicial: salta si N <= 0
bucle:
        slli    t3, t0, 2
        add     t5, t2, t3
        lw      t3, 0(t5)
        add     t4, t4, t3
        addi    t0, t0, 1
        blt     t0, t1, bucle       # salta si i < N
fibucle:

S’han extret li t1, N i la t2, v com a invariants fora del bucle (extracció d’invariants, Secció 2.8.5.1, prerequisit de tota optimització).

Instruccions per iteració:

Instrucció	Cost
`slli t3`	1
`add t5`	1
`lw t3`	4
`add t4`	1
`addi t0`	1
`blt` pres ($N-1$ vegades) / no pres (última)	2 / 1
Total per iteració (menys la darrera)	10

Inicialització: li t0 (1) + li t1 (1) + la t2 (2) + bge no pres (1) = 5 cicles.

Última iteració: blt no pres (1) → cost = $10 - 2 + 1 = 9$ cicles.

Total: $5 + 10(N-1) + 9 = 10N + 4$ cicles.

c) Reducció percentual per a $N = 100$

Versió inicial: $14 \times 100 + 4 = 1404$ cicles.

Versió optimitzada: $10 \times 100 + 4 = 1004$ cicles.

\[\text{Reducció} = \frac{1404 - 1004}{1404} \times 100 \approx \mathbf{28{,}5\ \%}\]

Exemple 22.14: Solució: optimització #3 — eliminació de la variable d’inducció

Enunciat: Problema 13.29.

int v[N], w[N];
// for (i = 0; i < N; i++) w[i] = v[i] * 2;

a) Versió sense cap optimització (usant i explícitament, condició a l’inici)

RV32I

        li      t0, 0               # i = 0
        li      t1, N               # N (invariant)
        la      t2, v               # @v (invariant)
        la      t3, w               # @w (invariant)
bucle:
        bge     t0, t1, fibucle     # [ctrl]
        slli    t4, t0, 2           # i*4
        add     t5, t2, t4          # @v[i]
        lw      t5, 0(t5)           # v[i]
        slli    t5, t5, 1           # v[i] * 2
        add     t6, t3, t4          # @w[i]
        sw      t5, 0(t6)           # w[i] = v[i] * 2
        addi    t0, t0, 1           # i++
        j       bucle
fibucle:

9 instruccions per iteració: bge, slli, add, lw, slli, add, sw, addi i j. Amb el model de costos de Problema 13.28 (memòria = 4 cicles, salt pres = 2, salt no pres = 1, resta = 1), 16 cicles.

b) Eliminació de la variable d’inducció (punters directes), mantenint la condició a l’inici

Es mantenen dos punters pv i pw que avancen en paral·lel amb stride 4, controlats amb la sentinella de pv. La condició es continua avaluant a l’inici de cada iteració (amb el salt incondicional j corresponent), sense aplicar encara l’optimització #2.

RV32I

        la      t0, v               # t0 = pv = @v[0]
        la      t1, w               # t1 = pw = @w[0]
        li      t2, N*4
        add     t2, t0, t2          # t2 = sentinella = @v[N]
bucle:
        bgeu    t0, t2, fibucle     # [ctrl]
        lw      t3, 0(t0)           # *pv = v[i]
        slli    t3, t3, 1           # v[i] * 2
        sw      t3, 0(t1)           # *pw = v[i] * 2
        addi    t0, t0, 4           # pv++
        addi    t1, t1, 4           # pw++
        j       bucle
fibucle:

7 instruccions per iteració: bgeu, lw, slli, sw, dues addi i j. Amb el mateix model de costos, 14 cicles.

c) Combinació amb l’avaluació de la condició al final

Partint de b), s’aplica l’optimització #2: la comprovació es fa una única vegada abans d’entrar al bucle (cas de zero iteracions) i el salt incondicional j se substitueix pel salt condicional bltu al final:

RV32I

        la      t0, v               # t0 = pv = @v[0]
        la      t1, w               # t1 = pw = @w[0]
        li      t2, N*4
        add     t2, t0, t2          # t2 = sentinella = @v[N]
        bgeu    t0, t2, fibucle     # comprovació inicial
bucle:
        lw      t3, 0(t0)           # *pv = v[i]
        slli    t3, t3, 1           # v[i] * 2
        sw      t3, 0(t1)           # *pw = v[i] * 2
        addi    t0, t0, 4           # pv++
        addi    t1, t1, 4           # pw++
        bltu    t0, t2, bucle
fibucle:

El cos del bucle conté:

Instrucció	Nombre
`lw`	1
`slli`	1
`sw`	1
`addi` (pv++)	1
`addi` (pw++)	1
`bltu` (control)	1
Total	6

Amb el mateix model de costos, 13 cicles per iteració (12 a la darrera, on bltu no és pres).

22.5 Divisió

Exemple 22.15: Solució: algorisme del divisor seqüencial amb restauració

Enunciat: Problema 13.30.

El circuit (Secció 4.4.2) prova de restar el divisor alineat a cada posició de pes, de la més significativa a la menys significativa. Paper dels registres, per a $n = 32$:

R ($2n$ bits): comença amb el dividend $x$ a la part baixa i zeros a la part alta; en acabar, la part baixa conté el residu.
D ($2n$ bits): comença amb el divisor $y$ a la part alta (equival a $y \cdot 2^n$) i es desplaça una posició a la dreta a cada iteració: a la iteració $i$-èsima queda alineat amb el pes $2^{n-i}$.
Q ($n$ bits): acumula els bits del quocient, del més significatiu al menys significatiu.

Algorisme iteratiu complet:

Pseudocodi: divisió amb restauració

// Inicialització
R[n-1:0] = x;  R[2n-1:n] = 0
D[2n-1:n] = y;  D[n-1:0] = 0
Q = 0

per i = 1 fins a n:
    D = D >> 1
    R = R − D
    si R[2n-1] == 0:        // resultat no negatiu: el divisor "hi cap"
        Q = (Q << 1) | 1
    sino:                   // resultat negatiu: restaurar
        R = R + D
        Q = Q << 1

q = Q           // quocient
r = R[n-1:0]    // residu

A cada iteració es fa la resta de prova R − D: si el resultat no és negatiu (bit $R_{2n-1}$ a 0), el divisor desplaçat «hi cap» i s’anota un 1 al quocient; si és negatiu, es restaura el valor de R sumant-hi D de nou, i s’anota un 0. Després de les $n$ iteracions, Q conté el quocient i la part baixa de R, el residu (Algorisme 4.2; per a un seguiment numèric complet, Exemple 4.7 i Solució 22.16).

Exemple 22.16: Solució: seguiment del circuit divisor seqüencial amb restauració

Enunciat: Problema 13.31.

El circuit treballa amb naturals. Per a operands de 6 bits, els registres R i D tenen 12 bits i Q en té 6. L’algorisme amb restauració a cada iteració:

D = D >> 1.
R = R - D.
Si R[11] == 0 (resultat no negatiu): Q = (Q << 1) | 1.
Altrament (resultat negatiu): R = R + D (restauració); Q = Q << 1.

Convenció de la taula: la columna «R − D» mostra el valor intermedi de la resta (abans de decidir si cal restaurar); la columna «R (final)» mostra l’estat ja restaurat si ha calgut; la fila inicial porta «—».

a) $x =$ 101000 ($40_{10}$), $y =$ 010011 ($19_{10}$). Resultat esperat: $q = 2$, $r = 2$.

Iter.	D (12 bits)	R − D	Signe	Acció	R (final)	Q
inicial	`010011 000000`	—	—	—	`000000 101000`	`000000`
1	`001001 100000`	`110111 001000`	neg.	restaura; `Q<<1`	`000000 101000`	`000000`
2	`000100 110000`	`111011 111000`	neg.	restaura; `Q<<1`	`000000 101000`	`000000`
3	`000010 011000`	`111110 010000`	neg.	restaura; `Q<<1`	`000000 101000`	`000000`
4	`000001 001100`	`111111 011100`	neg.	restaura; `Q<<1`	`000000 101000`	`000000`
5	`000000 100110`	`000000 000010`	pos.	`Q = (Q<<1)\\|1`	`000000 000010`	`000001`
6	`000000 010011`	`111111 101111`	neg.	restaura; `Q<<1`	`000000 000010`	`000010`

Quocient: $Q = 000010_2 = 2_{10}$, residu: $R[5:0] = 000010_2 = 2_{10}$ ✓

Verificació: $19 \times 2 + 2 = 40$ ✓

b) $x =$ 010101 ($21_{10}$), $y =$ 100100 ($36_{10}$). Resultat esperat: $q = 0$, $r = 21$.

Com que $x < y$, el quocient és 0 i el residu és $x$ en totes les iteracions: el divisor desplaçat sempre és més gran que el dividend parcial i cal restaurar en cada pas.

Iter.	D (12 bits)	R − D	Signe	Acció	R (final)	Q
inicial	`100100 000000`	—	—	—	`000000 010101`	`000000`
1	`010010 000000`	`101110 010101`	neg.	restaura; `Q<<1`	`000000 010101`	`000000`
2	`001001 000000`	`110111 010101`	neg.	restaura; `Q<<1`	`000000 010101`	`000000`
3	`000100 100000`	`111011 110101`	neg.	restaura; `Q<<1`	`000000 010101`	`000000`
4	`000010 010000`	`111110 000101`	neg.	restaura; `Q<<1`	`000000 010101`	`000000`
5	`000001 001000`	`111111 001101`	neg.	restaura; `Q<<1`	`000000 010101`	`000000`
6	`000000 100100`	`111111 110001`	neg.	restaura; `Q<<1`	`000000 010101`	`000000`

Quocient: $Q = 000000_2 = 0_{10}$, residu: $R[5:0] = 010101_2 = 21_{10}$ ✓

Exemple 22.17: Solució: divisió per restauració en programari

Enunciat: Problema 13.32.

El circuit (Algorisme 4.2) treballa amb registres R i D de $2n = 64$ bits, que no caben en un registre d’RV32I. En lloc de simular-los amb parells de registres, s’usa una formulació equivalent: mantenir el divisor fix i desplaçar R a l’esquerra (desplaçar D a la dreta respecte de R equival a desplaçar R a l’esquerra respecte del divisor), injectant a cada pas el bit següent del dividend. Així tots els valors caben en registres de 32 bits. A més, en lloc de restar i restaurar, és més senzill comparar abans de restar (bltu), que és equivalent: només es fa la resta quan el resultat no seria negatiu.

Registres: t3 = dividend $x$ (es va desplaçant; al final es reutilitza per al residu, com demana l’enunciat), t1 = divisor $y$, t2 = quocient (Q), t4 = residu parcial (R), t5 = comptador, t6 = bit extret.

RV32I

        li      t2, 0               # Q = 0
        li      t4, 0               # R = 0
        li      t5, 32              # 32 iteracions (una per bit)
bucle:
        slli    t4, t4, 1           # R = R << 1
        srli    t6, t3, 31          # bit més significatiu de X
        or      t4, t4, t6          # R = (R << 1) | X[31]
        slli    t3, t3, 1           # X = X << 1 (consumeix el bit)
        slli    t2, t2, 1           # Q = Q << 1
        bltu    t4, t1, seguent     # si R < y: bit de quocient = 0
        sub     t4, t4, t1          # R = R − y
        ori     t2, t2, 1           # Q = (Q << 1) | 1
seguent:
        addi    t5, t5, -1
        bnez    t5, bucle
        mv      t3, t4              # residu a t3

El bucle s’executa exactament 32 vegades: el nombre d’iteracions és conegut i positiu, de manera que no cal comprovació inicial i el salt condicional va al final (Secció 4.6.2). En acabar, t2 conté el quocient i t3 el residu.

--- number-sections: true language: crossref-exr-title: "Problema" crossref-exr-prefix: "Problema" --- # {{< var tema4 >}} {#sec-tema-enters-matrius-solucions} ## Suma i resta ::: {#sol-t4-sr-conversio .callout-tip} ## Solució: conversió a decimal en tres representacions **Enunciat**: @exr-t4-sr-conversio. Codificació en binari dels dos nombres de 16 bits: ```{.default filename="Codificació"} 0x0D34 = 0000 1101 0011 0100 0xBA1D = 1011 1010 0001 1101 ``` El bit de més pes (bit 15) és `0` per a `0x0D34` i `1` per a `0xBA1D`: les tres interpretacions coincideixen per al primer nombre i divergeixen per al segon. **`0x0D34`**: com que el bit 15 és `0`, el valor és el mateix en les tres representacions: $$0 \cdot 16^3 + 13 \cdot 16^2 + 3 \cdot 16 + 4 = 3380$$ **`0xBA1D`**: a) Natural: $11 \cdot 16^3 + 10 \cdot 16^2 + 1 \cdot 16 + 13 = 47\,645$. b) Enter en Ca2 (@sec-enters-en-ca2): el bit 15 val `1`, per tant, el nombre és negatiu. El valor absolut s'obté fent el complement a 2: `0xBA1D` → invertir bits → `0x45E2` → sumar 1 → `0x45E3` $= 17\,891$. Resultat: $-17\,891$. Comprovació: $47\,645 - 2^{16} = -17\,891$ ✓ c) Enter en signe-magnitud (@sec-enters-signe-magnitud): bit de signe `1` (negatiu) i magnitud als 15 bits restants: `0x3A1D` $= 14\,877$. Resultat: $-14\,877$. Resum: | | a) Natural | b) Ca2 | c) Signe-magnitud | | :---: | :---: | :---: | :---: | | `0x0D34` | $3380$ | $+3380$ | $+3380$ | | `0xBA1D` | $47\,645$ | $-17\,891$ | $-14\,877$ | ::: ::: {#sol-t4-sr-overflow-enters-8bits .callout-tip} ## Solució: desbordament en enters Ca2 de 8 bits **Enunciat**: @exr-t4-sr-overflow-enters-8bits. El rang dels enters en Ca2 de 8 bits és $[-128, 127]$. Es produeix desbordament quan els dos operands tenen el mateix signe i el resultat en té de diferent. **a) $(-25) + (-34)$** Codificació: $-25 =$ `1110 0111`, $-34 =$ `1101 1110`. ```{.default filename="Càlcul"} 1110 0111 (-25) + 1101 1110 (-34) ----------- 1 1100 0101 (descartant el ròssec de sortida: 0xC5) ``` El resultat truncat a 8 bits és `1100 0101` = $-59_{10}$ en Ca2. Els dos operands són negatius i el resultat també és negatiu: **no hi ha desbordament**. El resultat és correcte: $-25 + (-34) = -59$. **b) $(-25) - (-34) = (-25) + 34$** Codificació: $-25 =$ `1110 0111`. El subtrahend, $-34 =$ `1101 1110`, es nega complementant-lo i sumant-hi 1 (@sec-inversio-signe): `0010 0001` + 1 = `0010 0010` ($+34$). ```{.default filename="Càlcul"} 1110 0111 (-25) + 0010 0010 (+34) ----------- 1 0000 1001 (descartant el ròssec de sortida: 0x09) ``` Resultat: `0000 1001` = $+9_{10}$. Els operands tenen signes oposats: **no hi ha desbordament**. Correcte: $-25 + 34 = +9$. **c) $(+127) - (-20) = (+127) + 20$** Codificació: $+127 =$ `0111 1111`. El subtrahend, $-20 =$ `1110 1100`, es nega: `0001 0011` + 1 = `0001 0100` ($+20$). ```{.default filename="Càlcul"} 0111 1111 (+127) + 0001 0100 (+20) ----------- 1001 0011 (0x93) ``` Resultat: `1001 0011` = $-109_{10}$ en Ca2. Tots dos operands eren positius, però el resultat és negatiu: **hi ha desbordament**. El resultat correcte seria $+147$, que no és representable amb 8 bits en Ca2. **d) $(-128) - (-20) = (-128) + 20$** Codificació: $-128 =$ `1000 0000`. El subtrahend negat és, com a c), $+20 =$ `0001 0100`. ```{.default filename="Càlcul"} 1000 0000 (-128) + 0001 0100 (+20) ----------- 1001 0100 (0x94) ``` Resultat: `1001 0100` = $-108_{10}$ en Ca2. Els operands tenien signes oposats: **no hi ha desbordament**. Correcte: $-128 + 20 = -108$. ::: ::: {#sol-t4-sr-overflow-deteccio-natural .callout-tip} ## Solució: detecció del ròssec sense salts **Enunciat**: @exr-t4-sr-overflow-deteccio-natural. En sumar dos naturals de 32 bits, el resultat es trunca mòdul $2^{32}$. Si hi ha ròssec (*carry*, $c = 1$), el valor retornat és $S = A + B - 2^{32}$ i, com que $B < 2^{32}$, es compleix $S < A$ (i, simètricament, $S < B$). Si no n'hi ha, $S = A + B \geq A$. Per tant: $$c = 1 \iff S <_u A$$ que és exactament la indicació de l'enunciat. La comparació sense signe es fa amb `sltu` (@sec-instruccions-comparacio-slt), que deixa el resultat booleà (0 o 1) directament en un registre, sense cap salt: ```{.s filename="RV32I"} add t0, t1, t2 # t0 = t1 + t2 (truncat a 32 bits) sltu t3, t0, t1 # t3 = 1 si t0 < t1 (sense signe): hi ha ròssec ``` Dues instruccions en total. Comparar el resultat amb qualsevol dels dos sumands és equivalent; s'ha triat `t1`. ::: ::: {#sol-t4-sr-overflow-deteccio-enter .callout-tip} ## Solució: detecció de desbordament d'enters sense salts **Enunciat**: @exr-t4-sr-overflow-deteccio-enter. Les variables `t1` i `t2` contenen els sumands; el resultat ha d'anar a `t0` i l'indicador de desbordament a `t3` (1 si hi ha desbordament, 0 altrament), sense cap instrucció de salt. La condició de desbordament en la suma de dos enters és: els operands **tenen el mateix signe** i el resultat **té signe diferent** (@eq-sobreeiximent-software): $$v = \overline{(A_{31} \oplus B_{31})} \land (A_{31} \oplus S_{31})$$ ```{.s filename="RV32I"} add t0, t1, t2 # t0 = t1 + t2 (resultat truncat a 32 bits) xor t3, t1, t2 # t1 XOR t2: bit 31 = 0 si mateix signe not t3, t3 # NOT(t1 XOR t2): bit 31 = 1 si mateix signe xor t4, t1, t0 # t1 XOR resultat: bit 31 = 1 si signes diferents and t3, t3, t4 # condició de desbordament als 32 bits srli t3, t3, 31 # desplaça el bit 31 a la posició 0 # t3 = 1 si desbordament, 0 altrament ``` **Anàlisi pas a pas**: - `xor t3, t1, t2`: el bit 31 és `0` si `t1` i `t2` tenen el **mateix signe**, `1` si en tenen de diferent. - `not t3, t3`: el bit 31 passa a ser `1` si els operands tenien el **mateix signe**. - `xor t4, t1, t0`: el bit 31 és `1` si el **signe del resultat és diferent** del de `t1`. - `and t3, t3, t4`: el bit 31 és `1` si i **només si** es compleixen les dues condicions simultàniament: mateix signe als operands i signe diferent al resultat. - `srli t3, t3, 31`: posa el bit de condició a la posició 0. El programa no conté cap instrucció de salt: totes les operacions són aritmètiques o lògiques de cost $\mathcal{O}(1)$. ::: ## Multiplicació ::: {#sol-t4-mul-passos .callout-tip} ## Solució: seguiment del circuit multiplicador seqüencial **Enunciat**: @exr-t4-mul-passos. El circuit treballa amb naturals. Per a operands de 6 bits, els registres P i MD tenen 12 bits i MR en té 6. A cada iteració: 1. Si `MR[0] == 1`: `P = P + MD`. 2. `MD = MD << 1`. 3. `MR = MR >> 1`. *Convenció de la taula*: cada fila mostra l'estat **final** de la iteració; les columnes MR[0] i Acció indiquen el que s'ha **executat en aquella iteració** (decidit amb el valor de `MR[0]` **abans** del desplaçament); la fila inicial porta «—». **a) $x =$ `101000` ($40_{10}$), $y =$ `010011` ($19_{10}$). Resultat esperat: $760_{10}$.** | Iter. | P (12 bits) | MD (12 bits) | MR (6 bits) | MR[0] | Acció | | :---: | :---: | :---: | :---: | :---: | :--- | | inicial | `000000 000000` | `000000 101000` | `010011` | — | — | | 1 | `000000 101000` | `000001 010000` | `001001` | 1 | suma | | 2 | `000001 111000` | `000010 100000` | `000100` | 1 | suma | | 3 | `000001 111000` | `000101 000000` | `000010` | 0 | no suma | | 4 | `000001 111000` | `001010 000000` | `000001` | 0 | no suma | | 5 | `001011 111000` | `010100 000000` | `000000` | 1 | suma | | 6 | `001011 111000` | `101000 000000` | `000000` | 0 | no suma | Resultat: $P =$ `001011 111000`$_2 = 760_{10}$ ✓ **b) $x =$ `110110` ($54_{10}$), $y =$ `000100` ($4_{10}$). Resultat esperat: $216_{10}$.** | Iter. | P (12 bits) | MD (12 bits) | MR (6 bits) | MR[0] | Acció | | :---: | :---: | :---: | :---: | :---: | :--- | | inicial | `000000 000000` | `000000 110110` | `000100` | — | — | | 1 | `000000 000000` | `000001 101100` | `000010` | 0 | no suma | | 2 | `000000 000000` | `000011 011000` | `000001` | 0 | no suma | | 3 | `000011 011000` | `000110 110000` | `000000` | 1 | suma | | 4 | `000011 011000` | `001101 100000` | `000000` | 0 | no suma | | 5 | `000011 011000` | `011011 000000` | `000000` | 0 | no suma | | 6 | `000011 011000` | `110110 000000` | `000000` | 0 | no suma | Resultat: $P =$ `000011 011000`$_2 = 216_{10}$ ✓ ::: ::: {#sol-t4-mul-instruccions .callout-tip} ## Solució: coherència d'operands de `mul` i `div` **Enunciat**: @exr-t4-mul-instruccions. **a) `mul t3, t1, t2` amb resultat baix `0xFFFFFFFA` i `t1 = 0x00000002`** `mul` calcula els 32 bits de menys pes del producte, és a dir, el producte **mòdul $2^{32}$** (@nte-rv32im-instruccions-multiplicacio). Cal trobar un `t2` tal que: $$2 \cdot \texttt{t2} \equiv \texttt{0xFFFFFFFA} \pmod{2^{32}}$$ Com que el factor $2$ i el mòdul ($2^{32}$) no són coprimers, la solució **no és única**: n'hi ha exactament dues, separades per $2^{31}$: - `t2 = 0xFFFFFFFD`: interpretant els valors com a enters, $2 \times (-3) = -6 =$ `0xFFFFFFFA` ✓ - `t2 = 0x7FFFFFFD`: interpretant-los com a naturals, $2 \times 2\,147\,483\,645 = 4\,294\,967\,290 =$ `0xFFFFFFFA` ✓ Totes dues són coherents amb l'enunciat: els 32 bits de menys pes del producte són idèntics tant si els operands s'interpreten com a enters com si s'interpreten com a naturals — per això hi ha una única instrucció `mul`, mentre que per a la part alta cal distingir la interpretació amb `mulh`/`mulhu`/`mulhsu` (@sec-sobreeiximent-en-la-multiplicacio i @wrn-mul-modul-2n). **b) `div t3, t1, t2` amb `t1 = 0x00000005` i `t2 = 0xFFFFFFFE`** $\texttt{t2} =$ `0xFFFFFFFE` $= -2$. La divisió entera trunca cap a zero (@cau-divisio-enters-semantica): $$q = \operatorname{trunc}\!\left(\frac{5}{-2}\right) = \operatorname{trunc}(-2{,}5) = -2 \qquad \Rightarrow \qquad \texttt{t3} = \texttt{0xFFFFFFFE}$$ El residu té el signe del dividend i satisfà la identitat $x = y \cdot q + r$: $$r = 5 - (-2) \times (-2) = 5 - 4 = +1$$ **c) Casos de desbordament en la divisió entera** Un únic cas: $-2^{31} \div (-1)$, el resultat matemàtic del qual ($+2^{31}$) no és representable en Ca2 de 32 bits. RISC-V no genera cap excepció: `div` retorna $-2^{31}$ i `rem` retorna $0$ (@sec-casos-especials-divisio). La divisió per zero **no** és un cas de desbordament, sinó un cas especial amb resultat definit (`div` → $-1$, `rem` → dividend). ::: ## Matrius **Nota**: les solucions deixen les expressions aritmètiques als operands (`NC*4`, `mat + 3*NC*4`, `mat + (3*NC + 11)*4`) per fer visible l'invariant de cada càlcul d'adreces, tal com s'admet a la teoria i als exàmens (@imp-ec-operands-expressions). ::: {#sol-t4-matrius-adreces .callout-tip} ## Solució: càlcul d'adreces en una matriu **Enunciat**: @exr-t4-matrius-adreces. ```{.c filename="C"} int mat[NF][NC]; int f() { int i, j; // i a t0, j a t1 ... } ``` L'adreça de `mat[i][j]` és $@\texttt{mat} + (i \cdot \texttt{NC} + j) \cdot 4$. **a) `mat[3][11]`** — fila i columna constants: tot és invariant. ```{.s filename="RV32I"} la a0, mat + (3*NC + 11)*4 ``` **b) `mat[i][11]`** — fila variable, columna constant. ```{.s filename="RV32IM"} la a0, mat + 11*4 # @mat + 11*4 (invariant) li t2, NC*4 # NC*4 (invariant) mul t3, t0, t2 # i*NC*4 add a0, a0, t3 # @mat + i*NC*4 + 11*4 ``` **c) `mat[3][j]`** — fila constant, columna variable. ```{.s filename="RV32I"} la a0, mat + 3*NC*4 # @mat + 3*NC*4 (invariant) slli t2, t1, 2 # j*4 add a0, a0, t2 # @mat + 3*NC*4 + j*4 ``` **d) `mat[i][j]`** — fila i columna variables. ```{.s filename="RV32IM"} la a0, mat # @mat (invariant) li t2, NC # NC (invariant) mul t3, t0, t2 # i*NC add t3, t3, t1 # i*NC + j slli t3, t3, 2 # (i*NC + j)*4 add a0, a0, t3 # @mat + (i*NC + j)*4 ``` **e) `mat[i+5][j-1]`** Equivalent a `mat[i'][j']` amb `i' = i+5` i `j' = j-1`. Incorporant les constants als invariants: ```{.s filename="RV32IM"} la a0, mat + (5*NC - 1)*4 # @mat + (5*NC - 1)*4 (invariant) li t2, NC # NC (invariant) mul t3, t0, t2 # i*NC add t3, t3, t1 # i*NC + j slli t3, t3, 2 # (i*NC + j)*4 add a0, a0, t3 # @mat + (i*NC + j)*4 + (5*NC-1)*4 ``` **f) `mat[i*10+4][6]`** La fila és `i*10+4`, la columna és la constant `6`. La fila ja conté una multiplicació per 10 que no és potència de 2; les dues multiplicacions es fusionen en una: l'invariant `10*NC*4` permet resoldre-ho amb un únic `mul`. ```{.s filename="RV32IM"} la a0, mat + 4*NC*4 + 6*4 # @mat + (4*NC + 6)*4 (invariant) li t2, 10*NC*4 # 10*NC*4 (invariant) mul t3, t0, t2 # i*10*NC*4 add a0, a0, t3 # @mat + (i*10*NC + 4*NC + 6)*4 ``` ::: ::: {#sol-t4-matrius-diagonal .callout-tip} ## Solució: elements veïns de la diagonal amb un sol `mul` **Enunciat**: @exr-t4-matrius-diagonal. Adreces dels dos elements segons l'@eq-acces-aleatori-matriu (amb `NC = N` i $T = 4$), reagrupant els termes: $$@\texttt{M[i][i+1]} = @\texttt{M} + (i \cdot N + i + 1) \cdot 4 = @\texttt{M} + 1 \cdot 4 + i \cdot (N+1) \cdot 4$$ $$@\texttt{M[i+1][i]} = @\texttt{M} + ((i+1) \cdot N + i) \cdot 4 = @\texttt{M} + N \cdot 4 + i \cdot (N+1) \cdot 4$$ Les dues adreces comparteixen el terme variable $i \cdot (N+1) \cdot 4$: amb **un únic `mul`** n'hi ha prou. La part restant de cada adreça és un invariant que s'integra a la `la` corresponent: ```{.s filename="RV32IM"} # t0 = i, t1 = suma li t4, (N+1)*4 mul t4, t0, t4 # d = i*(N+1)*4 (comú a les dues adreces) la t2, M + 1*4 # invariant: @M[0][1] add t2, t2, t4 # @M[i][i+1] lw t2, 0(t2) # M[i][i+1] la t3, M + N*4 # invariant: @M[1][0] add t3, t3, t4 # @M[i+1][i] lw t3, 0(t3) # M[i+1][i] sub t2, t2, t3 # M[i][i+1] - M[i+1][i] add t1, t1, t2 # suma += M[i][i+1] - M[i+1][i] ``` Deu instruccions i una sola multiplicació. La traducció directa (calcular cada adreça per separat amb l'@eq-acces-aleatori-matriu) necessitaria dues multiplicacions i més instruccions. ::: ::: {#sol-t4-matrius-func-veci .callout-tip} ## Solució: `func` i `main` amb accés seqüencial **Enunciat**: @exr-t4-matrius-func-veci. ```{.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) Traducció de `func` amb accés seqüencial a `veci`** `func` és **uninivell**. El paràmetre `veci` arriba per `a0` (adreça base del vector). `j` s'assigna a `t0`. L'*stride* del recorregut per fila és 4 bytes (mida d'un `int`). El bucle es controla amb el punter; la variable `j` es manté, perquè se'n necessita el valor (`veci[j] = j`). ```{.s filename="RV32I"} func: # a0 = @veci mv t1, a0 # t1 = p = @veci[0] addi t2, a0, 4*4 # t2 = sentinella = @veci[4] li t0, 0 # j = 0 bgeu t1, t2, fibucle1 # comprovació inicial (longitud 4 > 0: mai no salta) bucle1: sw t0, 0(t1) # veci[j] = j addi t1, t1, 4 # p += stride (4 bytes) addi t0, t0, 1 # j++ bltu t1, t2, bucle1 # salta si p < sentinella fibucle1: ret ``` **b) Traducció de `main` amb accés seqüencial a `mati`** `main` és **multinivell** (crida `func`). Com que `p` i `fi` han de sobreviure a la crida i `func` (apartat a) utilitza `t0`–`t2`, cal desar-los en **registres segurs** (`s0`, `s1`) en lloc de `t0`/`t1`: `p` → `s0`, `fi` → `s1`. Cal desar `ra`, `s0` i `s1` al bloc d'activació. ```{.s filename="RV32I"} main: addi sp, sp, -12 sw ra, 8(sp) sw s1, 4(sp) sw s0, 0(sp) la s0, mati # s0 = p = @mati[0][0] (segur: sobreviu a la crida) addi s1, s0, 5*4*4 # s1 = fi = @mati[5][0] bgeu s0, s1, fibucle2 # comprovació inicial (5 > 0: mai no salta) bucle2: mv a0, s0 # a0 = p jal ra, func addi s0, s0, 4*4 # p += 4 (4 ints = 16 bytes) bltu s0, s1, bucle2 fibucle2: lw s0, 0(sp) lw s1, 4(sp) lw ra, 8(sp) addi sp, sp, 12 ret ``` ::: ## Accés seqüencial **Nota**: com a la secció anterior, les solucions deixen les expressions aritmètiques als operands (`N*4`, `(N+1)*4`, `3*(N-1)*4`, i també les directives `.eqv`) per fer visible l'*stride* de cada recorregut, tal com s'admet a la teoria i als exàmens (@imp-ec-operands-expressions). ::: {#sol-t4-seq-bucles .callout-tip} ## Solució: recorreguts per fila, columna i diagonal **Enunciat**: @exr-t4-seq-bucles. ```{.c filename="C"} void func(int A[N][N]) { int i, j, suma = 0; // i a t0, j a t1, suma a t2 ... } ``` `A` arriba per `a0`. `N` és una constant. Es demana accés seqüencial: les variables d'índex desapareixen de la traducció (el control es fa amb el punter i la sentinella), tret de l'apartat d, on `i` es conserva com a comptador. `suma` ocupa `t2`. **a) Suma de la fila 3: `for (i = 0; i < N; i++) suma += A[3][i]`** L'*stride* del recorregut per fila és 4 bytes. L'adreça del primer element és `@A[3][0] = @A + 3*N*4`. ```{.s filename="RV32I"} # a0 = @A, t2 = suma (inicialitzada prèviament a 0) li t3, 3*N*4 add t3, a0, t3 # t3 = p = @A[3][0] li t4, N*4 add t4, t3, t4 # t4 = sentinella = @A[3][N] bgeu t3, t4, fibucle # comprovació inicial bucle: lw t5, 0(t3) # A[3][i] add t2, t2, t5 # suma += A[3][i] addi t3, t3, 4 # p += stride (4 bytes) bltu t3, t4, bucle fibucle: ``` **b) Suma de la columna 4: `for (i = 0; i < N; i++) suma += A[i][4]`** L'*stride* del recorregut per columna és `N*4` bytes. L'adreça del primer element és `@A[0][4] = @A + 4*4`. La sentinella és `@A[N][4] = @A[0][4] + N*(N*4)`. Com que `N` és una constant, el desplaçament `N*N*4` també ho és, i va directament a l'operand de `li` (@imp-ec-operands-expressions): no cal `mul`. ```{.s filename="RV32I"} # a0 = @A, t2 = suma (inicialitzada prèviament a 0) addi t3, a0, 4*4 # t3 = p = @A[0][4] li t5, N*4 # stride = N*4 li t4, N*N*4 # N²*4 add t4, t3, t4 # t4 = sentinella = @A[N][4] bgeu t3, t4, fibucle # comprovació inicial bucle: lw t6, 0(t3) # A[i][4] add t2, t2, t6 # suma += A[i][4] add t3, t3, t5 # p += stride (N*4 bytes) bltu t3, t4, bucle fibucle: ``` **c) Suma de la diagonal principal: `for (i = 0; i < N; i++) suma += A[i][i]`** D'un element `A[i][i]` al següent `A[i+1][i+1]` hi ha $N + 1$ elements de distància: l'*stride* és `(N+1)*4` bytes (fila «diagonal principal» de la taula de *strides* de @sec-matrius-recorreguts). El primer element és `@A[0][0] = @A`, i la sentinella, `@A + N*((N+1)*4)`: com a l'apartat b, el desplaçament és constant i va a l'operand de `li`. ```{.s filename="RV32I"} # a0 = @A, t2 = suma (inicialitzada prèviament a 0) mv t3, a0 # t3 = p = @A[0][0] li t5, (N+1)*4 # stride = (N+1)*4 li t4, N*(N+1)*4 # N * (N+1)*4 add t4, t3, t4 # t4 = sentinella bgeu t3, t4, fibucle # comprovació inicial bucle: lw t6, 0(t3) # A[i][i] add t2, t2, t6 # suma += A[i][i] add t3, t3, t5 # p += stride ((N+1)*4 bytes) bltu t3, t4, bucle fibucle: ``` **d) Diagonal secundària saltant de 3 en 3: `for (i = 0; i < N; i += 3) suma += A[i][N-1-i]`** Entre dos elements accedits consecutivament, `A[i][N-1-i]` i `A[i+3][N-1-(i+3)]`, la distància en elements és $3N - 3 = 3(N-1)$: l'*stride* és constant, `3*(N-1)*4` bytes, i l'accés seqüencial és aplicable al càlcul d'adreces. Ara bé, el nombre d'iteracions és $\lceil N/3 \rceil$ i l'adreça de la sentinella no té una expressió senzilla. En aquest cas és més net **conservar `i` com a comptador** del bucle (la variable d'inducció sobreviu per al control) i avançar el punter només per a l'accés a `A`: ```{.s filename="RV32I"} # a0 = @A, t0 = i, t2 = suma (inicialitzada prèviament a 0) li t0, 0 # i = 0 li t3, (N-1)*4 add t3, a0, t3 # t3 = p = @A[0][N-1] li t5, 3*(N-1)*4 # stride = 3*(N-1)*4 li t4, N # invariant bge t0, t4, fibucle # comprovació inicial bucle: lw t6, 0(t3) # A[i][N-1-i] add t2, t2, t6 # suma += A[i][N-1-i] add t3, t3, t5 # p += stride addi t0, t0, 3 # i += 3 blt t0, t4, bucle fibucle: ``` **Contrast entre els recorreguts per fila i per columna (apartats a i b)**: el recorregut per fila (apartat a) té *stride* 4, el recorregut per columna (apartat b) té *stride* `N*4`. Per a valors grans de `N`, el recorregut per columna genera moltes fallades de memòria cau, ja que cada accés aterra en una línia de memòria cau diferent. El recorregut per fila aprofita molt millor la localitat espacial (aquests conceptes s'estudien a @sec-tema-mc). ::: ::: {#sol-t4-seq-mixed .callout-tip} ## Solució: accessos mixtos a matriu i vector **Enunciat**: @exr-t4-seq-mixed. **a) `vector[i] = z[4][j]`** Els paràmetres arriben per `a0` (`i`) i `a1` (`j`). La fila de `z[4][j]` és constant: l'invariant `@z[4][0] = @z + 4*3*4` s'integra a la `la` (com a @tip-matriu-acces-fila-cte) i només cal escalar `j`. L'adreça de `vector[i]` s'obté escalant `i`: ```{.s filename="RV32I"} la t0, z + 4*3*4 # invariant: @z[4][0] slli t1, a1, 2 # j*4 add t0, t0, t1 # @z[4][j] lw t0, 0(t0) # z[4][j] la t1, vector # invariant: @vector slli t2, a0, 2 # i*4 add t1, t1, t2 # @vector[i] sw t0, 0(t1) # vector[i] = z[4][j] ``` **b) Constants del recorregut seqüencial** El bucle accedeix sempre a `vector[2]` (posició fixa) i recorre la columna 2 de `z` (`int z[5][3]`): - `offset_vector`: distància de `@vector` a `@vector[2]` → `2*4` = 8. - `offset_z`: distància de `@z` al primer element del recorregut, `z[0][2]` → `2*4` = 8. - `stride`: d'un element `z[k][2]` al següent, `z[k+1][2]`, hi ha una fila sencera (3 `int`) → `3*4` = 12. - `max_dist`: la sentinella `t6` s'assoleix (`beq`) després de les 5 iteracions → 5 vegades l'*stride* → `5*3*4` = 60. ```{.s filename="RV32I"} .eqv offset_vector, 2*4 # 8 .eqv offset_z, 2*4 # 8 .eqv max_dist, 5*3*4 # 60 .eqv stride, 3*4 # 12 ``` ::: ::: {#sol-t4-seq-short .callout-tip} ## Solució: vector de `short` — traducció i inicialització **Enunciat**: @exr-t4-seq-short. **a) Traducció a C del fragment** Els paràmetres arriben per `a0` (`@p1`) i `a1` (`p2`). El fragment calcula `t2 = p2 + 3`, l'escala per la mida d'un `short` ($T = 2$; per això `slli t2, t2, 1`), el suma a la base `@p1` i hi escriu un zero de 16 bits (`sh`): ```{.c filename="C"} p1[p2 + 3] = 0; ``` **b) Inicialització de `p1` amb accés seqüencial** Sentències que falten (`i` a `t0`, `p` a `t1`): ```{.c filename="C"} p = p1; for (i = 0; i < 100; i++) { *p = 0; p++; } ``` Al fragment d'assemblador, els dos buits del cos del bucle són l'escriptura i l'avanç del punter. L'*stride* és $T = 2$ bytes (mida d'un `short`): `p++` es tradueix per `addi t1, t1, 2`, i l'escriptura de 16 bits, per `sh`: ```{.s filename="RV32I"} mv t1, a0 # p = p1 (prèvia al fragment mostrat) li t0, 0 li t2, 100 bucle: bge t0, t2, fibucle sh zero, 0(t1) # *p = 0 addi t1, t1, 2 # p++ (2 bytes) addi t0, t0, 1 j bucle fibucle: ``` **Nota**: la inicialització `p = p1` (`mv t1, a0`) no apareix al fragment de l'enunciat, que comença a `li t0, 0`; s'ha inclòs aquí per completesa. ::: ::: {#sol-t4-opt-condicio-final .callout-tip} ## Solució: optimització #2 — avaluació de la condició al final **Enunciat**: @exr-t4-opt-condicio-final. **Versió inicial**: ```{.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: ``` **a) Cost de la versió inicial** **10 instruccions** per iteració: les pseudoinstruccions es compten per les instruccions reals, i `la` en són dues, `auipc` i `addi`. Cost per iteració (model de costos: `lw` = 4, salt pres = 2, salt no pres = 1, resta = 1): | Instrucció | Cost | | :--- | :---: | | `li t1, N` | 1 | | `bge` (no pres, $N$ vegades) | 1 | | `la t2, v` (`auipc` + `addi`) | 2 | | `slli t3` | 1 | | `add t2` | 1 | | `lw t3` | 4 | | `add t4` | 1 | | `addi t0` | 1 | | `j bucle` (pres) | 2 | | **Total per iteració** | **14** | Inicialització: `li t0, 0` = 1 cicle. Última comprovació ($i = N$): `li t1, N` (1) + `bge` pres (2) = 3 cicles. **Total**: $1 + 14N + 3 = 14N + 4$ cicles. **b) Versió optimitzada (condició al final)** Es pot fer la comprovació inicial una sola vegada (si `N > 0` sempre es compleix, es pot ometre si es pot garantir). Per ser fidel a la semàntica del `while` original: ```{.s filename="RV32I"} li t0, 0 li t1, N la t2, v # extracció d'invariants fora del bucle bge t0, t1, fibucle # comprovació inicial: salta si N <= 0 bucle: slli t3, t0, 2 add t5, t2, t3 lw t3, 0(t5) add t4, t4, t3 addi t0, t0, 1 blt t0, t1, bucle # salta si i < N fibucle: ``` S'han extret `li t1, N` i `la t2, v` com a invariants fora del bucle (extracció d'invariants, @sec-extraccio-invariants, prerequisit de tota optimització). Instruccions per iteració: | Instrucció | Cost | | :--- | :---: | | `slli t3` | 1 | | `add t5` | 1 | | `lw t3` | 4 | | `add t4` | 1 | | `addi t0` | 1 | | `blt` pres ($N-1$ vegades) / no pres (última) | 2 / 1 | | **Total per iteració (menys la darrera)** | **10** | Inicialització: `li t0` (1) + `li t1` (1) + `la t2` (2) + `bge` no pres (1) = 5 cicles. Última iteració: `blt` no pres (1) → cost = $10 - 2 + 1 = 9$ cicles. **Total**: $5 + 10(N-1) + 9 = 10N + 4$ cicles. **c) Reducció percentual per a $N = 100$** Versió inicial: $14 \times 100 + 4 = 1404$ cicles. Versió optimitzada: $10 \times 100 + 4 = 1004$ cicles. $$\text{Reducció} = \frac{1404 - 1004}{1404} \times 100 \approx \mathbf{28{,}5\ \%}$$ ::: ::: {#sol-t4-opt-variable-induccio .callout-tip} ## Solució: optimització #3 — eliminació de la variable d'inducció **Enunciat**: @exr-t4-opt-variable-induccio. ```{.c filename="C"} int v[N], w[N]; // for (i = 0; i < N; i++) w[i] = v[i] * 2; ``` **a) Versió sense cap optimització (usant `i` explícitament, condició a l'inici)** ```{.s filename="RV32I"} li t0, 0 # i = 0 li t1, N # N (invariant) la t2, v # @v (invariant) la t3, w # @w (invariant) bucle: bge t0, t1, fibucle # [ctrl] slli t4, t0, 2 # i*4 add t5, t2, t4 # @v[i] lw t5, 0(t5) # v[i] slli t5, t5, 1 # v[i] * 2 add t6, t3, t4 # @w[i] sw t5, 0(t6) # w[i] = v[i] * 2 addi t0, t0, 1 # i++ j bucle fibucle: ``` **9 instruccions** per iteració: `bge`, `slli`, `add`, `lw`, `slli`, `add`, `sw`, `addi` i `j`. Amb el model de costos de @exr-t4-opt-condicio-final (memòria = 4 cicles, salt pres = 2, salt no pres = 1, resta = 1), 16 cicles. **b) Eliminació de la variable d'inducció (punters directes), mantenint la condició a l'inici** Es mantenen dos punters `pv` i `pw` que avancen en paral·lel amb *stride* 4, controlats amb la sentinella de `pv`. La condició es continua avaluant a l'inici de cada iteració (amb el salt incondicional `j` corresponent), sense aplicar encara l'optimització #2. ```{.s filename="RV32I"} la t0, v # t0 = pv = @v[0] la t1, w # t1 = pw = @w[0] li t2, N*4 add t2, t0, t2 # t2 = sentinella = @v[N] bucle: bgeu t0, t2, fibucle # [ctrl] lw t3, 0(t0) # *pv = v[i] slli t3, t3, 1 # v[i] * 2 sw t3, 0(t1) # *pw = v[i] * 2 addi t0, t0, 4 # pv++ addi t1, t1, 4 # pw++ j bucle fibucle: ``` **7 instruccions** per iteració: `bgeu`, `lw`, `slli`, `sw`, dues `addi` i `j`. Amb el mateix model de costos, 14 cicles. **c) Combinació amb l'avaluació de la condició al final** Partint de b), s'aplica l'optimització #2: la comprovació es fa una única vegada abans d'entrar al bucle (cas de zero iteracions) i el salt incondicional `j` se substitueix pel salt condicional `bltu` al final: ```{.s filename="RV32I"} la t0, v # t0 = pv = @v[0] la t1, w # t1 = pw = @w[0] li t2, N*4 add t2, t0, t2 # t2 = sentinella = @v[N] bgeu t0, t2, fibucle # comprovació inicial bucle: lw t3, 0(t0) # *pv = v[i] slli t3, t3, 1 # v[i] * 2 sw t3, 0(t1) # *pw = v[i] * 2 addi t0, t0, 4 # pv++ addi t1, t1, 4 # pw++ bltu t0, t2, bucle fibucle: ``` El cos del bucle conté: | Instrucció | Nombre | | :--- | :---: | | `lw` | 1 | | `slli` | 1 | | `sw` | 1 | | `addi` (pv++) | 1 | | `addi` (pw++) | 1 | | `bltu` (control) | 1 | | **Total** | **6** | Amb el mateix model de costos, 13 cicles per iteració (12 a la darrera, on `bltu` no és pres). ::: ## Divisió ::: {#sol-t4-div-algorisme .callout-tip} ## Solució: algorisme del divisor seqüencial amb restauració **Enunciat**: @exr-t4-div-algorisme. El circuit (@sec-circuit-divisio) prova de restar el divisor alineat a cada posició de pes, de la més significativa a la menys significativa. Paper dels registres, per a $n = 32$: - **R** ($2n$ bits): comença amb el dividend $x$ a la part baixa i zeros a la part alta; en acabar, la part baixa conté el residu. - **D** ($2n$ bits): comença amb el divisor $y$ a la part **alta** (equival a $y \cdot 2^n$) i es desplaça una posició a la dreta a cada iteració: a la iteració $i$-èsima queda alineat amb el pes $2^{n-i}$. - **Q** ($n$ bits): acumula els bits del quocient, del més significatiu al menys significatiu. Algorisme iteratiu complet: ```{.default filename="Pseudocodi: divisió amb restauració"} // Inicialització R[n-1:0] = x; R[2n-1:n] = 0 D[2n-1:n] = y; D[n-1:0] = 0 Q = 0 per i = 1 fins a n: D = D >> 1 R = R − D si R[2n-1] == 0: // resultat no negatiu: el divisor "hi cap" Q = (Q << 1) | 1 sino: // resultat negatiu: restaurar R = R + D Q = Q << 1 q = Q // quocient r = R[n-1:0] // residu ``` A cada iteració es fa la resta de prova R − D: si el resultat no és negatiu (bit $R_{2n-1}$ a 0), el divisor desplaçat «hi cap» i s'anota un 1 al quocient; si és negatiu, es **restaura** el valor de R sumant-hi D de nou, i s'anota un 0. Després de les $n$ iteracions, Q conté el quocient i la part baixa de R, el residu (@thm-divisio-sequencial-restauracio; per a un seguiment numèric complet, @tip-seguiment-divisio i @sol-t4-div-passos). ::: ::: {#sol-t4-div-passos .callout-tip} ## Solució: seguiment del circuit divisor seqüencial amb restauració **Enunciat**: @exr-t4-div-passos. El circuit treballa amb naturals. Per a operands de 6 bits, els registres R i D tenen 12 bits i Q en té 6. L'algorisme amb restauració a cada iteració: 1. `D = D >> 1`. 2. `R = R - D`. 3. Si `R[11] == 0` (resultat no negatiu): `Q = (Q << 1) | 1`. 4. Altrament (resultat negatiu): `R = R + D` (restauració); `Q = Q << 1`. *Convenció de la taula*: la columna «R − D» mostra el valor intermedi de la resta (abans de decidir si cal restaurar); la columna «R (final)» mostra l'estat ja restaurat si ha calgut; la fila inicial porta «—». **a) $x =$ `101000` ($40_{10}$), $y =$ `010011` ($19_{10}$). Resultat esperat: $q = 2$, $r = 2$.** | Iter. | D (12 bits) | R − D | Signe | Acció | R (final) | Q | | :---: | :---: | :---: | :---: | :--- | :---: | :---: | | inicial | `010011 000000` | — | — | — | `000000 101000` | `000000` | | 1 | `001001 100000` | `110111 001000` | neg. | restaura; `Q<<1` | `000000 101000` | `000000` | | 2 | `000100 110000` | `111011 111000` | neg. | restaura; `Q<<1` | `000000 101000` | `000000` | | 3 | `000010 011000` | `111110 010000` | neg. | restaura; `Q<<1` | `000000 101000` | `000000` | | 4 | `000001 001100` | `111111 011100` | neg. | restaura; `Q<<1` | `000000 101000` | `000000` | | 5 | `000000 100110` | `000000 000010` | pos. | `Q = (Q<<1)\|1` | `000000 000010` | `000001` | | 6 | `000000 010011` | `111111 101111` | neg. | restaura; `Q<<1` | `000000 000010` | `000010` | : {tbl-colwidths="[8,19,19,7,19,19,9]"} Quocient: $Q = 000010_2 = 2_{10}$, residu: $R[5:0] = 000010_2 = 2_{10}$ ✓ Verificació: $19 \times 2 + 2 = 40$ ✓ **b) $x =$ `010101` ($21_{10}$), $y =$ `100100` ($36_{10}$). Resultat esperat: $q = 0$, $r = 21$.** Com que $x < y$, el quocient és 0 i el residu és $x$ en totes les iteracions: el divisor desplaçat sempre és més gran que el dividend parcial i cal restaurar en cada pas. | Iter. | D (12 bits) | R − D | Signe | Acció | R (final) | Q | | :---: | :---: | :---: | :---: | :--- | :---: | :---: | | inicial | `100100 000000` | — | — | — | `000000 010101` | `000000` | | 1 | `010010 000000` | `101110 010101` | neg. | restaura; `Q<<1` | `000000 010101` | `000000` | | 2 | `001001 000000` | `110111 010101` | neg. | restaura; `Q<<1` | `000000 010101` | `000000` | | 3 | `000100 100000` | `111011 110101` | neg. | restaura; `Q<<1` | `000000 010101` | `000000` | | 4 | `000010 010000` | `111110 000101` | neg. | restaura; `Q<<1` | `000000 010101` | `000000` | | 5 | `000001 001000` | `111111 001101` | neg. | restaura; `Q<<1` | `000000 010101` | `000000` | | 6 | `000000 100100` | `111111 110001` | neg. | restaura; `Q<<1` | `000000 010101` | `000000` | : {tbl-colwidths="[11,18,18,11,13,18,11]"} Quocient: $Q = 000000_2 = 0_{10}$, residu: $R[5:0] = 010101_2 = 21_{10}$ ✓ ::: ::: {#sol-t4-div-programa .callout-tip} ## Solució: divisió per restauració en programari **Enunciat**: @exr-t4-div-programa. El circuit (@thm-divisio-sequencial-restauracio) treballa amb registres R i D de $2n = 64$ bits, que no caben en un registre d'RV32I. En lloc de simular-los amb parells de registres, s'usa una **formulació equivalent**: mantenir el divisor fix i desplaçar R a l'**esquerra** (desplaçar D a la dreta respecte de R equival a desplaçar R a l'esquerra respecte del divisor), injectant a cada pas el bit següent del dividend. Així tots els valors caben en registres de 32 bits. A més, en lloc de restar i restaurar, és més senzill **comparar abans de restar** (`bltu`), que és equivalent: només es fa la resta quan el resultat no seria negatiu. Registres: `t3` = dividend $x$ (es va desplaçant; al final es reutilitza per al residu, com demana l'enunciat), `t1` = divisor $y$, `t2` = quocient (Q), `t4` = residu parcial (R), `t5` = comptador, `t6` = bit extret. ```{.s filename="RV32I"} li t2, 0 # Q = 0 li t4, 0 # R = 0 li t5, 32 # 32 iteracions (una per bit) bucle: slli t4, t4, 1 # R = R << 1 srli t6, t3, 31 # bit més significatiu de X or t4, t4, t6 # R = (R << 1) | X[31] slli t3, t3, 1 # X = X << 1 (consumeix el bit) slli t2, t2, 1 # Q = Q << 1 bltu t4, t1, seguent # si R < y: bit de quocient = 0 sub t4, t4, t1 # R = R − y ori t2, t2, 1 # Q = (Q << 1) | 1 seguent: addi t5, t5, -1 bnez t5, bucle mv t3, t4 # residu a t3 ``` El bucle s'executa exactament 32 vegades: el nombre d'iteracions és conegut i positiu, de manera que no cal comprovació inicial i el salt condicional va al final (@sec-opt-condicio-final). En acabar, `t2` conté el quocient i `t3` el residu. :::

	a) Natural	b) Ca2	c) Signe-magnitud
`0x0D34`	\(3380\)	\(+3380\)	\(+3380\)
`0xBA1D`	\(47\,645\)	\(-17\,891\)	\(-14\,877\)