Calcolatori elettronici:Le memorie cache

Il titolo di questa voce non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è A8. Le memorie cache.

A7. Le memorie ad accesso casuale	Calcolatori elettronici	A9. Le memorie ad accesso seriale

Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna)

2 Le memorie cache si trovano a un livello intermedio tra i registri e la memoria principale, e servono per mitigare i tempi di attesa durante gli accessi in memoria da parte del processore. Il processore non deve passare attraverso il bus per accedere alla cache.

Prestazioni

5 Una cache per essere gestita in modo efficiente deve contenere meno dati che non vengono acceduti possibile. Il tempo medio di accesso in memoria per la CPU è la media pesata tra $M^*$ e $C$:

$t_{\text{medio}}=hC+(1-h)M^{*}$

dove:

• $h$ è la percentuale di accessi che avvengono con successo (hit) in cache;
• $C$ è il tempo di accesso alla cache;
• $M$ è la penalità di fallimento (miss), ossia il tempo di accesso in memoria quando il dato non si trova in cache;
• $M^*$ è il tempo impiegato dal processore per accorgersi che il dato non si trova in cache sommato a $M$.

Gestione dei miss

9 In caso di miss, dopo che il dato è stato letto dalla memoria si può scegliere se passarlo subito al processore oppure se salvarlo prima in cache:

• il dato viene subito salvato in cache, e poi viene letto dal processore in cache → si ottiene una semplificazione dell'hardware, perché il processore comunica solo con la cache;
• il dato viene subito passato al processore, e poi viene salvato in cache dal cache controller → non c'è il ritardo della cache, ma il cache controller si complica.

Aggiornamento dei dati in cache

26 Se il processore deve modificare un dato in cache:

• 27 write-back: ogni linea di cache ha un dirty bit, che viene impostato al momento della modifica di un dato, in modo che i dati modificati alla fine vengano salvati in memoria prima che la linea di cache venga sovrascritta;
• 28 write-through: il processore scrive parallelamente sia in memoria sia in cache per mantenerle sincronizzate tra loro → le operazioni di scrittura non beneficiano della presenza della cache, ma i miss in lettura costano meno rispetto al write-back ed è comunque vantaggioso perché le operazioni di scrittura sono molto più rare di quelle di lettura.

Mapping

7 La cache è organizzata in linee, ciascuna delle quali contiene un blocco di memoria, e generalmente ha una dimensione di 8, 16 o 32 byte. Il cache controller si occupa di verificare rapidamente se il dato è in cache e di decidere quale linea riportare in memoria in caso di miss, ovvero quando è necessario far posto a un nuovo blocco. All'inizio di ogni linea vi è un tag, che memorizza l'indirizzo originario del blocco.

31 Di solito ogni linea termina con un bit di validità, che informa se è vuota o se contiene informazioni significative.

Direct mapping

17 Il direct mapping è caratterizzato da una corrispondenza fissa tra il blocco di memoria e la linea di cache.

20 Supponendo che la dimensione dei blocchi sia pari a 16 byte, l'indirizzo della cella di memoria richiesta dal processore viene prima diviso per 16, in modo da escludere i primi 4 bit meno significativi che costituiscono l'offset all'interno del blocco, e quindi viene diviso per il numero di linee, così i bit meno significativi che costituiscono il resto della divisione forniscono direttamente il numero della linea (ad esempio se il numero di linee è 4 si considerano solo i primi 2 bit meno significativi dell'indirizzo). In caso di miss, l'informazione viene letta dalla memoria e caricata in cache in base all'indice calcolato in questo modo, sovrascrivendo il vecchio blocco, e il tag viene aggiornato all'indirizzo del nuovo blocco privato dei bit che costituiscono l'indice della linea di cache.

Vantaggi: il direct mapping richiede solo di dividere per potenze di 2, quindi con tempi di calcolo nulli, e di confrontare l'indirizzo del blocco richiesto con un solo tag. Svantaggio: può capitare che il programma in esecuzione utilizzi di frequente blocchi aventi lo stesso resto della divisione, senza la possibilità di distribuire il carico di lavoro sulle altre linee di cache.

Associative mapping

21 L'associative mapping non prevede la corrispondenza fissa, ma ogni blocco può essere memorizzato in qualsiasi linea di cache.

Vantaggio: la hit ratio è maggiore. Svantaggio: il cache controller deve confrontare l'indirizzo con tutti i tag → spreco di tempo.

25 Il cache controller deve adottare una strategia che in caso di miss con cache piena decida quale blocco sovrascrivere:

• si sovrascrive un blocco a caso → economico;
• coda FIFO: si sovrascrive il blocco che si trova da più tempo in cache → può capitare di sovrascrivere un blocco che il processore utilizza tantissimo;
• LRU: si sovrascrive il blocco usato meno di recente → difficile da realizzare perché è necessario aggiornare la graduatoria delle linee di cache a ogni accesso in cache;
• LFU: si sovrascrive il blocco usato meno di frequente → ancora più difficile da realizzare.

Set associative mapping

23 Nel set associative mapping, le linee di cache sono organizzate a insiemi, detti set; l'indirizzo di ogni set è ottenuto dal resto della divisione per direct mapping, e la scansione dei tag si limita al set → più efficiente. Anche nel set associative mapping, in caso di miss con set pieno il cache controller deve adottare una strategia.

Architettura Harvard

27 L'architettura Harvard si differenzia dall'architettura di Von Neumann per la separazione della memoria dati e della memoria codice.

12 Nell'architettura Harvard sono presenti due cache separate: una per i dati e l'altra per le istruzioni.

Vantaggio: la cache per le istruzioni può evitare di supportare l'aggiornamento delle singole parole. Svantaggio: si potrebbe avere uno spreco economico legato al cattivo dimensionamento della cache: soprattutto nei sistemi general-purpose, il costruttore non può prevedere se il programma utilizzerà molto una cache piuttosto che l'altra.

Cache multiple

30 Nei sistemi a multiprocessore in cui un'unica memoria è condivisa attraverso un singolo bus, se ogni CPU non avesse la propria cache si verificherebbe un collo di bottiglia per l'accesso in memoria. Le attese dovute a due miss concomitanti sono compensate dalla maggiore potenza di calcolo. Se si esegue un programma distribuito su più processori, i programmi in esecuzione sui singoli processori non sono indipendenti, ma ogni tanto richiedono di comunicare tra loro attraverso dei dati condivisi → se un processore modifica un da­to condiviso, anche la copia nella cache dell'altro processore dovrebbe essere aggiornata → esistono dei protocolli di coerenza:

• i dati condivisi possono non venire salvati in cache;
• un cache controller verifica se un altro cache controller sta accedendo a un dato condiviso tramite il bus e blocca la scrittura di quel da­to all'interno della sua cache azzerando il bit di validità.

33 È conveniente avere più livelli di cache: il dato richiesto viene cercato a partire dalla cache di livello più basso (più veloce) a quella di livello più alto (più lenta), e tutto ciò che si trova in una cache deve trovarsi anche nelle cache di livello superiore. Nei sistemi a multiprocessore, le cache nei livelli più alti possono essere condivise da più processori.

Note

A7. Le memorie ad accesso casuale	Calcolatori elettronici	A9. Le memorie ad accesso seriale