Architetture dei processori/Cache
I processori nel corso degli anni sono diventati sempre più veloci mentre le memorie per computer non hanno avuto un incremento paragonabile quindi mentre negli anni '70 le memorie erano significativamente più veloci dei processori dagli anni '90 in poi i microprocessori sono diventati molto più veloci delle memorie. Per impedire al processore di passare più del 90% del suo tempo ad attendere i dati dalla memoria si è deciso di dotare i processori di una ridotta quantità di memoria molto veloce dove conservare i dati utilizzati di frequente. Questa scelta deriva dalla constatazione del principio della località del software: sebbene i programmi utilizzino molta memoria in realtà passano più del 90% del loro tempo ad accedere sempre alle stesse locazioni.
Essendo le cache una copia della memoria la copia deve essere fedele ed aggiornata, disallineamenti tra ciò che si trova in cache e lo stato della memoria possono portare ad errori di elaborazione. Nel caso si voglia realizzare una cache che contenga anche i dati da elaborare bisogna progettare accuratamente il processore in modo da impedire disallineamenti tra lo stato della memoria e lo stato della cache. In un sistema con più processori infatti esistono appositi protocolli che invalidano il contenuto della cache di un microprocessore nel caso la cache non sia aggiornata con lo stato nella memoria. Questi meccanismi aumentano la complessità circuitale e riducono le prestazioni dei processori ma sono indispensabili per ottenere un'elaborazione corretta dei programmi.
Le prestazioni della cache dipendono moltissimo dalla scelta di un'adeguata politica di riempimento della stessa. Nella cache vanno memorizzati i dati utilizzati più di frequente e quindi i microprocessori includono dei circuiti che provvedono a scegliere i dati che nel futuro verranno probabilmente utilizzati. Sebbene vi siano stati molti studi teorici sull'argomento allo stato attuale l'algoritmo più utilizzato provvede a eliminare dalla cache i dati utilizzati meno di recente per sostituirli con i nuovi dati da caricare.
La politica di rimpiazzamento decide dove, nella cache, può risiedere una copia di una particolare locazione di memoria. Se la politica di rimpiazzamento è libera di scegliere in quale linea di cache caricare il dato, la cache è chiamata fully associative. Invece, se ogni dato in memoria può essere posizionato solo in una particolare linea di cache, essa è detta direct mapped. La maggior parte delle cache, però, implementa un compromesso chiamato set associative.
Per esempio, la cache dati di livello 1 dell'AMD Athlon è 2-way set associative, cioè una particolare locazione di memoria può essere caricata in cache in due distinte locazioni nella cache dati di livello 1.
Se ogni locazione in memoria principale può essere caricata in due locazioni diverse, la domanda sorge spontanea: quali? Lo schema utilizzato più frequentemente è mostrato nel diagramma a lato: i bit meno significativi dell'indice della locazione di memoria vengono usati come indici per la cache e ad ognuno di questi indici sono associate due linee di cache. Una buona proprietà di questo schema è che le etichette dei dati caricati in cache non devono includere quella parte dell'indice già codificata dalla linea di cache scelta. Poiché i tag sono espressi su meno bit, occupano meno memoria ed il tempo per processarli è minore.
Sono stati suggeriti altri schemi, come quello della skewed cache, dove l'indice della way 0 è diretto, come sopra, mentre l'indice per la way 1 è calcolato attraverso una funzione di hash. Una buona funzione di hash ha la proprietà che gli indirizzi che sono in conflitto con il direct mapping tendono a non collidere quando sono mappati con la funzione di hash, così è meno probabile che un programma soffra di un numero imprevedibilmente grande di collisioni dovuti ad un metodo d'accesso particolarmente patologico. Lo svantaggio è il ritardo aggiuntivo necessario per calcolare il risultato della funzione di hash. In aggiunta, quando diventa necessario caricare una nuova linea ed eliminarne una vecchia, potrebbe rivelarsi difficile determinare quale tra le linee esistenti è stata usata meno recentemente, in quanto la nuova linea entra in conflitto con differenti "set" di linee per ogni "way"; il tracciamento LRU è infatti normalmente calcolato per ogni set di linee.
L'associatività è un compromesso. Se ci sono dieci posizioni, la politica di rimpiazzamento può riempire una nuova linea, ma quando bisogna cercare un dato devono essere controllate tutte e 10 le posizioni. Controllare più posizioni necessita di più potenza, area e tempo. D'altra parte, le cache con più associatività soffrono di meno cache miss (vedere anche più in basso). La regola di massima è che raddoppiare l'associatività ha circa lo stesso effetto sull'hit rate che il raddoppio della dimensione della cache, da 1-way (direct mapping) a 4-way. Aumenti dell'associatività oltre il 4-way hanno molto meno effetto sull'hit rate e sono generalmente utilizzati per altri motivi (vedere il virtual aliasing, più in basso).
Uno dei vantaggi della cache direct mapped è che permette una esecuzione speculativa semplice e veloce. Una volta che l'indirizzo è stato calcolato, è nota quale sia la linea di cache che potrebbe contenere il dato. Questa può essere letta ed il processore può continuare a lavorare con quel dato prima che finisca di controllare che l'etichetta effettivamente combaci con l'indirizzo richiesto.
L'idea che il processore utilizzi i dati in cache prima ancora che sia verificata la corrispondenza tra etichetta ed indirizzo può essere applicata anche alle cache associative. Un sottoinsieme dell'etichetta, chiamato in inglese hint, può essere utilizzato per scegliere temporaneamente una delle linee di cache associate all'indirizzo richiesto. Questo dato può essere utilizzato dalla CPU in parallelo, mentre l'etichetta viene controllata completamente. Questa tecnica lavora al meglio quando usata nel contesto della traduzione degli indirizzi, come spiegato più in basso.
Quando un dato è scritto nella cache, dopo un po' di tempo deve comunque essere scritto in memoria principale. La decisione del momento in cui questa scrittura deve aver luogo è controllata dalla politica di scrittura. In una cache write-through, ogni scrittura sulla cache comporta una scrittura contemporanea nella memoria principale. In alternativa, una cache write-back non esegue immediatamente questa azione: al contrario, la cache tiene traccia delle linee che contengono dati da aggiornare settando opportunamente quello che viene chiamato il dirty bit. Il dato viene effettivamente scritto in memoria solo quando esso deve essere eliminato dalla cache per far spazio a nuove informazioni. Per questa ragione, una ricerca fallita in una cache write-back spesso genera due accessi alla memoria: uno per leggere il nuovo dato, l'altro per scrivere la vecchia informazione (se indicato dal dirty bit).
Esistono anche alcune politiche intermedie. La cache potrebbe essere ad esempio write-through, ma le scritture potrebbero essere temporaneamente inserite in una coda, così da processare insieme scritture multiple, ottimizzando l'accesso al bus.
Con l'evoluzione dei processori si è deciso di realizzare più livelli di cache. Questi livelli vengono indicato con L1, L2 e L3 a seconda che sia il primo, secondo o terzo livello. Il primo livello usualmente funziona alla stessa frequenza della CPU, il secondo livello funziona a un mezzo o un terzo della frequenza di clock del processore e non sempre è incluso nello stesso processore mentre il terzo livello che non sempre esiste è una cache spesso montata sulla scheda madre del computer ed è una memoria funzionante a frequenza maggiore di quella della memoria RAM ma con frequenza inferiore a quella della cache L2.
Quasi tutti i processori moderni inoltre suddividono le cache in cache dati e cache istruzioni. Questa suddivisione permette di ottimizzare la gestione della cache dato che usualmente il processore esegue sempre le stesse istruzioni mentre i dati possono cambiare con frequenza e quindi una suddivisione dei flussi evita conflitti tra dati che cambiano rapidamente e istruzioni che tendono ad essere sostituite con lentezza.