Si consideri una gerarchia di memoria con:

• una memoria centrale costituita da 256K parole da 16-bit (unità indirizzabile).
• una cache di 4K parole (da 16 bit), set associativa a 4 vie, con linee da 64 parole (da 16 bit)

Si assuma che:

• il tempo di accesso alla cache sia 10 volte più breve rispetto al tempo di accesso alla memoria centrale.
• la cache sia inizialmente vuota
• la CPU carichi 4352 parole (da 16 bit) dalle locazioni 0,1,2,3...,4351, in ordine, e che ripeta tale caricamento per altre 14 volte.

a) Specificare il numero di bit per i campi in cui un indirizzo di memoria centrale viene suddiviso.

Soluzione:

Poiché la memoria centrale possiede 256K (cioè 2¹⁸) parole, occorrono 18 bit per rappresentare un generico indirizzo. Questi bit vengono suddivisi nei campi tag, set e parola. La dimensione del campo parola è determinato dalla dimensione del blocco, che è di  64 = 2⁶ parole. Quindi il campo parola è costituito da 6 bit (i meno significativi dell'indirizzo). Poiché ogni set della cache contiene 4 linee, considerando che in totale la cache contiene 4K (cioè 2¹²) parole e quindi 2¹²/2⁶ = 2⁶ linee, si avranno 2⁶/2² = 2⁴ linee. Pertanto il campo set sarà costituito da 4 bit, e per differenza il campo tag sarà costituito da 18-4-6=8 bit.

b) Assumendo una politica di rimpiazzo LRU per i blocchi, stimare il fattore di velocizzazione (speedup: rapporto fra il tempo impiegato senza cache e il tempo impiegato con la cache) risultante con l'uso della cache.

Soluzione:
 

Avendo Niter = 15 iterazioni di riferimenti agli indirizzi da 0 a 4351 (numero totale riferimenti per iterazione Nrif = 4352), il numero totale di blocchi acceduti per iterazione è

(ricordiamo che la cache ha 64 linee).

dove   Nmiss è il numero di miss per tutte le iterazioni,
              Penalità di miss  è il tempo per trasferire un blocco dalla memoria alla cache assumendo il trasferimento di 1 parola alla volta.

Penalità di miss = dim blocco * Tempo di accesso alla memoria centrale = 64 * 10 * t

Nmiss = ∑ _{i = 1..15}  Nmiss_i
 
Assumendo una politica LRU calcoleremo il numero di miss per la prima iterazione e i seguenti da inserire nella formula di sopra.

Prima Iterazione
Stato della cache prima della iterazione
(inizialmente la cache è vuota)

Set 0

Set 1

Set 2

Set 3

Set 4

Set 5

Set 6

Set 7

Set 8

Set 9

Set10

Set11

Set12

Set13

Set14

Set15

Stato della cache dopo l'iterazione

Set 0	Set 1	Set 2	Set 3	Set 4	Set 5	Set 6	Set 7	Set 8	Set 9	Set10	Set11	Set12	Set13	Set14	Set15
0/64	1/65	2/66	3/67	4	5	6	7	8	9	10	11	12	13	14	15
16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47
48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63

Quindi, ci sono 64 miss iniziali per riempire la cache e 4 rimpiazzi fatti secondo la politica LRU (la linea meno recentemente usata in ogni set è la 0).
Nmiss₁= 64 + 4 = 68

Seconda Iterazione
Stato della cache prima della iterazione

Set 0	Set 1	Set 2	Set 3	Set 4	Set 5	Set 6	Set 7	Set 8	Set 9	Set10	Set11	Set12	Set13	Set14	Set15
64	65	66	67	4	5	6	7	8	9	10	11	12	13	14	15
16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31
32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47
48	49	50	51	52	53	54	55	56	57	58	59	60	61	62	63

(adesso la linea meno recentemente usata in ogni set è la 1. In grassetto sono mostrati i blocchi più recentemente riferiti.)

Stato della cache dopo l'iterazione

Set 0	Set 1	Set 2	Set 3	Set 4	Set 5	Set 6	Set 7	Set 8	Set 9	Set10	Set11	Set12	Set13	Set14	Set15
64/48	65/49	66/50	67/51	4	5	6	7	8	9	10	11	12	13	14	15
16/0/64	17/1/65	18/2/66	19/3/67	20	21	22	23	24	25	26	27	28	29	30	31
32/16	33/17	34/18	35/19	36	37	38	39	40	41	42	43	44	45	46	47
48/32	49/33	50/34	51/35	52	53	54	55	56	57	58	59	60	61	62	63

Inizialmente i blocchi 0..3 sono caricati nella linea 1 di ogni set e di seguito si hanno miss per tutte le linee dei Set 0..2:
Nmiss₂= 4 + 4 + 4 + 4 + 4= 20
 

Terza Iterazione
Stato della cache prima della iterazione

Set 0	Set 1	Set 2	Set 3	Set 4	Set 5	Set 6	Set 7	Set 8	Set 9	Set10	Set11	Set12	Set13	Set14	Set15
48	49	50	51	4	5	6	7	8	9	10	11	12	13	14	15
64	65	66	67	20	21	22	23	24	25	26	27	28	29	30	31
16	17	18	19	36	37	38	39	40	41	42	43	44	45	46	47
32	33	34	35	52	53	54	55	56	57	58	59	60	61	62	63

(adesso la linea meno recentemente usata in ogni set è la 2.)

Stato della cache dopo l'iterazione

Set 0	Set 1	Set 2	Set 3	Set 4	Set 5	Set 6	Set 7	Set 8	Set 9	Set10	Set11	Set12	Set13	Set14	Set15
48/32	49/33	50/34	51/35	4	5	6	7	8	9	10	11	12	13	14	15
64/48	65/49	66/50	67/51	20	21	22	23	24	25	26	27	28	29	30	31
16/0/64	17/1/65	18/2/66	19/3/67	36	37	38	39	40	41	42	43	44	45	46	47
32/16	33/17	34/18	35/19	52	53	54	55	56	57	58	59	60	61	62	63

Inizialmente i blocchi 0..3 sono caricati nella linea 2 di ogni set e di seguito si hanno miss per tutte le linee dei Set 0..2, come nel caso precedente:

Nmiss₃= 4 + 4 + 4 + 4 + 4= 20

Le iterazioni successive (da 4 a 15) si comporteranno similmente, portando il numero totale di miss a:

Nmiss = 68 + 20*14 = 348
 
Tempo totale con cache = 4352*15*t + 348*(64*10*t)
                                                                        = 65280*t + 222720*t
                                                                        = 288000*t
 

                             Tempo totale senza cache                   652800*t
Speedup = ------------------------------------------------------- = ----------- = 2.26
                               Tempo totale con cache                    288000*t

c) Risolvere il punto (b) assumendo per il rimpiazzo dei blocchi la politica del blocco più recentemente riferito (MRU).