Newsgroup: it.comp.hardware
Titolo: cache

Sapete indicarmi un sito o qualcosa che parli della memoria cache molto
molto dettagliatamente??
Grazie mille
Alex


Intanto potresti leggere questo miniarticolo tratto dalle Faq del NG
che parla di cpu:
Leggo che i processori hanno la cache associativa a n vie, cosa
significa?
Uno dei più grossi colli di bottiglia presenti all'interno di un
calcolatore è la RAM, che lavora a frequenze nettamente inferiori a
quelle delle cpu (o, se consideriamo un processore pipelined, di un
singolo stadio della pipeline). I calcolatori utilizzano come memoria
centrale delle memorie di tipo DRAM, molto economiche ma allo stesso
tempo lente, altro tipo di memoria è la SRAM, più veloce ma anche più
ingombrante e costosa, in quanto un bit di SRAM richiede molti più
transistor di un bit di DRAM. Si è quindi cercato di ottimizzare
questa
situazione ponendosi come obiettivo ultimo il raggiungimento di una
memoria grande, veloce ed economica.
Giocando su due fondamentali principi (principio di località temporale
= quando si accede ad un elemento di memoria c'è alta probabilità che
entro pochi cicli si acceda nuovamente allo stesso elemento; principio
di località spaziale = quando si fa riferimento ad un elemento di
memoria, c'è alta probabilità che entro breve si acceda ad elementi
con
indirizzo simile) si è pensato di creare più gerarchie di memoria,
ponendo vicino alla cpu memorie piccole e veloci, e all'ultimo livello
la memoria cetrale di sistema. Poichè i livelli gerarchici più alti
(più vicini alla cpu) sono di dimensioni ridotte, è necessario molto
spesso trasferire dati tra i vari livelli gerarchici (sempre tra du
livelli adiacenti). I moderni processori x86 hanno usualmente due
livelli di cache.
La memoria cache viene vista come organizzata in blocchi o linee
(cache lines); la minima quantità di informazione che può essere
trasferita fra due livelli è appunto un blocco. Se il dato richiesto
dalla CPU fa parte di uno dei blocchi presenti nella cache di livello
superiore, si dice che la richiesta ha avuto successo (hit). Se invece
il dato non si trova nel livello superiore, si dice che la richiesta
fallisce (miss): per trovare il blocco che contiene i dati richiesti,
bisogna accedere al livello inferiore della gerarchia e trasferire il
blocco corrispondente al livello superiore.
Si indica come frequenza dei successi (hit rate) la frazione di
accessi alla memoria che hanno trovato il dato desiderato nel livello
superiore; spesso questo valore viene utilizzato come indice delle
prestazioni della memoria gerarchica. Dualmente, la frequenza dei
fallimenti (miss rate), pari a miss rate = (1.0 - hit rate) è la
frazione di accessi alla memoria che non hanno trovato il dato
desiderato nel livello superiore. Il tempo di successo (hit time) è il
tempo di accesso al livello superiore della gerarchia di memoria, e
comprende anche il tempo necessario per stabilire se il tentativo di
accesso si risolve in un successo o in un fallimento. La penalità di
fallimento (miss penalty) è 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. Il tempo di fallimento (miss time) è dato da: miss time
=
hit time + miss penalty. Poiché il livello superiore è più piccolo e
più veloce, il tempo di successo è molto inferiore al tempo necessario
per accedere al secondo livello della gerarchia, che invece
rappresenta
la componente principale della penalità di fallimento.
Durante il progetto di una gerarchia di memoria, quattro sono le
domande a cui bisogna
rispondere:
1. Dove si può mettere un blocco che viene portato dal livello
inferiore al livello superiore? (Problema del piazzamento di un
blocco).
2. Dove si trova il blocco che contiene il dato richiesto?( Problema
della ricerca di un blocco).
3. Quale blocco presente al livello superiore deve essere sostituito
da uno del livello inferiore, in caso di fallimento? (Problema della
sostituzione di un blocco).
4. Cosa succede in caso di scrittura? (Problema della strategia di
scrittura).
Consideriamo innanzitutto il problema del piazzamento di un blocco. In
fase di esecuzione, la CPU può a priori tentare di accedere a una
qualunque parola nello spazio totale di indirizzamento: spazio che può
essere qui visto come corrispondente all'intera memoria RAM (livello
più basso nelle gerarchie della memoria di lavoro), ma che certamente
eccede di gran lunga quello disponibile nella cache di livello
superiore. Occorre quindi definire le possibili modalità per
consentire
ad ogni parola della memoria indirizzabile di trovare (ove necessario)
una posizione della cache in cui possa essere trasferita - in altre
parole, occorre definire una corrispondenza tra l'indirizzo in memoria
della parola e la locazione nella cache. A questo scopo, sono state
definite essenzialmente tre soluzioni diverse:
1. Cache a indirizzamento diretto
2. Cache set-associativa a n vie
3. Cache completamente associativa
1. Cache a indirizzamento diretto
In una cache a indirizzamento diretto (direct mapped), ogni locazione
di memoria corrisponde esattamente a una locazione della cache. Questo
è il metodo meno ottimizzato in quanto 2 blocchi di memoria mappati
sulla stessa locazione di cache non potranno mai esservi presenti
contemporaneamente.
2. Cache completamente associativa
In una cache completamente associativa (fully associative) un blocco
di memoria può essere messo in una qualsiasi posizione della memoria
cache; si vedrà poi come viene creata la corrispondenza fra locazione
della cache e indirizzo in RAM. Poiché il blocco può essere messo in
un
posto qualsiasi della cache, al momento della ricerca tutti i blocchi
della cache dovranno essere esaminati. Questo metodo, sebbene sembri
il
più ottimizzato, è in realtà lento perchè di difficile
implementazione,
e i segnali vengono fortemente rallentati da tutta la logica che
devono
attraversare.
3. Cache set-associativa a n vie
Una cache set-associativa a n vie è costituita da numerosi insiemi
(set), ognuno dei quali comprende n blocchi. Anche la memoria RAM è
vista come organizzata in blocchi: ogni blocco della memoria
corrisponde ad un unico insieme della cache ed il blocco può essere
messo in uno qualsiasi degli n elementi dell'insieme. In altre parole,
in una cache set-associativa a n vie, ogni blocco della memoria può
essere trasferito in un numero prefissato n di posizioni all'interno
di
un insieme.
Si tratta di uno schema intermedio tra quello a indirizzamento diretto
e quello completamente associativo: la corrispondenza blocco di RAM -
insieme avviene con un indirizzamento diretto, mentre tutti i blocchi
nell'insieme vengono poi esaminati per verificare la corrispondenza.
Questo è il metodo migliore perchè bilancia costi, ottimizzazione e
prestazioni.
Problema della ricerca di un blocco.
Poiché ogni elemento della cache può contenere parole memorizzate in
diverse locazioni di memoria, per sapere se una parola di memoria si
trova nella cache bisogna aggiungere nella cache un insieme di
etichette (tag), che contengono le informazioni necessarie per
verificare se una delle parole presenti nella cache corrisponde o meno
alla parola cercata. E' necessario disporre di un metodo per
riconoscere se un blocco della cache contiene informazioni valide: ad
esempio, quando un processore viene acceso la cache è vuota e le
informazioni nelle etichette non hanno nessun significato. Si aggiunge
quindi a ogni elemento della cache un bit di validità (validity bit)
che indicare se l'elemento stesso contiene dei dati validi. Il
validity
bit è ovviamente indipendente dalla particolare filosofia scelta per
il
piazzamento, ed è quindi presente in tutte le soluzioni.
Problema della sostituzione di un blocco.
Quando si verifica un fallimento nell'accesso alla cache, nel caso di
cache a indirizzamento diretto c'è un solo candidato alla
sostituzione:
il problema si risolve quindi immediatamente. In una cache
completamente associativa, invece, bisogna decidere quale blocco
sostituire: ogni blocco è un potenziale candidato per la sostituzione.
Occorre stabilire una politica di sostituzione. Infine, se la cache è
set-associativa, l'insieme interessato è identificato immediatamente
ma
occorre stabilire una politica di sostituzione limitatamente ai
blocchi
compresi nell'insieme. Le principali strategie utilizzate per la
scelta
del blocco da sostituire sono sostanzialmente tre: sostituzione
casuale, sostituzione del blocco usato meno di recente, sostituzione
del tipo "first in first out". Nel caso di sostituzione casuale
(random), la scelta tra i blocchi candidati viene effettuata a caso,
eventualmente utilizzando dei componenti hardware di supporto per
l'identificazione del blocco.
Se la politica è quella del blocco utilizzato meno di recente (Least
Recently Used - LRU), il blocco sostituito è quello che è rimasto
inutilizzato da più lungo tempo. A questo scopo, nei termini più
semplici ad ogni blocco si associano dei contatori verso il basso che
al momento della scrittura nel blocco vengono posti al valore massimo
e
che vengono poi decrementati di un'unità ogni volta che si effettua
una
lettura in un blocco diverso. La sostituzione toccherà quindi il
blocco
associato al contatore col valore più basso. Infine, se la politica
scelta è quella First In First Out (FIFO), il blocco sostituito è
quello utilizzato N accessi precedenti, indipendentemente dal fatto
che
sia stato utilizzato o meno negli ultimi (N-1) accessi.
La selezione casuale ha evidentemente il vantaggio di essere semplice
da realizzare; peraltro, non tiene alcun conto del principio di
località temporale - si rischia di sostituire un blocco che è stato
scritto da poco e cui si tenterà ben presto di accedere nuovamente. Al
crescere del numero di blocchi di cui bisogna tenere traccia,
peraltro,
la politica LRU (che è basata proprio sul principio di località
temporale) diventa sempre più costosa; in pratica, si ricorre a
qualche
semplice approssimazione. Val la pena di notare che in una cache
setassociativa a 2 vie, la sostituzione a caso ha una frequenza dei
fallimenti pari a circa 1.1 volte quella ottenuta utilizzando la
politica LRU. Al crescere delle dimensioni della cache, la frequenza
dei fallimenti diminuisce per entrambe le strategie e la differenza in
termini assoluti diventa minima. Il vantaggio della sostituzione LRU
aumenta al crescere del grado di associatività, ma in tal caso è anche
più difficile da realizzare.
Problema della strategia di scrittura.
Il problema nasce dalla necessità che - quando si deve scrivere il
risultato di un'operazione - si vuole certamente che anche
l'istruzione
di scrittura sia eseguita velocemente (e quindi accedendo alla cache),
ma si vuole anche che l'informazione contenuta - in qualsiuasi istante
- nella cache sia consistente con quella contenuta nella RAM. Le
possibili strategie per la gestione delle scritture sono write through
e write-back.
Nell'approccio write-through, quando si esegue un'istruzione di
scrittura l'informazione viene scritta simultaneamente nel blocco
della
cache e nel blocco della memoria principale. La coerenza è quindi
sempre rispettata, a prezzo però di un maggior tempo richiesto da ogni
operazione di scrittura. Nella soluzione write-back (o copy back),
invece, al momento dell'esecuzione dell'istruzione l'informazione
viene
scritta solo nel blocco della cache. Il blocco modificato viene
scritto
nel livello inferiore della gerarchia solo quando se ne decide la
sostituzione. Al termine della istruzione di scrittura nella cache,
quindi, la memoria RAM conterrà un valore diverso da quello presente
nella cache; in questo caso si dice che la memoria e la cache sono
inconsistenti (cioè non sono coerenti): il blocco della cache può
essere clean (unmodified) se non ci sono state scritture, oppure dirty
(modified) se sono state effettuate scritture.
Poiché le prestazioni delle CPU continuano ad aumentare con un tasso
di crescita superiore a quello delle memorie principali basate su
DRAM,
la frequenza con cui vengono generate le scritture da parte del
processore sarà ben presto superiore a quella gestibile dal sistema di
memoria, anche in presenza di memoria più grandi sia in termini fisici
che in termini logici; è quindi ragionevole prevedere che in futuro
verrà utilizzata sempre più la strategia write-back. Fra l'altro,
ancora il principio di località porta a prevedere che se l'operazione
di scrittura ha interessato un particolare blocco di cache, la
probabilità che nuove scritture interessino lo stesso blocco è alta -
è
quindi probabile che ci siano state numerose modifiche del blocco di
cache prima che questo venga sotituito e che si ricorra al write-back
Ciao