Departament d'Arquitectura de Computadors (DAC)
Universitat Politècnica de Catalunya (UPC)

Laboratori 6: Memòria cau

Lliuraments

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

Exercici	Nom i format del fitxer
Exercici 33.1	s6_1_1.md
Exercici 33.2	s6_2_1.md
Exercici 33.3	s6_2_2.md
Exercici 33.4	s6_2_3.md
Exercici 33.5	s6_2_4.md
Exercici 33.6	s6_3_1.md
Exercici 33.7	s6_3_2.md
Exercici 33.8	s6_3_3.md
Exercici 33.9	s6_4_1.md
Exercici 33.10	s6_4_2.s
Exercici 33.11	s6_4_3.md
Exercici 33.12	s6_4_4.md
Exercici 33.13	s6_4_5.md
Exercici 33.14	s6_5_1.s

Lectura prèvia

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

Concepte	On trobar-ho
Localitat temporal i espacial	Secció 7.1.3
Organització de la memòria cau: blocs, línies, etiquetes i bit de validesa	Secció 7.2.2
Terminologia: encert, fallada, taxa d’encerts	Secció 7.2.3
Gestió d’una lectura	Secció 7.2.4
Correspondència directa: descomposició d’adreces	Secció 7.3.1
Memòria cau associativa per conjunts	Secció 7.3.2
Memòria cau completament associativa	Secció 7.3.3
Política de reemplaçament (LRU)	Secció 7.4
Política d’escriptura: gestió en cas d’encert i de fallada	Secció 7.5, Taula 7.3
Exemples de polítiques d’escriptura	Exemple 7.6, Exemple 7.7, Exemple 7.8
Model de temps simplificat	Secció 7.7.1, Essencial 7.2
Impacte de les fallades en el temps d’execució	Secció 7.7.3, Equació 7.4
Recorregut d’un vector per accés seqüencial	Exemple 2.30
L’stride i l’eficiència de la memòria cau	Secció 7.1.3

33.1 Descomposició d’adreces

En una memòria cau de correspondència directa (Secció 7.3.1), cada adreça generada pel processador es divideix en tres camps: etiqueta, índex i desplaçament (offset). El nombre de bits de cada camp depèn de la geometria de la memòria cau:

• Desplaçament: selecciona un byte dins del bloc. Si el bloc té \(N_P = 2^{n_p}\) paraules de 4 bytes, ocupa \(4 \cdot N_P = 2^{n_p+2}\) bytes i el camp de desplaçament té \(n_p + 2\) bits.
• Índex (\(n_l\) bits): identifica la línia de la memòria cau. Si la memòria cau té \(N_L = 2^{n_l}\) línies, l’índex té \(n_l\) bits.
• Etiqueta: la resta de bits de més pes.

A la teoria (Secció 7.2.2) la mida del bloc es dona directament en bytes com \(B = 2^b\); aquí, com que els programes operen amb paraules de 4 bytes, l’expressem en paraules, de manera que \(B = 4 \cdot N_P = 2^{n_p + 2}\) bytes i el desplaçament \(b = n_p + 2\). El nombre de línies \(N_L = 2^{n_l}\) és el mateix símbol en tots dos llocs.

En aquesta sessió es fa servir una geometria de referència de 32 línies amb blocs de 4 paraules (tots els exercicis tret que s’indiqui el contrari). Al Data Cache Simulator de RARS, el nombre de línies es diu Number of blocks. Les variables globals dels programes s’emmagatzemen a partir de l’adreça 0x10010000.

---

Exercici 33.1 (s6_1_1.md) Considereu una memòria cau de correspondència directa amb 32 línies amb blocs de 4 paraules.

1. Determineu el nombre de bits dels camps desplaçament, índex i etiqueta per a adreces de 32 bits. Justifiqueu cada valor.

2. El processador genera una referència de lectura a l’adreça 0x1001014C. Calculeu:

   1. El número del bloc de memòria principal al qual pertany aquesta referència.
   2. L’índex de la línia de memòria cau corresponent.
   3. L’etiqueta corresponent.

3. En el moment de la referència, la línia de memòria cau seleccionada conté el bloc de memòria principal número 0x1001034. Indiqueu si la referència és un encert o una fallada i justifiqueu-ho.

---

Solució 33.1. Apartat 1. Descomposició de bits.

El bloc té 4 paraules de 4 bytes = 16 bytes = \(2^4\) bytes → desplaçament: 4 bits.

La memòria cau té 32 línies = \(2^5\) línies → índex: 5 bits.

Etiqueta: \(32 - 4 - 5 = 23\) bits.

Camp	Bits	Posicions
Etiqueta	23	31–9
Índex	5	8–4
Desplaçament	4	3–0

Apartat 2. Anàlisi de l’adreça 0x1001014C.

En binari: 0001 0000 0000 0001 0000 0001 0100 1100

Descomposició per camps:

Camp	Bits extraïts	Valor hex
Etiqueta (bits 31–9)	0001 0000 0000 0001 0000 000	0x080080
Índex (bits 8–4)	1 0100	0x14 (20 en decimal)
Desplaçament (bits 3–0)	1100	0xC

1. Número del bloc d’MP: l’adreça 0x1001014C dividida per la mida del bloc (16 bytes) és \(\lfloor \texttt{0x1001014C} / 16 \rfloor = \texttt{0x1001014}\).
2. Índex de la línia d’MC: \(\texttt{0x1001014} \bmod 32 = 20 = \texttt{0x14}\).
3. Etiqueta: 0x080080.

Apartat 3. Encert o fallada.

La línia d’índex 0x14 conté el bloc 0x1001034 (que hi mapa correctament: \(\texttt{0x1001034} \bmod 32 = 20\)), amb etiqueta 0x080081. La referència pertany al bloc 0x1001014, que té el mateix índex 0x14 però etiqueta 0x080080. Com que les dues etiquetes no coincideixen (\(\texttt{0x080080} \neq \texttt{0x080081}\)), la referència és una fallada.

33.2 Recorregut seqüencial d’un vector

En aquesta secció s’analitza el comportament de la memòria cau durant el recorregut seqüencial d’un vector. El programa calcula la suma de tots els elements d’un vector de 100 enters:

suma_vector.c

int vector[100];

void main() {
    int i, suma = 0;
    for (i = 0; i < 100; i++)
        suma += vector[i];
}

La traducció a RV32I segueix el patró d’accés seqüencial (Exemple 2.30), mantenint un punter t2 que avança 4 bytes a cada iteració:

Codi 33.1: Suma dels elements d’un vector amb accés seqüencial.

suma_vector.s

.eqv N, 100

.data
vector: .space  400             # int vector[100]

.text

        mv      t1, zero        # suma = 0
        la      t2, vector      # t2 = @vector[0]
        li      t3, N
        slli    t3, t3, 2
        add     t3, t2, t3      # t3 = @vector[N] (sentinella)
for:
        bgeu    t2, t3, fifor   # salta si t2 >= sentinella
        lw      t4, 0(t2)       # t4 = vector[i]
        add     t1, t1, t4      # suma += vector[i]
        addi    t2, t2, 4       # t2++ (stride = 4 bytes)
        j       for
fifor:
        li      a7, 93
        li      a0, 0
        ecall

Carregueu el programa del Codi 33.1 a RARS i activeu el mòdul Tools → Data Cache Simulator. Configureu la memòria cau amb 32 línies (Number of blocks) amb blocs de 4 paraules i correspondència directa. Premeu Connect to Program abans d’executar.

---

Exercici 33.2 (s6_2_1.md) Considereu la memòria cau de correspondència directa amb 32 línies amb blocs de 4 paraules i les variables globals emmagatzemades a partir de 0x10010000.

1. Ompliu la taula següent per a les 10 primeres iteracions del bucle. Per a cada iteració, indiqueu l’adreça de vector[i], la línia de la memòria cau a què s’accedeix i si la referència és un encert (En) o una fallada (F).

Iteració	Adreça de vector[i]	Línia d’MC	En / F
1
2
3
4
5
6
7
8
9
10

2. Calculeu la taxa d’encerts que s’obté en l’execució completa del programa. Raoneu la resposta a partir del patró de fallades observat.

Verifiqueu les respostes amb el Data Cache Simulator de RARS.

---

Solució 33.2. Apartat 1.

vector[0] comença a 0x10010000. Cada element ocupa 4 bytes; el bloc té 16 bytes (4 paraules), de manera que cada bloc conté 4 elements consecutius del vector. L’índex de línia és \(\lfloor \text{adreça} / 16 \rfloor \bmod 32\).

Iteració	Adreça de vector[i]	Línia d’MC	En / F
1	0x10010000	0	F
2	0x10010004	0	En
3	0x10010008	0	En
4	0x1001000C	0	En
5	0x10010010	1	F
6	0x10010014	1	En
7	0x10010018	1	En
8	0x1001001C	1	En
9	0x10010020	2	F
10	0x10010024	2	En

Apartat 2.

El vector té 100 elements. Cada bloc d’MC conté 4 elements: la primera referència a cada grup de 4 és una fallada d’arrencada en fred (cold-start) i les tres restants són encerts. Hi ha \(\lceil 100 / 4 \rceil = 25\) blocs d’MP accedits, cadascun amb 1 fallada i 3 encerts.

\[\text{taxa d'encerts} = \frac{75}{100} = 0{,}75\]

---

Exercici 33.3 (s6_2_2.md) Considereu el mateix programa i la mateixa geometria de referència (correspondència directa, 32 línies amb blocs de 4 paraules).

1. Si dupliqueu la mida de la memòria cau doblant el nombre de línies (64 línies amb blocs de 4 paraules), la taxa d’encerts variarà? Raoneu la resposta.

2. Si dupliqueu la mida de la memòria cau doblant el nombre de paraules per bloc (32 línies amb blocs de 8 paraules), la taxa d’encerts variarà? Raoneu la resposta.

Verifiqueu les respostes canviant la geometria al Data Cache Simulator i executant el programa de nou. Reinicialitzeu la memòria cau amb Reset abans de cada execució.

---

Solució 33.3. Apartat 1. Doblar el nombre de línies (64 línies amb blocs de 4 paraules).

La mida del bloc no canvia (4 paraules = 16 bytes), de manera que cada fallada continua portant un bloc de 4 elements. El patró de fallades és idèntic: 1 fallada cada 4 accessos. La taxa d’encerts no varia: \(0{,}75\).

Apartat 2. Doblar el nombre de paraules per bloc (32 línies amb blocs de 8 paraules).

Ara cada bloc conté 8 paraules = 32 bytes = 8 elements del vector. La primera referència a cada grup de 8 és una fallada i les 7 restants són encerts. Hi ha \(\lceil 100 / 8 \rceil = 13\) blocs accedits (12 complets + 1 de parcial amb 4 elements). Fallades: 13. Encerts: \(100 - 13 = 87\).

\[\text{taxa d'encerts} = \frac{87}{100} = 0{,}87\]

La taxa millora perquè blocs més grans aprofiten millor la localitat espacial del recorregut seqüencial.

---

Exercici 33.4 (s6_2_3.md) Si el programa recorregués el vector des del darrer element fins al primer (en ordre decreixent d’índexs), la taxa d’encerts seria la mateixa o diferent respecte al recorregut en ordre creixent? Raoneu la resposta.

Modifiqueu el programa suma_vector.s per invertir l’ordre del recorregut i verifiqueu la resposta amb el Data Cache Simulator.

---

Solució 33.4. La taxa d’encerts és la mateixa: \(0{,}75\).

El patró de fallades no depèn de la direcció del recorregut, sinó de la relació entre la mida del bloc i l’stride d’accés (Secció 7.1.3). En ambdós casos, cada bloc d’MC conté 4 elements consecutius del vector: la primera referència a cada bloc és una fallada d’arrencada en fred i les tres restants són encerts, independentment de si el recorregut és creixent o decreixent.

---

Exercici 33.5 (s6_2_4.md) Considereu un sistema amb memòria cau d’instruccions i de dades separades. La memòria cau d’instruccions és ideal (taxa d’encerts = 1). La memòria cau de dades és de correspondència directa amb 32 línies amb blocs de 4 paraules i el model de temps simplificat següent:

• Temps de cicle: \(t_c = 10\ \text{ns}\).
• Temps d’accés en cas d’encert: \(t_h = 1\ \text{cicle}\).
• Temps per copiar un bloc d’MP a MC: \(t_{bloc} = 10\ \text{cicles}\).

Useu el programa suma_vector.s de Secció 33.2. Per obtenir el nombre d’instruccions executades i el nombre de fallades, useu les eines Tools → Instruction Statistics i Tools → Data Cache Simulator de RARS.

1. Calculeu \(t_p\) (penalització per fallada) per a una lectura en política d’escriptura immediata amb assignació (Secció 7.7.1).

2. Determineu el nombre d’instruccions executades (\(n_{ins}\)) i el nombre de fallades de la memòria cau de dades (\(n_{fallades}\)).

3. Calculeu el temps d’execució suposant \(\text{CPI}_{ideal} = 2\) (Equació 7.4).

4. Calculeu el temps d’execució si el sistema no tingués memòria cau de dades, sabent que el temps d’accés a la memòria principal és \(t_{MP} = 6\ \text{cicles}\) (Secció 7.1.2). Calculeu també el guany de rendiment respecte al cas sense memòria cau.

---

Solució 33.5. Apartat 1. Càlcul de \(t_p\).

Per a una lectura amb fallada en política d’escriptura immediata amb assignació (Essencial 7.2):

\[t_p = t_{bloc} + t_h = 10 + 1 = 11\ \text{cicles}\]

Apartat 2. Nombre d’instruccions i fallades.

El bucle for executa 5 instruccions per iteració (bgeu, lw, add, addi, j), és a dir \(5 \times 100 = 500\) instruccions, més el bgeu final que provoca la sortida (1). Les instruccions d’inicialització són mv, la i tres per al sentinella (li, slli, add); cal recordar que la és una pseudoinstrucció que s’expandeix a dues instruccions reals (auipc + addi), de manera que la inicialització ocupa 6 instruccions. Finalment, la sortida (li, li, ecall) són 3 instruccions més. El nombre total d’instruccions executades és, doncs:

\[n_{ins} = 5 \times 100 + 1 + 6 + 3 = 510\ \text{instruccions}\]

Aquest és el valor que reporta l’eina Tools → Instruction Statistics de RARS (compta cada instrucció executada, inclosa l’ecall de sortida). El nombre de fallades de la memòria cau de dades s’obté amb el Data Cache Simulator: 25 fallades (una per cada bloc de 4 elements, com es calcula a Solució 33.2).

\[n_{fallades} = 25\]

Apartat 3. Temps d’execució amb memòria cau.

Aplicant Equació 7.4:

\[t_{exe} = t_c \cdot (n_{ins} \cdot \text{CPI}_{ideal} + n_{fallades} \cdot t_p)\]

\[t_{exe} = 10\ \text{ns} \cdot (510 \cdot 2 + 25 \cdot 11) = 10 \cdot (1020 + 275) = 12\,950\ \text{ns} \approx 12{,}95\ \mu\text{s}\]

Apartat 4. Temps d’execució sense memòria cau i guany.

Sense memòria cau, tots els lw (100 accessos) sofreixen una penalització \(t_p' = t_{MP} - t_h = 6 - 1 = 5\ \text{cicles}\) (Secció 7.7.3):

\[t_{exe,\text{sense cau}} = 10 \cdot (510 \cdot 2 + 100 \cdot 5) = 10 \cdot (1020 + 500) = 15\,200\ \text{ns}\]

\[\text{Guany} = \frac{t_{exe,\text{sense cau}}}{t_{exe,\text{amb cau}}} = \frac{15\,200}{12\,950} \approx 1{,}17\]

Els valors de \(n_{ins}\) i \(n_{fallades}\) es poden confirmar amb les eines de RARS (Instruction Statistics i Data Cache Simulator).

33.3 Escriptures i polítiques d’escriptura

En aquesta secció s’analitza com afecten les escriptures al comportament de la memòria cau. El programa ordena en ordre decreixent els elements d’un vector de 5 enters pel mètode de selecció (a cada pas selecciona el màxim dels elements restants):

ordenacio.c

int vec[5] = {20, -18, 45, 12, -1};

void main() {
    int i, j, aux, max;
    for (i = 0; i < 4; i++) {
        max = i;
        for (j = i + 1; j < 5; j++)
            if (vec[j] > vec[max]) max = j;
        aux = vec[i];
        vec[i] = vec[max];
        vec[max] = aux;
    }
}

La traducció a RV32I que es fa servir en aquesta secció és el Codi 33.2:

Codi 33.2: Ordenació per selecció d’un vector de 5 enters.

ordenacio.s

.eqv N, 5

.data
vec:    .word   20, -18, 45, 12, -1  # int vec[5]

.text

        la      t0, vec              # t0 = @vec[0]
        li      t6, N                # t6 = N
        li      s0, 0                # i = 0
buc_i:
        addi    t5, t6, -1
        bge     s0, t5, fibuc_i      # surt si i >= N-1

        mv      s1, s0               # max = i
        addi    s2, s0, 1            # j = i+1
buc_j:
        bge     s2, t6, fibuc_j      # surt si j >= N

        slli    t1, s2, 2
        add     t1, t0, t1           # t1 = @vec[j]
        lw      t2, 0(t1)            # t2 = vec[j]

        slli    t3, s1, 2
        add     t3, t0, t3           # t3 = @vec[max]
        lw      t4, 0(t3)            # t4 = vec[max]

        ble     t2, t4, no_canvi     # si vec[j] <= vec[max], no actualitza
        mv      s1, s2               # max = j
no_canvi:
        addi    s2, s2, 1            # j++
        j       buc_j
fibuc_j:
        slli    t1, s0, 2
        add     t1, t0, t1           # t1 = @vec[i]
        lw      t2, 0(t1)            # t2 = aux = vec[i]

        slli    t3, s1, 2
        add     t3, t0, t3           # t3 = @vec[max]
        lw      t4, 0(t3)            # t4 = vec[max]

        sw      t4, 0(t1)            # vec[i] = vec[max]
        sw      t2, 0(t3)            # vec[max] = aux

        addi    s0, s0, 1            # i++
        j       buc_i
fibuc_i:
        li      a7, 93
        li      a0, 0
        ecall

Carregueu el programa del Codi 33.2 a RARS i activeu el mòdul Tools → Data Cache Simulator amb 32 línies (Number of blocks) amb blocs de 4 paraules i correspondència directa. El simulador de RARS no té cap opció de política d’escriptura: en comptar encerts i fallades, tracta cada escriptura com una lectura (una escriptura amb fallada porta el bloc a la memòria cau), que és el comportament de la política amb assignació d’aquest exercici, i no compta el trànsit cap a la memòria principal.

---

Exercici 33.6 (s6_3_1.md) Considereu la memòria cau de correspondència directa amb 32 línies amb blocs de 4 paraules i política d’escriptura immediata amb assignació (Exemple 7.6). Les variables globals comencen a 0x10010000.

1. Per a cada iteració del bucle exterior (i = 0, 1, 2, 3), ompliu la taula amb els accessos a elements de vec: índex de l’element accedit, tipus d’accés (L = lectura, E = escriptura) i resultat (En = encert, F = fallada).

2. Compteu el nombre total d’accessos i d’encerts per a cada iteració del bucle exterior.

3. Calculeu la taxa d’encerts global de l’execució completa del programa.

Verifiqueu la taxa d’encerts amb el Data Cache Simulator de RARS. Comproveu també que, en acabar, el vector queda ordenat de gran a petit: {45, 20, 12, -1, -18}.

---

Solució 33.6. Els 5 elements de vec ocupen \(5 \times 4 = 20\) bytes. Com que 20 > 16 (la mida d’un bloc), vec ocupa 2 blocs consecutius: el bloc 0 conté vec[0]–vec[3] i el bloc 1 conté vec[4].

Com que vec comença a 0x10010000:

Element	Adreça	Línia d’MC
vec[0]	0x10010000	0
vec[1]	0x10010004	0
vec[2]	0x10010008	0
vec[3]	0x1001000C	0
vec[4]	0x10010010	1

Iteració i = 0 (max iniciat a 0; bucle j d’1 a 4; intercanvi vec[0] ↔︎ vec[max]):

Accés	Element	L/E	En/F
Lectura vec[1] (j=1)	1	L	F
Lectura vec[max=0] (j=1)	0	L	En
Lectura vec[2] (j=2)	2	L	En
Lectura vec[max] (j=2)	0	L	En
Lectura vec[3] (j=3)	3	L	En
Lectura vec[max] (j=3)	2	L	En
Lectura vec[4] (j=4)	4	L	F
Lectura vec[max] (j=4)	2	L	En
Lectura vec[i=0] (intercanvi)	0	L	En
Lectura vec[max] (intercanvi)	2	L	En
Escriptura vec[i=0]	0	E	En
Escriptura vec[max]	2	E	En

La lectura de vec[max] usa el valor de max abans de la seva possible actualització. Amb vec = {20, -18, 45, 12, -1}, max = 0 fins que a j = 2 es detecta el nou màxim vec[2] = 45; a partir d’aleshores max = 2 durant la resta de la iteració (per això les lectures de vec[max] a j = 1 i j = 2 accedeixen a l’element 0, i les posteriors, a l’element 2).

ExempleComprovació pràctica

Executeu ordenacio.s a RARS amb el Data Cache Simulator configurat amb 32 línies (Number of blocks) amb blocs de 4 paraules i correspondència directa (les escriptures hi compten com amb assignació). En acabar l’execució, el simulador mostra el nombre total de referències, encerts i fallades.

Per seguir l’evolució accés a accés, poseu un punt de ruptura a la primera instrucció del bucle interior i avanceu pas a pas observant els canvis a la vista Cache Block Table del simulador.

Apartat 2. Accessos i encerts per iteració del bucle exterior.

A cada iteració i, el bucle interior fa \(2 \times (4 - i)\) lectures (dues per cada valor de j, d’i+1 a 4) i l’intercanvi hi afegeix 4 accessos més (2 lectures + 2 escriptures):

Iteració i	Accessos	Fallades	Encerts
0	12	2	10
1	10	0	10
2	8	0	8
3	6	0	6
Total	36	2	34

Apartat 3. Taxa d’encerts global.

Les úniques fallades són les dues d’arrencada en fred de la iteració i = 0 (primer accés al bloc 0, amb vec[1], i al bloc 1, amb vec[4]); a partir d’aleshores tots dos blocs romanen a la memòria cau (vector de 2 blocs, cap conflicte amb 32 línies). Per tant:

\[\text{taxa d'encerts} = \frac{34}{36} \approx 0{,}944\]

El Data Cache Simulator ha de reportar 36 referències i 2 fallades.

---

Exercici 33.7 (s6_3_2.md) Considereu el mateix programa i la mateixa geometria de memòria cau (32 línies amb blocs de 4 paraules).

1. Com canviaria la taxa d’encerts si la política d’escriptura fos immediata sense assignació (Exemple 7.7)? Raoneu la resposta indicant quins accessos canvien de resultat.

2. Com canviaria la taxa d’encerts si la política d’escriptura fos retardada amb assignació (Exemple 7.8)? Raoneu la resposta.

---

Solució 33.7. Apartat 1. Escriptura immediata sense assignació.

En política d’escriptura immediata sense assignació, una escriptura amb fallada no porta el bloc a MC: l’escriptura es fa directament a MP i el bloc no s’emmagatzema a la memòria cau. En el programa d’ordenació, totes les escriptures (sw) es produeixen sobre elements que ja han estat llegits prèviament en la mateixa iteració del bucle exterior, de manera que el bloc ja és present a MC en el moment de l’escriptura (és un encert). Per tant, la taxa d’encerts no varia respecte a la política immediata amb assignació: el cas de fallada en escriptura no es produeix en aquest programa.

Apartat 2. Escriptura retardada amb assignació.

En política d’escriptura retardada amb assignació, les escriptures es fan únicament a MC (sense actualitzar MP immediatament) i el bloc es marca com a modificat (bit D). Quan el bloc és expulsat, s’escriu a MP. En el programa d’ordenació, el vector és tan petit (2 blocs) que cap bloc és expulsat durant l’execució. Les escriptures sobre blocs presents a MC (encerts) no generen cap penalització addicional. La taxa d’encerts és, per tant, la mateixa que en les polítiques anteriors.

---

Exercici 33.8 (s6_3_3.md) Considereu ara un vector de 64 elements (en lloc de 5), mantenint la mateixa geometria de memòria cau (correspondència directa, 32 línies amb blocs de 4 paraules) i la política d’escriptura immediata amb assignació.

1. Quantes fallades es produirien en l’execució del programa d’ordenació adaptat a 64 elements? Justifiqueu la resposta indicant si es produeixen fallades d’arrencada en fred, de capacitat o de conflicte (Secció 7.8, Essencial 7.4).

2. Sense que augmenti el nombre de fallades, fins a quin nombre mínim de línies es podria reduir la memòria cau? Raoneu la resposta.

Modifiqueu ordenacio.s per adaptar-lo a un vector de 64 elements: poseu .eqv N, 64 i substituïu la declaració per vec: .space 256 (els valors concrets no afecten el nombre de fallades). Verifiqueu les respostes amb el Data Cache Simulator.

---

Solució 33.8. Apartat 1. Nombre de fallades amb 64 elements.

El vector de 64 enters ocupa \(64 \times 4 = 256\) bytes, és a dir 16 blocs de 16 bytes. Amb 32 línies disponibles, tots els blocs del vector caben simultàniament a la memòria cau: no hi ha fallades de conflicte ni de capacitat.

Les úniques fallades són d’arrencada en fred: la primera referència a cada un dels 16 blocs. En el recorregut del bucle interior, cada bloc és accedit per primera vegada en ordre creixent d’índex, i a partir d’aquell moment roman a la memòria cau durant tota l’execució (no és expulsat perquè no hi ha conflictes). El nombre total de fallades és, doncs:

\[n_{fallades} = 16\]

Apartat 2. Nombre mínim de línies.

Perquè no augmenti el nombre de fallades (que ha de continuar sent només les 16 d’arrencada en fred), cal que els 16 blocs del vector puguin conviure a la memòria cau sense expulsar-se. Al llarg de l’execució, qualsevol bloc expulsat es tornaria a referenciar en una iteració posterior del bucle exterior i provocaria una fallada addicional; per tant, els 16 blocs han de residir simultàniament a la memòria cau. Amb una memòria cau de correspondència directa de 16 línies, els 16 blocs consecutius del vector (0–15) es mapen a 16 línies diferents (bloc \(b\) → línia \(b \bmod 16\)), de manera que no hi ha conflictes. El mínim és, doncs, 16 línies.

33.4 Accés a múltiples estructures

En aquesta secció s’analitza com la presència de múltiples estructures de dades pot provocar conflictes a la memòria cau (Secció 7.8): dues estructures que es mapen a les mateixes línies s’expulsen mútuament, degradant la taxa d’encerts fins i tot quan la memòria cau tindria capacitat suficient per contenir-les totes.

El programa calcula la suma element a element de dos vectors i desa el resultat en un tercer:

suma_vectors.c

int X[128], Y[128], Z[128];

void main() {
    int i;
    for (i = 0; i < 128; i++)
        Z[i] = X[i] + Y[i];
}

La traducció a RV32I fa servir tres punters que avancen en paral·lel:

Codi 33.3: Suma de dos vectors en un tercer, amb tres punters.

suma_vectors.s

.eqv N, 128

.data
X:      .space  512             # int X[128]
Y:      .space  512             # int Y[128]
Z:      .space  512             # int Z[128]

.text

        la      t0, X           # t0 = @X[0]
        la      t1, Y           # t1 = @Y[0]
        la      t2, Z           # t2 = @Z[0]
        li      t3, N
        slli    t3, t3, 2
        add     t3, t0, t3      # t3 = @X[N] (sentinella)
for:
        bgeu    t0, t3, fifor
        lw      t4, 0(t0)       # t4 = X[i]
        lw      t5, 0(t1)       # t5 = Y[i]
        add     t4, t4, t5      # t4 = X[i] + Y[i]
        sw      t4, 0(t2)       # Z[i] = X[i] + Y[i]
        addi    t0, t0, 4       # X[i+1]
        addi    t1, t1, 4       # Y[i+1]
        addi    t2, t2, 4       # Z[i+1]
        j       for
fifor:
        li      a7, 93
        li      a0, 0
        ecall

Carregueu el programa del Codi 33.3 a RARS i activeu el Data Cache Simulator.

---

Exercici 33.9 (s6_4_1.md) Considereu una memòria cau de correspondència directa amb 16 línies amb blocs de 4 paraules i política d’escriptura immediata amb assignació. Les variables globals comencen a 0x10010000.

1. Calculeu la mida en blocs de cada vector. Determineu a quines línies d’MC es mapen els blocs d’X, Y i Z. Identifiqueu si hi ha conflictes entre els tres vectors i expliqueu-ne la causa.

2. Calculeu la taxa d’encerts esperada. Justifiqueu el resultat a partir de l’anàlisi de conflictes.

Verifiqueu la resposta amb el Data Cache Simulator configurat amb 16 línies (Number of blocks) amb blocs de 4 paraules.

---

Solució 33.9. Apartat 1. Mapatge i conflictes.

Cada vector té 128 enters × 4 bytes = 512 bytes = 32 blocs de 16 bytes. La memòria cau té 16 línies. El mapatge en correspondència directa assigna el bloc \(n\) d’MP a la línia \(n \bmod 16\). Per simplicitat, numerem els blocs de manera relativa a l’inici d’X (el bloc que conté X[0] és el bloc 0).

X comença a 0x10010000 → bloc MP 0 a la línia 0, bloc MP 1 a la línia 1, …, bloc MP 15 a la línia 15, bloc MP 16 a la línia 0, …

Y comença a 0x10010000 + 512 = 0x10010200 → bloc MP 32 a la línia 0, bloc MP 33 a la línia 1, … Els blocs d’Y es mapen exactament a les mateixes línies que els d’X.

Z comença a 0x10010000 + 1024 = 0x10010400 → bloc MP 64 a la línia 0, bloc MP 65 a la línia 1, … Els blocs de Z es mapen també a les mateixes línies que X i Y.

Els tres vectors es mapen a les mateixes 16 línies: conflicte total. A cada iteració del bucle, l’accés a X[i], Y[i] i Z[i] accedeix a la mateixa línia d’MC, expulsant el bloc anterior en cada accés.

Apartat 2. Taxa d’encerts.

A cada iteració es fan 3 accessos (lectura X[i], lectura Y[i], escriptura Z[i]), cadascun a la mateixa línia d’MC. Seqüència per a la iteració \(i\):

1. lw X[i]: fallada (el bloc d’X[i] no és a MC o ha estat expulsat).
2. lw Y[i]: fallada (expulsa el bloc d’X[i] que s’acaba de portar).
3. sw Z[i]: fallada en escriptura amb assignació (expulsa el bloc d’Y[i]).

Els 3 accessos de cada iteració són fallades. Amb 128 iteracions i 3 accessos cadascuna:

\[\text{taxa d'encerts} = \frac{0}{384} = 0{,}00\]

ExempleComprovació pràctica

Configureu el Data Cache Simulator amb 16 línies (Number of blocks) amb blocs de 4 paraules i correspondència directa (les escriptures hi compten com amb assignació). Executeu suma_vectors.s i observeu que la taxa d’encerts és exactament 0: el simulador només comptabilitza els accessos a dades (les 384 lectures i escriptures als vectors), i totes són fallades.

---

Exercici 33.10 (s6_4_2.s) La taxa d’encerts nul·la de l’exercici anterior es deu al fet que els tres vectors es mapen exactament a les mateixes línies. Una manera d’eliminar els conflictes sense canviar l’algorisme és afegir farciment (padding) entre vectors: un espai buit que desplaça l’adreça base del vector següent i trenca l’alineació que causa el conflicte.

Modifiqueu la declaració de dades de suma_vectors.s afegint farciment entre els vectors de manera que la taxa d’encerts sigui 0,75. El fitxer resultant ha de ser s6_4_2.s.

Justifiqueu al mateix fitxer (com a comentaris) el valor de farciment escollit i per què produeix la taxa d’encerts desitjada.

Verifiqueu el resultat amb el Data Cache Simulator.

---

Solució 33.10. Amb 16 línies i blocs de 4 paraules (16 bytes), la memòria cau cobreix \(16 \times 16 = 256\) bytes. Els conflictes es produeixen perquè X, Y i Z estan separats exactament 512 bytes = 32 blocs, múltiple del nombre de línies (16), de manera que es mapen a les mateixes línies.

Per aconseguir una taxa d’encerts de 0,75 cal que 3 de cada 4 accessos siguin encerts. Això s’obté quan els tres vectors es mapen a línies diferents: en cada iteració del bucle, els blocs d’X[i], Y[i] i Z[i] van a línies distintes, de manera que no s’expulsen mútuament. Amb 128 elements i blocs de 4 paraules, hi ha 32 blocs per vector. La primera referència a cada bloc és una fallada d’arrencada en fred: 32 fallades per vector × 3 vectors = 96 fallades. El total d’accessos és 384. Taxa d’encerts:

\[\text{taxa d'encerts} = \frac{384 - 96}{384} = \frac{288}{384} = 0{,}75\]

Per separar els vectors cal que X, Y i Z es mapin a línies diferents. Com que X comença en una adreça alineada a bloc, un farciment de PAD bytes (múltiple de 16) desplaça la línia base d’Y en PAD/16 línies i la de Z en 2·PAD/16 línies (el doble, perquè Z acumula els dos farciments). Cal, doncs, que 0, PAD/16 i 2·PAD/16 siguin tres línies diferents mòdul 16. Compte: no serveix qualsevol valor —per exemple, PAD = 128 desplaçaria Z en \(2 \times 128 / 16 = 16 \equiv 0\) línies, fent-la coincidir de nou amb X. Un farciment d’un sol bloc (PAD = 16) porta X, Y i Z a les línies base 0, 1 i 2, que són diferents, i és suficient:

s6_4_2.s

.eqv N, 128
.eqv PAD, 16                    # 1 bloc de farciment entre vectors

.data
X:      .space  512             # int X[128]: 512 bytes, línies 0–15
        .space  PAD             # farciment: desplaça Y 1 bloc
Y:      .space  512             # int Y[128]: 512 bytes, línies 1–0 (rotació)
        .space  PAD             # farciment: desplaça Z 1 bloc addicional
Z:      .space  512             # int Z[128]: 512 bytes, línies 2–1 (rotació)

.text

        la      t0, X
        la      t1, Y
        la      t2, Z
        li      t3, N
        slli    t3, t3, 2
        add     t3, t0, t3
for:
        bgeu    t0, t3, fifor
        lw      t4, 0(t0)
        lw      t5, 0(t1)
        add     t4, t4, t5
        sw      t4, 0(t2)
        addi    t0, t0, 4
        addi    t1, t1, 4
        addi    t2, t2, 4
        j       for
fifor:
        li      a7, 93
        li      a0, 0
        ecall

ExempleComprovació pràctica

Executeu s6_4_2.s amb el Data Cache Simulator (16 línies amb blocs de 4 paraules, correspondència directa). La taxa d’encerts ha de ser 0,75. Comproveu també que el resultat al vector Z coincideix amb el de suma_vectors.s original (els valors de Z han de ser iguals en ambdós casos, ja que el farciment no afecta la lògica del programa).

---

Exercici 33.11 (s6_4_3.md) Considereu ara una memòria cau completament associativa (Secció 7.3.3) amb 16 línies amb blocs de 4 paraules i política LRU (Secció 7.4).

Calculeu la taxa d’encerts en l’execució del programa suma_vectors.s. Raoneu la resposta indicant si es produeixen fallades de conflicte, de capacitat o únicament d’arrencada en fred.

Verifiqueu la resposta amb el Data Cache Simulator configurat en mode completament associatiu.

---

Solució 33.11. En una memòria cau completament associativa, qualsevol bloc d’MP pot anar a qualsevol línia: no hi ha mapatge fix i, per tant, no hi ha fallades de conflicte. Podria semblar que hi haurà fallades de capacitat, ja que els tres vectors sumen \(3 \times 32 = 96\) blocs mentre que la memòria cau només en té 16 (\(96 > 16\)); però el que determina les fallades de capacitat no és l’ocupació total del programa, sinó el working set instantani (els blocs realment vius en un moment donat).

A cada iteració del bucle s’accedeix a un bloc d’X, un d’Y i un de Z. Amb política LRU i 16 línies, els blocs actius en qualsevol moment són els tres blocs corrents (un per vector). Com que 3 < 16, els tres blocs sempre caben a la memòria cau simultàniament sense expulsar-se: la primera referència a cada bloc és una fallada d’arrencada en fred i les tres referències restants al mateix bloc (els altres 3 elements) són encerts.

El comportament és idèntic al d’accés seqüencial sense conflictes: 32 fallades per vector × 3 vectors = 96 fallades, 384 − 96 = 288 encerts.

\[\text{taxa d'encerts} = \frac{288}{384} = 0{,}75\]

ExempleComprovació pràctica

Configureu el Data Cache Simulator en mode completament associatiu (seleccioneu Fully Associative al camp Placement Policy) amb 16 línies (Number of blocks) amb blocs de 4 paraules i política de reemplaçament LRU. Executeu suma_vectors.s i verifiqueu que la taxa d’encerts és 0,75.

---

Exercici 33.12 (s6_4_4.md) Considereu una memòria cau associativa per conjunts (Secció 7.3.2) amb blocs de 4 paraules i 16 conjunts.

Quin ha de ser el grau mínim d’associativitat (nombre de vies per conjunt) perquè la taxa d’encerts del programa suma_vectors.s sigui superior a 0? Raoneu la resposta sense usar el simulador.

Verifiqueu la resposta amb el Data Cache Simulator ajustant el camp Set size a la potència de 2 igual o immediatament superior al grau calculat (el simulador només accepta potències de 2).

---

Solució 33.12. Amb 16 conjunts i blocs de 4 paraules (16 bytes), el mapatge és: bloc d’MP \(n\) → conjunt \(n \bmod 16\). Els tres vectors ocupen 32 blocs cadascun i es mapen als mateixos 16 conjunts amb el mateix patró que en correspondència directa: els blocs \(i\), \(i + 32\) i \(i + 64\) (un de cada vector) van tots al conjunt \(i \bmod 16\).

Amb grau 1 (correspondència directa), els 3 blocs que competeixen per cada conjunt s’expulsen contínuament: taxa d’encerts = 0.

Amb grau 2, cada conjunt té 2 vies. A cada iteració hi ha 3 blocs actius que competeixen pel mateix conjunt (un d’X, un d’Y, un de Z): 3 > 2, de manera que amb LRU un dels tres blocs és expulsat a cada accés. Encara hi haurà conflictes i la taxa d’encerts continuarà sent 0.

Amb grau 3, cada conjunt té 3 vies: els 3 blocs actius (\(X[i]\), \(Y[i]\), \(Z[i]\)) caben simultàniament al mateix conjunt sense expulsar-se. La primera referència a cada bloc és una fallada d’arrencada en fred i les tres referències restants al bloc són encerts. La taxa d’encerts és 0,75 > 0.

El grau mínim és, per tant, 3.

ExempleComprovació pràctica

El simulador RARS només accepta potències de 2. Configureu Set size = 4 (la potència de 2 immediatament superior a 3) amb Number of blocks = 64 (16 conjunts × 4 vies) i 4 paraules/bloc. Executeu suma_vectors.s i verifiqueu que la taxa d’encerts és 0,75. Comproveu també amb Set size = 2 i Number of blocks = 32 (16 conjunts × 2 vies) que la taxa és 0.

---

Exercici 33.13 (s6_4_5.md) En aquest exercici classificareu les fallades del programa suma_vectors.s segons la taxonomia de les tres C (Secció 7.8, Essencial 7.4) usant el Runtime Log del Data Cache Simulator.

Activeu la casella Runtime Log (Enabled) del Data Cache Simulator: per a cada accés, el registre indica l’adreça, l’etiqueta i si és un encert o una fallada. Tingueu present que RARS no etiqueta el tipus de fallada; la classificació és un pas de raonament vostre, a partir del mètode següent:

• Una fallada és d’arrencada en fred si és la primera referència a aquell bloc: la primera vegada que apareix al registre una adreça del bloc. El bloc s’identifica pel número de bloc, l’adreça sense els 4 bits del desplaçament (adreça >> 4), i no per l’etiqueta sola, que en correspondència directa comparteixen blocs diferents.
• Les fallades que no són d’arrencada en fred són de conflicte o de capacitat. Per distingir-les, es compara amb una execució en què no hi pugui haver conflictes: una memòria cau completament associativa de la mateixa capacitat. Les fallades que desapareixen en passar a completament associativa eren de conflicte; les que persisteixen (més enllà de les d’arrencada en fred) són de capacitat.

1. Executeu suma_vectors.s amb la memòria cau de correspondència directa de 16 línies amb blocs de 4 paraules (la de Exercici 33.9). Amb el Runtime Log, determineu quantes de les fallades són d’arrencada en fred. (Pista: quants blocs diferents s’accedeixen en total?)

2. Executeu ara el mateix programa amb la memòria cau completament associativa de 16 línies (la de Exercici 33.11). Quantes fallades queden? De quin tipus són?

3. A partir dels dos resultats, feu el desglossament complet de les fallades de la memòria cau de correspondència directa en fallades d’arrencada en fred, de conflicte i de capacitat.

---

Solució 33.13. Apartat 1. Fallades de la memòria cau de correspondència directa i d’arrencada en fred.

Amb la memòria cau de correspondència directa (Solució 33.9), els 384 accessos són fallades. Ara bé, d’arrencada en fred només ho són les primeres referències a cada bloc diferent. Cada vector ocupa 32 blocs, i són tres vectors sense superposició, de manera que s’accedeixen \(3 \times 32 = 96\) blocs diferents:

\[n_{\text{obligatòries}} = 96\]

Apartat 2. Fallades de la memòria cau completament associativa.

Amb la memòria cau completament associativa (Solució 33.11), la taxa d’encerts és 0,75: hi ha 96 fallades. Com que en una memòria cau completament associativa no hi pot haver fallades de conflicte, i el working set instantani (3 blocs) és molt inferior a la capacitat (16 línies), tampoc no n’hi ha de capacitat: les 96 fallades són totes d’arrencada en fred.

Apartat 3. Desglossament de les fallades de la memòria cau de correspondència directa.

Les 96 fallades de la memòria cau completament associativa són el nombre irreductible de fallades d’arrencada en fred. Les fallades addicionals de la memòria cau de correspondència directa (les que desapareixen en passar a completament associativa) són de conflicte:

Tipus de fallada	Correspondència directa	Completament associativa
Obligatòria	96	96
Conflicte	288	0
Capacitat	0	0
Total	384	96

El cas confirma que aquí la degradació de la correspondència directa (taxa 0 enfront de 0,75) es deu íntegrament a fallades de conflicte, no de capacitat: la memòria cau tindria prou espai per als 3 blocs actius, però el mapatge fix els força a la mateixa línia.

33.5 Optimització: loop tiling

El programa de suma de vectors de la secció anterior té un patró d’accés favorable: recorre les tres estructures de manera estrictament seqüencial i en paral·lel, de manera que la localitat espacial és màxima. No tots els programes tenen aquest comportament. En alguns casos, el patró d’accés provoca que elements carregats a la memòria cau siguin expulsats abans de ser reutilitzats, malbaratant la localitat temporal.

El programa del Codi 33.4 calcula el producte d’una matriu per un vector:

Codi 33.4: Producte d’una matriu per un vector.

matvec.c

int V1[16], M[16][16], V2[16];

void main() {
    int i, j, tmp;
    for (i = 0; i < 16; i++) {
        tmp = 0;
        for (j = 0; j < 16; j++)
            tmp += M[i][j] * V2[j];
        V1[i] = tmp;
    }
}

M s’emmagatzema per files (row-major order, Secció 4.5.1): els elements M[i][0], M[i][1], …, M[i][15] són contigus en memòria. El bucle interior recorre la fila i de M i tot el vector V2 de manera seqüencial. A cada iteració del bucle exterior, V2 es llegeix sencer (16 elements). Si la memòria cau pot mantenir alhora V2, la fila de M i el bloc de V1 en ús, sense que es facin conflicte, els accessos a V2 a partir de la segona iteració exterior són encerts. Si la memòria cau és massa petita, V2 és expulsat a cada iteració i s’ha de tornar a carregar des de la memòria principal.

La traducció a RV32IM de la versió original és:

matvec.s

.eqv NI, 16
.eqv NJ, 16

.data
        .align 2
V1:     .space  64                # int V1[16]
        .align 2
M:      .space  1024             # int M[16][16]
        .align 2
V2:     .space  64                # int V2[16]

.text

        la      s3, V1          # s3 = @V1[0] (invariant)
        la      s4, M           # s4 = @M[i][0] (punter de fila)
        la      s5, V2          # s5 = @V2[0] (invariant)
        li      s2, NI          # s2 = sentinella i (invariant)
        li      s6, NJ
        slli    s6, s6, 2       # s6 = NJ*4: mida d'una fila en bytes (invariant)

        li      s1, 0           # i = 0
buc_i:
        bge     s1, s2, fibuc_i

        li      t1, 0           # tmp = 0
        mv      t2, s4          # t2 = punter a M[i][j] (j = 0)
        mv      t4, s5          # t4 = punter a V2[j] (j = 0)
        add     t5, s4, s6      # t5 = sentinella j: @M[i][NJ]
buc_j:
        bgeu    t2, t5, fibuc_j
        lw      t6, 0(t2)       # t6 = M[i][j]
        lw      a0, 0(t4)       # a0 = V2[j]
        mul     t6, t6, a0      # t6 = M[i][j] * V2[j]
        add     t1, t1, t6      # tmp += M[i][j] * V2[j]
        addi    t2, t2, 4       # punter M avança (stride = 4)
        addi    t4, t4, 4       # punter V2 avança (stride = 4)
        j       buc_j
fibuc_j:
        slli    t6, s1, 2
        add     t6, s3, t6      # t6 = @V1[i]
        sw      t1, 0(t6)       # V1[i] = tmp
        add     s4, s4, s6      # punter de fila: @M[i+1][0]
        addi    s1, s1, 1       # i++
        j       buc_i
fibuc_i:
        li      a7, 93
        li      a0, 0
        ecall

L’optimització loop tiling (també anomenada loop blocking o tiling) reorganitza el recorregut per aprofitar la localitat temporal de V2: en lloc de multiplicar tota una fila de M per tot V2, es processen grups de 4 columnes alhora. Primer s’itera per totes les files amb les columnes 0–3, després amb les columnes 4–7, i així fins a completar les 16 columnes. D’aquesta manera, els 4 elements de V2 implicats en cada grup caben en un únic bloc de memòria cau, que es pot reutilitzar en totes les files si cap altre bloc no l’expulsa:

matvec_tiling.c

int V1[16];              // global (inicialitzat a 0 en C)
int M[16][16], V2[16];

void main() {
    int i, j, k, tmp;
    for (k = 0; k < 4; k++)
        for (i = 0; i < 16; i++) {
            tmp = 0;
            for (j = 0; j < 4; j++)
                tmp += M[i][k * 4 + j] * V2[k * 4 + j];
            V1[i] += tmp;
        }
}

El bucle k itera els 4 grups de columnes (0–3, 4–7, 8–11, 12–15). Per a cada bloc, el bucle i recorre totes les files de M acumulant parcialment el resultat a V1[i]. El bucle j recorre els 4 elements del bloc de columnes. Amb blocs de 4 elements (= 1 bloc de memòria cau de 4 paraules), els accessos a V2[k*4 + j] són encerts a partir del primer element del bloc, perquè els 4 elements es carreguen junts en la primera fallada.

Carregueu matvec.s (versió original) a RARS i mesureu amb el Data Cache Simulator la seva taxa d’encerts per a diverses geometries de memòria cau; registrareu aquests valors i els compareu amb els del programa amb tiling a la Taula 33.1 de l’exercici.

---

Exercici 33.14 (s6_5_1.s) Traduïu a RV32IM el programa matvec_tiling.c. El fitxer s6_5_1.s ha de contenir el programa complet.

Abans d’escriure cap instrucció:

1. Identifiqueu totes les variables del programa (i, j, k, tmp, els punters o adreces base que calgui) i assigneu-les a registres. Justifiqueu si useu registres t o s.

2. Determineu l’stride d’accés a M[i][k*4 + j] en funció de com varien i, j i k. Indiqueu quin dels tres índexs varia més ràpidament al bucle interior i com avança el punter corresponent.

A continuació, escriviu el codi RV32IM complet.

Comproveu que, amb M[i][j] = 1 per a tots i, j i V2[j] = j, cada element de V1 val 120, com amb el programa original no optimitzat.

3. Amb el Data Cache Simulator, mesureu la taxa d’encerts del programa amb tiling per a les geometries de la taula següent i compareu-les amb les del programa original matvec.s:

Taula 33.1: Taxa d’encerts del programa amb tiling per a diferents geometries de memòria cau

Capacitat	CD	Assoc. grau 2	Assoc. grau 4	Assoc. grau 8	Comp. assoc.
8 línies
16 línies
32 línies
64 línies
128 línies

---

Solució 33.14. Pas 1. Assignació de registres.

El programa és pla: no fa cap crida, de manera que tot el codi és al bloc principal i no hi ha context que preservar. Tots els registres són t tret dels que han de sobreviure als tres nivells de bucle imbricat. Els valors que creuen el bucle interior (i, k, les adreces base) han de ser en registres que el bucle interior no destrueixi. Com que no hi ha crides, es poden usar registres t sempre que el compilador (o el programador) garanteixi que el bucle interior no els sobreescriu. Per claredat i robustesa s’usen s per als índexs dels bucles exteriors:

Variable	Registre	Justificació
k	s0	índex del bucle més exterior; ha de sobreviure als bucles i i j
i	s1	índex del bucle mitjà; ha de sobreviure al bucle j
sentinella k	s6	límit del bucle k; invariant durant tota l’execució
sentinella i	s2	límit del bucle i; invariant durant tota l’execució
@V1[0]	s3	adreça base de V1; invariant durant tota l’execució
@M[0][0]	s4	adreça base de M; invariant durant tota l’execució
@V2[0]	s5	adreça base de V2; invariant durant tota l’execució
j	t0	índex del bucle interior
tmp	t1	acumulador parcial; reinicialitzat a cada iteració d’i
punter @M[i][k*4+j]	t2	avança 4 bytes a cada iteració de j; recalculat a cada i
@V2[k*4]	t3	adreça base del bloc de V2 per al k actual; recalculada a cada k
còpia de t3 per al bucle j	t4	avança 4 bytes a cada iteració de j
sentinella j	t5	límit del bucle j; reinicialitzat a cada i
temporals del bucle j	t6, a0	lectures i producte; no cal preservar-los entre iteracions. Com que t0–t6 ja estan tots assignats i no hi ha crides, a0 queda lliure per usar-lo com a temporal dins el bucle (i es reaprofita per a l’ecall de sortida)

Pas 2. Stride d’accés.

Al bucle interior (j de 0 a 3), j varia més ràpidament. L’element accedit és M[i][k*4 + j]: per a i i k fixos, en incrementar j en 1 l’adreça avança 4 bytes (stride = 4, elements contigus a la mateixa fila). Es pot usar un punter t2 que s’inicialitza a @M[i][k*4] i s’incrementa 4 bytes a cada iteració del bucle j. Anàlogament, V2[k*4 + j] avança 4 bytes per iteració de j.

s6_5_1.s

.eqv NI, 16
.eqv NJ, 16
.eqv BLK, 4                    # mida del bloc de tiling

.data
        .align 2
V1:     .word   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0 # int V1[16] inicialitzat a 0
        .align 2
M:      .space  1024                           # int M[16][16]
        .align 2
V2:     .space  64                              # int V2[16]

.text

        la      s3, V1          # s3 = @V1[0]
        la      s4, M           # s4 = @M[0][0]
        la      s5, V2          # s5 = @V2[0]
        li      s6, 4           # s6 = sentinella k = NJ/BLK (invariant)
        li      s2, NI          # s2 = sentinella i (invariant)

        li      s0, 0           # k = 0
buc_k:
        bge     s0, s6, fibuc_k

        # @V2[k*4] = @V2 + k*BLK*4 = @V2 + k*16
        slli    t3, s0, 4       # t3 = k * 16
        add     t3, s5, t3      # t3 = @V2[k*4]

        li      s1, 0           # i = 0
buc_i:
        bge     s1, s2, fibuc_i

        li      t1, 0           # tmp = 0

        # @M[i][k*4] = @M + i*NJ*4 + k*16
        li      t0, NJ
        mul     t2, s1, t0      # t2 = i * NJ
        slli    t2, t2, 2       # t2 = i * NJ * 4 (bytes)
        add     t2, s4, t2      # t2 = @M[i][0]
        slli    t0, s0, 4       # t0 = k * 16 (desplaçament de columna en bytes)
        add     t2, t2, t0      # t2 = @M[i][k*4]

        mv      t4, t3          # t4 = @V2[k*4] (còpia local per al bucle j)

        li      t0, 0           # j = 0
        li      t5, BLK         # t5 = sentinella j
buc_j:
        bge     t0, t5, fibuc_j

        lw      t6, 0(t2)       # t6 = M[i][k*4 + j]
        lw      a0, 0(t4)       # a0 = V2[k*4 + j]
        mul     t6, t6, a0      # t6 = M[i][k*4+j] * V2[k*4+j]
        add     t1, t1, t6      # tmp += producte

        addi    t2, t2, 4       # punter M avança al següent element de la fila
        addi    t4, t4, 4       # punter V2 avança al següent element del bloc
        addi    t0, t0, 1       # j++
        j       buc_j
fibuc_j:
        # V1[i] += tmp
        slli    t2, s1, 2       # t2 = i * 4
        add     t2, s3, t2      # t2 = @V1[i]
        lw      t6, 0(t2)       # t6 = V1[i]
        add     t6, t6, t1      # t6 = V1[i] + tmp
        sw      t6, 0(t2)       # V1[i] += tmp

        addi    s1, s1, 1       # i++
        j       buc_i
fibuc_i:
        addi    s0, s0, 1       # k++
        j       buc_k
fibuc_k:
        li      a7, 93
        li      a0, 0
        ecall

ExempleComprovació pràctica

Verificació de correctesa. Inicialitzeu M i V2 amb els valors de l’enunciat, executeu primer el programa original i després s6_5_1.s, i compareu-ne V1 al segment de dades.

Verificació de rendiment. Executant s6_5_1.s (amb tiling) i matvec.s (original) amb el Data Cache Simulator per a les geometries de la Taula 33.1 s’obtenen les taxes d’encerts següents (format tiling / original):

Taxes d’encerts de referència (solució)

Capacitat	CD	Assoc. grau 2	Assoc. grau 4	Assoc. grau 8	Comp. assoc.
8 línies	0,52 / 0,43	0,84 / 0,81	0,87 / 0,78	0,87 / 0,73	0,87 / 0,73
16 línies	0,70 / 0,65	0,88 / 0,86	0,88 / 0,86	0,88 / 0,86	0,87 / 0,86
32 línies	0,80 / 0,76	0,88 / 0,86	0,88 / 0,86	0,88 / 0,86	0,89 / 0,86
64 línies	0,84 / 0,82	0,89 / 0,86	0,89 / 0,86	0,89 / 0,86	0,89 / 0,86
128 línies	0,89 / 0,86	0,89 / 0,86	0,89 / 0,86	0,89 / 0,86	0,89 / 0,86

Les taxes, però, no comparen bé els dos programes: la versió amb tiling fa 640 accessos a dades, i l’original, 528, perquè hi afegeix 112 accessos a V1 (una lectura i una escriptura per a cada parella k, i), que són gairebé tots encerts i fan pujar la taxa. El que cal comparar és el nombre de fallades (format tiling / original):

Fallades de referència (solució)

Capacitat	CD	Assoc. grau 2	Assoc. grau 4	Assoc. grau 8	Comp. assoc.
8 línies	306 / 300	105 / 99	82 / 114	84 / 144	84 / 144
16 línies	190 / 184	78 / 72	78 / 72	78 / 72	84 / 72
32 línies	131 / 126	76 / 72	76 / 72	76 / 72	72 / 72
64 línies	100 / 97	73 / 72	72 / 72	72 / 72	72 / 72
128 línies	72 / 72	72 / 72	72 / 72	72 / 72	72 / 72

El tiling només redueix les fallades amb 8 línies i grau 4 o més (també completament associativa): és el cas en què la memòria cau no pot mantenir tot V2, però sí el bloc actiu de V2 al costat de la fila de M. Amb correspondència directa no les redueix: el bloc de M[i][…] i el de V2 que es fan servir alhora cauen a la mateixa línia i s’expulsen l’un a l’altre. Amb prou capacitat, tots dos programes es queden en les 72 fallades d’arrencada en fred (64 blocs de M, 4 de V2 i 4 de V1), i el tiling no aporta res.