Appunti Calcolatori elettronici - parte seconda

ORGANIZZAZIONE DELLA MEMORIA

Data un processore che può indirizzare uno spazio di memoria di

2 locazioni da W bit, l’organizzazione della memoria dipende da

N

diversi parametri

Tipo di integrati, loro parallelismo e dimensione

 Parallelismo del BUS dati e dimensione complessiva desiderata

 LA GERARCHIA DI MEMORIA

GAP DELLE PRESTAZIONI DRAM - CPU

1000 CPU

100

10 DRAM

1 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000

LOCALITÀ ED ORGANIZZAZIONE

GERARCHICA

Le RAM statiche sono veloci ma consumano

⚫ molto ed offrono densità medio/basse

Le RAM dinamiche consumano poco ed

⚫ offrono densità molto alte ma sono lente

rispetto alla CPU (ed ogni anno il divario

aumenta)

LOCALITÀ DEI PROGRAMMI

I programmi godono della proprietà di

❑ località sia Spaziale sia Temporale

Località temporale:

❑ CPU

È molto probabile che un’istruzione

• L

verrà referenziata nuovamente a Registri 0

breve

Località spaziale L

❑ Cache (SRAM) 1

È molto probabile che vengano

• referenziate istruzioni vicine a quella L

Main Memory (DRAM)

attualmente in esecuzione 2

La località dei programmi suggerisce una

❑ gerarchia di memoria Livello Inferiore (Hard Disk) L

3

GERARCHIA DI MEMORIA

I livelli più alti sono caratterizzati da:

 Alta Velocità,

 Alto Costo

 Piccole Dimensioni



I livelli più bassi sono caratterizzati da

 Bassa Velocità

 Basso Costo

 Grandi Dimensioni



L’uso della gerarchia di memoria vuole creare

 l’illusione di una memoria

Grande quanto la memoria di livello più basso

 Veloce come la memoria di livello più alto



GERARCHIA DI MEMORIA

Quando la CPU deve accedere a un dato in memoria

 Il dato viene cercato nella memoria a partire dal livello più alto

1. (L )

1

Se il dato non è presente a livello L , viene cercato al livello

2. i

inferiore L

i+1

Se il dato è presente a livello L , viene trasferito al livello

3. i

superiore L

i-1

Il trasferimento di informazioni all’interno della gerarchia

 avviene tra livelli adiacenti.

Se il dato si trova ad esempio a livello L2, prima viene

 trasferito da L2 a L1 e poi da L1 al processore (L0)

Ogni livello è organizzato in blocchi di n byte

 TEMPO MEDIO DI ACCESSO ALLA MEMORIA

AMAT = Hit time + Miss rate•Miss Penalty

dove:

hit rate: tentativi riusciti/numero di tentativi

⚫ miss rate: miss rate= 1 – hit rate

⚫ Hit time =(t + tempo per determinare se dato è nel livello attuale)

⚫ acc

Miss penalty= (tempo accesso al livello inferiore + tempo

⚫ trasferimento blocco) più basso livello

più alto livello di memoria

al Processore di memoria

Blk X

dal Processore Blk Y

QUATTRO DOMANDE PER CHI PROGETTA LA

GERARCHIA DI MEMORIA

Q1: Dove piazzare un blocco ?

❑ (Block placement)

Q2: Come faccio a sapere se un blocco è

❑ presente?

(Block identification)

Q3: Quale blocco devo sostituire nel caso di Miss?

❑ (Block replacement)

Q4: Cosa succede in scrittura ?

❑ (Write strategy)

Q5: Cosa succede nel caso di miss in scrittura ?

❑ (Write Miss strategy)

Q1: DOVE PIAZZARE UN BLOCCO ?

Full Associative:

❑ Un blocco della main memory può essere mappato in un

• blocco qualsiasi della cache 0

0 blocco 24

7 31

Q1: DOVE PIAZZARE UN BLOCCO ?

Direct Mapped:

❑ Data una memoria cache di NB blocchi, il blocco della

• memoria principale di indice j può essere mappato

solo nel blocco della memoria cache di indice

Index = j modulo NB

Es.

NB = 8

j= 0 --> index= 0 mod 8 = 0

j= 8 --> index= 8 mod 8 = 0

j= 16 --> index= 16 mod 8 = 0

j= 7 --> index= 7 mod 8 = 7

j= 15 --> index= 15 mod 8 = 7

j= 23 --> index= 23 mod 8 = 7

Q1: DOVE PIAZZARE UN BLOCCO ?

N-WAY SET ASSOCIATIVE

N-way Set Associative

❑ Data una memoria cache di NS set, ciascuno di N blocchi, il

• blocco della memoria principale di indice j può essere mappato

nel set della memoria cache di indice

Index = j modulo NS

All’interno del set un blocco può essere piazzato in una

• posizione qualsiasi.

NS = 4

j= 0 --> index= 0 mod 4 = 0

j= 4 --> index= 4 mod 4 = 0

j= 8 --> index= 8 mod 4 = 0

j= 3 --> index= 3 mod 4 = 3

j= 7 --> index= 7 mod 4 = 3

j= 27 --> index= 27 mod 4 =3

Q2: COME FACCIO A SAPERE SE UN BLOCCO

È PRESENTE?

Data una cache direct mapped di NB blocchi e un main memory di NM

❑ blocchi, nello stesso blocco della cache possono essere mappati NM div

NB blocchi.

Per sapere se il blocco presente in cache è quello effettivamente cercato,

❑ oltre a memorizzare il blocco, viene memorizzata una informazione

supplementare, che identifica in modo univoco il blocco.

Potrebbe essere memorizzato l’intero indirizzo di blocco, ma una parte di

❑ tale indirizzo è superflua poiché tutti i blocchi della main memory

mappati sullo stesso blocco della cache hanno lo stesso index

Per una cache direct mapped con NB= 256, IL = 8 bit



j= 0 = “0000000000000000” -> index= 0 mod 256 = 0 = “00000000”

j= 256 = “0000000100000000” --> index= 256 mod 256 = 0 = “00000000”

j= 512 = “0000001000000000” --> index= 512 mod 256 = 0 = “00000000”

j= 1024 = “0000010000000000” --> index= 1024 mod 16 = 0 = “00000000”

j= 2048 = “0000100000000000” --> index= 2048 mod 16 = 0 = “00000000”

Q2: COME FACCIO A SAPERE SE UN BLOCCO

È PRESENTE?

Per sapere se il blocco presente in cache viene memorizzato, oltre al

❑ blocco, il tag ovvero la parte più significativa dell’indirizzo del blocco

che si sta cercando ovvero l’indirizzo di blocco privo dell’index .

Per una cache direct mapped con NB= 256, IL = 8 bit



j= 0 = “0000000000000000” Tag= “00000000” index= “00000000”

j= 259 = “0000000100000011” Tag= “00000001” index= “00000011”

j= 524 = “0000001000001100” Tag= “00000010” index= “00001100”

La memorizzazione del Tag richiede IB= log (NM div NB) bit con NM =

❑ 2

numero di blocchi della Main memory

Q2: COME FACCIO A SAPERE SE UN BLOCCO È

PRESENTE?

Indirizzo di generato dal processore

Tag Index Offset

n bits m bits

L’Offset permette di individuare una word all’interno di un blocco

Se la cache contiene 2 blocchi e il blocco è di 2 bytes, con un indirizzo della

n m

CPU a 32 bit, il tag ha dimensione

32- (n+m)

Q2: COME FACCIO A SAPERE SE UN BLOCCO È

PRESENTE?

Poiché all’avvio i blocchi della cache non contengono

 blocchi della main memory, per verificare se un blocco è

presente in cache è necessario un bit di validità che

all’avvio è posto a 0. Quando un blocco viene caricato in

cache, il bit di validità del blocco viene posto a 1.

Pertanto perché sia presente un hit è necessario che il

 tag prodotto dalla CPU coincida con il tag memorizzato

nella cache all’indirizzo index e che il bit di validità in

corrispondenza dello stesso index sia posto a 1

Se il tag è diverso o il bit di validità è posto a 0 viene

 generato un miss

Q2: COME FACCIO A SAPERE SE UN BLOCCO

È PRESENTE?

l’index

❑ Mediante viene individuato il blocco in cache, mediante il Tag viene

verificato se il blocco presente è quello cercato

L’offset individua la word all’interno del blocco

❑

Q2: COME FACCIO A SAPERE SE UN BLOCCO

È PRESENTE?

Data una cache Set Associative a N vie di NS set e un main memory di NM

❑ blocchi, nello stesso set della cache possono essere mappati NM div NS

blocchi.

La memorizzazione del Tag richiede IB= log (NM div NS) bit

❑ 2

Fissata la dimensione della memoria cache, all’aumentare del numero di

❑ blocchi di ciascun set diminuisce il numero di set presenti ( diminuisce il

numero di bit dell’index e aumenta quello del tag)

Se la cache a N vie ha dimensione 1024 blocchi, offset di 4 bit ( blocco di

❑ 16 byte) e un indirizzo a 32 bit abbiamo

Con N=1 TAG = 18 bit, index = 10 bit, offset = 4 bit

Con N=2 TAG = 19 bit, index = 9 bit, offset = 4 bit

Con N=4 TAG = 20 bit, index = 8 bit, offset = 4 bit

Con N=512 TAG = 27 bit, index = 1 bit, offset = 4 bit

Con N=1024 TAG = 28 bit, index = 0 bit, offset = 4 bit

Nel caso di memoria full associative possiamo pensare la cache con un

❑ unico set e pertanto il tag coincide con l’indirizzo del blocco

Q3: QUALE BLOCCO DEVO SOSTITUIRE NEL

CASO DI MISS?

Random

❑ Least Recently Used

❑

Associativity: 2-way 4-way 8-way

Size LRU Random LRU Random LRU Random

16 KB 5.18% 5.69% 4.67% 5.29% 4.39% 4.96%

64 KB 1.88% 2.01% 1.54% 1.66% 1.39% 1.53%

256 KB 1.15% 1.17% 1.13% 1.13% 1.12% 1.12%

Miss Rate

Q4: COSA SUCCEDE IN SCRITTURA ?

Write through: L’informazione è scritta sia in cache sia nel livello

❑ inferiore di memoria. Coerenza in ogni istante tra la copia in Main

memory è quella nella cache.

Write back: L’informazione è scritta solo in cache. Il blocco della cache

❑ modificato è scritto in main memory solo quando è sostituito. Ad ogni

blocco è associato un dirty bit che viene settato a 1 se il blocco viene

modificato, altrimenti resta a 0. Nel caso di sostituzione vengono

scritti solo i blocchi con dirty bit settati a 1.

Pro e contro di entrambi

❑ WT: Pro: un read miss non richiede scritture (in main memory) se serve

• scartare un blocco della cache poichè la copia presente in main memory del

blocco da scartare è già aggiornata.

Contro: Per realizzare 2 scritture consecutive è necessario che venga

• completata la prima scrittura in Main memory (in questo caso si scrive alla

velocità della main memory).

WB: Pro:più scritture sullo stesso blocco (in cache) comportano una sola

• scrittura in main memory => Richiede una minore quantità di banda tra

memoria e processore.

Contro: nel caso di read miss, se il blocco da scartare ha il dirty bit a 1, è

• necessario prima scriverlo nella main memory.

Q4: COSA SUCCEDE IN SCRITTURA ?

Nel caso in cui si utilizzi il Write Through, per