Esercizi sulla memoria cache - Informatica 2 - L. …unina.stidue.net/Calcolatori Elettronici...

Esercizi sulla memoria cache - Informatica 2 - L. Breveglieri 1

Esercizio 1

Sia data una memoria cache di tipo a “indirizzamento diretto” (direct-mapped), con blocchi didimensioni pari a una sola parola per blocco, e contenente 8 blocchi. La parola è lunga 16bit, e la memoria principale ha dimensioni pari a 64 K parole. Svolgere i punti seguenti:

1. Definire le dimensioni e la struttura degli indirizzi per la memoria cache.

2. Disegnare l’architettura della memoria cache e determinare il numero globale di bitnecessario a realizzare tale memoria cache, spiegandone il funzionamento.

TRACCIA DI SOLUZIONE ALL'ESERCIZIO 1

Il caso proposto nella domanda è un po’ particolare, perché un blocco di memoria cache hadimensione pari a una sola parola. Ecco la struttura dell’indirizzo, nel caso proposto:

• # di blocchi in memoria centrale: 64 K parole / 1 parola = 64 K blocchi

• # di blocchi in memoria cache: 8 parole / 1 parola = 8 blocchi

• indirizzo di memoria centrale: �log2 64 K � = 16 bit

• numero di blocco in memoria cache: �log2 8 � = 3 bit

Ne consegue che l’indirizzo di memoria centrale va così suddiviso:

ETICHETTADEL BLOCCO

# BLOCCO INDIRIZZO DELLAPAROLA ALL’INTERNODEL BLOCCO

13 bit 3 bit 0 bit

L’indirizzo di parola nel blocco non esiste, giacché ogni blocco è formato da una singolaparola; il numero di blocco è espresso da 3 bit; e l’etichetta da memorizzare nella memoriaassociativa della cache è formata, per differenza, da 16 − 3 = 13 bit.

Le due figure seguenti mostrano, in un caso particolare (non coincidente con quello dato neltesto della domanda), l’architettura della gerarchia di memoria comprendente una memoriacache a indirizzamento diretto (direct-mapped): ogni blocco della memoria centrale puòessere caricato in un unico blocco della memoria cache. Naturalmente, poiché in generale lamemoria centrale ha dimensioni superiori alla memoria cache, ogni blocco della memoriacache è messo in corrispondenza con più blocchi della memoria centrale.


M7

M6

M5

M4

M3

M2

M1

M0

C3

C2

C1

C0

MEMORIACENTRALE

MEMORIACACHE

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

IND. DIBLOCCO

00

01

10

11

IND. DIBLOCCO

M7

M6

M5

M4

M3

M2

M1

M0

C3 = M3

C2 = M6

C1 = M5

C0 = M0

MEMORIACENTRALE

MEMORIACACHE

0 0 0

00

01

10

11

IND. DIBLOCCO

IND. DIBLOCCO

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Memoria cache a indirizzamento diretto. Caricamento di alcuni blocchi in cache.


La struttura della memoria cache nel caso proposto dalla domanda è la seguente:

1 2 161 2 13

Memoria Associativadelle Etichette Memoria dei Blocchi

C1

C2

C3

C4

C5

C6

C7

E1

E2

E3

E4

E5

E6

E7

DATOINDIRIZZO

Unità di Controllo della Memoria Cache

Comando di Lettura

Comandodi Scrittura

Bit diValidità

16 bit 16 bit

Miss

La memoria cache ad indirizzamento diretto è formata dalle parti seguenti:

• Memoria dei blocchi, che contiene gli 8 blocchi dati da una parola di 16 bit ciascuno.

• Memoria associativa delle etichette, che contiene le 8 etichette associate agli 8 blocchicaricabili nella cache; ogni etichetta è da 13 bit.

• Memoria dei bit di validità, che contiene il bit di modifica per ogni blocco. Tale bit indicase il blocco in cache è occupato oppure no.

• Unità di controllo, che coordina il funzionamento delle parti restanti.

Dalla figura si può constatare come il numero di bit necessari sia il seguente:

• # bit della memoria associativa delle etichette: 8 parole × 13 bit = 104 bit

• # bit della memoria dei blocchi: 8 parole × 16 bit = 128 bit

• # bit di validità: 8 bit

Dunque, la memoria cache proposta richiede in totale 104 + 128 + 8 = 240 bit. La memoriacache è comunque dotata anche di un’unità di controllo, che coordina il funzionamento dellealtre parti. Tale unità di controllo potrebbe anche essere di natura sequenziale, e pertantocontenere dei bistabili di qualche tipo.


Esercizio 2

Si consideri un sistema costituito da un processore, avente a sua disposizione una memoriacache (cache dati) per memorizzare i dati, una memoria cache per memorizzare le istruzioni(cache istruzioni), e un bus indirizzi e un bus dati, entrambi da 32 bit, per leggere e scriverein memoria centrale.

La cache istruzioni utilizza la tecnica di indirizzamento diretto e ha dimensioni di 4Kbyte,con blocchi da 8 byte ciascuno. La frequenza di fallimento (miss rate) di questa cache è parial 2% degli accessi in memoria.

La cache dati utilizza anch’essa la tecnica a indirizzamento diretto, ha dimensioni totali di8Kbyte e blocchi da 8 byte ciascuno. La frequenza di fallimento di questa cache (miss rate) èpari al 15% degli accessi in memoria.

Si chiede di svolgere i punti seguenti:

1. Disegnare la struttura degli indirizzi della cache istruzioni e della cache dati, supponendoche ogni byte sia indirizzabile.

2. Disegnare lo schema dell’architettura della cache dati, spiegando come avviene la ricercadi un elemento e quali sono i bit di controllo necessari per il corretto funzionamento dellacache.

3. Si supponga che in media il 40% delle istruzioni di un programma rappresenti un accessoai dati (esecuzione di un’istruzione di tipo load oppure store). Il trasferimento di un datodalla cache dati o istruzioni alla CPU richiede 1 ciclo di clock. Si assuma che la memoriaprincipale abbia tempo di accesso pari a 50 cicli di clock per la prima parola (32 bit)mentre per le parole successive (sempre da 32 bit) sono necessari solo 20 cicli di clock.

Calcolare il tempo medio di trasferimento di un dato o istruzione dalla memoria centrale,ricordando che un trasferimento tra memoria e cache consiste sempre di un blocco intero(8 byte).

TRACCIA DI SOLUZIONE ALL’ESERCIZIO 2

L’indirizzo di memoria centrale è da 32 bit.

STRUTTURA DELLE ETICHETTE

Cache dati:

• i 3 bit meno significativi dell'indirizzo di memoria centrale servono per indirizzare un bytenel blocco

• si hanno 8K / 8 = 1024 blocchi nella cache

• si hanno log2 1024 = 10 bit per indirizzare il blocco

• i rimanenti 32 − 3 − 10 = 19 bit servono per l’etichetta

Cache istruzioni:

• i 3 bit meno significativi dell'indirizzo di memoria centrale servono per indirizzare un bytenel blocco

• si hanno 4K / 8 = 512 blocchi nella cache

• si hanno log2 512 = 9 bit per indirizzare il blocco

• i rimanenti 32 − 3 − 9 = 20 bit servono per l’etichetta

CALCOLO DELLE PRESTAZIONI MEDIE

Supponendo di fare uguale a 100 il numero di istruzioni, si hanno 100 accessi alla memoriadi programma per leggere le istruzioni stesse, e 40 di queste istruzioni fanno un ulteriore


accesso alla memoria dati per leggere un dato ciascuna. Dunque, in totale si hanno 140accessi alla memoria (senza distinguere se si tratta della memoria di programma o dellamemoria dati). In termini percentuali, si ha che sul totale di accessi alla memoria, unafrazione pari a 1 / 1,4 = 0,71 = 71% è di lettura di un'istruzione, mentre una frazione di 0,4 /1,4 = 0,28 = 28% è di lettura di un dato; giacché dati e istruzioni hanno la stessa dimensione(32 bit), tra questi due tipi di accesso non c'è differenza sostanziale. Naturalmente la somma1 / 1,4 + 0,4 / 1,4 vale 1 (a meno di arrotondamenti).

Si ha dunque che il valore medio Ttotale di accesso alla memoria è dato dalla formulaseguente:

Ttotale = 1 / 1,4 ∗ Tistruzioni + 0,4 / 1,4 ∗ Tdati = 0,71 ∗ Tistruzioni + 0,28 ∗ Tdati

Per prima cosa, è necessario calcolare il valore medio di Tistruzioni:

Tistruzioni = Hit_rate ∗ Taccesso alla mem. cache + Miss_rate ∗ Tpenalità di fallimento

che richiede il calcolo dei valori medi di Taccesso alla mem. cache e di Tpenalità di fallimento. Perquest'ultimo si deve ricordare che la memoria centrale ha parole da 32 bit, mentre lamemoria cache ha parole da 8 bit (un byte); ne consegue che una parola di memoriacentrale contiene 4 parole di memoria cache. Dunque, un blocco di memoria cache, formatoda 8 byte, viene caricato dalla memoria centrale in due colpi: nel primo si leggono i primi 4byte, nel secondo i rimanenti 4 byte.

Taccesso alla mem. cache = 1 ciclo di clock

Tpenalità di fallimento = Taccesso primi 4 byte in mem. centrale + Taccesso secondi 4 byte in mem. centrale + Taccesso alla mem.

cache =

= 50 + 20 + 1 = 71 cicli di clock

Tistruzioni = 0,98 ∗ 1 + 0,02 ∗ 71 = 2,4 cicli di clock

Come seconda cosa, è necessario calcolare il valore medio di Tdati; il calcolo è molto simile aquello di Tistruzioni:

Tdati = Hit_rate ∗ Taccesso alla mem. cache + Miss_rate ∗ Tpenalità di fallimento =

= 0,85 ∗ 1 + 0,15 ∗ 71 = 11,5 cicli di clock

Infine, il calcolo del valore medio di Ttotale:

Ttotale = 0,71 ∗ 2,4 + 0,28 ∗ 11,5 = 4,9 cicli di clock

Possiamo chiederci se le prestazioni della cache così calcolate siano buone oppure no.Supponendo che la memoria venga letta in modo puramente sequenziale, si ha che:

Ttotale senza cache = Taccesso secondi 4 byte in mem. centrale / 4 = 20 / 4 = 5 cicli di clock

Il guadagno varrebbe dunque 5 / 4,9 ≈ 1, che è modestissimo.


Esercizio 3

Data una gerarchia di memoria con una memoria cache e una memoria centrale, discutere,in base alle tre organizzazioni di cache disponibili, a indirizzamento diretto (direct-mapped),completamente associativo (fully-associative), e associativo a gruppi (set-associative), comeavvengono le operazioni seguenti:

1. posizionamento di un blocco nella cache;

2. verifica della presenza di un blocco nella cache;

3. scelta del blocco da sostituire nella cache in caso di fallimento di un'operazione dilettura;

4. scrittura di un blocco.


Posizionamento di un blocco:

Indirizzamento diretto:

Posizione univoca: indirizzo di memoria modulo numero dei blocchi in cache

Completamente associativa:

Posizione qualunque all’interno della cache

Associativo a gruppi

Posizione libera all’interno del gruppo

Insieme = (indirizzo di memoria / numero dei blocchi) modulo numero dei gruppi

Identificazione del blocco

Indirizzamento diretto:

Calcolo posizione

Verifica etichetta e verifica bit di validità

Completamente associativo:

Confronta etichetta in ogni blocco e verifica bit di validità

Associativo a gruppi

Identifica il gruppo

Confronta etichette del gruppo e verifica bit di validità

Sostituzione del blocco

Definito dall’indirizzo nelle cache a indirizzamento diretto

Cache associativa a gruppi oppure completamente associativa:

Casuale

LRU (Least Recently Used)

Strategia di scrittura

Write through (o scrittura immediata)

Write back (o scrittura differita)


Esercizio 4

È dato un sistema di memoria facoltativamente dotato di cache a indirizzamento diretto(direct-mapped); il sistema di memoria ha le caratteristiche seguenti:

• Capacità di memoria centrale: 32 K × 8, e tempo di accesso: 100 ns

• Dimensione del blocco: 128 parole da 8 bit ciascuna

• Capacità di memoria cache: 4 blocchi, e tempo di accesso: 10 ns

• Politica di lettura in cache: lettura differita (read back)

Un programma legge ciclicamente per 10 volte un vettore di 640 parole da 8 bit ciascuna.All’inizio il vettore si trova tutto in blocchi consecutivi della memoria centrale. Svolgere i puntiseguenti:

1. Calcolare la dimensione delle etichette di blocco da conservare nella memoriaassociativa facente parte della cache.

2. Spiegare brevemente in cosa consistono le politiche di lettura e scrittura differita (readback e write back, rispettivamente).

3. Calcolare il guadagno di tempo di lettura del vettore:

guadagno = Tempo di lettura del vettore sul sistema senza cache Tempo di lettura del vettore sul sistema con cache

ottenuto passando dal sistema senza cache al sistema con cache.

Si rammenta che per risolvere il punto (3) occorre fare una breve simulazione delcomportamento della memoria cache; le tabelle riportate di seguito sono liberamente usabiliper questo scopo.

C1

C2

C3

C4

C1

C2

C3

C4

C1

C2

C3

C4

C1

C2

C3

C4

C1

C2

C3

C4

C1

C2

C3

C4

C1

C2

C3

C4

C1

C2

C3

C4

1° ciclo di lettura del vettore 2° ciclo di lettura del vettore

3° ciclo di lettura del vettore eccetera …



Memoria centrale:

• 32 K / 128 = 256 blocchi

• spazio di indirizzamento della memoria centrale memoria = 32 K, pertanto l’indirizzodi memoria centrale è di log2 32 K = 15 bit

• per identificare uno dei 4 blocchi della memoria cache bastano 2 bit

• ogni blocco è di 128 parole, indirizzabili mediante log2 128 = 7 bit

• pertanto, la dimensione dell’etichetta è di 15 bit − 2 bit − 7 bit = 6 bit

Etichetta # Blocco Parola

6 bit 2 bit 7 bit

Occupazione blocchi da parte del vettore: 640 / 128 = 5 blocchi

Andamento della simulazione: si immagini di numerare i 5 blocchi del vettore come V0, V1,V2, V3 e V4.

4 miss

C1 V0

C2 V1

C3 V2

C4 V3

1 miss

C1 V0

C2 V1

C3 V2

C4 V3

1 miss

C1 V4

C2 V1

C3 V2

C4 V3

1 miss

C1 V4

C2 V1

C3 V2

C4 V3

1 miss

C1 V0

C2 V1

C3 V2

C4 V3

ecc.

C1 V0

C2 V1

C3 V2

C4 V3

1 miss

C1 V4

C2 V1

C3 V2

C4 V3

ecc.

C1 V4

C2 V1

C3 V2

C4 V3

1° ciclo di lettura del vettore 2° ciclo di lettura del vettore

3° ciclo di lettura del vettore eccetera …


Alla prima iterazione si hanno 5 miss, poi solo 2 per ogni iterazione successiva.

# miss = 5 + 9 × 2 = 23 miss

# hit = (10 × 640) − 23 = 6377 hit

Tsenza cache = 10 × 640 × 100 ns = 640 µs

Tcon cache = 6377 × 10 ns + 23 × (128 × 100 ns + 10 ns) = 358,4 µs

Con la politica “read back” il processore attende che il blocco sia stato interamente copiato nellamemoria cache prima di leggere la parola cercata. Con la politica “write back” il processore scrivesolo nella cache, senza aggiornare la copia del blocco in memoria centrale; questa vieneaggiornata in seguito, di solito quando occorre espellere il blocco dalla cache.

Infine, si ha:

Guadagno = Tsenza cache / Tcon cache = 640 µs / 358,4 µs = 1,78

In conclusione, il sistema dotato di memoria cache è il 78% più veloce del sistema senza memoriacache.


Esercizio 5

Supponendo di avere una memoria centrale da 64 K × 32, divisa un blocchi da 32 × 32, e unamemoria cache da 1K × 32, anch’essa suddivisa in blocchi da 32 × 32, mostrare come vascomposto l’indirizzo di una parola in memoria centrale, nei tre casi seguenti:

CACHE A INDIRIZZAMENTO DIRETTO (direct-mapped):

ETICHETTA # BLOCCO PAROLA

CACHE A INDIRIZZAMENTO ASSOCIATIVO (fully-associative):

ETICHETTA PAROLA

CACHE A INDIRIZZAMENTO A GRUPPI (set-associative): si supponga che ogni gruppocontenga 4 blocchi.

ETICHETTA # GRUPPO PAROLA


L’indirizzo di memoria centrale è a 16 bit, quello di memoria cache è a 10 bit, quello di parolaall’interno del blocco è a 5 bit; la memoria centrale contiene 64K / 32 = 2048 blocchi, la memoriacache contiene 1K / 32 = 32 blocchi che, nella versione a gruppi, sono organizzati in 32 / 4 = 8gruppi.

Pertanto:

# di bit dell’indirizzo della parola in memoria centrale: 16

# di bit dell’indirizzo della parola nel blocco: 5

# di gruppi contenuti nella cache:

indirizzamento diretto: 32

indirizzamento associativo: 1

indirizzamento a gruppi: 8


REGOLA GENERALE:

m: # di bit dell’indirizzo della parola in memoria centrale

b: # di bit dell’indirizzo della parola nel blocco

g: # di gruppi contenuti nella cache

e: # di bit dell’etichetta di blocco da memorizzare nella memoria associativa

m = b + � log2g � + e

Pertanto: e = m − b − � log2g �

CACHE A INDIRIZZAMENTO DIRETTO (direct-mapped):

ETICHETTA # BLOCCO PAROLA

6 bit 5 bit 5 bit

Poiché m = 16, b = 5 e g = 32, si ha e = 16 − 5 − � log232 � = 16 − 5 − 5 = 6

CACHE A INDIRIZZAMENTO ASSOCIATIVO (fully-associative):

ETICHETTA PAROLA

11 bit 5 bit


CACHE A INDIRIZZAMENTO A GRUPPI (set-associative): ogni gruppo contiene 4 blocchi.

ETICHETTA # GRUPPO PAROLA

8 bit 3 bit 5 bit



Esercizio 6

Si supponga di avere una memoria centrale da 64 K × 32, divisa un blocchi da 64 × 32, e unamemoria cache da 512 × 32, anch’essa suddivisa in blocchi da 64 × 32, di tipo a indirizzamentodiretto (direct-mapped).

Un programma legge ciclicamente per 4 volte un vettore lungo 640 parole. Si calcoli il guadagno diprestazione che si ottiene nella lettura del vettore, eseguendo il programma in questione su uncalcolatore dotato della cache descritta rispetto a eseguire lo stesso programma su un calcolatoreche non dispone di tale cache, ma solo della memoria centrale indicata. Il guadagno di prestazionesi esprime così:

guadagno lettura vettore = Tempo di lettura vettore sul sistema senza cache Tempo di lettura vettore sul sistema con cache

Si supponga che il processore impieghi 10 ns per leggere una parola dalla memoria cache e 100ns per leggere una parola dalla memoria centrale. Si supponga anche che l’unità funzionale checarica i blocchi di memoria centrale in cache impieghi 64 × 100 ns = 6400 ns = 6,4 µs per caricareun blocco in memoria cache. Si supponga infine che il sistema di cache adotti il metodo di letturaread back (o di lettura differita). All’inizio il vettore si trova tutto in memoria centrale e tutti i blocchidella cache sono liberi.


Tempo di lettura vettore sul sistema senza cache:

T1 = # iterazioni ciclo × lunghezza vettore × tempo lettura parola in mem. centrale

# di iterazioni ciclo = 4

lunghezza del vettore = 640

tempo di lettura della parola in memoria centrale = 100 ns

T1 = 4 × 640 × 100 ns = 256000 ns = 256 µs

Tempo di lettura vettore sul sistema con cache:

T2 = si ricava per simulazione

I blocchi sono da 64 parole. Il vettore è formato da 640 / 64 = 10 blocchi, che si possono numerareB0, … B9. La memoria cache contiene 8 blocchi. Chiaramente, in cache ci possono stare almassimo 8 dei 10 blocchi che formano il vettore. Ecco i passi di simulazione:


1a iterazione

B0

B1

B2

B3

B4

B5

B6

B7

8 blocchi

8 miss

B8

B9

B2

B3

B4

B5

B6

B7

10 blocchi

2 miss

2a iterazione

B0

B1

B2

B3

B4

B5

B6

B7

8 blocchi

2 miss

B8

B9

B2

B3

B4

B5

B6

B7

10 blocchi

2 miss

3a iterazione

B0

B1

B2

B3

B4

B5

B6

B7

8 blocchi

2 miss

B8

B9

B2

B3

B4

B5

B6

B7

10 blocchi

2 miss

4a iterazione

B0

B1

B2

B3

B4

B5

B6

B7

8 blocchi

2 miss

B8

B9

B2

B3

B4

B5

B6

B7

10 blocchi

2 miss

Dalla simulazione si ha che:

# miss = 8 + 2 + 2 + 2 + 2 + 2 + 2 + 2 = 22

Siccome in totale vengono lette 640 × 4 = 2560 parole, il numero di hit vale:

# hit = # parole lette − # miss = 2560 − 22 = 2538

In caso di miss, il processore si sospende per: tempo caricamento blocco + tempo lettura parola incache, perché la politica di lettura è read back e dunque prima si carica tutto il blocco in cache epoi si legge la parola.

Dunque, il tempo necessario vale:

T2 = # hit × tempo lettura parola in cache + # miss × (tempo caricamento blocco + tempolettura parola in cache)

T2 = 2538 × 10 ns + 22 × (6400 ns + 10 ns)

T2 = 25380 ns + 22 × 6410 ns = 166400 ns = 166,4 µs

E infine si calcola il guadagno:


guadagno lettura vettore = T1

T2 =

256 µs 166,4 µs

≈ 1,53

Pertanto, il guadagno è di circa il 53%.

Estensione: rifare il calcolo del guadagno supponendo che il numero di iterazioni del ciclo dilettura del vettore tenda a infinito.

Soluzione (facile): è chiaro che asintoticamente ci sono 4 miss per iterazione, pertanto ragionandosu 4 iterazioni (come prima) i miss sono 16:

T2 = # hit × tempo lettura parola in cache + # miss × (tempo caricamento blocco + tempolettura parola in cache)

T2 = 2538 × 10 ns + 16 × (6400 ns + 10 ns)

T2 = 25380 ns + 16 × 6410 ns = 127940 ns = 127,94 µs

guadagno lettura vettore = T1

T2 =

256 µs 127,9 µs

≈ 2 µs

Pertanto, il guadagno è di circa il 100%. Tale limite non è superabile con lo schema diindirizzamento proposto.

Altra estensione: rifare il calcolo del guadagno supponendo che la cache sia di tipo associativo(fully-associative). VEDERE SCHEMA IN FONDO.

(vengono 40 miss, che è il massimo!)

Altra estensione ancora: rifare il calcolo del guadagno supponendo che la cache sia di tipo agruppi (set-associative), con 2 blocchi per gruppo.

(vengono 28 miss, che è una situazione intermedia tra indirizzamento diretto e associativo).VEDERE SCHEMA IN FONDO.


Esercizio 7

È data la seguente memoria cache a indirizzamento associativo (fully-associative). I blocchi sonoda 64 parole, la cache contiene 4 blocchi e la memoria centrale contiene 8 blocchi. Il sistema dicache utilizza l’algoritmo di sostituzione LRU.

B7

B6

B5

B4

B3

B2

B1

B0

C3

C2

C1

C0

MEMORIACENTRALE

MEMORIACACHE

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0 0 0

etichetta IND. DIBLOCCO

00

01

10

11

IND. DIBLOCCO

Si supponga che ogni blocco nella cache possieda un “contatore di invecchiamento” da 2 bit (cheassume valori 0, 1, 2, e 3). La cache inizialmente ha i 4 blocchi tutti liberi. È quindi data laseguente successione di operazioni di lettura di parole a certi indirizzi, accompagnata in parte dallarelativa successione di “cache hit” e “cache miss”:

Operazione Esito Azione C0 C1 C2 C3

Legge a ind. 000010101 Miss Carica: C0 ← B0 B0, 0

Legge a ind. 000111111 Hit Nessuna B0, 0


Legge a ind. 101001010 Miss Carica: C1 ← B5 B0, 1 B5, 0

Legge a ind. 010000000 Miss Carica: C2 ← B2 B0, 2 B5, 1 B2, 0

Legge a ind. 010101100 Hit Nessuna B0, 2 B5, 1 B2, 0

Legge a ind. 111110010 Miss Carica: C3 ← B7 B0, 3 B5, 2 B2, 1 B7, 0

Legge a ind. 111000111






Completare la tabella di simulazione riempiendo le celle lasciate vuote, secondo l’algoritmo LRU.Nelle colonne C0, C1, C2 e C3, che rappresentano lo stato dei 4 blocchi della cache, vanno scrittiil blocco caricato in cache e il contatore di invecchiamento, oppure nulla (grigio) se il blocco dicache è libero.



Si prosegue la simulazione LRU

Operazione Esito Azione C0 C1 C2 C3

Legge a ind. 000010101 Miss Carica: C0 ← B0 B0, 0



Legge a ind. 101001010 Miss Carica: C1 ← B5 B0, 1 B5, 0

Legge a ind. 010000000 Miss Carica: C2 ← B2 B0, 2 B5, 1 B2, 0

Legge a ind. 010101100 Hit Nessuna B0, 2 B5, 1 B2, 0

Legge a ind. 111110010 Miss Carica: C3 ← B7 B0, 3 B5, 2 B2, 1 B7, 0

Legge a ind. 111000111 Hit Nessuna B0, 3 B5, 2 B2, 1 B7, 0


Legge a ind. 100000000 Miss Sost: C0 ← B4 B4, 0 B5, 1 B2, 3 B7, 2


Legge a ind. 110000000 Miss Sost: C2 ← B6 B4, 2 B5, 1 B6, 0 B7, 3



SIMULAZIONE CON SCHEMA DI INDIRIZZAMENTO ASSOCIATIVO (fully-associative)

si ricordi che l’algoritmo di sostituzione è LRU

1a iterazione

B0

B1

B2

B3

B4

B5

B6

B7

8 blocchi

8 miss

B8

B9

B2

B3

B4

B5

B6

B7

10 blocchi

2 miss

2a iterazione

B8

B9

B0

B1

B2

B3

B4

B5

8 blocchi

6 miss

B6

B7

B8

B9

B2

B3

B4

B5

10 blocchi

4 miss

3a iterazione

B6

B7

B8

B9

B0

B1

B2

B3

8 blocchi

4 miss

B4

B5

B6

B7

B8

B9

B2

B3

10 blocchi

6 miss

4a iterazione

B4

B5

B6

B7

B8

B9

B0

B1

8 blocchi

2 miss

B2

B3

B4

B5

B6

B7

B8

B9

10 blocchi

8 miss


SIMULAZIONE CON SCHEMA DI INDIRIZZAMENTO A GRUPPI (set-associative)

1a iterazione

B0

B4

B1

B5

B2

B6

B3

B7

8 blocchi

8 miss

B8

B4

B9

B5

B2

B6

B3

B7

10 blocchi

2 miss

2a iterazione

B4

B0

B5

B1

B2

B6

B3

B7

8 blocchi

4 miss

B4

B8

B5

B9

B2

B6

B3

B7

10 blocchi

2 miss


3a iterazione

B0

B4

B1

B5

B2

B6

B3

B7

8 blocchi

4 miss

B8

B4

B9

B5

B2

B6

B3

B7

10 blocchi

2 miss

4a iterazione

B4

B0

B5

B1

B2

B6

B3

B7

8 blocchi

4 miss

B4

B8

B5

B9

B2

B6

B3

B7

10 blocchi

2 miss


Esercizio 8

Si consideri un sistema di memoria costituito da una memoria centrale di 16 M parole e da unamemoria cache di 16 K parole, con 64 parole per blocco. Si chiede di illustrare la struttura degliindirizzi in caso di:

1. Indirizzamento diretto (direct-mapped)

2. Indirizzamento completamente associativo (fully-associative)

3. Indirizzamento associativo a gruppi (set-associative), con 4 blocchi per gruppo

Si supponga ora che la memoria cache con schema di indirizzamento diretto (direct-mapped) siainizialmente vuota. La CPU esegue un ciclo nel quale accede sequenzialmente in lettura aglielementi di un vettore. Il ciclo viene iterato 5 volte. Il vettore contiene 2560 elementi. Ognielemento del vettore è una parola di memoria. Si supponga che il tempo di accesso a una paroladella memoria cache valga 1 ns e che il tempo di accesso a una parola della memoria centralevalga 10 ns. Si chiede di stimare il fattore di miglioramento risultante dell'uso della cache.

DA FARE …


Esercizio 9

Si supponga di avere una memoria centrale da 4 M byte e una memoria cache dati da 64 K bytead indirizzamento associativo a gruppi (set-associative); ogni gruppo contiene 2 blocchi. Lamemoria centrale e la memoria cache sono suddivise in blocchi da 8 K byte ciascuno. La memoriacache si serve dell'algoritmo di sostituzione LRU. Si supponga che un programma debba scandirecircolarmente per 2 volte un vettore di 72 K byte, che inizialmente si trova tutto in memoria centraleed è allineato ai blocchi della memoria centrale (ciò implica che il vettore occupi esattamente 9blocchi di memoria centrale). SI chiede di:

• mostrare la struttura dell'indirizzo di memoria centrale;• calcolare il numero di hit e di miss di cache dati che si verificano durante l'esecuzione del

programma;• supponendo poi che il tempo di accesso a una parola di memoria centrale sia di 100 ns, il

tempo di accesso a una parola di memoria cache sia di 10 ns, e che la penalità di fallimento(miss) sia di 100 microsecondi, calcolare l'eventuale guadagno temporale che si otterrebbepassando da un sistema senza cache a uno con cache.

DA FARE …

Esercizi sulla memoria cache - Informatica 2 - L. …unina.stidue.net/Calcolatori Elettronici...

Documents

Transcript of Esercizi sulla memoria cache - Informatica 2 - L. …unina.stidue.net/Calcolatori Elettronici...