Tema 7: Memòria cau

16.1 Disseny bàsic

Vegeu Secció 7.2, Secció 7.3 i Secció 7.5.

Problema 16.1 Considereu que la jerarquia de memòria d’un sistema computador està formada per una memòria principal de 64 bytes i una memòria cau de 16 bytes, amb correspondència directa i blocs de 4 bytes. La unitat d’adreçament és el byte.

Donada l’adreça 0x39 de memòria principal, indiqueu:
- Quin és l’índex de la memòria cau que li correspon.
- Quina és l’etiqueta que li correspon.
- Quin és el byte que li correspon dins el bloc.
Considereu la seqüència de referències de lectura a blocs de memòria principal següent: 0, 1, 0, 3, 12, 10, 3, 7, 12, 15, 3. Indiqueu per a cada referència si es produeix un encert o una fallada a la memòria cau.

Problema 16.2 Considereu un processador de 16 bits amb una memòria cau amb les característiques següents:

Correspondència directa.
Mida total: 256 bytes.
Mida de bloc: 16 bytes.
Escriptura immediata sense assignació.

Ompliu la taula següent a partir de la seqüència de referències donada:

Tipus	Adreça (hex)	Etiqueta (hex)	Índex MC (hex)	Encert/Fallada	Bytes llegits MP	Bytes escrits MP	Lectura dades MC	Escriptura dades MC
L	`4534`
L	`4568`
E	`13A4`
E	`13A8`
L	`3560`
E	`453C`
E	`60A0`
L	`453C`
E	`3900`
L	`A238`

Ompliu la mateixa taula suposant que la memòria cau té una política d’escriptura retardada amb assignació.
Indiqueu per a cada política: taxa de fallades, nombre de bytes llegits d’MP i nombre de bytes escrits a MP.

Problema 16.3 El programa del Codi 16.1 multiplica una matriu A(32×32) per un vector B(32) produint com a resultat un vector C(32):

Codi 16.1: Producte d’una matriu de bytes per un vector.

char A[32][32], B[32], C[32];
void main() {
    int i, j;
    for (i = 0; i < 32; i++)
        for (j = 0; j < 32; j++)
            C[i] = A[i][j] * B[j] + C[i];
}

Els elements d’A, B i C són bytes. Tots els elements de C han estat prèviament inicialitzats a zero. A s’emmagatzema a partir de l’adreça 0 (adreces 0..1023), B a continuació (adreces 1024..1055) i C tot seguit (adreces 1056..1087). Les variables i i j estan en registres.

El computador disposa d’una memòria cau de correspondència directa amb 4 línies i blocs de 32 bytes, amb escriptura immediata. Suposant que en iniciar-se l’execució la memòria cau és buida, calculeu la taxa d’encerts.

Problema 16.4 Es vol dissenyar una nova versió d’un processador que disposa d’una memòria cau de correspondència directa amb 4 línies i blocs d’una paraula (32 bits). La nova versió tindrà el doble de capacitat. Es consideren dues alternatives:

Alternativa 1: doblar el nombre de línies (8 línies d’una paraula).
Alternativa 2: doblar la mida del bloc (4 línies de 2 paraules).

Proposeu una seqüència de referències a paraules de memòria principal tal que la taxa d’encerts de l’alternativa 1 sigui major que la de l’alternativa 2.
Proposeu una seqüència de referències tal que la taxa d’encerts de l’alternativa 2 sigui major que la de l’alternativa 1.
Raoneu quina característica dels programes s’explota en major mesura en cadascuna de les dues alternatives.

16.2 Rendiment

Vegeu Secció 7.7; en particular, Equació 7.1 i Equació 7.4.

Problema 16.5 Una mesura possible del rendiment d’una memòria cau és la taxa de tràfic, definida com el quocient entre el nombre de bytes transferits des de/cap a la memòria principal en un sistema amb memòria cau i el nombre de bytes transferits en un sistema sense memòria cau.

Suposeu que totes les referències a memòria són de paraules de 32 bits. Calculeu la taxa de tràfic en funció de la taxa d’encerts ($h$), la mida del bloc en bytes ($B$), el percentatge d’escriptures ($p_e$) i el percentatge de blocs reemplaçats que han estat modificats ($p_m$) per a:

Escriptura immediata sense assignació.
Escriptura retardada amb assignació.

Problema 16.6 Es vol definir la política d’escriptura de la memòria cau d’un processador. Es consideren dues alternatives: (1) escriptura immediata sense assignació i (2) escriptura retardada amb assignació.

Mitjançant simulació s’han obtingut les mesures següents:

Percentatge d’escriptures ($p_e$): 20 %.
Percentatge de blocs modificats sobre el total de blocs reemplaçats ($p_m$): 33,33 %.
Taxa d’encerts en el cas (1): 0,9.
Taxa d’encerts en el cas (2): 0,85.

El temps d’accés en cas d’encert ($t_h$) és 10 ns. La lectura o escriptura d’un bloc de memòria principal ($t_{bloc}$) requereix 100 ns.

Calculeu el temps d’accés mitjà (TAM) en ambdues alternatives.
Indiqueu quina alternativa seria la més ràpida per a un programa que només fes lectures.

Problema 16.7 Considereu una CPU amb memòria cau en què s’han observat les característiques següents:

$\text{CPI}_{ideal}$: 1,5 cicles/instrucció.
Temps de cicle ($t_c$): 10 ns.
Nombre de referències per instrucció ($n_r$): 1,6.
Memòries cau d’instruccions i dades separades.
Memòria cau de dades amb escriptura retardada amb assignació.

Característica	MC d’instruccions	MC de dades
Accessos per instrucció	1	0,6
Percentatge d’escriptures ($p_e$)	—	40 %
Percentatge de blocs modificats ($p_m$)	—	20 %
Taxa de fallades ($m$)	4 %	10 %
Penalització bloc no modificat ($t_p$)	10 cicles	15 cicles
Penalització bloc modificat ($t_p$)	—	20 cicles
Temps d’encert ($t_h$)	1 cicle	1 cicle

Quin és el temps d’accés mitjà (TAM) en cicles?
Quin és el temps mitjà d’execució d’una instrucció ($t_{exe}$) en ns?

Problema 16.8 Considereu una CPU amb memòria cau en què s’han observat les característiques següents:

$\text{CPI}_{ideal}$: 1,8 cicles/instrucció.
Temps de cicle ($t_c$): 10 ns.
Nombre de referències per instrucció ($n_r$): 1,4.
Mida del bloc: 8 bytes.
Política d’escriptura retardada amb assignació.
Temps d’encert ($t_h$): 1 cicle.
Temps de servei d’MP per llegir/escriure blocs ($t_{bloc}$): 15 cicles.
Percentatge d’escriptures ($p_e$): 15 %.
Percentatge de blocs modificats ($p_m$): 20 %.
Taxa d’encerts ($h$): 90 %.

Quin és el temps de penalització ($t_p$) en cas que el bloc estigui modificat? I en cas que no ho estigui?
Quin és el temps d’accés mitjà (TAM) en cicles?
Quin és el temps mitjà d’execució d’una instrucció en ns?

Problema 16.9 A l’hora de dissenyar una memòria cau d’instruccions de 8 KiB es dubta entre dues mides de bloc, amb les taxes de fallades mesurades següents:

8 bytes: 16 %.
16 bytes: 10 %.

Calculeu el temps d’accés mitjà (TAM) sabent que:
- El temps d’accés en cas d’encert ($t_h$) és 1 cicle.
- El temps de servei d’MP per a blocs de 8 bytes és 6 cicles; per a blocs de 16 bytes és 12 cicles.
Quant ocuparan totes les etiquetes en cadascuna de les dues opcions, sabent que:
- MP té $2^{32}$ bytes.
- Les memòries cau són de correspondència directa.
- La unitat mínima d’accés a memòria és el byte.

16.3 Associativitat i multinivell

Vegeu Secció 7.3.2, Secció 7.4 i Secció 7.9.

Problema 16.10 Considereu un processador de 16 bits (paraules i adreces de 16 bits) amb una memòria cau amb les característiques següents:

Correspondència associativa de 2 vies.
Mida total: 1024 bytes.
Mida de bloc: 16 bytes.
Política d’escriptura immediata sense assignació.
Algorisme de reemplaçament: LRU.

Ompliu la taula següent a partir de la seqüència de referències donada (L byte = lectura d’1 byte, L paraula = lectura d’una paraula, de 2 bytes, E byte = escriptura d’1 byte, E paraula = escriptura d’una paraula):

Tipus	Adreça (hex)	Bloc MP	Conjunt MC	Encert/Fallada	Lectura MP (S/N, adreça, mida)	Escriptura MP (S/N, adreça, mida)
L byte	`A930`
L paraula	`B930`
E byte	`A972`
E paraula	`A932`
E byte	`C935`
L paraula	`C934`
E byte	`B976`
E paraula	`B936`
L byte	`B938`
L paraula	`A978`

Problema 16.11 Sobre un sistema amb una memòria cau de dades amb 64 conjunts, 4 vies per conjunt, 32 bytes per bloc i algorisme LRU, s’executen dues versions d’una mateixa aplicació:

int A[128][1024]; // emmagatzemada a partir de l'adreça 0

// Versió A
sumA = 0;
for (i = 0; i < 128; i++)
    for (j = 0; j < 1024; j++)
        sumA = sumA + A[i][j];

// Versió B
sumA = 0;
for (j = 0; j < 1024; j++)
    for (i = 0; i < 128; i++)
        sumA = sumA + A[i][j];

Indiqueu quantes fallades hi ha a la memòria cau de dades per a cadascuna de les dues versions. Considereu que i, j i sumA estan en registres.

Problema 16.12 El subsistema de memòria d’un computador està organitzat en tres nivells: L1 (4 línies amb blocs de 4 bytes, correspondència directa), L2 (16 línies amb blocs de 4 bytes, associativa de 2 vies, LRU) i MP (1 MiB). En cas de fallada a L1 es comprova L2; si hi és, es copia a L1 sense accedir a MP. Si no hi és a L2, s’accedeix a MP i es copia a les dues memòries cau.

La taxa d’encerts de cada nivell es defineix com $h_{L1} = \text{encerts a L1} / \text{peticions a L1}$, i igualment $h_{L2}$.

Donada la seqüència de 7 adreces de lectura següent, repetida 4 vegades (28 accessos en total):

0, 5, 10, 12, 34, 0, 66

Suposant les memòries cau inicialment buides, calculeu les taxes $h_{L1}$ i $h_{L2}$.
Calculeu de nou les taxes $h_{L1}$ i $h_{L2}$ suposant que l’algorisme de reemplaçament de L2 és FIFO.

Problema 16.13 Es vol dissenyar una memòria cau multinivell (L1 i L2). Es coneixen les dades següents:

El temps de servei de L1 en cas d’encert és $t_{h_{L1}}$; en cas de fallada cal afegir-hi el temps de servei de L2.
El temps de servei de L2 en cas d’encert és $t_{h_{L2}}$; en cas de fallada cal afegir-hi la penalització $t_p$ (temps d’accés a MP).
$m_{L1}$: taxa de fallades a L1.
$m_{L2}$: taxa de fallades local a L2 (fallades a L2 / accessos a L2).

Obteniu l’expressió del temps d’accés mitjà (TAM) en cicles, en funció de $t_{h_{L1}}$, $t_{h_{L2}}$, $t_p$, $m_{L1}$ i $m_{L2}$.

Problema 16.14 Es disposa d’un processador de 8 bits amb una memòria cau completament associativa amb les característiques següents:

Nombre de línies: 4.
Mida del bloc: 8 bytes.
Algorisme de reemplaçament: LRU.
Política d’escriptura retardada amb assignació.
Temps d’encert ($t_h$): 1 cicle.
Temps de servei d’MP ($t_{bloc}$): 10 cicles.

Temps de servei en cas de fallada de lectura que reemplaça un bloc no modificat.
Temps de servei en cas de fallada de lectura que reemplaça un bloc modificat.
Temps de servei en cas de fallada d’escriptura que reemplaça un bloc no modificat.
Temps de servei en cas de fallada d’escriptura que reemplaça un bloc modificat.
Suposant la memòria cau inicialment buida i la llista d’accessos (en decimal, L = lectura, E = escriptura):

2L, 9L, 16L, 2L, 33E, 42E, 33L, 2L, 17L, 27E, 43L, 3L, 44L, 46L, 3L, 14L, 17L, 6L, 35L

- Indiqueu per a cada accés si produeix encert, fallada amb reemplaçament (indicant el número del bloc reemplaçat) o fallada sense reemplaçament.
- Calculeu el temps total de servei de la llista d'accessos.

16.4 Tipologia de les fallades

Vegeu Secció 7.8 i Essencial 7.4.

Problema 16.15 Una memòria cau de correspondència directa té 8 línies amb blocs de 4 bytes. Considereu les seqüències d’accés a bytes següents (les adreces estan en decimal):

Seqüència A: 0, 4, 8, 12, 16, 20, 24, 28, 0, 4, 8, 12.
Seqüència B: 0, 4, 8, 12, 0, 4, 8, 12, 0, 4, 8, 12.
Seqüència C: 0, 32, 0, 32, 0, 32, 0, 32.

Per a cada seqüència, calculeu el nombre de fallades i classifiqueu-les en fallades d’arrencada en fred (cold-start), de conflicte o de capacitat.
Per a la seqüència C, quin canvi de disseny de la memòria cau eliminaria les fallades de conflicte? Justifiqueu-ho.
Una memòria cau associativa de 2 vies (mateixa capacitat total) milloraria els resultats de la seqüència C? I de la seqüència B?

Problema 16.16 Considereu el programa C del Codi 16.2, on N = 256 i els elements d’A i B són enters de 4 bytes:

Codi 16.2: Suma dels elements de A i de B.

int A[N], B[N];
void main() {
    int i, suma = 0;
    for (i = 0; i < N; i++)
        suma += A[i] + B[i];
}

A s’emmagatzema a partir de l’adreça 0x000 i B a partir de 0x400. La memòria cau té correspondència directa, 16 línies amb blocs de 32 bytes i política d’escriptura immediata.

Nota: en aquest problema, excepcionalment, les adreces s’escriuen en format reduït, sense els zeros de l’esquerra. Totes són inferiors a 0x1000, i per saber a quina línia de la memòria cau va cada bloc només calen els bits de menys pes (els 5 de desplaçament i els 4 d’índex).

Quantes fallades d’arrencada en fred es produeixen en el primer recorregut d’A? I en el de B?
Es produeixen fallades de conflicte entre A i B? Raoneu la resposta calculant a quines línies de la memòria cau es mapen.
Si B comencés a 0x600 en comptes de 0x400, canviaria la resposta a l’apartat b)?

--- number-sections: true language: crossref-exr-title: "Problema" crossref-exr-prefix: "Problema" --- # {{< var tema7 >}} {#sec-tema-mc-enunciats} ## Disseny bàsic *Vegeu @sec-mc, @sec-politica-emplacament i @sec-politica-escriptura.* ::: {#exr-t7-cache-adreces} Considereu que la jerarquia de memòria d'un sistema computador està formada per una memòria principal de 64 bytes i una memòria cau de 16 bytes, amb correspondència directa i blocs de 4 bytes. La unitat d'adreçament és el byte. a) Donada l'adreça `0x39` de memòria principal, indiqueu: - Quin és l'índex de la memòria cau que li correspon. - Quina és l'etiqueta que li correspon. - Quin és el byte que li correspon dins el bloc. b) Considereu la seqüència de referències de lectura a blocs de memòria principal següent: 0, 1, 0, 3, 12, 10, 3, 7, 12, 15, 3. Indiqueu per a cada referència si es produeix un encert o una fallada a la memòria cau. ::: ::: {#exr-t7-cache-politiques} Considereu un processador de 16 bits amb una memòria cau amb les característiques següents: - Correspondència directa. - Mida total: 256 bytes. - Mida de bloc: 16 bytes. - Escriptura immediata sense assignació. a) Ompliu la taula següent a partir de la seqüència de referències donada: | Tipus | Adreça (hex) | Etiqueta (hex) | Índex MC (hex) | Encert/Fallada | Bytes llegits MP | Bytes escrits MP | Lectura dades MC | Escriptura dades MC | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | L | `4534` | | | | | | | | | L | `4568` | | | | | | | | | E | `13A4` | | | | | | | | | E | `13A8` | | | | | | | | | L | `3560` | | | | | | | | | E | `453C` | | | | | | | | | E | `60A0` | | | | | | | | | L | `453C` | | | | | | | | | E | `3900` | | | | | | | | | L | `A238` | | | | | | | | : {tbl-colwidths="[8,10,12,8,20,8,9,11,14]"} b) Ompliu la mateixa taula suposant que la memòria cau té una política d'escriptura retardada amb assignació. c) Indiqueu per a cada política: taxa de fallades, nombre de bytes llegits d'MP i nombre de bytes escrits a MP. ::: :::: {#exr-t7-cache-matriu} El programa del @lst-t7-cache-matriu multiplica una matriu `A(32×32)` per un vector `B(32)` produint com a resultat un vector `C(32)`: ::: {#lst-t7-cache-matriu} ```{.c filename="C"} char A[32][32], B[32], C[32]; void main() { int i, j; for (i = 0; i < 32; i++) for (j = 0; j < 32; j++) C[i] = A[i][j] * B[j] + C[i]; } ``` Producte d'una matriu de bytes per un vector. ::: Els elements d'`A`, `B` i `C` són bytes. Tots els elements de `C` han estat prèviament inicialitzats a zero. `A` s'emmagatzema a partir de l'adreça 0 (adreces 0..1023), `B` a continuació (adreces 1024..1055) i `C` tot seguit (adreces 1056..1087). Les variables `i` i `j` estan en registres. El computador disposa d'una memòria cau de correspondència directa amb 4 línies i blocs de 32 bytes, amb escriptura immediata. Suposant que en iniciar-se l'execució la memòria cau és buida, calculeu la taxa d'encerts. :::: ::: {#exr-t7-cache-alternatives} Es vol dissenyar una nova versió d'un processador que disposa d'una memòria cau de correspondència directa amb 4 línies i blocs d'una paraula (32 bits). La nova versió tindrà el doble de capacitat. Es consideren dues alternatives: - **Alternativa 1**: doblar el nombre de línies (8 línies d'una paraula). - **Alternativa 2**: doblar la mida del bloc (4 línies de 2 paraules). a) Proposeu una seqüència de referències a paraules de memòria principal tal que la taxa d'encerts de l'alternativa 1 sigui major que la de l'alternativa 2. b) Proposeu una seqüència de referències tal que la taxa d'encerts de l'alternativa 2 sigui major que la de l'alternativa 1. c) Raoneu quina característica dels programes s'explota en major mesura en cadascuna de les dues alternatives. ::: ## Rendiment *Vegeu @sec-rendiment-mc; en particular, @eq-tam i @eq-texe.* ::: {#exr-t7-rend-taxa-traffic} Una mesura possible del rendiment d'una memòria cau és la taxa de tràfic, definida com el quocient entre el nombre de bytes transferits des de/cap a la memòria principal en un sistema amb memòria cau i el nombre de bytes transferits en un sistema sense memòria cau. Suposeu que totes les referències a memòria són de paraules de 32 bits. Calculeu la taxa de tràfic en funció de la taxa d'encerts ($h$), la mida del bloc en bytes ($B$), el percentatge d'escriptures ($p_e$) i el percentatge de blocs reemplaçats que han estat modificats ($p_m$) per a: a) Escriptura immediata sense assignació. b) Escriptura retardada amb assignació. ::: ::: {#exr-t7-rend-politiques} Es vol definir la política d'escriptura de la memòria cau d'un processador. Es consideren dues alternatives: (1) escriptura immediata sense assignació i (2) escriptura retardada amb assignació. Mitjançant simulació s'han obtingut les mesures següents: - Percentatge d'escriptures ($p_e$): 20 %. - Percentatge de blocs modificats sobre el total de blocs reemplaçats ($p_m$): 33,33 %. - Taxa d'encerts en el cas (1): 0,9. - Taxa d'encerts en el cas (2): 0,85. El temps d'accés en cas d'encert ($t_h$) és 10 ns. La lectura o escriptura d'un bloc de memòria principal ($t_{bloc}$) requereix 100 ns. a) Calculeu el temps d'accés mitjà (TAM) en ambdues alternatives. b) Indiqueu quina alternativa seria la més ràpida per a un programa que només fes lectures. ::: ::: {#exr-t7-rend-cpi-separat} Considereu una CPU amb memòria cau en què s'han observat les característiques següents: - $\text{CPI}_{ideal}$: 1,5 cicles/instrucció. - Temps de cicle ($t_c$): 10 ns. - Nombre de referències per instrucció ($n_r$): 1,6. - Memòries cau d'instruccions i dades separades. - Memòria cau de dades amb escriptura retardada amb assignació. | Característica | MC d'instruccions | MC de dades | | :--- | :---: | :---: | | Accessos per instrucció | 1 | 0,6 | | Percentatge d'escriptures ($p_e$) | — | 40 % | | Percentatge de blocs modificats ($p_m$) | — | 20 % | | Taxa de fallades ($m$) | 4 % | 10 % | | Penalització bloc no modificat ($t_p$) | 10 cicles | 15 cicles | | Penalització bloc modificat ($t_p$) | — | 20 cicles | | Temps d'encert ($t_h$) | 1 cicle | 1 cicle | a) Quin és el temps d'accés mitjà (TAM) en cicles? b) Quin és el temps mitjà d'execució d'una instrucció ($t_{exe}$) en ns? ::: ::: {#exr-t7-rend-cpi-unica} Considereu una CPU amb memòria cau en què s'han observat les característiques següents: - $\text{CPI}_{ideal}$: 1,8 cicles/instrucció. - Temps de cicle ($t_c$): 10 ns. - Nombre de referències per instrucció ($n_r$): 1,4. - Mida del bloc: 8 bytes. - Política d'escriptura retardada amb assignació. - Temps d'encert ($t_h$): 1 cicle. - Temps de servei d'MP per llegir/escriure blocs ($t_{bloc}$): 15 cicles. - Percentatge d'escriptures ($p_e$): 15 %. - Percentatge de blocs modificats ($p_m$): 20 %. - Taxa d'encerts ($h$): 90 %. a) Quin és el temps de penalització ($t_p$) en cas que el bloc estigui modificat? I en cas que no ho estigui? b) Quin és el temps d'accés mitjà (TAM) en cicles? c) Quin és el temps mitjà d'execució d'una instrucció en ns? ::: ::: {#exr-t7-rend-mida-bloc} A l'hora de dissenyar una memòria cau d'instruccions de 8 KiB es dubta entre dues mides de bloc, amb les taxes de fallades mesurades següents: - 8 bytes: 16 %. - 16 bytes: 10 %. a) Calculeu el temps d'accés mitjà (TAM) sabent que: - El temps d'accés en cas d'encert ($t_h$) és 1 cicle. - El temps de servei d'MP per a blocs de 8 bytes és 6 cicles; per a blocs de 16 bytes és 12 cicles. b) Quant ocuparan totes les etiquetes en cadascuna de les dues opcions, sabent que: - MP té $2^{32}$ bytes. - Les memòries cau són de correspondència directa. - La unitat mínima d'accés a memòria és el byte. ::: ## Associativitat i multinivell *Vegeu @sec-associativa-conjunts, @sec-politica-reemplacament i @sec-multinivell.* ::: {#exr-t7-assoc-2vies} Considereu un processador de 16 bits (paraules i adreces de 16 bits) amb una memòria cau amb les característiques següents: - Correspondència associativa de 2 vies. - Mida total: 1024 bytes. - Mida de bloc: 16 bytes. - Política d'escriptura immediata sense assignació. - Algorisme de reemplaçament: LRU. Ompliu la taula següent a partir de la seqüència de referències donada (L byte = lectura d'1 byte, L paraula = lectura d'una paraula, de 2 bytes, E byte = escriptura d'1 byte, E paraula = escriptura d'una paraula): | Tipus | Adreça (hex) | Bloc MP | Conjunt MC | Encert/Fallada | Lectura MP (S/N, adreça, mida) | Escriptura MP (S/N, adreça, mida) | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | L byte | `A930` | | | | | | | L paraula | `B930` | | | | | | | E byte | `A972` | | | | | | | E paraula | `A932` | | | | | | | E byte | `C935` | | | | | | | L paraula | `C934` | | | | | | | E byte | `B976` | | | | | | | E paraula | `B936` | | | | | | | L byte | `B938` | | | | | | | L paraula | `A978` | | | | | | : {tbl-colwidths="[13,13,13,14,19,14,14]"} ::: ::: {#exr-t7-assoc-versions} Sobre un sistema amb una memòria cau de dades amb 64 conjunts, 4 vies per conjunt, 32 bytes per bloc i algorisme LRU, s'executen dues versions d'una mateixa aplicació: ```{.c filename="C"} int A[128][1024]; // emmagatzemada a partir de l'adreça 0 // Versió A sumA = 0; for (i = 0; i < 128; i++) for (j = 0; j < 1024; j++) sumA = sumA + A[i][j]; // Versió B sumA = 0; for (j = 0; j < 1024; j++) for (i = 0; i < 128; i++) sumA = sumA + A[i][j]; ``` Indiqueu quantes fallades hi ha a la memòria cau de dades per a cadascuna de les dues versions. Considereu que `i`, `j` i `sumA` estan en registres. ::: ::: {#exr-t7-assoc-multinivell} El subsistema de memòria d'un computador està organitzat en tres nivells: L1 (4 línies amb blocs de 4 bytes, correspondència directa), L2 (16 línies amb blocs de 4 bytes, associativa de 2 vies, LRU) i MP (1 MiB). En cas de fallada a L1 es comprova L2; si hi és, es copia a L1 sense accedir a MP. Si no hi és a L2, s'accedeix a MP i es copia a les dues memòries cau. La taxa d'encerts de cada nivell es defineix com $h_{L1} = \text{encerts a L1} / \text{peticions a L1}$, i igualment $h_{L2}$. Donada la seqüència de 7 adreces de lectura següent, repetida 4 vegades (28 accessos en total): `0, 5, 10, 12, 34, 0, 66` a) Suposant les memòries cau inicialment buides, calculeu les taxes $h_{L1}$ i $h_{L2}$. b) Calculeu de nou les taxes $h_{L1}$ i $h_{L2}$ suposant que l'algorisme de reemplaçament de L2 és FIFO. ::: ::: {#exr-t7-assoc-tam} Es vol dissenyar una memòria cau multinivell (L1 i L2). Es coneixen les dades següents: - El temps de servei de L1 en cas d'encert és $t_{h_{L1}}$; en cas de fallada cal afegir-hi el temps de servei de L2. - El temps de servei de L2 en cas d'encert és $t_{h_{L2}}$; en cas de fallada cal afegir-hi la penalització $t_p$ (temps d'accés a MP). - $m_{L1}$: taxa de fallades a L1. - $m_{L2}$: taxa de fallades local a L2 (fallades a L2 / accessos a L2). Obteniu l'expressió del temps d'accés mitjà (TAM) en cicles, en funció de $t_{h_{L1}}$, $t_{h_{L2}}$, $t_p$, $m_{L1}$ i $m_{L2}$. ::: ::: {#exr-t7-assoc-completament} Es disposa d'un processador de 8 bits amb una memòria cau completament associativa amb les característiques següents: - Nombre de línies: 4. - Mida del bloc: 8 bytes. - Algorisme de reemplaçament: LRU. - Política d'escriptura retardada amb assignació. - Temps d'encert ($t_h$): 1 cicle. - Temps de servei d'MP ($t_{bloc}$): 10 cicles. a) Temps de servei en cas de fallada de lectura que reemplaça un bloc no modificat. b) Temps de servei en cas de fallada de lectura que reemplaça un bloc modificat. c) Temps de servei en cas de fallada d'escriptura que reemplaça un bloc no modificat. d) Temps de servei en cas de fallada d'escriptura que reemplaça un bloc modificat. e) Suposant la memòria cau inicialment buida i la llista d'accessos (en decimal, L = lectura, E = escriptura): `2L, 9L, 16L, 2L, 33E, 42E, 33L, 2L, 17L, 27E, 43L, 3L, 44L, 46L, 3L, 14L, 17L, 6L, 35L` - Indiqueu per a cada accés si produeix encert, fallada amb reemplaçament (indicant el número del bloc reemplaçat) o fallada sense reemplaçament. - Calculeu el temps total de servei de la llista d'accessos. ::: ## Tipologia de les fallades *Vegeu @sec-tipologia-fallades i @cau-tres-c.* ::: {#exr-t7-fallades-tipologia} Una memòria cau de correspondència directa té 8 línies amb blocs de 4 bytes. Considereu les seqüències d'accés a bytes següents (les adreces estan en decimal): - Seqüència A: 0, 4, 8, 12, 16, 20, 24, 28, 0, 4, 8, 12. - Seqüència B: 0, 4, 8, 12, 0, 4, 8, 12, 0, 4, 8, 12. - Seqüència C: 0, 32, 0, 32, 0, 32, 0, 32. a) Per a cada seqüència, calculeu el nombre de fallades i classifiqueu-les en fallades d'arrencada en fred (*cold-start*), de conflicte o de capacitat. b) Per a la seqüència C, quin canvi de disseny de la memòria cau eliminaria les fallades de conflicte? Justifiqueu-ho. c) Una memòria cau associativa de 2 vies (mateixa capacitat total) milloraria els resultats de la seqüència C? I de la seqüència B? ::: :::: {#exr-t7-fallades-programa} Considereu el programa C del @lst-t7-fallades-programa, on `N = 256` i els elements d'`A` i `B` són enters de 4 bytes: ::: {#lst-t7-fallades-programa} ```{.c filename="C"} int A[N], B[N]; void main() { int i, suma = 0; for (i = 0; i < N; i++) suma += A[i] + B[i]; } ``` Suma dels elements de `A` i de `B`. ::: `A` s'emmagatzema a partir de l'adreça `0x000` i `B` a partir de `0x400`. La memòria cau té correspondència directa, 16 línies amb blocs de 32 bytes i política d'escriptura immediata. **Nota**: en aquest problema, excepcionalment, les adreces s'escriuen en format reduït, sense els zeros de l'esquerra. Totes són inferiors a `0x1000`, i per saber a quina línia de la memòria cau va cada bloc només calen els bits de menys pes (els 5 de desplaçament i els 4 d'índex). a) Quantes fallades d'arrencada en fred es produeixen en el primer recorregut d'`A`? I en el de `B`? b) Es produeixen fallades de conflicte entre `A` i `B`? Raoneu la resposta calculant a quines línies de la memòria cau es mapen. c) Si `B` comencés a `0x600` en comptes de `0x400`, canviaria la resposta a l'apartat b)? ::::