Calcolatori elettronici/Le memorie cache

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

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

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

Se il processore deve modificare un dato in cache:

• 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;
• 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

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.

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

Direct mapping

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

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

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

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

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

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

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

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 dato 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 dato all'interno della sua cache azzerando il bit di validità.

È 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.