Architettura degli elaboratori

(1)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Memoria cache e gerarchie di memoria

Marco Tarini

Dipartimento di Scienze Teoriche e Applicate [email protected]

Il problema della memoria

Problema: la velocità delle memorie cresce più lentamente della velocità dei processori

Parametro economico: tempo di accesso rispetto al costo per Mbyte.

(2)

Prestazioni di processori e cache

Memoria cache

Architettura degli elaboratori - 3 -

1 10 100 1000

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

1982

Prestazioni

Legge di Moore

+9%/anno Raddoppia ogni 10 anni

+ 60%/anno

Raddoppia ogni anno e mezzo

Divario di prestazioni Processore-Memoria (cresce del 50% / anno)

Obiettivo:

Migliorare le prestazioni attraverso il sistema di memoria:

fornire agli utenti una memoria grande e veloce

fornire al processore i dati alla velocità con cui è in grado di elaborarli

Memoria cache

(3)

Soluzione: gerarchia di memoria

Utilizzare diversi livelli di memoria, con tecnologie diverse in modo da ottenere un buon compromesso costo/prestazioni

Memoria cache

Tempo di accesso da parte della CPU

Dimensioni della memoria Livelli della

gerarchia di memoria

Livello 2 Livello 1

Livello n CPU

. . . .

costo per Mbyte

Livelli della gerarchia di memoria

Register File dim: ~1000 bytes

t: <10s ns

$: N/A Cache (SRAM) dim: KBytes – MBytes

t: 10-100 ns

$: 1-0.1 cents/bit RAM (DRAM) dim: G Bytes

t: 200ns- 500ns

$: .0001-.00001 cents/bit

Disco, oSSD dim: T Bytes,

t: msec s

$: 10^-5 - 10^-6 cents/bit Internet

Registri Cache

Memoria Centrale Memoria di massa

Singoli registri

«Blocchi»

Pagine / File

Files

Prog. assembler /compilatore 1-8 bytes

Controlore cache 8-128 bytes

OS 512-4K bytes

Browser

G R A N D E V E L O C E

(4)

Il principio di località

Località: in ogni istante di tempo il tipico programma accede a una parte relativamente piccola del suo spazio di indirizzamento

Località temporale: se un dato viene referenziato in un dato istante, è probabile che lo stesso dato venga nuovamente richiesto entro breve

Località Spaziale: Se un dato viene utilizzato in un dato istante, è probabile che dati posizionati in celle di memoria adiacenti vengano anch’essi richiesti (entro breve)

Importanza pratica:

Per chi progetta l’Hardware:

ottimizzare l’architettura assumendo che valga il principio di località (negli ultimi 25 anni, le tecniche di miglioramento delle prestazioni nell’hardware si sono basate sul principio di località!)

Per chi progetta il Software:

ottimizzare i programmi per far si che valga il principio di località!

Memoria cache

Alcune note terminologiche

Pattern di accesso alla memoria: (di un programma)

la sequenza temporale di indirizzi di memoria a cui il programma accede (in lettura e scrittura) nel corso della sua esecuzione.

Può rispettare più o meno bene i principi di località Spazio di indirizzamento:

l’insieme di indirizzi di memoria a cui un programma può accedere (in lettura e scrittura).

a causa di memoria virtuale e altri meccanismi automatici del sistema operativo, non necessariamente coincide con l’insieme di indirizzi (fisici) messi a disposizione da un data architettura Locazione di memoria: sinonimo di indirizzo di memoria

di solito, coincide con la parola dell’archiettura

Cache coherent: un programma il cui pattern di accesso alla memoria rispetti bene il principio di località. Sfrutta bene la cache!

La cache coherence può influenzare drasticamente la velocità di esecuzione di un programma!

Memoria cache

(5)

Gerarchia di memoria

Si considerino solo due livelli di gerarchia:

Il processore richiede un dato al sistema di memoria:

La richiesta viene prima inviata al livello di memoria superiore (più vicino al processore, più alto nella gerarchia di memoria)

Se il dato non è presente nel livello superiore (fallimento della richiesta) la ricerca viene effettuata nel livello inferiore

Memoria cache

Livello inf di memoria Livello sup.

di memoria blocco X

blocco Y Processore

blocco X

Gerarchia di memoria: definizioni

Hit (successo): dati presenti in un blocco del livello superiore (esempio:

Blocco X è nella cache)

Hit Rate (tasso di successo): numero di accessi a memoria che trovano il dato nel livello superiore sul numero totale di accessi Hit Time (tempo di successo): tempo per accedere al dato nel livello superiore della gerarchia = Tempo di accesso alla cache + tempo per determinare successo/fallimento della richiesta

(6)

Gerarchia di memoria: definizioni

Miss (fallimento): i dati devono essere recuperati dal livello inferiore della memoria (Blocco Y)

Miss Rate (tasso di fallimento)= 1 - (Hit Rate)

Miss Penalty (tempo di fallimento): tempo necessario a sostituire un blocco nel livello superiore + tempo per trasferire il dato al

processore

Hit Time << Miss Penalty

Memoria cache

Memoria Cache

Memoria al livello superiore della gerarchia (subito sotto ai registri)

Tenere in memoria cache i dati utilizzati più di recente

(il principio di località dice: di solito saranno utilizzati nel futuro prossimo!) Obiettivo: fornire dati al processore in uno o due cicli di clock

Veloce nei tempi di accesso ma di dimensioni ridotte Caratteristiche tipiche:

SRAM

Integrata nel processore! (nello stesso microchip) Dim tipiche: da decine a migliaia di Kbytes.

Non necessariamente un livello solo!

Spesso, questo spezzato in due o più livelli distanti:

Cache L1 (più piccola, più veloce, più vicina) Cache L2 (più grande, più lenta, più lontana)

(ma cmq molto più piccola e veloce della memoria centrale!)

Memoria cache

(7)

Cache e principio di località

Le memorie cache trasferiscono dal livello inferiore della gerarchia più dati di quanti ne siano stati strettamente richiesti

Si trasferisce l’intero «blocco» di memoria (o linea di cache) invece che solo il dato richiesto

In lettura:

Cache hit: trovo il dato richesto in un blocco già nella cache:

lo fornisco alla CPU, e non serve altro

Cache miss: carico il dato dalla RAM e intanto copio l’intero blocco nella cache…

…al posto di qualche altro blocco nella cache. Ma quale?

Diverse strategie.

Idealmente, vorremmo sostituire quel blocco che verrà usato fra più tempo (ma non si può sapere quale sia!)

Es di strategia: LRU (Least Recently Used)

«sostituire il blocco a cui si è fatto accesso meno di recente»

(funziona bene, assumendo il principio località)

Memoria cache

Memoria cache: organizzazione

Problemi pratici:

Come verifico se un dato è presente in cache?

Se lo è, dove lo trovo nella cache?

Se non lo è, e accedo alla memoria centrale…

…quale dato della cache sovrascrivo?

Primo esempio di soluzione:

Indirizzamento diretto

Ogni blocco di RAM può finire in 1 e 1 sola posizione di cache (ma un blocco in Cache viene da 1 di molti blocchi possibili in RAM) L’indice di blocco nella cache

è dato dai k bit meno significativi dell’indice del blocco in RAM

(8)

Struttura delle cache a indirizzamento diretto

Ogni posizione della cache include:

Valid bitche indica se questa posizione contiene o meno dati validi.

0: posizione di cache non ancora utilizzata

1: posizione di cache occupata con dei dati dalla RAM

(Quando il calcolatore viene acceso tutte le posizioni della cache sono segnalate come NON valide)

Campo etichetta (Tag) contiene un valore che identifica

univocamente l’indirizzo del blocco di memoria memorizzato nella posizione della cache

Il valore del Tag include l’indirizzo del blocco in RAM,

eccetto i k bit meno significativi (non mi servono! Sono la posizione nella cache)

Campo datiche contiene una copia del blocco in RAM

Memoria cache

Indirizzamento diretto

Per sapere se un blocco di un dato indirizzo m è in cache:

con m composto da due sottosequenze di bit m0 e m1 m = m0 , m1

accedo al blocco m1 della cache se valid bit = 0 : cache miss se valid bit = 1

analizzo il tag memorizzato nel blocco di cache.

Se corrisponde a m0 : cache hit Altrimenti: cache miss

Memoria cache

(9)

Cache a indirizzamento diretto

Indirizzo del dato in cache = indirizzo in memoria modulo il num di blocchi

Memoria cache

Cache Memoria

N Blocchi

000001 010011 100101 110111 00000

00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

N Blocchi

Cache a indirizzamento diretto

Memoria centrale: N blocchi in memoria Ogni blocco, B parole

Ogni parola, P byte (di 8 bit ciascuno!)

Memoria Cache:

C blocchi, C << N

Totale memoria RAM: BxN parole , NxMxP bytes , NxMxP bits Assunzione importante: C e M e K tutti sono potenze di 2

Ricorda: modulo e divisione intera per potenze di due…

k mod 2^m= gli m bit meno significativi di k k div 2^m = gli altri bit più siginificativi di k

(10)

Cache a indirizzamento diretto

Esempio dati:

memoria RAM totale = 16 MegaByte parole da 32 bit

blocchi di : 512 parole

mem cache (esclusi bit di tag) = 128 Kbytes Domande:

Lunghezza indirizzo di una parola in RAM?

Lunghezza indirizzo di un byte in RAM?

Bit di tag della cache?

Dato il byte di indirizzo 101101001111011110001101:

indice della parola in RAM?

indice del byte nella parola? (il “byte offset”) indice del blocco nella cache?

posizione del byte nel blocco?

TAG del blocco in cache?

Memoria cache

Cache a indirizzamento diretto

Esempio dati:

memoria RAM totale = 16 MegaByte= 2²⁴bytes parole da 32 bit = 4 bytes = 2²bytes

blocchi di : 512 parole = 2⁹parole = 2¹¹ bytes

mem cache (esclusi bit di tag) = 128 Kbytes = 2¹⁷bytes = 2¹⁵ parole Domande:

Lunghezza indirizzo di una parola in RAM? 24 – 2 = 22 Lunghezza indirizzo di un byte in RAM? 24

N. blocchi in memoria cache? 2¹⁷/ 2¹¹= 2⁶= 64 N. blocchi in memoria RAM? 2²⁴/ 2¹¹= 2¹³= ~ 8000 Bit di tag della cache? 13 – 6 = 7

Memoria cache

(11)

indice del byte in RAM

Cache a indirizzamento diretto

Esempio dati:

memoria RAM totale = 16 MegaByte= 2²⁴bytes parole da 32 bit = 4 bytes = 2²bytes

blocchi di : 512 parole = 2⁹parole = 2¹¹ bytes

mem cache (esclusi bit di tag) = 128 Kbytes = 2¹⁷bytes = 2¹⁵ parole

Memoria cache

indice parola in RAM

byte offset indice parola

nel blocco TAG del blocco

in Cache

1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 0 0 0 1 1 0 1 indice blocco in RAM

indir. blocco in Cache

Indirizzamento nella cache a indirizzamento diretto: esempio

Ad ogni indirizzo di memoria

corrisponde una ed una solaposizione nella cache.

Ogni parola di memoria può trovrsi in un’unica posizione della cache Ad ogni posizione della cache

corrispondono più indirizzi di memoria Memory (16 parole)

Direct Mapped Cache (4 parole) Address

Cache Index

0 1 2 3 0

1 2 3 4 5 6 7 8 9 A B C D E

(12)

Cache a indirizzamento diretto da 4 parole

Posizione 0 (00) può essere occupata da dati (parole) provenienti da:

Indirizzi di memoria 0, 4, 8, ... etc.

In generale: ogni indirizzo di memoria i cui 2 bit meno significativi dell’indirizzo sono 0

La posizione in cache è data dai due bit meno significativi dell’indirizzo

Memoria cache

0 (0000) 1 (0001) 2 (0010) 3 (0011) 4 (0100) 5 (0101) 6 (0110) 7 (0111) 8 (1000) 9 (1001) A (1010) B (1011) C (1100) D (1101) E (1110) F (1111)

0 (00) 1 (01) 2 (10) 3 (11) Memory (16 parole)

Direct Mapped Cache (4 parole)

Cache a indirizzamento diretto da 4 parole

Ciascuna parola della cache può corrispondere a diverse locazioni di memoria.

Come fare a individuare quella giusta?

Mediante il campo “TAG”

Memoria cache

0 (0000) 1 (0001) 2 (0010) 3 (0011) 4 (0100) 5 (0101) 6 (0110) 7 (0111) 8 (1000) 9 (1001) A (1010) B (1011) C (1100) D (1101) E (1110) F (1111)

Memory (16 parole)

Direct Mapped Cache (4 parole)

xyz ccc

aaa bbb

0 (00) 1 (01) 2 (10) 3 (11)

Valid Tag Data

1 10 xyz 1 11 aaa 1 10 bbb 1 00 ccc

(13)

Memoria cache

Hit

Tag

20 10

IndexValid Data

Index Tag

Data

20 32

0 1 2

…

… 1021 1022 1023 Address

31..12 11..2 1,0 Byte offset

Il byte offset può essere usato per selezionare un byte all’interno della parola

trovata

Cache a indirizzamento diretto con blocchi da una porola

Linee di cache (blocchi) di dimensioni superiori alla parola

Indirizzi di memoria a 32 bit

Cache a indirizzamento diretto con 4096 (2¹²) linee di cache. Ciascuna linea contiene 4 parole a 4 byte.

Struttura dell’indirizzo di memoria:

Bit 0 e 1 per individuare il singolo byte

Bit 2 e 3 per individuare una parola nel blocco Bit 4-15 per individuare il blocco di cache Bit 16-31 come tag

(14)

Cache a indirizzamento diretto

La linea di cache di dimensioni maggiori (es. 4 parole) per sfruttare la località spaziale

Memoria cache

31 30 29 28 27 ………16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Spiazzamento byte

4 K elementi Dati

Successo Dato

128 bit

Spiazzamento blocco 16 bit

Indice Etichetta

Etichetta V

=

32 16 16 12

Indirizzo (con l’indicazione della posizione dei bit)

32 32 32

2

Multiplexer

32

Prestazioni

Aumento delle dimensioni della linea di cache (blocco) infludenza il miss-rate… in meglio o in peggio?

Memoria cache

1 KB 8 KB 16 KB 64 KB 256 KB

256 40%

35%

30%

25%

20%

15%

10%

5%

0%

Missrate

64 16

4

Block size (bytes)

Total cache size:

(15)

Prestazioni

Dimensione della cache:

diminuisce il miss rate,

ma il beneficio diminuisce all’aumetare della dimensione

aumenta il costo (ovviamente) e lo hit-time (memoria più grande) Indirizzamento diretto: semplice e veloce

Indirizzamento associativo: caro oppure lento

Per compiere tutte queste difficili scelte, si utilizza profiling:

si simula il comportamento della cache su programmi reali di esempio e si valuta il bilancio fra costi e benefici:

serve un benchmark di programmi di esempio

il benchmark deve includere programmi di natura molto diversa es un simulazione fisica e del video processing e un foglio di calcolo e…

Memoria cache

Hit vs. Miss in lettura

Interazione tra processore e cache: lettura o scrittura di un dato Cache hit in lettura

Dato letto dalla cache

Tutto ok. Nient’altro da fare  Cache miss in lettura

richiesta alla memoria del blocco contenente il dato cercato, copia in cache,

ripetizione dell’operazione di lettura in cache

stallo della CPU: durante tutto questo tempo la CPU aspetta

(16)

Hit vs Miss in scrittura

Successo nella scrittura:

due strategie possibili

Sostituzione del dato sia in cache sia in memoria (write-through) Scrittura del dato solo nella cache (write-back) :

(la copia in memoria avverrà in un secondo momento) Fallimento nella scrittura (il dato non è in cache):

stallo della CPU, mentre:

richiesta del blocco contenente il dato cercato alla memoria, copia in cache,

ripetizione dell’operazione di scrittura

Memoria cache