LE MEMORIE
Davide D’Amico
PERCHE’ E’ IMPORTANTE LA PERCHE’ E’ IMPORTANTE LA VELOCITA’ DELLE MEMORIE ?VELOCITA’ DELLE MEMORIE ?
1
10
100
1000
19
80
19
81
19
82
19
83
19
84
19
85
19
86
19
87
19
88
19
89
19
90
19
91
19
92
19
93
19
94
19
95
19
96
19
97
19
98
19
99
20
00
DRAM
CPU
I tempi di accesso alle normali memorie RAM sono nettamente più alti dei tempi di propagazione attraverso le unità CPU, e questo crea il cosiddetto “COLLO DI BOTTIGLIA” in termini di prestazioni.
ASSIOMA DEL PROGETTO HARDWARE :
“PICCOLO E VELOCE”
APPLICATO ALLE MEMORIE PER DUE RAGIONI DIFFERENTI:
1. RITARDO MAGGIORE NELLA PROPAGAZIONE DEI SEGNALI
2. MEMORIE PICCOLE PIU’ VELOCI DELLE GROSSE
PRINCIPIO DI LOCALITA’ SPAZIALE E TEMPORALE
• LOCALITA’ TEMPORALE : QUANDO UNA CELLA DI MEMORIA VIENE UTILIZZATA, E’ PROBABILE CHE PRESTO VENGA UTILIZZATA DI NUOVO
• LOCALITA’ SPAZIALE : QUANDO UNA CELLA DI MEMORIA VIENE UTILIZZATA, LE CELLE VICINE HANNO UN’ALTA PROBABILITA’ DI ESSERE A LORO VOLTA UTILIZZATE DI LI’ A POCO
GERARCHIA
DI MEMORIE
PRINCIPIO DI
LOCALITA’+
ASSIOMA
“PICCOLO E VELOCE”
INTRODUZIONEINTRODUZIONE
GERARCHIA DI MEMORIEGERARCHIA DI MEMORIE
Sfruttando il principio di località, la memoria di un calcolatore viene realizzata
come una gerarchia di memorie
OBIETTIVO
DARE AL PROGRAMMATORE L’ILLUSIONE DI POTER USUFRUIRE DI UNA MEMORIA AL TEMPO STESSO VELOCE (idealmente, quanto la
memoria al livello più alto) E GRANDE (quanto quella al livello più basso)
Ci sono molti livelli di memoria ciascuna di diversa velocità e dimensione
Le memorie veloci sono più costose e perciò di solito più piccole
Le memorie lente sono più economiche ma anche molto più grandi
Al livello più alto, quello più vicino alla CPU, troviamo memorie più piccole e veloci
Al livello più basso quelle più lente e meno costose
GERARCHIA DI MEMORIEGERARCHIA DI MEMORIEVI SONO 3 TECNOLOGIE PRINCIPALI PER LA COSTRUZIONE DELLE GERARCHIE DI MEMORIE :
LA MEMORIA PRINCIPALE E’ REALIZZATA CON DRAMDRAM (memoria dinamica ad accesso casuale)
LA MEMORIA CACHE E’ REALIZZATA USANDO SRAMSRAM (memoria statica ad accesso casuale)
L’ULTIMA TECNOLOGIA, USATA PER IMPLEMENTARE IL LIVELLO PIU’ CAPIENTE E PIU’ LENTO DELLA GERARCHIA, E’ RAPPRESENTATO DAI DISCHI MAGNETICI.
IL TEMPO DI ACCESSO ED IL COSTO PER BIT VARIANO NOTEVOLMENTE TRA QUESTE TECNOLOGIE, COME MOSTRATO NELLA TABELLA SEGUENTE, CHE RIPORTA VALORI
TIPICI PER IL 1997 ESPRESSI IN DOLLARI
TECNOLOGIA DI MEMORIZZAZIONE TEMPO DI ACCESSO TIPICO COSTO PER Mbyte NEL 1997
SRAM 5 – 25 ns $100 - $250
DRAM 60 – 120 ns $5 - $10
DISCHI MAGNETICI 10 – 20 milioni ns $0.10 - $0.20
LA DIFFERENZA DI PREZZO DIPENDE DAL FATTO CHE LE MEMORIE DRAM UTILIZZANO MENO TRANSISTORI PER OGNI BIT DA MEMORIZZARE : CONSENTONO
QUINDI DI RAGGIUNGERE CAPACITA’ MAGGIORI A PARITA’ DI AREA DI SILICIO
Gerarchia di Memoria : EsempioGerarchia di Memoria : Esempio
DIMENSIONE
Più piccolo
Più grande
COSTO
Più elevato
Più basso
VELOCITA’
Maggiore
Minore
Gerarchia di Memoria : Comunicazione tra livelliGerarchia di Memoria : Comunicazione tra livelli
• Anche se una gerarchia di memoria è in genere composta da più livelli, i dati
vengono scambiati solo tra 2 livelli adiacenti :
LIVELLO
SUPERIORE
LIVELLO
INFERIORE
BLOCCHI
• La più piccola unità d’informazione che un livello sottostante può cedere o
richiedere al livello superiore viene chiamata BLOCCO o LINEA.
LIVELLO SUPERIORE LIVELLO INFERIORE
GLOSSARIOGLOSSARIO
MISS RATEMISS RATE : E’ la frequenza dei fallimenti , ossia la frazione di accessi che non hanno trovato il dato nel livello superiore ( miss rate = 1.0 – hit rate ) .
HIT RATEHIT RATE : E’ la frequenza dei successi , ossia la frazione di accessi alla memoria che hanno trovato il dato desiderato nel livello superiore. Spesso questo parametro viene utilizzato come indice delle prestazioni della memoria gerarchica.
MISSMISS : Se il dato manca ( in inglese MISS ) , per trovare il blocco bisogna accedere al livello inferiore della gerarchia .
HITHIT : Se il dato richiesto dal processore si trova in uno dei blocchi presenti nel livello superiore si dice che la richiesta ha successo ( in inglese HIT ).
GLOSSARIOGLOSSARIO
HIT TIMEHIT TIME : E’ il tempo di successo, cioè il tempo di accesso al livello
superiore della gerarchia di memoria. Comprende anche il tempo necessario a
stabilire se il tentativo di accesso si risolve in un successo o in un fallimento.
TM = hit time + ( miss rate * miss penalty )
Dato che ovviamente è : hit rate + miss rate = 1 , si ottiene che
TTMM : E’ il tempo medio di accesso alla memoria, ed è dato da:
TM = ( hit rate * hit time ) + ( miss rate * miss time ) =
= ( hit rate * hit time ) + [ miss rate * ( hit time + miss penalty )] =
= [ hit time * (hit rate + miss rate)] + (miss rate * miss penalty)
MISS TIMEMISS TIME : E’ il tempo di fallimento, ed è dato da:
miss time = hit time + miss penalty
MISS PENALTYMISS PENALTY : E’ la penalità di fallimento, cioè il tempo necessario per
sostituire un blocco nel livello superiore con un altro blocco preso dal livello
inferiore e per passare alla CPU le informazioni contenute in questo nuovo blocco.
E’ un buffer piccolo e veloce posto tra CPU e memoria centrale
Rende più scorrevole il collo di bottiglia tra processore ( più veloce ) e
memoria ( più lenta )
Affinché la cache sia sufficientemente veloce , la sua dimensione dovrà essere
molto ridotta rispetto alla memoria centrale
Infatti per una memoria VELOCITA’ (tempo di accesso) e DIMENSIONI sono
parametri in conflitto
ESEMPIO DI UTILIZZO DELLA ESEMPIO DI UTILIZZO DELLA MEMORIA CACHEMEMORIA CACHE
Si faccia l’ipotesi che una cache sia 5 volte più veloce della memoria principale e che possa venir usata per il 90% del tempo.Qual’è il guadagno in velocità dovuto all’uso della cache?
RISPOSTA
Applichiamo la LEGGE DI AMDAHL
3,60,28
1
5
0,90,9)-(1
1
CACHE LA CON SPEEDUP
CACHE LAPER TEMPO % CACHE) LAPER %TEMPO-(1
1
SPEEDUP
FRAZIONE) FRAZIONE(1
1
ESECUZIONE DI TEMPO
ESECUZIONE DI TEMPOSPEEDUP
MIGLIORATO
MIGLIORATA
MIGLIORATANUOVO
VECCHIO
USANDO LA CACHE SI OTTIENE QUINDI UNO SPEEDUP 3,6 VOLTE SUPERIORE
CACHE SET ASSOCIATIVE
A N VIE
CACHE COMPLETAMENTE
ASSOCIATIVA
CACHE A INDIRIZZAMENTO
DIRETTO
IN FASE DI ESECUZIONE, LA CPU PUO’ A PRIORI TENTARE DI ACCEDERE A UNA QUALUNQUE PAROLA NELLO SPAZIO TOTALE DI INDIRIZZAMENTO, SPAZIO CHE PUO’
ESSERE VISTO COME CORRISPONDENTE ALL’INTERA MEMORIA RAM
OCCORRE QUINDI DEFINIRE UNA CORRISPONDENZA TRA INDIRIZZO IN MEMORIA DELLA PAROLA E LOCAZIONE NELLA CACHE
A TALE SCOPO SONO STATE DEFINITE ESSENZIALMENTE 3 SOLUZIONI :
PROBLEMA DEL PIAZZAMENTO DI
UN BLOCCO
PROBLEMA DELLA RICERCA DI UN
BLOCCO
PROBLEMA DELLA SOSTITUZIONE DI
UN BLOCCO
PROBLEMA DELLA STRATEGIA DI
SCRITTURA
1. DOVE DI PUO’ METTERE UN BLOCCO CHE VIENE PORTATO DAL LIVELLO INFERIORE AL LIVELLO SUPERIORE ?
2. DOVE SI TROVA IL BLOCCO CHE CONTIENE IL DATO RICHIESTO ?
3. QUALE BLOCCO PRESENTE AL LIVELLO SUPERIORE DEVE ESSERE SOSTITUITO DA UNO DEL LIVELLO INFERIORE ?
4. CHE COSA SUCCEDE IN CASO DI SCRITTURA ?
PROGETTO del SISTEMA di MEMORIA PROGETTO del SISTEMA di MEMORIA per SUPPORTARE la CACHEper SUPPORTARE la CACHE
Gli accessi alla cache che falliscono devono essere soddisfatti dalla memoria principale. Il prezzo da pagare per un fallimento è il MISS PENALTY, cioè un tempo di accesso pari a quello della tecnologia più lenta.
E’ possibile ridurre la PENALITA’ di FALLIMENTO aumentando la banda passante tra memoria e cache.
BANDA PASSANTEBANDA PASSANTE = Numero di byte trasferiti (tra cache e memoria) per ogni ciclo di clock.
Aumentare la banda passante significa aumentare la velocità dei trasferimenti tra cache e memoria
1° PROGETTO del SISTEMA di MEMORIA1° PROGETTO del SISTEMA di MEMORIA
CACHE
MEMORIA
CPU
MEMORIA LARGA una PAROLA
BUS
GLI ACCESSI AVVENGONO SEQUENZIALMENTE
2° PROGETTO del SISTEMA di MEMORIA2° PROGETTO del SISTEMA di MEMORIA
MEMORIA, BUS E CACHE ALLARGATI
CACHE
MEMORIA
BUS
MUX
CPU
AUMENTO DELLA LARGHEZZA DI BANDA
L’ACCESSO IN PARALLELO A TUTTE LE PAROLE DI UN BLOCCO
Fallimento di accesso alla memoria cacheFallimento di accesso alla memoria cache
Si possono distinguere tre cause di fallimento di accesso alle memorie cache:
1. Obbligatorietà (Compulsory) : durante il primo accesso un blocco non è presente nella cache e deve esservi trasferito. Si tratta dei cosiddetti “fallimenti di partenza a freddo” o “fallimenti di primo accesso”, chiaramente indipendenti dalla dimensione della cache.
2. Capacità (Capacity) : se la cache non può contenere tutti i blocchi necessari all’esecuzione di un programma, alcuni blocchi devono essere scartati e ricaricati successivamente. Fallimenti di questo tipo diminuiscono al crescere della dimensione della cache.
3. Conflitto (Conflict) : se la cache è di tipo set – associativo o a corrispondenza diretta ci sono fallimenti causati dai blocchi che bisogna scartare e recuperare più tardi in conseguenza del fatto che più blocchi devono essere caricati nello stesso insieme : nascono così fallimenti per collisione, che diminuiscono con l’aumentare dell’associatività.
Riduzione della penalità di miss mediante cache a più livelliRiduzione della penalità di miss mediante cache a più livelli
Tutti gli elaboratori moderni fanno uso di cache; in molti casi, le cache sono addirittura implementate sullo stesso die del microprocessore usato come CPU.
Per colmare ulteriormente il divario tra le alte frequenze di clock dei processori odierni ed il tempo relativamente lungo necessario ad accedere alle DRAM, i microprocessori ad alte prestazioni supportano un livello aggiuntivo di cache.
Tale cache di secondo livello, che si trova spesso al di fuori del chip in un insieme separato di SRAM, è consultata ogniqualvolta avviene un miss nella cache principale.
Se la cache di secondo livello contiene il dato richiesto, la penalità di miss sarà solamente relativa al tempo di accesso a tale cache, decisamente inferiore al tempo di accesso alla memoria principale.
Se il dato non è presente né nella cache principale né in quella secondaria, si renderà necessario un accesso alla memoria principale, determinando una penalità di miss maggiore.
Frequenza dei fallimenti e dimensione dei blocchiFrequenza dei fallimenti e dimensione dei blocchi
La frequenza dei fallimenti in una memoria cache dipende fortemente dalla dimensione dei blocchi.
In generale la frequenza dei fallimenti diminuisce con l’aumentare della dimensione del blocco, perché un incremento della dimensione del blocco consente una località spaziale superiore.
Però se il blocco è troppo grande rispetto alla dimensione della cache , la frequenza dei fallimenti aumenta con l’aumentare della dimensione del blocco, perché i blocchi diventano pochi , perciò aumenta la competizione per occuparli.
Inoltre aumentare la dimensione del blocco , significa incrementare i tempi di trasferimento del blocco stesso. Perciò aumenta anche il MISS PENALTY.
Ciò può compromettere l’efficienza delle prestazioni della cache.
Frequenza fallimentiFrequenza fallimentiESEMPI di CACHE DIRECT MAPPING ESEMPI di CACHE DIRECT MAPPING
1 kb
8 kb
16 kb
64 kb256 kb
PRESTAZIONI della CACHE e PRESTAZIONI della CACHE e DIMENSIONE dei BLOCCHIDIMENSIONE dei BLOCCHI
AUMENTO della DIMENSIONE dei
BLOCCHI
MIGLIOR SFRUTTAMENTO
PRINCIPIO LOCALITA’
MIGLIORI PRESTAZIONI
PRESTAZIONI della CACHE e PRESTAZIONI della CACHE e DIMENSIONE dei BLOCCHIDIMENSIONE dei BLOCCHI
AUMENTO ECCESSIVO della DIMENSIONE dei
BLOCCHI
MAGGIORE FREQUENZA FALLIMENTI
PRESTAZIONI PEGGIORI
AUMENTO ESAGERATO del
MISS TIME
MEMORIE DI LETTURA / SCRITTURA AD MEMORIE DI LETTURA / SCRITTURA AD ACCESSO CASUALE : RAMACCESSO CASUALE : RAM
Alcune RAM MOS sono di tipo statico mentre altre sono di tipo dinamico.
In una memoria dinamica i dati sono caricati all’interno di
particolari condensatori che, per mantenere i dati, richiedono una
fase periodica di ricarica (rinfresco, o refresh).
In una RAM ( read / write random access memory ) i dati possono essere scritti e letti in
un qualunque indirizzo selezionato secondo una
sequenza qualsiasi
Quando i dati vengono scritti in un dato indirizzo della RAM, i dati precedentemente
memorizzati in quell’indirizzo vengono distrutti e sostituiti con i nuovi
Quando, invece, i dati vengono letti da un dato
indirizzo della RAM, i dati presenti in quell’indirizzo
non vengono distrutti.
Le RAM vengono costruite o con tecnologia bipolare (BJT) oppure con tecnologia
MOS.
Le RAM bipolari sono tutte RAM statiche: ciò significa che gli elementi di memoria utilizzati nel dispositivo
sono i latch, e pertanto i dati possono essere mantenuti per un
periodo di tempo indefinito purché l’alimentazione rimanga applicata
al dispositivo.
RAM
MOS
RAMstatiche
BIPOLARE
RAMdinamiche
RAMstatiche
CLASSIFICAZIONE MEMORIE RAMCLASSIFICAZIONE MEMORIE RAM
S
R
&
&
Q
Ingresso dati
R/W
SCHEMA SCHEMA LOGICO DELLA CELLA DI UNA SRAMLOGICO DELLA CELLA DI UNA SRAM
Uscita dati
COLONNA
RIGA
Matrice di celle di memoria
32X32
Decoderdi
riga
1
32
.
.
.
.
A0
A1
A3
A2
A4
A5
A6
A7
CS
R / W
LETTURA IN UNA SRAM 256 x 4 LETTURA IN UNA SRAM 256 x 4
Decoder di uscita delle colonne
Selettore del dato di ingresso
Buffer di ingresso
Buffer di uscita
ADDRESS VALID
DIAGRAMMA TEMPORALE DI UN CICLO DI LETTURADIAGRAMMA TEMPORALE DI UN CICLO DI LETTURA
ADDRESS
CHIP SELECT
READ / WRITE
DATA OUT
HI - Z
tACS
tCHZ
tOH
tRC
HI - Z
tRC = tempo di durata del ciclo di lettura tACS = tempo di accesso dall’ingresso di selezione
tOH = tempo in cui il dato in uscita si mantiene nonostante il cambiamento di indirizzo
tCHZ = tempo impiegato dal dispositivo a portare l’uscita in alta impedenza
Matrice di celle di memoria
32X32
Decoderdi
riga
1
32
.
.
.
.
A0
A1
A3
A2
A4
A5
A6
A7
CS
R / W
SCRITTURA IN UNA SRAM 256 x 4SCRITTURA IN UNA SRAM 256 x 4
Decoder di uscita delle colonne
Selettore del dato di ingresso
Buffer di ingresso
Buffer di uscita
DIAGRAMMA TEMPORALE DI UN CICLO DI SCRITTURADIAGRAMMA TEMPORALE DI UN CICLO DI SCRITTURA
tDS
tWC
tDH
ADDRESS
CHIP SELECT
READ / WRITE
INPUT DATA
ADDRESS VALID
VALID
tWC = tempo di durata del ciclo di scrittura
tDS = tempo di predisposizione
tDH = tempo per il quale il dato si mantieneoltre il fronte di scrittura
SCHEMA SCHEMA LOGICO DELLA CELLA DI UNA DRAMLOGICO DELLA CELLA DI UNA DRAM
Le celle di una memoria dinamica immagazzinano un bit in un piccolo condensatore invece che in un latch.
Il vantaggio fornito da tale soluzione costruttiva è che questo tipo di cella ha una struttura molto semplice, il che permette di costruire su un unico chip matrici di memoria molto grandi, con un costo per bit inferiore a quello delle memorie statiche.
Lo svantaggio fondamentale consiste, invece, nel fatto che il condensatore di memoria non può mantenere la propria carica indefinitamente : ciò significa che il bit memorizzato viene perso, a meno che la carica del condensatore stesso non venga periodicamente reintegrata (rinfrescata). Tale processo di refresh richiede ulteriori circuiti di memoria e rende quindi più complesso il funzionamento della RAM dinamica.
COLONNA (linea del bit)
RIGA
Descrizione del funzionamento della cella di una memoria dinamicaDescrizione del funzionamento della cella di una memoria dinamica
RIGA
BASSO
BUFFER DI RINFRESCO
RINFRESCO
BUFFER DI INGRESSO
BUFFER DI USCITA
DOUT
R/W
DIN
+
-1
COLONNA
SCRITTURA DI UN 1 NELLA CELLA DI MEMORIA
LINEA DEL BIT
ON
ALTO
BASSOALTO
ALTO
Descrizione del funzionamento della cella di una memoria dinamicaDescrizione del funzionamento della cella di una memoria dinamica
RIGA
BASSO
Buffer di rinfresco
RINFRESCO
Buffer di ingresso
Buffer di uscita
DOUT
R/W
DIN
0
COLONNA
SCRITTURA DI UNO 0 NELLA CELLA DI MEMORIA
LINEA DEL BIT
ON
ALTO
BASSOBASSO
BASSO
Descrizione del funzionamento della cella di una memoria dinamicaDescrizione del funzionamento della cella di una memoria dinamica
RIGA
BASSO
Buffer di rinfresco
RINFRESCO
Buffer di ingresso
Buffer di uscita
DOUT
R/W
DIN
1
COLONNA
LETTURA DI UN 1 DALLA CELLA DI MEMORIA
LINEA DEL BIT
+
-
ALTOALTO
ON
ALTO
ALTO
Descrizione del funzionamento della cella di una memoria dinamicaDescrizione del funzionamento della cella di una memoria dinamica
RIGA
Buffer di rinfresco
RINFRESCO
Buffer di ingresso
Buffer di uscita
DOUT
R/W
DIN
1
COLONNA
RINFRESCO DELLA MEMORIZZAZIONE DI UN 1
LINEA DEL BIT
+
-
ON
ALTO
ALTOALTO
ALTO