Tema 7: Memòria cau

25.1 Disseny bàsic

Exemple 25.1: Solució: adreçament i seqüència de blocs

Memòria principal de 64 bytes (adreces de 6 bits), memòria cau de 16 bytes, correspondència directa, blocs de 4 bytes ($b = 2$). L’MC té $16/4 = 4$ línies ($n_l = 2$). L’adreça es descompon en:

\[A = \underbrace{\cdot\cdot}_{2\text{ bits etiqueta}} \; \underbrace{\cdot\cdot}_{2\text{ bits índex}} \; \underbrace{\cdot\cdot}_{2\text{ bits desplaçament}}\]

a) Adreça 0x39 $= 57 = 111001_2$:

\[\underbrace{11}_{\text{etiqueta}=3}\;\underbrace{10}_{\text{índex}=2}\;\underbrace{01}_{\text{desplaçament}=1}\]

La dada correspon a la línia 2, amb etiqueta 3 i byte 1 dins el bloc.

b) Mapatge de blocs a línies ($\text{índex} = \text{bloc} \bmod 4$):

Bloc	0	1	3	7	10	12	15
Línia	0	1	3	3	2	0	3

Evolució de la seqüència (MC inicialment buida):

#	Bloc	Línia	Contingut línia	En/F
1	0	0	buida	F
2	1	1	buida	F
3	0	0	bloc 0	En
4	3	3	buida	F
5	12	0	bloc 0 $\neq$ 12	F
6	10	2	buida	F
7	3	3	bloc 3	En
8	7	3	bloc 3 $\neq$ 7	F
9	12	0	bloc 12	En
10	15	3	bloc 7 $\neq$ 15	F
11	3	3	bloc 15 $\neq$ 3	F

Encerts: 3. Fallades: 8. Taxa d’encerts: $h = 3/11 \approx 27{,}3\ \%$.

De les 8 fallades, 7 són d’arrencada en fred (cold-start: el primer accés a cadascun dels blocs 0, 1, 3, 12, 10, 7 i 15) i la de l’accés 11 és de conflicte: el bloc 3, carregat a l’accés 4, ha estat expulsat pels blocs 7 i 15, que competeixen amb ell per la línia 3 (en una memòria cau completament associativa de la mateixa capacitat, aquest accés seria un encert). El conflicte a la línia 3 és especialment greu: els tres blocs s’hi expulsen l’un a l’altre, i el bloc 3 només hi encerta un cop (a l’accés 7).

Exemple 25.2: Solució: polítiques d’escriptura

Enunciat: Problema 16.2.

Processador de 16 bits. MC de correspondència directa, 256 bytes, blocs de 16 bytes. L’MC té $256/16 = 16$ línies. Descomposició de l’adreça (16 bits):

\[A = \underbrace{\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot}_{8\text{ bits etiqueta}} \; \underbrace{\cdot\cdot\cdot\cdot}_{4\text{ bits índex}} \; \underbrace{\cdot\cdot\cdot\cdot}_{4\text{ bits desplaçament}}\]

Exemples de descomposició:

0x4534: etiqueta = 0x45, índex = 0x3, desplaçament = 0x4.
0x13A4: etiqueta = 0x13, índex = 0xA, desplaçament = 0x4.
0x60A0: etiqueta = 0x60, índex = 0xA, desplaçament = 0x0.

Cada accés L o E transfereix una paraula de 2 bytes (processador de 16 bits).

a) Escriptura immediata sense assignació.

Comportament per tipus d’accés:

L encert: es llegeix de l’MC. Cap tràfic amb MP.
L fallada: es llegeix el bloc sencer d’MP (16 B), es carrega a l’MC i se’n llegeix la dada.
E encert: s’escriu a l’MC i a l’MP (2 B, a través de la memòria intermèdia d’escriptura).
E fallada: s’escriu directament a MP (2 B). L’MC no s’altera.

Les columnes Lect. MC i Escr. MC indiquen si l’accés llegeix o escriu la matriu de dades de l’MC (la dada lliurada a la CPU, la càrrega d’un bloc, l’escriptura d’una dada o la còpia d’un bloc modificat cap a MP).

#	Tipus	Adr.	Etiq.	Índ.	En/F	Llegits MP	Escrits MP	Lect. MC	Escr. MC
1	L	`4534`	`45`	`3`	F	16	0	S	S
2	L	`4568`	`45`	`6`	F	16	0	S	S
3	E	`13A4`	`13`	`A`	F	0	2	N	N
4	E	`13A8`	`13`	`A`	F	0	2	N	N
5	L	`3560`	`35`	`6`	F	16	0	S	S
6	E	`453C`	`45`	`3`	En	0	2	N	S
7	E	`60A0`	`60`	`A`	F	0	2	N	N
8	L	`453C`	`45`	`3`	En	0	0	S	N
9	E	`3900`	`39`	`0`	F	0	2	N	N
10	L	`A238`	`A2`	`3`	F	16	0	S	S

Justificació dels casos clau:

#3 i #4 (E 13A4, E 13A8): ambdues escriptures fallen a la línia A (buida). Sense assignació, cap de les dues carrega el bloc → la línia resta buida i la segona escriptura també falla.
#6 (E 453C): la línia 3 conté el bloc carregat al pas 1 (etiqueta 45) → encert. S’escriu a MC i a MP (2 B).
#8 (L 453C): la línia 3 encara conté l’etiqueta 45 → encert.
#10 (L A238): etiqueta A2 $\neq$ 45 a la línia 3 → fallada, reemplaça.

b) Escriptura retardada amb assignació.

Comportament per tipus d’accés:

L/E encert: accés a MC. Cap tràfic amb MP. En cas d’escriptura, $D \leftarrow 1$.
L/E fallada, $D=0$: es llegeix el bloc d’MP (16 B) i es carrega a l’MC.
L/E fallada, $D=1$: es llegeix el bloc antic de l’MC i es copia a MP (16 B), i després es llegeix el nou bloc d’MP (16 B) i es carrega a l’MC.

A les columnes Lect. MC i Escr. MC, tota fallada escriu l’MC (càrrega del bloc i, si és E, la dada); l’MC es llegeix quan la dada es lliura a la CPU (L) o quan cal copiar un bloc modificat cap a MP. La columna D dona el bit de modificació de la línia abans de l’accés i, si canvia, també el de després (abans→després).

#	Tipus	Adr.	Etiq.	Índ.	En/F	D	Llegits MP	Escrits MP	Lect. MC	Escr. MC
1	L	`4534`	`45`	`3`	F	0	16	0	S	S
2	L	`4568`	`45`	`6`	F	0	16	0	S	S
3	E	`13A4`	`13`	`A`	F	0→1	16	0	N	S
4	E	`13A8`	`13`	`A`	En	1	0	0	N	S
5	L	`3560`	`35`	`6`	F	0	16	0	S	S
6	E	`453C`	`45`	`3`	En	0→1	0	0	N	S
7	E	`60A0`	`60`	`A`	F	1	16	16	S	S
8	L	`453C`	`45`	`3`	En	1	0	0	S	N
9	E	`3900`	`39`	`0`	F	0→1	16	0	N	S
10	L	`A238`	`A2`	`3`	F	1→0	16	16	S	S

Justificació dels casos clau:

#3 (E 13A4): amb assignació, es carrega el bloc d’MP (16 B) a la línia A i s’escriu la dada a l’MC ($D \leftarrow 1$).
#4 (E 13A8): encert (el bloc és a la línia A des del pas 3). S’escriu a MC, $D$ ja és 1.
#7 (E 60A0): la línia A conté l’etiqueta 13 amb $D=1$. Fallada: cal copiar primer el bloc antic a MP (16 B escrits), després carregar el nou bloc d’MP (16 B llegits), i finalment escriure la dada ($D \leftarrow 1$).
#10 (L A238): la línia 3 conté l’etiqueta 45 amb $D=1$ (des del pas 6). Fallada amb còpia del bloc modificat a MP: 16 B escrits + 16 B llegits.

c) Resum comparatiu:

	Escr. immediata s/a	Escr. retardada a/a
Taxa de fallades	80 % (8/10)	70 % (7/10)
Bytes llegits d’MP	64	112
Bytes escrits a MP	10	32
Bytes totals MP	74	144

L’escriptura retardada amb assignació té una taxa de fallades inferior (l’accés #4 passa de fallada a encert perquè el bloc es va assignar al pas 3), però genera més tràfic total amb MP: cada assignació per escriptura carrega un bloc de 16 B, i cada escriptura a MP d’un bloc modificat n’escriu 16 B més. L’escriptura immediata sense assignació genera menys tràfic perquè les escriptures que fallen només transfereixen la paraula escrita (2 B), sense carregar blocs sencers.

25.2 Rendiment

Exemple 25.3: Solució: comparació de polítiques d’escriptura

Enunciat: Problema 16.6.

Dades: $p_e = 20\ \%$, $p_m = 1/3$, $t_h = 10$ ns, $t_{bloc} = 100$ ns, $h_1 = 0{,}9$ (immediata s/a), $h_2 = 0{,}85$ (retardada a/a).

a) Aplicant Equació 7.1, amb el temps de penalització mitjà per fallada de cada política (Essencial 7.2; per a l’escriptura retardada, Essencial 7.3). Se suposa que la taxa de fallades és independent del tipus d’accés: així, la fracció de fallades que corresponen a escriptures coincideix amb el percentatge d’escriptures $p_e$.

Escriptura immediata sense assignació ($m_1 = 0{,}10$): les fallades de lectura paguen $t_{bloc} + t_h$ i les d’escriptura paguen 0 (la memòria intermèdia absorbeix l’escriptura):

\[t_{p_1} = (1 - p_e)(t_{bloc} + t_h) = 0{,}80 \cdot 110 = 88 \text{ ns}\]

\[\text{TAM}_1 = t_h + m_1 \cdot t_{p_1} = 10 + 0{,}10 \cdot 88 = \mathbf{18{,}8} \text{ ns}\]

Escriptura retardada amb assignació ($m_2 = 0{,}15$): la penalització depèn de si el bloc expulsat està modificat:

\[t_{p_2} = (1 + p_m) \cdot t_{bloc} + t_h = \frac{4}{3} \cdot 100 + 10 = 133{,}3 + 10 \approx 143{,}3 \text{ ns}\]

\[\text{TAM}_2 = t_h + m_2 \cdot t_{p_2} = 10 + 0{,}15 \cdot 143{,}3 \approx 10 + 21{,}5 = \mathbf{31{,}5} \text{ ns}\]

L’escriptura immediata sense assignació és més ràpida ($18{,}8$ vs. $31{,}5$ ns). Té una taxa de fallades inferior ($10\ \%$ vs. $15\ \%$) i, sobretot, una penalització mitjana per fallada molt menor: les fallades d’escriptura no paguen penalització i les de lectura no generen escriptures de blocs modificats a MP. La penalització mitjana de l’escriptura retardada és un 63 % més gran ($143{,}3$ vs. $88$ ns).

b) Per a un programa de només lectures ($p_e = 0$), ambdues polítiques es comporten de manera idèntica: en absència d’escriptures, no hi ha diferència entre escriptura immediata i retardada ($p_m = 0$, cap bloc es modifica), i ambdues polítiques carreguen blocs a l’MC exactament igual en les fallades de lectura. La taxa de fallades seria la mateixa per a ambdues i la penalització també ($t_{bloc} + t_h = 110$ ns), de manera que cap de les dues alternatives seria més ràpida que l’altra.

Exemple 25.4: Solució: MC separades d’instruccions i dades

Enunciat: Problema 16.7.

Dades: $\text{CPI}_{ideal} = 1{,}5$, $t_c = 10$ ns, $n_r = 1{,}6$ referències/instrucció. MC de dades amb escriptura retardada amb assignació.

	MC Instruccions	MC Dades
Accessos per instrucció	1	0,6
$m$	4 %	10 %
$t_p$ (bloc no modif.)	10 cicles	15 cicles
$t_p$ (bloc modif.)	—	20 cicles
$p_m$	—	20 %

a) Penalització per fallada a l’MC de dades (escriptura retardada):

\[t_{pd} = (1 - p_m) \cdot 15 + p_m \cdot 20 = 0{,}80 \cdot 15 + 0{,}20 \cdot 20 = 12 + 4 = 16 \text{ cicles}\]

El percentatge d’escriptures ($p_e = 40\ \%$) no és necessari per resoldre el problema: la penalització de l’MC de dades ja es dona directament en funció de si el bloc reemplaçat és modificat o no.

TAM ponderat per la fracció d’accessos de cada MC:

\[\text{TAM} = t_h + \frac{1}{n_r} \cdot m_i \cdot t_{pi} + \frac{0{,}6}{n_r} \cdot m_d \cdot t_{pd}\]

\[= 1 + \frac{1}{1{,}6} \cdot 0{,}04 \cdot 10 + \frac{0{,}6}{1{,}6} \cdot 0{,}10 \cdot 16\]

\[= 1 + 0{,}625 \cdot 0{,}4 + 0{,}375 \cdot 1{,}6 = 1 + 0{,}25 + 0{,}6 = \mathbf{1{,}85} \text{ cicles}\]

b) Cicles de penalització per instrucció:

\[\text{CPI}_{penal,i} = m_i \cdot 1 \cdot t_{pi} = 0{,}04 \cdot 10 = 0{,}4 \text{ cicles/instr.}\]

\[\text{CPI}_{penal,d} = m_d \cdot 0{,}6 \cdot t_{pd} = 0{,}10 \cdot 0{,}6 \cdot 16 = 0{,}96 \text{ cicles/instr.}\]

\[\text{CPI} = \text{CPI}_{ideal} + \text{CPI}_{penal,i} + \text{CPI}_{penal,d} = 1{,}5 + 0{,}4 + 0{,}96 = 2{,}86\]

\[t_{exe} = \text{CPI} \cdot t_c = 2{,}86 \cdot 10 = \mathbf{28{,}6} \text{ ns/instrucció}\]

Observació: les fallades de memòria cau incrementen el CPI un $90{,}7\ \%$ respecte del valor ideal (d’$1{,}5$ a $2{,}86$). L’MC de dades, amb només el $37{,}5\ \%$ dels accessos, contribueix el $70{,}6\ \%$ de la penalització ($0{,}96 / 1{,}36$), a causa de la seva taxa de fallades més alta i la penalització per les escriptures de blocs modificats a MP.

25.3 Associativitat i multinivell

Exemple 25.5: Solució: associativa de 2 vies

Enunciat: Problema 16.10.

Processador de 16 bits. MC associativa de 2 vies, 1 KiB, blocs de 16 bytes, escriptura immediata sense assignació, LRU. L’MC té $1024/16 = 64$ línies organitzades en $64/2 = 32$ conjunts de 2 vies.

Descomposició de l’adreça (16 bits):

\[A = \underbrace{\cdot\cdot\cdot\cdot\cdot\cdot\cdot}_{7\text{ bits etiqueta}} \; \underbrace{\cdot\cdot\cdot\cdot\cdot}_{5\text{ bits conjunt}} \; \underbrace{\cdot\cdot\cdot\cdot}_{4\text{ bits desplaçament}}\]

El conjunt es determina pels bits [8:4] i l’etiqueta pels bits [15:9]. Descomposició de les adreces:

Adreça	Bloc MP	Conjunt	Etiqueta
`A930`	`A93`	19 (`0x13`)	`0x54`
`B930`	`B93`	19	`0x5C`
`A972`	`A97`	23 (`0x17`)	`0x54`
`A932`	`A93`	19	`0x54`
`C935`	`C93`	19	`0x64`
`C934`	`C93`	19	`0x64`
`B976`	`B97`	23	`0x5C`
`B936`	`B93`	19	`0x5C`
`B938`	`B93`	19	`0x5C`
`A978`	`A97`	23	`0x54`

Exemple de descomposició per a 0xA972:

\[\texttt{A972}_{16} = \underbrace{1010100}_{0\texttt{x54}}\;\underbrace{10111}_{23}\;\underbrace{0010}_{2}\]

Els bits [8:4] són $10111_2 = 23$, no $00111_2 = 7$. El bit 8 (que forma part del dígit hex 9 = $1001_2$) és 1.

La seqüència accedeix a dos conjunts: 19 (7 accessos) i 23 (3 accessos). Amb escriptura immediata sense assignació, les escriptures que fallen no modifiquen l’MC.

Evolució del conjunt 19 (2 vies):

#	Accés	En/F	Via 0	Via 1	LRU
1	L `A930` (0x54)	F	0x54	—	v1
2	L `B930` (0x5C)	F	0x54	0x5C	v0
4	E `A932` (0x54)	En	0x54	0x5C	v1
5	E `C935` (0x64)	F	0x54	0x5C	(s/a)
6	L `C934` (0x64)	F	0x54	0x64	v0
8	E `B936` (0x5C)	F	0x54	0x64	(s/a)
9	L `B938` (0x5C)	F	0x5C	0x64	v1

#4: encert a via 0 (etiqueta 0x54). S’escriu a MC i a MP (2 B). LRU passa a v1.
#5: fallada, però és E sense assignació → MC inalterada, LRU inalterat.
#6: fallada de lectura. LRU = v1 (des de #4; #5 no altera res) → s’expulsa v1 (0x5C) i es carrega 0x64.
#8: E fallada sense assignació → MC inalterada.
#9: L fallada. LRU = v0 (des de #6) → s’expulsa v0 (0x54) i es carrega 0x5C.

Evolució del conjunt 23 (2 vies):

#	Accés	En/F	Via 0	Via 1	LRU
3	E `A972` (0x54)	F	—	—	(s/a)
7	E `B976` (0x5C)	F	—	—	(s/a)
10	L `A978` (0x54)	F	0x54	—	v1

Les escriptures #3 i #7 fallen, però sense assignació no carreguen cap bloc. El conjunt 23 resta buit fins a la lectura #10.

Taula resum:

#	Tipus	Adr.	Bloc	Conj.	En/F	Lectura MP	Escriptura MP
1	L byte	`A930`	`A93`	19	F	S, `A930`, 16 B	N
2	L paraula	`B930`	`B93`	19	F	S, `B930`, 16 B	N
3	E byte	`A972`	`A97`	23	F	N	S, `A972`, 1 B
4	E paraula	`A932`	`A93`	19	En	N	S, `A932`, 2 B
5	E byte	`C935`	`C93`	19	F	N	S, `C935`, 1 B
6	L paraula	`C934`	`C93`	19	F	S, `C930`, 16 B	N
7	E byte	`B976`	`B97`	23	F	N	S, `B976`, 1 B
8	E paraula	`B936`	`B93`	19	F	N	S, `B936`, 2 B
9	L byte	`B938`	`B93`	19	F	S, `B930`, 16 B	N
10	L paraula	`A978`	`A97`	23	F	S, `A970`, 16 B	N

Encerts: 1 (pas 4). Fallades: 9. Taxa de fallades: 90 %.

La taxa de fallades és molt alta perquè la seqüència barreja accessos a tres blocs diferents dins el conjunt 19 (etiquetes 0x54, 0x5C i 0x64), i les escriptures sense assignació impedeixen que els blocs escrits s’instal·lin a l’MC per a futurs accessos.

Exemple 25.6: Solució: TAM multinivell

Enunciat: Problema 16.13.

Un accés a memòria segueix la cadena L1 → L2 → MP:

S’accedeix a L1 amb temps $t_{h_{L1}}$.
En cas de fallada a L1 (probabilitat $m_{L1}$), s’accedeix a L2 amb temps $t_{h_{L2}}$.
En cas de fallada a L2 (probabilitat $m_{L2}$, local), s’accedeix a MP amb penalització $t_p$.

El temps mitjà d’accés és la suma del temps de L1 més les penalitzacions ponderades:

\[\boxed{\text{TAM} = t_{h_{L1}} + m_{L1} \cdot \bigl(t_{h_{L2}} + m_{L2} \cdot t_p\bigr)}\]

La fórmula coincideix amb Equació 7.5. Desenvolupant:

\[\text{TAM} = t_{h_{L1}} + m_{L1} \cdot t_{h_{L2}} + m_{L1} \cdot m_{L2} \cdot t_p\]

El terme $m_{L1} \cdot m_{L2}$ és la taxa de fallades global de L2 (proporció de tots els accessos que fallen tant a L1 com a L2 i arriben a MP).

Observació: en un sistema ben dissenyat, $t_{h_{L1}}$ domina el TAM perquè afecta tots els accessos. Per això L1 s’optimitza per minimitzar $t_{h_{L1}}$, mentre que L2 s’optimitza per minimitzar $m_{L2}$.

25.4 Tipologia de les fallades

Exemple 25.7: Solució: classificació de fallades

Enunciat: Problema 16.15.

MC de correspondència directa, 8 línies, blocs de 4 bytes ($b = 2$). Capacitat total: $8 \times 4 = 32$ bytes. El mapatge és $\text{línia} = \text{bloc} \bmod 8$, on $\text{bloc} = \text{adreça} \div 4$. La classificació de les fallades segueix les tres C (Secció 7.8, Essencial 7.4).

a) Seqüència A: 0, 4, 8, 12, 16, 20, 24, 28, 0, 4, 8, 12

Blocs accedits: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3. Cadascun ocupa una línia diferent ($k \bmod 8 = k$ per a $k = 0\ldots7$). El working set (8 blocs) cap exactament a l’MC.

Accés	Bloc	Línia	Resultat	Tipus
0	0	0	Fallada	Obligatòria
4	1	1	Fallada	Obligatòria
8	2	2	Fallada	Obligatòria
12	3	3	Fallada	Obligatòria
16	4	4	Fallada	Obligatòria
20	5	5	Fallada	Obligatòria
24	6	6	Fallada	Obligatòria
28	7	7	Fallada	Obligatòria
0	0	0	Encert	—
4	1	1	Encert	—
8	2	2	Encert	—
12	3	3	Encert	—

Total: 8 fallades (totes obligatòries), 4 encerts. Cap fallada de conflicte (cada bloc té línia pròpia) ni de capacitat (el working set cap a l’MC).

Seqüència B: 0, 4, 8, 12, 0, 4, 8, 12, 0, 4, 8, 12

Blocs: 0, 1, 2, 3 (repetits 3 vegades). Quatre blocs, cadascun amb línia diferent: el working set (4 blocs) és la meitat de la capacitat.

Primer recorregut (0, 4, 8, 12): 4 fallades d’arrencada en fred.
Segon i tercer recorreguts: tot encerts (els 4 blocs continuen a l’MC).

Total: 4 fallades (totes obligatòries), 8 encerts.

Seqüència C: 0, 32, 0, 32, 0, 32, 0, 32

Blocs: 0, 8, 0, 8, … El bloc 0 i el bloc 8 es mapen tots dos a la línia 0 ($0 \bmod 8 = 0$, $8 \bmod 8 = 0$).

Accés	Bloc	Resultat	Tipus
0	0	Fallada	Obligatòria
32	8	Fallada	Obligatòria (expulsa bloc 0)
0	0	Fallada	Conflicte
32	8	Fallada	Conflicte
0	0	Fallada	Conflicte
32	8	Fallada	Conflicte
0	0	Fallada	Conflicte
32	8	Fallada	Conflicte

Total: 8 fallades (2 obligatòries, 6 de conflicte), 0 encerts. El working set és de només 2 blocs (molt inferior a la capacitat de 8 línies), però tots dos competeixen per la mateixa línia. L’MC té 7 línies buides que no s’aprofiten.

b) Per eliminar les fallades de conflicte de la seqüència C, cal que els blocs 0 i 8 puguin coexistir a l’MC. La solució és augmentar l’associativitat a 2 o més vies: amb 2 vies, el conjunt 0 tindria dues posicions i ambdós blocs hi cabrien simultàniament.

c) Amb una MC associativa de 2 vies de la mateixa capacitat total (8 línies → 4 conjunts de 2 vies):

Seqüència C: blocs 0 i 8 es mapen al conjunt $0 \bmod 4 = 0$ i $8 \bmod 4 = 0$. Amb 2 vies, ambdós hi caben. Després de les 2 fallades d’arrencada en fred, els 6 accessos restants serien encerts. Sí, millora (de 8 a 2 fallades).
Seqüència B: blocs 0, 1, 2, 3 es mapen als conjunts 0, 1, 2, 3. Cada bloc ocupa un conjunt diferent: no hi ha conflictes ni amb correspondència directa. No millora (les 4 fallades d’arrencada en fred són igualment inevitables).

Exemple 25.8: Solució: conflictes entre dos vectors

Enunciat: Problema 16.16.

A[256] d’enters de 4 bytes, des de l’adreça 0x000 (1 KiB, fins a 0x3FF). B[256] des de 0x400 (fins a 0x7FF). MC de correspondència directa, 16 línies, blocs de 32 bytes. Variables i i suma en registres.

Paràmetres: bloc = 32 bytes = 8 enters per bloc. A i B ocupen cadascun $256/8 = 32$ blocs.

a) En el primer recorregut, cada bloc s’accedeix per primera vegada: 32 fallades d’arrencada en fred per a A i 32 per a B (una per bloc, quan s’accedeix a $A[0], A[8], A[16], \ldots, A[248]$ i anàlogament per a $B$).

b) Mapatge de cada vector:

Bloc $k$ d’A ($k = 0\ldots31$): adreça base $= 32k$. Número de bloc $= k$. Línia $= k \bmod 16$.
Bloc $k$ de B ($k = 0\ldots31$): adreça base $= \texttt{0x400} + 32k$. Número de bloc $= 1024/32 + k = 32 + k$. Línia $= (32 + k) \bmod 16 = k \bmod 16$.

El bloc $k$ d’A i el bloc $k$ de B es mapen a la mateixa línia ($k \bmod 16$). Això és perquè la distància entre A i B ($\texttt{0x400} - \texttt{0x000} = 1024$ bytes, 1 KiB, que són 32 blocs) és un múltiple exacte del nombre de línies de l’MC (16).

En el bucle, els accessos s’intercalen: $A[i], B[i], A[i+1], B[i+1], \ldots$ Dins de cada grup de 8 iteracions (que correspon a un bloc), l’accés a $A[i]$ carrega el bloc d’A a la línia $k$, i l’accés a $B[i]$ el reemplaça pel bloc de B; i viceversa.

$A[0]$ (bloc 0, línia 0): fallada (obligatòria), carrega bloc 0.
$B[0]$ (bloc 32, línia 0): fallada (obligatòria), expulsa bloc 0.
$A[1]$ (bloc 0, línia 0): fallada (conflicte), expulsa bloc 32.
$B[1]$ (bloc 32, línia 0): fallada (conflicte), expulsa bloc 0.
$\ldots$ i així fins a $A[7], B[7]$.

Dins de cada grup de 8 iteracions: 2 fallades d’arrencada en fred (primer accés a cada bloc) + 14 fallades de conflicte. El patró es repeteix per a cada bloc, amb 32 grups. En total: tots els 512 accessos a dades fallen, cosa que anul·la completament l’efecte de l’MC.

Sí, es produeixen fallades de conflicte massives, causades per l’alineament dels dos vectors respecte a l’MC.

c) Si B comença a 0x600:

Bloc $k$ de B: adreça base $= \texttt{0x600} + 32k = 1536 + 32k$. Número de bloc $= 1536/32 + k = 48 + k$. Línia $= (48 + k) \bmod 16 = k \bmod 16$.

El mapatge és idèntic: la distància entre A i B ($\texttt{0x600} = 1536$ bytes $= 48$ blocs) torna a ser un múltiple exacte del nombre de línies (16). El patró de conflictes no canvia.

Observació: perquè els conflictes desapareguin, la distància entre A i B (en nombre de blocs) no ha de ser múltiple de 16. Per exemple, si B comencés a 0x420 (bloc 33), el bloc $k$ d’A aniria a la línia $k \bmod 16$ i el bloc $k$ de B a la línia $(33 + k) \bmod 16 = (k + 1) \bmod 16$: línies diferents, sense conflictes. Això il·lustra que les fallades de conflicte depenen de l’adreça base relativa dels vectors, un efecte que el programador no controla directament, però que el compilador o l’assignador de memòria poden mitigar mitjançant farciment (padding) o alineament estratègic.

--- number-sections: true language: crossref-exr-title: "Problema" crossref-exr-prefix: "Problema" --- # {{< var tema7 >}} {#sec-tema-mc-solucions} ## Disseny bàsic ::: {#sol-t7-cache-adreces .callout-tip} ## Solució: adreçament i seqüència de blocs **Enunciat**: @exr-t7-cache-adreces. Memòria principal de 64 bytes (adreces de 6 bits), memòria cau de 16 bytes, correspondència directa, blocs de 4 bytes ($b = 2$). L'MC té $16/4 = 4$ línies ($n_l = 2$). L'adreça es descompon en: $$A = \underbrace{\cdot\cdot}_{2\text{ bits etiqueta}} \; \underbrace{\cdot\cdot}_{2\text{ bits índex}} \; \underbrace{\cdot\cdot}_{2\text{ bits desplaçament}}$$ **a)** Adreça `0x39` $= 57 = 111001_2$: $$\underbrace{11}_{\text{etiqueta}=3}\;\underbrace{10}_{\text{índex}=2}\;\underbrace{01}_{\text{desplaçament}=1}$$ La dada correspon a la **línia 2**, amb **etiqueta 3** i **byte 1** dins el bloc. **b)** Mapatge de blocs a línies ($\text{índex} = \text{bloc} \bmod 4$): | Bloc | 0 | 1 | 3 | 7 | 10 | 12 | 15 | | :--- | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | Línia | 0 | 1 | 3 | 3 | 2 | 0 | 3 | : {.striped} Evolució de la seqüència (MC inicialment buida): | # | Bloc | Línia | Contingut línia | En/F | | :---: | :---: | :---: | :--- | :---: | | 1 | 0 | 0 | buida | **F** | | 2 | 1 | 1 | buida | **F** | | 3 | 0 | 0 | bloc 0 | **En** | | 4 | 3 | 3 | buida | **F** | | 5 | 12 | 0 | bloc 0 $\neq$ 12 | **F** | | 6 | 10 | 2 | buida | **F** | | 7 | 3 | 3 | bloc 3 | **En** | | 8 | 7 | 3 | bloc 3 $\neq$ 7 | **F** | | 9 | 12 | 0 | bloc 12 | **En** | | 10 | 15 | 3 | bloc 7 $\neq$ 15 | **F** | | 11 | 3 | 3 | bloc 15 $\neq$ 3 | **F** | : {tbl-colwidths="[10,13,13,51,13]" .striped} Encerts: 3. Fallades: 8. Taxa d'encerts: $h = 3/11 \approx 27{,}3\ \%$. De les 8 fallades, 7 són **d'arrencada en fred** (*cold-start*: el primer accés a cadascun dels blocs 0, 1, 3, 12, 10, 7 i 15) i la de l'accés 11 és de **conflicte**: el bloc 3, carregat a l'accés 4, ha estat expulsat pels blocs 7 i 15, que competeixen amb ell per la línia 3 (en una memòria cau completament associativa de la mateixa capacitat, aquest accés seria un encert). El conflicte a la línia 3 és especialment greu: els tres blocs s'hi expulsen l'un a l'altre, i el bloc 3 només hi encerta un cop (a l'accés 7). ::: ::: {#sol-t7-cache-politiques .callout-tip} ## Solució: polítiques d'escriptura **Enunciat**: @exr-t7-cache-politiques. Processador de 16 bits. MC de correspondència directa, 256 bytes, blocs de 16 bytes. L'MC té $256/16 = 16$ línies. Descomposició de l'adreça (16 bits): $$A = \underbrace{\cdot\cdot\cdot\cdot\cdot\cdot\cdot\cdot}_{8\text{ bits etiqueta}} \; \underbrace{\cdot\cdot\cdot\cdot}_{4\text{ bits índex}} \; \underbrace{\cdot\cdot\cdot\cdot}_{4\text{ bits desplaçament}}$$ Exemples de descomposició: - `0x4534`: etiqueta = `0x45`, índex = `0x3`, desplaçament = `0x4`. - `0x13A4`: etiqueta = `0x13`, índex = `0xA`, desplaçament = `0x4`. - `0x60A0`: etiqueta = `0x60`, índex = `0xA`, desplaçament = `0x0`. Cada accés L o E transfereix una paraula de 2 bytes (processador de 16 bits). **a)** Escriptura immediata sense assignació. Comportament per tipus d'accés: - **L encert**: es llegeix de l'MC. Cap tràfic amb MP. - **L fallada**: es llegeix el bloc sencer d'MP (16 B), es carrega a l'MC i se'n llegeix la dada. - **E encert**: s'escriu a l'MC i a l'MP (2 B, a través de la memòria intermèdia d'escriptura). - **E fallada**: s'escriu directament a MP (2 B). L'MC no s'altera. Les columnes **Lect. MC** i **Escr. MC** indiquen si l'accés llegeix o escriu la matriu de dades de l'MC (la dada lliurada a la CPU, la càrrega d'un bloc, l'escriptura d'una dada o la còpia d'un bloc modificat cap a MP). | # | Tipus | Adr. | Etiq. | Índ. | En/F | Llegits MP | Escrits MP | Lect. MC | Escr. MC | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | L | `4534` | `45` | `3` | **F** | 16 | 0 | S | S | | 2 | L | `4568` | `45` | `6` | **F** | 16 | 0 | S | S | | 3 | E | `13A4` | `13` | `A` | **F** | 0 | 2 | N | N | | 4 | E | `13A8` | `13` | `A` | **F** | 0 | 2 | N | N | | 5 | L | `3560` | `35` | `6` | **F** | 16 | 0 | S | S | | 6 | E | `453C` | `45` | `3` | **En** | 0 | 2 | N | S | | 7 | E | `60A0` | `60` | `A` | **F** | 0 | 2 | N | N | | 8 | L | `453C` | `45` | `3` | **En** | 0 | 0 | S | N | | 9 | E | `3900` | `39` | `0` | **F** | 0 | 2 | N | N | | 10 | L | `A238` | `A2` | `3` | **F** | 16 | 0 | S | S | : {tbl-colwidths="[6,8,10,8,8,8,13,13,13,13]" .striped} Justificació dels casos clau: - \#3 i #4 (`E 13A4`, `E 13A8`): ambdues escriptures fallen a la línia `A` (buida). Sense assignació, cap de les dues carrega el bloc → la línia resta buida i la segona escriptura també falla. - \#6 (`E 453C`): la línia 3 conté el bloc carregat al pas 1 (etiqueta `45`) → encert. S'escriu a MC i a MP (2 B). - \#8 (`L 453C`): la línia 3 encara conté l'etiqueta `45` → encert. - \#10 (`L A238`): etiqueta `A2` $\neq$ `45` a la línia 3 → fallada, reemplaça. **b)** Escriptura retardada amb assignació. Comportament per tipus d'accés: - **L/E encert**: accés a MC. Cap tràfic amb MP. En cas d'escriptura, $D \leftarrow 1$. - **L/E fallada, $D=0$**: es llegeix el bloc d'MP (16 B) i es carrega a l'MC. - **L/E fallada, $D=1$**: es llegeix el bloc antic de l'MC i es copia a MP (16 B), i després es llegeix el nou bloc d'MP (16 B) i es carrega a l'MC. A les columnes **Lect. MC** i **Escr. MC**, tota fallada escriu l'MC (càrrega del bloc i, si és E, la dada); l'MC es llegeix quan la dada es lliura a la CPU (L) o quan cal copiar un bloc modificat cap a MP. La columna **D** dona el bit de modificació de la línia abans de l'accés i, si canvia, també el de després (abans→després). | # | Tipus | Adr. | Etiq. | Índ. | En/F | D | Llegits MP | Escrits MP | Lect. MC | Escr. MC | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | L | `4534` | `45` | `3` | **F** | 0 | 16 | 0 | S | S | | 2 | L | `4568` | `45` | `6` | **F** | 0 | 16 | 0 | S | S | | 3 | E | `13A4` | `13` | `A` | **F** | 0→1 | 16 | 0 | N | S | | 4 | E | `13A8` | `13` | `A` | **En** | 1 | 0 | 0 | N | S | | 5 | L | `3560` | `35` | `6` | **F** | 0 | 16 | 0 | S | S | | 6 | E | `453C` | `45` | `3` | **En** | 0→1 | 0 | 0 | N | S | | 7 | E | `60A0` | `60` | `A` | **F** | 1 | 16 | 16 | S | S | | 8 | L | `453C` | `45` | `3` | **En** | 1 | 0 | 0 | S | N | | 9 | E | `3900` | `39` | `0` | **F** | 0→1 | 16 | 0 | N | S | | 10 | L | `A238` | `A2` | `3` | **F** | 1→0 | 16 | 16 | S | S | : {tbl-colwidths="[5,9,9,8,7,8,7,12,12,11,12]" .striped} Justificació dels casos clau: - \#3 (`E 13A4`): amb assignació, es carrega el bloc d'MP (16 B) a la línia `A` i s'escriu la dada a l'MC ($D \leftarrow 1$). - \#4 (`E 13A8`): encert (el bloc és a la línia `A` des del pas 3). S'escriu a MC, $D$ ja és 1. - \#7 (`E 60A0`): la línia `A` conté l'etiqueta `13` amb $D=1$. Fallada: cal copiar primer el bloc antic a MP (16 B *escrits*), després carregar el nou bloc d'MP (16 B *llegits*), i finalment escriure la dada ($D \leftarrow 1$). - \#10 (`L A238`): la línia 3 conté l'etiqueta `45` amb $D=1$ (des del pas 6). Fallada amb còpia del bloc modificat a MP: 16 B escrits + 16 B llegits. **c)** Resum comparatiu: | | Escr. immediata s/a | Escr. retardada a/a | | :--- | :---: | :---: | | Taxa de fallades | 80 % (8/10) | 70 % (7/10) | | Bytes llegits d'MP | 64 | 112 | | Bytes escrits a MP | 10 | 32 | | Bytes totals MP | 74 | 144 | : {tbl-colwidths="[30,35,35]" .striped} L'escriptura retardada amb assignació té una taxa de fallades inferior (l'accés #4 passa de fallada a encert perquè el bloc es va assignar al pas 3), però genera més tràfic total amb MP: cada assignació per escriptura carrega un bloc de 16 B, i cada escriptura a MP d'un bloc modificat n'escriu 16 B més. L'escriptura immediata sense assignació genera menys tràfic perquè les escriptures que fallen només transfereixen la paraula escrita (2 B), sense carregar blocs sencers. ::: ## Rendiment ::: {#sol-t7-rend-politiques .callout-tip} ## Solució: comparació de polítiques d'escriptura **Enunciat**: @exr-t7-rend-politiques. Dades: $p_e = 20\ \%$, $p_m = 1/3$, $t_h = 10$ ns, $t_{bloc} = 100$ ns, $h_1 = 0{,}9$ (immediata s/a), $h_2 = 0{,}85$ (retardada a/a). **a)** Aplicant @eq-tam, amb el temps de penalització mitjà per fallada de cada política (@cau-model-temps; per a l'escriptura retardada, @cau-tam-retardada). Se suposa que la taxa de fallades és independent del tipus d'accés: així, la fracció de fallades que corresponen a escriptures coincideix amb el percentatge d'escriptures $p_e$. *Escriptura immediata sense assignació* ($m_1 = 0{,}10$): les fallades de lectura paguen $t_{bloc} + t_h$ i les d'escriptura paguen 0 (la memòria intermèdia absorbeix l'escriptura): $$t_{p_1} = (1 - p_e)(t_{bloc} + t_h) = 0{,}80 \cdot 110 = 88 \text{ ns}$$ $$\text{TAM}_1 = t_h + m_1 \cdot t_{p_1} = 10 + 0{,}10 \cdot 88 = \mathbf{18{,}8} \text{ ns}$$ *Escriptura retardada amb assignació* ($m_2 = 0{,}15$): la penalització depèn de si el bloc expulsat està modificat: $$t_{p_2} = (1 + p_m) \cdot t_{bloc} + t_h = \frac{4}{3} \cdot 100 + 10 = 133{,}3 + 10 \approx 143{,}3 \text{ ns}$$ $$\text{TAM}_2 = t_h + m_2 \cdot t_{p_2} = 10 + 0{,}15 \cdot 143{,}3 \approx 10 + 21{,}5 = \mathbf{31{,}5} \text{ ns}$$ L'escriptura immediata sense assignació és més ràpida ($18{,}8$ vs. $31{,}5$ ns). Té una taxa de fallades inferior ($10\ \%$ vs. $15\ \%$) i, sobretot, una penalització mitjana per fallada molt menor: les fallades d'escriptura no paguen penalització i les de lectura no generen escriptures de blocs modificats a MP. La penalització mitjana de l'escriptura retardada és un 63 % més gran ($143{,}3$ vs. $88$ ns). **b)** Per a un programa de només lectures ($p_e = 0$), ambdues polítiques es comporten de manera **idèntica**: en absència d'escriptures, no hi ha diferència entre escriptura immediata i retardada ($p_m = 0$, cap bloc es modifica), i ambdues polítiques carreguen blocs a l'MC exactament igual en les fallades de lectura. La taxa de fallades seria la mateixa per a ambdues i la penalització també ($t_{bloc} + t_h = 110$ ns), de manera que cap de les dues alternatives seria més ràpida que l'altra. ::: ::: {#sol-t7-rend-cpi-separat .callout-tip} ## Solució: MC separades d'instruccions i dades **Enunciat**: @exr-t7-rend-cpi-separat. Dades: $\text{CPI}_{ideal} = 1{,}5$, $t_c = 10$ ns, $n_r = 1{,}6$ referències/instrucció. MC de dades amb escriptura retardada amb assignació. | | MC Instruccions | MC Dades | | :--- | :---: | :---: | | Accessos per instrucció | 1 | 0,6 | | $m$ | 4 % | 10 % | | $t_p$ (bloc no modif.) | 10 cicles | 15 cicles | | $t_p$ (bloc modif.) | — | 20 cicles | | $p_m$ | — | 20 % | : {tbl-colwidths="[40,30,30]" .striped} **a)** Penalització per fallada a l'MC de dades (escriptura retardada): $$t_{pd} = (1 - p_m) \cdot 15 + p_m \cdot 20 = 0{,}80 \cdot 15 + 0{,}20 \cdot 20 = 12 + 4 = 16 \text{ cicles}$$ El percentatge d'escriptures ($p_e = 40\ \%$) no és necessari per resoldre el problema: la penalització de l'MC de dades ja es dona directament en funció de si el bloc reemplaçat és modificat o no. TAM ponderat per la fracció d'accessos de cada MC: $$\text{TAM} = t_h + \frac{1}{n_r} \cdot m_i \cdot t_{pi} + \frac{0{,}6}{n_r} \cdot m_d \cdot t_{pd}$$ $$= 1 + \frac{1}{1{,}6} \cdot 0{,}04 \cdot 10 + \frac{0{,}6}{1{,}6} \cdot 0{,}10 \cdot 16$$ $$= 1 + 0{,}625 \cdot 0{,}4 + 0{,}375 \cdot 1{,}6 = 1 + 0{,}25 + 0{,}6 = \mathbf{1{,}85} \text{ cicles}$$ **b)** Cicles de penalització per instrucció: $$\text{CPI}_{penal,i} = m_i \cdot 1 \cdot t_{pi} = 0{,}04 \cdot 10 = 0{,}4 \text{ cicles/instr.}$$ $$\text{CPI}_{penal,d} = m_d \cdot 0{,}6 \cdot t_{pd} = 0{,}10 \cdot 0{,}6 \cdot 16 = 0{,}96 \text{ cicles/instr.}$$ $$\text{CPI} = \text{CPI}_{ideal} + \text{CPI}_{penal,i} + \text{CPI}_{penal,d} = 1{,}5 + 0{,}4 + 0{,}96 = 2{,}86$$ $$t_{exe} = \text{CPI} \cdot t_c = 2{,}86 \cdot 10 = \mathbf{28{,}6} \text{ ns/instrucció}$$ Observació: les fallades de memòria cau incrementen el CPI un $90{,}7\ \%$ respecte del valor ideal (d'$1{,}5$ a $2{,}86$). L'MC de dades, amb només el $37{,}5\ \%$ dels accessos, contribueix el $70{,}6\ \%$ de la penalització ($0{,}96 / 1{,}36$), a causa de la seva taxa de fallades més alta i la penalització per les escriptures de blocs modificats a MP. ::: ## Associativitat i multinivell ::: {#sol-t7-assoc-2vies .callout-tip} ## Solució: associativa de 2 vies **Enunciat**: @exr-t7-assoc-2vies. Processador de 16 bits. MC associativa de 2 vies, 1 KiB, blocs de 16 bytes, escriptura immediata sense assignació, LRU. L'MC té $1024/16 = 64$ línies organitzades en $64/2 = 32$ conjunts de 2 vies. Descomposició de l'adreça (16 bits): $$A = \underbrace{\cdot\cdot\cdot\cdot\cdot\cdot\cdot}_{7\text{ bits etiqueta}} \; \underbrace{\cdot\cdot\cdot\cdot\cdot}_{5\text{ bits conjunt}} \; \underbrace{\cdot\cdot\cdot\cdot}_{4\text{ bits desplaçament}}$$ El conjunt es determina pels bits [8:4] i l'etiqueta pels bits [15:9]. Descomposició de les adreces: | Adreça | Bloc MP | Conjunt | Etiqueta | | :---: | :---: | :---: | :---: | | `A930` | `A93` | 19 (`0x13`) | `0x54` | | `B930` | `B93` | 19 | `0x5C` | | `A972` | `A97` | 23 (`0x17`) | `0x54` | | `A932` | `A93` | 19 | `0x54` | | `C935` | `C93` | 19 | `0x64` | | `C934` | `C93` | 19 | `0x64` | | `B976` | `B97` | 23 | `0x5C` | | `B936` | `B93` | 19 | `0x5C` | | `B938` | `B93` | 19 | `0x5C` | | `A978` | `A97` | 23 | `0x54` | : {tbl-colwidths="[20,20,33,27]" .striped} Exemple de descomposició per a `0xA972`: $$\texttt{A972}_{16} = \underbrace{1010100}_{0\texttt{x54}}\;\underbrace{10111}_{23}\;\underbrace{0010}_{2}$$ Els bits [8:4] són $10111_2 = 23$, no $00111_2 = 7$. El bit 8 (que forma part del dígit hex `9` = $1001_2$) és 1. La seqüència accedeix a dos conjunts: **19** (7 accessos) i **23** (3 accessos). Amb escriptura immediata sense assignació, les escriptures que fallen no modifiquen l'MC. Evolució del conjunt 19 (2 vies): | # | Accés | En/F | Via 0 | Via 1 | LRU | | :---: | :--- | :---: | :---: | :---: | :---: | | 1 | L `A930` (0x54) | **F** | **0x54** | — | v1 | | 2 | L `B930` (0x5C) | **F** | 0x54 | **0x5C** | v0 | | 4 | E `A932` (0x54) | **En** | 0x54 | 0x5C | v1 | | 5 | E `C935` (0x64) | **F** | 0x54 | 0x5C | (s/a) | | 6 | L `C934` (0x64) | **F** | 0x54 | **0x64** | v0 | | 8 | E `B936` (0x5C) | **F** | 0x54 | 0x64 | (s/a) | | 9 | L `B938` (0x5C) | **F** | **0x5C** | 0x64 | v1 | : {tbl-colwidths="[7,34,11,17,17,14]" .striped} - \#4: encert a via 0 (etiqueta `0x54`). S'escriu a MC i a MP (2 B). LRU passa a v1. - \#5: fallada, però és E sense assignació → MC inalterada, LRU inalterat. - \#6: fallada de lectura. LRU = v1 (des de #4; #5 no altera res) → s'expulsa v1 (`0x5C`) i es carrega `0x64`. - \#8: E fallada sense assignació → MC inalterada. - \#9: L fallada. LRU = v0 (des de #6) → s'expulsa v0 (`0x54`) i es carrega `0x5C`. Evolució del conjunt 23 (2 vies): | # | Accés | En/F | Via 0 | Via 1 | LRU | | :---: | :--- | :---: | :---: | :---: | :---: | | 3 | E `A972` (0x54) | **F** | — | — | (s/a) | | 7 | E `B976` (0x5C) | **F** | — | — | (s/a) | | 10 | L `A978` (0x54) | **F** | **0x54** | — | v1 | : {tbl-colwidths="[7,34,11,17,17,14]" .striped} Les escriptures #3 i #7 fallen, però sense assignació no carreguen cap bloc. El conjunt 23 resta buit fins a la lectura #10. Taula resum: | # | Tipus | Adr. | Bloc | Conj. | En/F | Lectura MP | Escriptura MP | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | 1 | L byte | `A930` | `A93` | 19 | **F** | S, `A930`, 16 B | N | | 2 | L paraula | `B930` | `B93` | 19 | **F** | S, `B930`, 16 B | N | | 3 | E byte | `A972` | `A97` | 23 | **F** | N | S, `A972`, 1 B | | 4 | E paraula | `A932` | `A93` | 19 | **En** | N | S, `A932`, 2 B | | 5 | E byte | `C935` | `C93` | 19 | **F** | N | S, `C935`, 1 B | | 6 | L paraula | `C934` | `C93` | 19 | **F** | S, `C930`, 16 B | N | | 7 | E byte | `B976` | `B97` | 23 | **F** | N | S, `B976`, 1 B | | 8 | E paraula | `B936` | `B93` | 19 | **F** | N | S, `B936`, 2 B | | 9 | L byte | `B938` | `B93` | 19 | **F** | S, `B930`, 16 B | N | | 10 | L paraula | `A978` | `A97` | 23 | **F** | S, `A970`, 16 B | N | : {tbl-colwidths="[6,10,9,9,8,7,25,26]" .striped} Encerts: 1 (pas 4). Fallades: 9. Taxa de fallades: 90 %. La taxa de fallades és molt alta perquè la seqüència barreja accessos a tres blocs diferents dins el conjunt 19 (etiquetes `0x54`, `0x5C` i `0x64`), i les escriptures sense assignació impedeixen que els blocs escrits s'instal·lin a l'MC per a futurs accessos. ::: ::: {#sol-t7-assoc-tam .callout-tip} ## Solució: TAM multinivell **Enunciat**: @exr-t7-assoc-tam. Un accés a memòria segueix la cadena L1 → L2 → MP: 1. S'accedeix a L1 amb temps $t_{h_{L1}}$. 2. En cas de fallada a L1 (probabilitat $m_{L1}$), s'accedeix a L2 amb temps $t_{h_{L2}}$. 3. En cas de fallada a L2 (probabilitat $m_{L2}$, local), s'accedeix a MP amb penalització $t_p$. El temps mitjà d'accés és la suma del temps de L1 més les penalitzacions ponderades: $$\boxed{\text{TAM} = t_{h_{L1}} + m_{L1} \cdot \bigl(t_{h_{L2}} + m_{L2} \cdot t_p\bigr)}$$ La fórmula coincideix amb @eq-tam-multinivell. Desenvolupant: $$\text{TAM} = t_{h_{L1}} + m_{L1} \cdot t_{h_{L2}} + m_{L1} \cdot m_{L2} \cdot t_p$$ El terme $m_{L1} \cdot m_{L2}$ és la **taxa de fallades global** de L2 (proporció de tots els accessos que fallen tant a L1 com a L2 i arriben a MP). Observació: en un sistema ben dissenyat, $t_{h_{L1}}$ domina el TAM perquè afecta tots els accessos. Per això L1 s'optimitza per minimitzar $t_{h_{L1}}$, mentre que L2 s'optimitza per minimitzar $m_{L2}$. ::: ## Tipologia de les fallades ::: {#sol-t7-fallades-tipologia .callout-tip} ## Solució: classificació de fallades **Enunciat**: @exr-t7-fallades-tipologia. MC de correspondència directa, 8 línies, blocs de 4 bytes ($b = 2$). Capacitat total: $8 \times 4 = 32$ bytes. El mapatge és $\text{línia} = \text{bloc} \bmod 8$, on $\text{bloc} = \text{adreça} \div 4$. La classificació de les fallades segueix les tres C (@sec-tipologia-fallades, @cau-tres-c). **a) Seqüència A**: 0, 4, 8, 12, 16, 20, 24, 28, 0, 4, 8, 12 Blocs accedits: 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3. Cadascun ocupa una línia diferent ($k \bmod 8 = k$ per a $k = 0\ldots7$). El *working set* (8 blocs) cap exactament a l'MC. | Accés | Bloc | Línia | Resultat | Tipus | | :---: | :---: | :---: | :---: | :--- | | 0 | 0 | 0 | Fallada | Obligatòria | | 4 | 1 | 1 | Fallada | Obligatòria | | 8 | 2 | 2 | Fallada | Obligatòria | | 12 | 3 | 3 | Fallada | Obligatòria | | 16 | 4 | 4 | Fallada | Obligatòria | | 20 | 5 | 5 | Fallada | Obligatòria | | 24 | 6 | 6 | Fallada | Obligatòria | | 28 | 7 | 7 | Fallada | Obligatòria | | 0 | 0 | 0 | **Encert** | — | | 4 | 1 | 1 | **Encert** | — | | 8 | 2 | 2 | **Encert** | — | | 12 | 3 | 3 | **Encert** | — | : {tbl-colwidths="[18,15,15,22,30]" .striped} Total: **8 fallades** (totes obligatòries), **4 encerts**. Cap fallada de conflicte (cada bloc té línia pròpia) ni de capacitat (el *working set* cap a l'MC). **Seqüència B**: 0, 4, 8, 12, 0, 4, 8, 12, 0, 4, 8, 12 Blocs: 0, 1, 2, 3 (repetits 3 vegades). Quatre blocs, cadascun amb línia diferent: el *working set* (4 blocs) és la meitat de la capacitat. - Primer recorregut (0, 4, 8, 12): 4 fallades d'arrencada en fred. - Segon i tercer recorreguts: tot encerts (els 4 blocs continuen a l'MC). Total: **4 fallades** (totes obligatòries), **8 encerts**. **Seqüència C**: 0, 32, 0, 32, 0, 32, 0, 32 Blocs: 0, 8, 0, 8, ... El bloc 0 i el bloc 8 es mapen tots dos a la línia 0 ($0 \bmod 8 = 0$, $8 \bmod 8 = 0$). | Accés | Bloc | Línia | Resultat | Tipus | | :---: | :---: | :---: | :---: | :--- | | 0 | 0 | 0 | Fallada | Obligatòria | | 32 | 8 | 0 | Fallada | Obligatòria (expulsa bloc 0) | | 0 | 0 | 0 | Fallada | Conflicte | | 32 | 8 | 0 | Fallada | Conflicte | | 0 | 0 | 0 | Fallada | Conflicte | | 32 | 8 | 0 | Fallada | Conflicte | | 0 | 0 | 0 | Fallada | Conflicte | | 32 | 8 | 0 | Fallada | Conflicte | : {tbl-colwidths="[18,15,15,22,30]" .striped} Total: **8 fallades** (2 obligatòries, 6 de conflicte), **0 encerts**. El *working set* és de només 2 blocs (molt inferior a la capacitat de 8 línies), però tots dos competeixen per la mateixa línia. L'MC té 7 línies buides que no s'aprofiten. **b)** Per eliminar les fallades de conflicte de la seqüència C, cal que els blocs 0 i 8 puguin coexistir a l'MC. La solució és **augmentar l'associativitat** a 2 o més vies: amb 2 vies, el conjunt 0 tindria dues posicions i ambdós blocs hi cabrien simultàniament. **c)** Amb una MC associativa de 2 vies de la mateixa capacitat total (8 línies → 4 conjunts de 2 vies): - **Seqüència C**: blocs 0 i 8 es mapen al conjunt $0 \bmod 4 = 0$ i $8 \bmod 4 = 0$. Amb 2 vies, ambdós hi caben. Després de les 2 fallades d'arrencada en fred, els 6 accessos restants serien encerts. **Sí, millora** (de 8 a 2 fallades). - **Seqüència B**: blocs 0, 1, 2, 3 es mapen als conjunts 0, 1, 2, 3. Cada bloc ocupa un conjunt diferent: no hi ha conflictes ni amb correspondència directa. **No millora** (les 4 fallades d'arrencada en fred són igualment inevitables). ::: ::: {#sol-t7-fallades-programa .callout-tip} ## Solució: conflictes entre dos vectors **Enunciat**: @exr-t7-fallades-programa. `A[256]` d'enters de 4 bytes, des de l'adreça `0x000` (1 KiB, fins a `0x3FF`). `B[256]` des de `0x400` (fins a `0x7FF`). MC de correspondència directa, 16 línies, blocs de 32 bytes. Variables `i` i `suma` en registres. Paràmetres: bloc = 32 bytes = 8 enters per bloc. A i B ocupen cadascun $256/8 = 32$ blocs. **a)** En el primer recorregut, cada bloc s'accedeix per primera vegada: **32 fallades d'arrencada en fred per a A** i **32 per a B** (una per bloc, quan s'accedeix a $A[0], A[8], A[16], \ldots, A[248]$ i anàlogament per a $B$). **b)** Mapatge de cada vector: - Bloc $k$ d'A ($k = 0\ldots31$): adreça base $= 32k$. Número de bloc $= k$. Línia $= k \bmod 16$. - Bloc $k$ de B ($k = 0\ldots31$): adreça base $= \texttt{0x400} + 32k$. Número de bloc $= 1024/32 + k = 32 + k$. Línia $= (32 + k) \bmod 16 = k \bmod 16$. El bloc $k$ d'A i el bloc $k$ de B es mapen a la **mateixa línia** ($k \bmod 16$). Això és perquè la distància entre A i B ($\texttt{0x400} - \texttt{0x000} = 1024$ bytes, 1 KiB, que són 32 blocs) és un múltiple exacte del nombre de línies de l'MC (16). En el bucle, els accessos s'intercalen: $A[i], B[i], A[i+1], B[i+1], \ldots$ Dins de cada grup de 8 iteracions (que correspon a un bloc), l'accés a $A[i]$ carrega el bloc d'A a la línia $k$, i l'accés a $B[i]$ el reemplaça pel bloc de B; i viceversa. - $A[0]$ (bloc 0, línia 0): **fallada** (obligatòria), carrega bloc 0. - $B[0]$ (bloc 32, línia 0): **fallada** (obligatòria), expulsa bloc 0. - $A[1]$ (bloc 0, línia 0): **fallada** (conflicte), expulsa bloc 32. - $B[1]$ (bloc 32, línia 0): **fallada** (conflicte), expulsa bloc 0. - $\ldots$ i així fins a $A[7], B[7]$. Dins de cada grup de 8 iteracions: 2 fallades d'arrencada en fred (primer accés a cada bloc) + 14 fallades de conflicte. El patró es repeteix per a cada bloc, amb 32 grups. En total: **tots els 512 accessos a dades fallen**, cosa que anul·la completament l'efecte de l'MC. **Sí, es produeixen fallades de conflicte massives**, causades per l'alineament dels dos vectors respecte a l'MC. **c)** Si B comença a `0x600`: - Bloc $k$ de B: adreça base $= \texttt{0x600} + 32k = 1536 + 32k$. Número de bloc $= 1536/32 + k = 48 + k$. Línia $= (48 + k) \bmod 16 = k \bmod 16$. El mapatge és idèntic: la distància entre A i B ($\texttt{0x600} = 1536$ bytes $= 48$ blocs) torna a ser un múltiple exacte del nombre de línies (16). El patró de conflictes **no canvia**. Observació: perquè els conflictes desapareguin, la distància entre A i B (en nombre de blocs) **no ha de ser múltiple de 16**. Per exemple, si B comencés a `0x420` (bloc 33), el bloc $k$ d'A aniria a la línia $k \bmod 16$ i el bloc $k$ de B a la línia $(33 + k) \bmod 16 = (k + 1) \bmod 16$: línies diferents, sense conflictes. Això il·lustra que les **fallades de conflicte depenen de l'adreça base relativa dels vectors**, un efecte que el programador no controla directament, però que el compilador o l'assignador de memòria poden mitigar mitjançant **farciment** (*padding*) o alineament estratègic. :::