CPU cache

La CPU cache è una memoria veloce e di piccole dimensioni integrata nel processore, progettata per migliorare le prestazioni riducendo il tempo necessario per accedere ai dati dalla memoria principale (RAM).

Caratteristiche

Confronto tra memoria RAM e memoria CPU cache

Il diagramma a sinistra mostra due memorie, la principale e la cache. Ogni posizione della memoria cache contiene un dato (una linea di cache), che, tra i diversi tipi di cache, varia tra 512 byte e 8 MB. La dimensione della posizione di memoria della cache è normalmente più piccola di quella di una memoria normale, che tipicamente varia tra 1 e 16 GB. Ogni posizione di memoria ha un indice (anche chiamato indirizzo di memoria), cioè un identificatore univoco utilizzato per riferirsi a quella specifica posizione. Ogni posizione nella cache possiede anche un'etichetta (tag) che contiene l'indice in memoria principale del dato ivi caricato. Nelle cache dati, questi valori sono chiamati blocchi di cache o linee di cache. Finché la maggior parte degli accessi alla memoria avviene per i dati memorizzati nella cache, la latenza media dell'accesso alla memoria sarà più vicina alla latenza della cache piuttosto che a quella della memoria principale, perciò le performance saranno migliori.

Quando il processore necessita di leggere o scrivere in una data collocazione in memoria principale, inizialmente controlla se il contenuto di questa posizione è caricato in cache. Questa operazione viene effettuata confrontando l'indirizzo della posizione di memoria con tutte le etichette nella cache che potrebbero contenere il dato a quell'indirizzo. Se il processore trova che la posizione di memoria è in cache, si parla di cache hit (accesso avvenuto con successo), altrimenti di cache miss (fallimento dell'accesso). Nel caso di un cache hit, il processore legge o scrive immediatamente il dato sulla linea di cache. Il rapporto tra cache hit e accessi totali è chiamato anche hit rate ed è una misura indiretta dell'efficacia dell'algoritmo di cache.

Nel caso di un cache miss, ne consegue (per la maggior parte delle cache) la creazione di una nuova entità, che comprende l'etichetta appena richiesta dal processore e una copia del dato nella memoria principale. Un fallimento del genere è relativamente lento, in quanto richiede il trasferimento del dato dalla memoria principale, in taluni casi dopo avere cancellato il dato non più valido.

Questo è il motivo per cui una cache molto capiente, anche se gestita con un algoritmo efficiente, in alcune circostanze può essere controproducente in termini di prestazioni. Infatti, il processo di cancellazione di un dato in cache, scaduto e non più valido, e il caricamento nella cache del dato corretto richiede tipicamente più tempo rispetto a quando la CPU legge il dato direttamente dalla memoria principale senza valersi della cache. In altre parole, una cache ampia può comportare, in specifiche situazioni di calcolo, per esempio non iterativi, un numero superiore di cache miss che di cache hit, con un sensibile degrado delle prestazioni.

Alcuni dettagli operativi

Per poter far spazio a nuovi dati nel caso di un cache miss, la cache generalmente deve eliminare il contenuto di una delle linee. L'euristica che utilizza per scegliere quale dato eliminare è chiamata politica di rimpiazzamento. Il problema fondamentale di ogni politica di rimpiazzamento è quello di dover predire il dato della cache che verrà richiesto nel futuro con minor probabilità.

Predire il futuro è difficile, soprattutto per le cache hardware che devono sfruttare regole facilmente implementabili in circuiteria, perciò esistono una serie di politiche di rimpiazzamento e nessuna di esse può essere ritenuta perfetta. Una delle più popolari, la LRU (dall'inglese Least Recently Used, cioè usato meno recentemente), rimpiazza, appunto, il dato al quale si è fatto accesso meno recentemente.

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). Sia il write-back, sia il write-through servono a mantenere la coerenza tra i livelli di memoria.

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.

I dati in memoria principale, dei quali esiste una copia nella cache, potrebbero essere modificati da altre cause (evento non improbabile, ad esempio, in un sistema multiprocessore), perciò i dati nella cache potrebbero diventare obsoleti. I protocolli di comunicazione tra i sistemi di gestione delle cache che conservano la consistenza dei dati sono chiamati protocolli di coerenza.

Il tempo impiegato per leggere un dato dalla memoria (la latenza di lettura) è importante, perché spesso una CPU potrebbe completare la propria coda di operazioni mentre aspetta l'arrivo del dato richiesto. Quando un microprocessore raggiunge questo stato, si parla di stallo della CPU. Con l'aumento della velocità dei microprocessori, l'andare in stallo per cache miss spreca molta potenza di calcolo; le CPU moderne, infatti, possono eseguire centinaia d'istruzioni nello stesso tempo necessario per caricare un singolo dato dalla memoria. Sono state studiate, perciò, varie tecniche per "tenere occupata" la CPU durante questa fase. Alcuni microprocessori, come il Pentium Pro, tentano di eseguire le operazioni che seguono quella che sta aspettando il dato, se indipendenti da essa (per questo in inglese sono chiamati out-of-order). Il Pentium 4 usa il multithreading simultaneo (chiamato HyperThreading nella terminologia Intel), che permette a un altro programma di usare la CPU mentre un primo programma sta aspettando l'arrivo di dati dalla memoria principale.

Associatività

Quali posizioni di memoria possono essere caricate in quali posizioni della cache

La politica di rimpiazzamento decide dove, nella cache, può risiedere una copia di una particolare posizione di memoria. Se tale politica è libera di scegliere in quale linea di cache caricare il dato, la cache viene chiamata fully associative (o anche completamente associativa). Invece, se ogni dato in memoria può essere posizionato solo in una particolare linea di cache, essa è detta direct mapped (o anche a mappatura diretta). La maggior parte delle cache, però, implementa un compromesso chiamato set associative (o anche parzialmente associativa). Per esempio, la cache dati di livello 1 dell'AMD Athlon è 2-way set associative, cioè una particolare posizione di memoria può essere caricata in cache in due distinte posizioni nella cache dati di livello 1.

Se ogni posizione in memoria principale può essere caricata in due posizioni diverse, la domanda sorge spontanea: quali? Lo schema utilizzato più frequentemente è mostrato nel diagramma a lato: i bit meno significativi dell'indice della posizione di memoria vengono usati come indici per la cache e a 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 e 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 a 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à rappresenta un compromesso. Se ci sono dieci posizioni, la politica di rimpiazzamento può riempire una nuova linea, ma quando si cerca un dato, è necessario controllare tutte e 10 le posizioni. La necessità di controllare più posizioni richiede più potenza, spazio e tempo. D'altra parte, le cache con più associatività soffrono di meno di cache miss (di cui si parlerà nel paragrafo successivo). La regola generale è che raddoppiare l'associatività ha circa lo stesso effetto sull'hit rate del raddoppiare della dimensione della cache, passando da 1-way (direct mapping) a 4-way. Aumenti dell'associatività oltre il 4-way hanno un impatto molto meno significativo sull'hit rate e sono generalmente utilizzati per altri motivi (come il virtual aliasing, trattato nella sezione "Traduzione degli Indizi").

Uno dei vantaggi della cache direttamente mappata, è che permette un'esecuzione speculativa semplice e veloce. Una volta calcolato l'indirizzo, è noto quale linea di cache potrebbe contenere il dato. Questa può essere letta e il processore può continuare a lavorare con quel dato prima di completare il controllo per verificare se l'etichetta corrisponde effettivamente all'indirizzo richiesto.

L'idea che il processore utilizzi i dati in cache prima ancora di verificare la corrispondenza tra etichetta e indirizzo può essere applicata anche alle cache associative. Un sottoinsieme dell'etichetta, chiamato hint in inglese, può essere utilizzato temporaneamente per selezionare 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 funziona meglio quando è utilizzata nel contesto della traduzione degli indirizzi, come spiegato più avanti.

Cache miss

Con fallimento della cache (in inglese cache miss) ci si riferisce a un intento fasullo nel leggere o scrivere un pezzo di dati nella cache, che ha come risultato una latenza molto più lunga nell'accesso alla memoria principale. Per un fallimento nella lettura dalla cache istruzioni, il processore deve aspettare (stallo) finché l'istruzione non è caricata dalla memoria principale. Un fallimento della cache causato dal caricamento di un dato può invece essere meno doloroso, perché le altre istruzioni non correlate a esso possono comunque essere eseguite, finché l'operazione che richiede i dati da caricare può essere eseguita. Comunque, i dati sono spesso usati immediatamente dopo l'istruzione di caricamento. L'ultimo caso di cache miss, cioè un fallimento in scrittura, è il meno preoccupante, perché di solito la scrittura è bufferizzata. Il processore può continuare tranquillamente finché il buffer non è pieno. (Non esiste un fallimento nella scrittura della cache istruzioni perché esse sono di sola lettura.)

Per minimizzare la frequenza di cache miss, un grande sforzo di analisi è stato fatto sul comportamento della cache per trovare la miglior combinazione di dimensione, associatività, dimensione dei blocchi e così via. Sequenze di referenze di memoria create dai programmi di benchmark sono salvati come address traces. Ulteriori analisi simulano molte differenti possibilità d'implementazione della cache basate su queste lunghe address traces. Far capire come le molteplici variabili modifichino la frequenza di cache hit può risultare abbastanza confusionario.

Un contributo significante fu fatto da Mark Hill, il quale separò i vari fallimenti della cache in tre categorie (conosciute come "le tre C"):

Compulsory misses sono quei fallimenti causati dalla prima referenza a un dato. La dimensione della cache e la associatività non fanno differenze al numero di compulsory misses. Il prefetching può aiutare qui, così come lo possono fare larghe dimensioni dei blocchi della cache (che sono un tipo di prefetching).
Capacity misses sono quei fallimenti che una cache di una data dimensione avrà, a dispetto dell'associatività o della dimensione del blocco. La curva della frequenza dei capacity misses rispetto alla dimensione della cache fornisce una qualche misura della località temporanea di un particolare flusso di referenze.
Conflict misses sono quei fallimenti che avrebbero potuto essere evitati se la cache non avesse ripulito un dato precedentemente. I conflict misses potrebbero essere ulteriormente divisi in mapping misses, che sono inevitabili data una particolare associatività, e replacement misses, che sono causati dalla particolare scelta della regola di rimpiazzamento.

Frequenza di fallimento (*miss rate*) a confronto con la dimensione della cache (Cache size) sulla porzione degli interi di SPEC CPU2000

Il grafico a destra riassume la performance della cache vista dai benchmarks della porzione degli interi di un SPEC CPU2000, ripresa da Hill e Cantin [1]. Questi benchmark servono a rappresentare il tipo di carico di lavoro che una postazione di lavoro potrebbe subire un giorno qualsiasi. In questo grafico possiamo vedere i differenti effetti delle tre C.

All'estrema destra, quando la cache size assume un valore "Inf" (che, in altre parole, tende all'infinito), abbiamo i compulsory misses. Se volessimo migliorare le caratteristiche dello SpecInt2000, aumentare la dimensione della cache oltre 1MB sarebbe praticamente inutile.

La frequenza di fallimento della cache fully-associative rappresenta a pieno la frequenza dei capacity misses. Nelle simulazioni, è stata scelta una regola di rimpiazzamento LRU: questo mostra che per minimizzare la frequenza dei capacity misses sarebbe necessaria una regola di rimpiazzamento perfetta, come se ad esempio un veggente indagasse nel futuro per trovare una posizione della cache che non stia per essere utilizzata.

Notare come, nella nostra approssimazione della frequenza dei capacity misses, il grafico abbia una brusca caduta tra i 32KB e i 64KB. Questo indica che il benchmark ha un working set di circa 64KB. Un progettista di cache, esaminando questi benchmark, sarebbe fortemente tentato d'impostare la dimensione della cache appena sopra i 64KB, piuttosto che appena sotto questo valore. Bisogna notare inoltre che, su questa simulazione, nessun tipo di associatività può far andare una cache a 32KB bene come una da 64KB 4-way, o addirittura come una direct-mapped da 128KB.

Infine, notare che tra i 64KB ed 1MB c'è una grande differenza tra la cache di tipo direct-mapped e quella fully-associative. Questa differenza è la frequenza dei conflict misses. Secondo i dati del 2004, le cache di secondo livello montate direttamente sul chip del processore tendono a stare in questo intervallo di valori, in quanto le cache piccole sono veloci abbastanza da essere cache di primo livello, mentre quelle più grandi sono troppo costose per essere montate economicamente sul chip stesso (l'Itanium 2 ha una cache di terzo livello da 9MB, la più grande cache on-chip disponibile sul mercato nel 2004). Dal punto di vista della frequenza dei conflict misses, risulta che la cache di secondo livello trae un grande beneficio dall'alta associatività.

Questo beneficio era ben conosciuto nei tardi anni ottanta e primi anni novanta, quando i progettisti di CPU non potevano far stare grandi cache sui chip e non disponevano di sufficiente larghezza di banda per implementare alta associatività sulle cache al di fuori del chip del processore. Furono provate varie soluzioni: il MIPS R8000 usava delle costose SRAM off-chip dedicate, che includevano dei comparatori di etichette e dei grandi driver, per implementare una cache associativa 4-way da 4MB. Il MIPS R10000 usava dei chip ordinari di SRAM per le etichette. L'accesso alle etichette, in entrambe le direzioni, necessitava di due cicli: per ridurre la latenza, il R10000, per ogni accesso, cercava di predire quale modo della cache sarebbe stato quello corretto.

Cache hit

Con cache colpita (in inglese cache hit) ci si riferisce invece a un successo da parte del processore nel trovare l'indirizzo della posizione di memoria tra le varie etichette della cache che potrebbero contenerlo. In caso di successo, il processore può leggere (Hit di lettura di cache) o scrivere (Hit di scrittura di cache) il dato sulla linea di cache.

In caso di Hit di lettura, il processore legge la parola direttamente dalla cache senza coinvolgere la memoria centrale. Per quanto riguarda la Hit di scrittura, ci si rimanda all'approfondimento sulla politica di scrittura della cache

Traduzione degli indirizzi

La maggior parte delle CPU comunemente utilizzate implementano un qualche tipo di memoria virtuale. In pratica, ogni programma che gira sulla macchina vede il proprio spazio di memoria, che contiene codice e dati per il solo programma stesso, in maniera semplificata. Ogni programma mette tutto nel proprio spazio di memoria senza preoccuparsi di quello che gli altri programmi fanno nei loro rispettivi spazi di memoria.

La memoria virtuale richiede che il processore traduca gli indirizzi virtuali generati dal programma in indirizzi fisici nella memoria principale. La porzione del processore che fa questa traduzione è conosciuta come la memory management unit (MMU). La MMU può accedere velocemente alla tabella di traduzioni attraverso il Translation Lookaside Buffer (TLB), che è una cache di mappature per la page table del sistema operativo.

La traduzione degli indirizzi ha tre caratteristiche importanti:

Latenza: Generalmente, la MMU rende disponibile l'indirizzo fisico pochi cicli dopo che l'indirizzo virtuale è computato dal generatore d'indirizzi.
Aliasing: Più indirizzi virtuali possono riferirsi a uno stesso indirizzo fisico. La maggior parte dei processori garantisce che tutti gli aggiornamenti al singolo indirizzo fisico vengano eseguiti in ordine. Per permettere ciò, il processore deve assicurarsi che, in ogni istante, esista in cache una sola copia di ogni indirizzo fisico.
Granularità: Lo spazio degli indirizzi virtuali è suddiviso in pagine. Per esempio, uno spazio virtuale d'indirizzi di 4GB potrebbe essere spezzettato in 1048576 pagine da 4Kb, ognuna delle quali può essere referenziata indipendentemente. Per il supporto di pagine di dimensioni variabili, vedere la voce memoria virtuale.

Una nota storica: i primi sistemi con memoria virtuale erano molto lenti, perché richiedevano un accesso alla page table (residente in memoria) prima di ogni accesso programmato alla memoria. Senza cache, questo dimezza la velocità di accesso alla memoria della macchina. Per questo motivo, la prima cache hardware usata in un computer non è stata una cache di dati o d'istruzioni, ma invece una TLB.

L'esistenza d'indirizzi fisici e virtuali pone la questione su quali di essi utilizzare per le etichette e gli indici della cache. La motivazione di usare indirizzi virtuali è la velocità: una cache di dati con indici ed etichette virtuali esclude la MMU dalle operazioni di caricamento e uso dei dati dalla memoria. Il ritardo provocato dal caricamento dei dati dalla memoria RAM (load latency) è cruciale per le prestazioni della CPU: per questo motivo, la maggior parte delle cache di livello 1 sono indicizzate con indirizzi virtuali, permettendo alla MMU di ricercare nella TLB in parallelo con il recupero dei dati dalla cache della RAM.

L'indirizzamento virtuale non è sempre la scelta migliore: introduce, ad esempio, il problema degli alias virtuali, cioè la cache potrebbe immagazzinare in più posizioni il valore di uno stesso indirizzo fisico. Il costo per la gestione degli alias virtuali cresce con la dimensione della cache e, come risultato, la maggior parte delle cache di livello 2 e superiori sono indicizzate con indirizzi fisici.

Non è comune, invece, l'uso degli indirizzi virtuali per le etichette (virtual tagging). Se la ricerca nella TLB finisse prima di quella nella cache RAM, allora l'indirizzo fisico sarebbe disponibile in tempo per il confronto delle etichette e, quindi, il virtual tagging non sarebbe necessario. Cache di grandi dimensioni, quindi, tendono a essere etichettate con indirizzi fisici (physically tagged) e solo le piccole cache con bassa latenza sono virtually tagged. Nelle CPU più recenti il virtual tagging è stato sostituito dai vhints, come descritto più in basso.

Virtual indexing e virtual aliases

Il tipico modo con cui il processore garantisce che gli alias virtuali funzionino correttamente è ordinarli in maniera che, in ogni istante, solo un alias virtuale possa essere nella cache.

Ogni volta che un nuovo valore è aggiunto alla cache, il processore cerca altri alias virtuali e li rimuove. Questa operazione avviene solo in caso di un fallimento della cache. Nessun lavoro particolare è necessario durante un cache hit, il che aiuta a mantenere il più rapido possibile il percorso veloce nella cache.

La via più immediata per trovare gli alias è di mapparli tutti alla stessa area della cache. Questo succede, per esempio, se il TLB ha pagine da 4KB, e la cache è direct-mapped e a 4KB o meno.

Le moderne cache di primo livello sono molto più grandi di 4KB, ma le pagine di memoria virtuale sono rimaste della stessa dimensione. Se, per esempio, la cache è da 16KB e indicizzata virtualmente, ogni indirizzo fisico può essere indirizzato da 4 diverse posizioni della cache, per altrettanti indirizzi virtuali. Se la cache fallisce, tutte e quattro le posizioni devono essere controllate per verificare se i loro indirizzi fisici corrispondenti effettivamente coincidono con l'indirizzo fisico dell'accesso che ha generato il fallimento.

Questi controlli sono gli stessi che una cache set associative usa per selezionare una particolare corrispondenza. Quindi se un cache indicizzata virtualmente da 16KB, 4-way set associative, viene usata con pagine di memoria virtuale da 4KB, non è necessario alcun lavoro aggiuntivo per eliminare gli alias virtuali in caso di cache miss, in quanto i controlli sono già stati effettuati durante il controllo della cache.

Usiamo ancora un AMD Athlon come esempio: esso ha una cache dati di primo livello da 64KB, con pagine da 4KB, set associative 2-way. Quando la cache dati di primo livello risente di un fallimento, 2 dei 16 (=64KB/4KB) possibili alias virtuali sono già stati controllati e sono necessari sette ulteriori cicli del circuito di controllo delle etichette per completare l'eliminazione degli ulteriori alias virtuali.

Virtual tags and vhints

È possibile anche l'etichettatura virtuale (Virtual tagging). Il grande vantaggio del virtual tag è che, per le cache associative, permettono la corrispondenza delle etichette prima che la traduzione da virtuale a fisica sia fatta. Comunque:

Controlli di coerenza e rimozione presentano un indirizzo fisico per azione. L'hardware deve avere qualche metodo per convertire l'indirizzo fisico in un indirizzo della cache, generalmente immagazzinando etichette fisiche così come le etichette virtuali. Per confronto, una cache etichettata fisicamente non necessita di mantenere etichette virtuali, il che è più semplice.
Quando un riferimento da virtuale a fisico viene eliminato dalla TLB, le informazioni della cache con quegli indirizzi virtuali dovranno essere svuotati in qualche maniera. Se le informazioni della cache sono permesse su pagine non mappate dalla TLB, allora queste informazioni dovranno essere svuotate quando i diritti di accesso su queste pagine cambiano nella page table.

È possibile per il sistema operativo assicurarsi che più virtual aliases siano contemporaneamente residenti nella cache. Il sistema operativo garantisce questo sforzando il page coloring che viene descritto più avanti. Alcuni recenti processori RISC (SPARC, RS/6000) hanno preso questo approccio. Non è stato usato di recente, siccome il costo dell'hardware per scoprire e rimuovere gli alias virtuali si è abbassato mentre la complessità e il prezzo prestazionale del software per un perfetto page coloring si è alzato.

Potrebbe essere utile distinguere le due funzioni di etichettatura in una cache associativa: vengono utilizzate per determinare quale modalità del set d'informazioni da selezionare, e vengono utilizzate per determinare se la cache fallisce o no. La seconda funzione deve essere sempre corretta, ma è permesso alla prima funzione d'indovinare, e avere la risposta sbaglia occasionalmente.

Alcuni processori (Ad esempio recenti SPARC) hanno le cache sia con etichette virtuali che fisiche. Le etichette virtuali vengono utilizzate per la selezione del modo, e le etichette fisiche sono utilizzate per determinare il centro o il fallimento. Questo tipo di cache favorisce il vantaggio della latenza di una cache a etichette virtuali, e la semplice interfaccia software di una cache a etichette fisiche. Supporta il costo aggiunto di etichette duplicate, comunque. Anche durante i processi di fallimento, i modi alternati della linea della cache devono essere controllati per virtual alias e per ogni corrispondenza rimossa.

L'area extra (e qualche latenza) può essere mitigata mantenendo virtual hints con ogni informazione della cache invece che con etichette virtuali. Questi hints sono un sottoinsieme o hash di un'etichetta virtuale, e vengono utilizzati per selezionare il modo della cache tramite cui prelevare un dato e un'etichetta fisica. Con una cache virtually tagged, ci potrebbe essere una corrispondenza di virtual hint ma una non corrispondenza di etichetta fisica, in questo caso la informazione nella cache con la corrispondenza dell'hint deve essere rimossa cosicché accessi alla cache dopo il riempimento della cache in questo indirizzo avranno solamente una sola corrispondenza di hint. Siccome gli hint hanno minori bit delle etichette virtuali distinguerli uno dall'altro, una cache con hint virtuali soffre di più mancanze di conflitti di una cache a etichette virtuali.

Forse la riduzione finale di hint virtuali può essere trovata nel Pentium 4 (Willamette and Northwood cores). In questi processori, l'hint virtuale è effettivamente di soli 2 bit, e la cache è 4-way associative. In effetti, l'hardware mantiene una semplice permutazione da indirizzi virtuali a indirizzi di cache, cosicché nessun CAM sia necessario per selezionare quello giusto dei quattro modi di recupero.

Page coloring

Cache indicizzate fisicamente larghe (solitamente cache secondarie) riscontrano un problema: il sistema operativo piuttosto che le applicazioni controlla quali pagine collidono vicendevolmente nella cache. Differenze nell'allocazione delle pagine da un programma portano al prossimo livello di differenze nei percorsi di collisione della cache, i quali possono portare a differenze molto larghe nelle prestazioni dei programmi. Queste differenze possono far diventare molto difficile ottenere un consistente e ripetibile tempo di benchmark per i programmi in esecuzione, che porta ingegneri pagati e sconsolati a richiedere che gli autori del sistema operativo risolvano il problema.

Per capire il problema, consideriamo una CPU con 1MB di cache di livello-2 direct-mapped indicizzata fisicamente e 4KB di pagine di memoria virtuale. Pagine fisiche in sequenza si mappano in posizioni in sequenza nella cache fino a che dopo 256 pagine il percorso torna su se stesso. Possiamo etichettare ogni pagina fisica con un colore da 0-255 per denotare dove nella cache può andare. Posizioni all'interno di pagine fisiche con colori differenti non possono entrare in conflitto nella cache.

Un programmatore che voglia usare al massimo l'uso della cache potrebbe arrangiare i suoi accessi del programma cosicché solo 1MB di data necessiti di essere messo in cache per volta, tutto questo evitando fallimenti di capacità. Ma dovrebbe anche assicurarsi che gli accessi non abbiano fallimenti di conflitto. Un modo per pensare a questo problema è di suddividere le pagine virtuali che utilizza il programma e assegnare a loro colori virtuali nello stesso modo come colori fisici erano assegnati a pagine fisiche precedentemente. Il programmatore può poi arrangiare gli accessi del suo codice in modo che due pagine con lo stesso colore virtuale non siano in uso nello stesso momento. C'è una distesa letteratura su queste ottimizzazioni (per esempio. Loop nest optimization), proveniente soprattutto dalla comunità High Performance Computing (HPC).

Il concetto è che mentre tutte le pagine in uso in un determinato momento, potrebbero avere differenti colori virtuali, alcune potrebbero avere lo stesso colore fisico, Infatti, se il sistema operativo assegna pagine fisiche a pagine virtuali in modo casuale e uniforme, è molto probabile che alcune pagine abbiano lo stesso colore fisico, e quindi posizioni da queste pagine coincidano nella cache (questo è il Birthday paradox).

La soluzione sta nel fare in modo che il sistema operativo tenti di assegnare pagine fisiche colorate diversamente a differenti colori virtuali, una tecnica chiamata page coloring. Sebbene la mappatura attuale da colori virtuali a fisici sia irrilevante per le prestazioni del sistema, mappature dispari sono difficili da tracciare e hanno piccoli benefici, quindi la maggior parte degli approcci alla colorazione delle pagine tenta semplicemente di tenere pagine fisiche e virtuali colorate nello stesso modo.

Se il sistema operativo può garantire che ogni pagina fisica si riferisca a un solo colore virtuale, allora non vi sono virtual alias, e il processore può usare cache virtually indexed senza la necessità di controlli su extra virtual alias durante la gestione del fallimento. Alternativamente il sistema operativo può svuotare una pagina dalla cache quantunque cambi da un colore virtuale a un altro. Come menzionato prima, questo approccio fu usato da qualche recente progettazione SPARC e RC/6000.

Gerarchia delle cache in un processore moderno

I processori moderni dispongono sul chip di cache multiple con cui interagire. Due motivi, in particolare, hanno portato allo sviluppo della attuale gerarchia delle cache.

Cache specializzate

Il primo motivo è che CPU con pipeline accedono alla memoria da molteplici punti nella pipeline: recupero delle istruzioni, traduzione indirizzi da virtuali a fisici, e recupero dei dati. La naturale implementazione è di utilizzare differenti cache fisiche per ognuno di questi punti, cosicché nessuna risorsa fisica debba essere programmata per servire due punti nella pipeline. Sebbene la pipeline finisca naturalmente con almeno tre cache separate (istruzioni, TLB, e data), ognuna è specializzata in un ruolo particolare.

Victim cache

Una victim cache è una cache utilizzata per mantenere blocchi rimossi dalla cache della CPU a causa di un conflict miss o capacity miss. La victim cache è situata tra la cache primaria e la memoria sottostante, e mantiene solamente i blocchi rimossi dopo un miss. Questa tecnica è utilizzata per ridurre la penalità in cui si incorre per un fallimento della cache, perché può accadere che i dati che sono nella victim cache vengano richiesti qualche tempo dopo, e allora invece di dichiarare un miss, e andare in memoria a recuperare questi dati, si controlla la victim cache e si utilizzano i dati che sono ancora dentro di essa.

La victim cache originale su un HP PA7200 fu una cache piccola, fully-associative. Processori posteriori, come gli AMD Athlon, Athlon XP e Athlon 64 utilizzavano la cache secondaria molto grande come una victim cache, per evitare ripetizioni d'immagazzinamenti del contesto sulla cache primaria.

Trace cache

Uno dei più estremi esempi di specializzazione della cache è quello della trace cache utilizzata nei microprocessori Pentium 4. Una trace cache è un meccanismo per aumentare il fetch bandwidth d'istruzioni immagazzinando tracce d'istruzioni che sono già state immagazzinate. Il meccanismo fu per la prima volta proposta da Eric Rotenberg, Steve Bennett e Jim Smith nel loro articolo del 1996: "Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching."

Una trace cache immagazzina le istruzioni anche dopo che esse siano state eseguite, o come vengono ritirate. Generalmente, le istruzioni vengono aggiunte alle trace cache in gruppi che rappresentano sia blocchi individuali di base che tracce d'istruzioni dinamiche. Un blocco base consiste in un gruppo d'istruzioni non-branch (Non suddivise) che finiscono con una ramificazione. Una traccia dinamica ("trace path" o "traccia del percorso") consistono nelle solo istruzioni di cui il risultato viene effettivamente utilizzato, ed elimina le istruzioni seguenti che prendono ramificazioni (Siccome non sono eseguite); una traccia dinamica può essere il concatenamento di multipli di blocchi base. Questo permette all'unità di recupero delle istruzioni di recuperare parecchi blocchi basici, senza la preoccupazioni riguardante la ramificazione nel flusso dell'esecuzione.

Le linee di traccia vengono immagazzinate nella trace cache in base al program counter della prima istruzione nella traccia e un set di predizioni di ramificazioni. Questo permette l'immagazzinamento di differenti tracce di percorsi che iniziano con lo stesso indirizzo, ognuna delle quali rappresenta differenti risultati di ramificazione. Nello stage dell'immagazzinamento delle istruzioni di un'Instruction pipeline, il program counter corrente insieme a un set di predizioni di ramificazione viene controllato nella trace cache per un hit. Se un hit avviene, una linea di trace viene fornita per recuperare quale non deve andare in una cache regolare o in memoria per queste istruzioni. La trace cache continua ad alimentare la fetch unit fino a che la linea di traccia finisce o fino a che vi sia una misprediction nella pipeline. Se c'è un fallimento, una nuova traccia inizia a essere creata. Il vantaggio rispetto alle normali cache per il codice è che non vengono mantenute in cache tutte le istruzioni successive a un branch che sia incondizionato o predetto come non seguito: il risultato è che non si formano "bolle" di codice non utilizzato che sprecano spazio di memoria della cache.

Le Trace cache vengono anche impiegate in processori quali l'Intel Pentium 4 per immagazzinare micro operazioni già decodificate, o traduzioni di complesse istruzioni x86, cosicché alla successiva richiesta della stessa istruzione, non debba essere decodificata.

L'idea che sta alla base della trace cache è che nei processori CISC che internamente utilizzano istruzioni RISC, come il Pentium 4, la decodifica delle istruzioni è un'operazione estremamente onerosa, e il suo risultato dovrebbe essere sfruttato al meglio. Utilizzare una trace cache in luogo di una normale cache ha proprio questo vantaggio: non dover decodificare un'istruzione già incontrata durante l'esecuzione di un programma.

Ultimamente la trace cache non gode di molti favori a causa di alcuni difetti. Il primo è che molte istruzioni RISC sono tradotte in una singola istruzione CISC in un solo ciclo di clock, e le istruzioni che necessitano di più cicli di clock per essere tradotte in più istruzioni di tipo RISC sono relativamente poche e poco frequenti, per cui il vantaggio effettivo della trace cache è limitato. A questo si aggiunge il fatto che, nel caso dell'architettura di Intel, le istruzioni di tipo CISC hanno lunghezza variabile in genere tra 1 e 6 byte (tra gli 8 e i 48 bit), mentre tutte le istruzioni RISC utilizzate internamente hanno lunghezza fissa di 118 bit. Quindi a parità di dimensioni una trace cache contiene molte meno istruzioni di una cache normale.

Vedi il testo Smith, Rotenberg and Bennett s paper. URL consultato il 30 novembre 2019 (archiviato dall'url originale il 3 aprile 2008). In Citeseer.

Cache multilivello

Il secondo motivo è il fondamentale compromesso tra la cache latency e lo hit rate. Le cache più grandi sono più lente e hanno migliori hit rate. Per migliorare questo tradeoff, molti sistemi utilizzano livelli multipli di cache, con cache piccole e veloci che si appoggiano a cache più grandi e più lente. Siccome la differenza di latenza tra la memoria principale e le cache più veloci è diventata più grande, alcuni processori hanno cominciato a utilizzare anche tre livelli di cache nel chip. Per esempio nel 2003, Itanium II iniziò a essere fornito con una cache sul chip unificata di livello 3 di 6MB. L'IBM Power 4 series ha una cache di livello 3 a 256 MB fuori dal chip, condivisa attraverso parecchi processori.

Le cache multilivello generalmente operano controllando dapprima le cache a livello 1; se avviene un hit, il processore procede ad alta velocità. Se la cache più piccola “fallisce”, allora viene controllata quella più grande e così via, fino a dover accedere alla memoria principale.

Le cache multi livello introducono un nuovo modello decisionale. Per esempio, in alcuni processori (come gli Intel Pentium 2, 3, e 4, così come in molti RISC), i dati nella cache L1 possono essere anche in quella L2. Queste cache vengono denominato inclusive. Altri processori (come l'AMD Athlon) hanno cache exclusive in cui è garantito che i dati siano al massimo in una delle cache L1 o L2.

Il vantaggio delle cache esclusive è che possono memorizzare più dati. Questo vantaggio diventa più evidente con cache di dimensioni maggiori, sebbene questa caratteristica non sia presente nelle implementazioni Intel x86. D'altra parte, un vantaggio delle cache inclusive è che quando dispositivi esterni o altri processori in un sistema multiprocessore vogliono rimuovere una linea di cache dal processore, devono far controllare al processore solo la cache L2. Nelle gerarchie di cache che non utilizzano l'inclusione, è necessario controllare anche le cache L1. Inoltre, esiste una correlazione tra l'associatività delle cache L1 e L2: se le cache L2 non hanno almeno tanti modi quanti le cache L1 complessivamente, l'effettiva associatività delle cache L1 risulta limitata.

Un altro vantaggio delle cache inclusive è che le cache più grandi possono usare linee di cache più grandi, che riducono la dimensione delle etichette delle cache secondarie. Se la cache secondaria è di un ordine di grandezza maggiore di quella primaria, e i dati della cache sono di un ordine di grandezza più grande delle etichette della cache, queste etichette di dati salvati può essere confrontato con l'area incrementale necessaria a immagazzinare i dati nella cache L1 ed L2.

Come menzionato prima, grandi computer hanno a volte un'altra cache tra quella L2 e la memoria principale chiamata cache L3. Questa cache è implementata generalmente su un chip separato dalla CPU, e come nel 2004, ha una capacità dai 2MB ai 256 MB. Queste cache costeranno ben oltre i $1000 da costruire, e i loro benefici dipenderanno dai percorsi di accesso delle applicazioni. Workstation x86 di fascia alta e server sono ora disponibili con un'opzione per la cache L3.

Infine, dall'altro lato della gerarchia della memoria, il Register file della CPU può essere considerato la più piccola, veloce cache nel sistema, con la speciale caratteristica che viene richiamata dal software—tipicamente da un compilatore, siccome alloca registri che devono mantenere valori recuperati dalla memoria principale.

Esempio: architettura AMD K8

Per illustrare sia la specializzazione che il multilivello delle cache, qui è la gerarchia della cache di un AMD Athlon 64, la cui implementazione del core è conosciuta come architettura K8. La K8 ha 4 cache specializzate: una cache d'istruzioni, una d'istruzioni TLB, una cache di dati e una di dati TLB. Ognuna di queste cache è specializzata:

La cache d'istruzione mantiene copie di line di memoria da 64 bytes, e recupera 16 bytes per ogni ciclo. Ogni byte in questa cache è immagazzinato in 10 bit piuttosto che 8, con gli extra bit che segnano i limiti delle istruzioni (Questo è un esempio del precoding). La cache ha solamente una protezione di parità piuttosto che una ECC, perché la parità è più piccola, e ogni dato danneggiato può essere sostituito da un dato fresco dalla memoria (che ha sempre una copia aggiornata delle istruzioni).
La TLB d'istruzioni tiene copia delle informazioni nella page table (PTE). Ogni ciclo di recupero d'istruzione ha il suo indirizzo virtuale tradotto attraverso questo TLB in uno fisico. Ogni informazione è sia da 4 che da 8 byte in memoria. Ogni TLB è suddivisa in due sezioni, una per mantenere il PTE che mappa 4KB, e una per tenere i PTE per mappare 4MB o 2MB. La suddivisione permette un circuito semplice per un confronto fully associative in ogni sezione. Il sistema operativo mappa sezioni differenti dello spazio d'indirizzi virtuali con differenti dimensioni di PTE.
La TLB dei dati ha due differenti copie che mantengono le stesse informazioni. Le due copie permettono due accessi ai dati per ogni ciclo per tradurre indirizzi virtuali in fisici. Come la TLB d'istruzioni, questa TLB è suddivisa in due tipi d'informazioni.
La cache dei dati mantiene copie di memoria di linee da 64 bytes. È suddivisa in 8 banchi (ognuno immagazzina 8KB di dati), e può recuperare due dati da 8-byte per ogni ciclo per tanto che questi dati siano in banchi diversi. Vi sono due copie delle etichette, perché ogni line da 64 byte è sparsa in tutti gli 8 banchi. Ogni copia di etichetta gestisce uno dei due accessi per ciclo.

La K8 ha anche cache a multilivello. Vi sono TLB d'istruzioni e dati di secondo livello, che immagazzinano solo mappature di PTE da 4KB. Sia le cache d'istruzioni che di dati e le varie TLB, possono essere riempite dalla grande cache unified di livello 2. Questa cache è esclusiva per entrambe le cache L1 di dati e istruzioni, il che significa che qualsiasi line a 8-byte può risiedere in una delle cache d'istruzioni L1, cache di dati L1 o cache L2. È comunque possibile per una linea nella cache dei dati di avere un PTE che sta anche in una delle cache TLB—il sistema operativo è responsabile di tenere le TLB coerenti scaricandone porzioni quando la page table nella memoria vengono aggiornate.

La K8 memorizza informazioni che non vengono mai immagazzinate in memoria—prediction information. Queste cache non vengono visualizzate nel diagramma precedente. Siccome è solito per questa classe di CPU, la K8 ha un branch prediction abbastanza complesso, con tabelle che aiutano a predire quali percorsi vengono presi e altre tabelle che predicono gli obbiettivi dei percorsi e salti. Alcune di queste informazioni vengono associate con delle istruzioni, sia nella cache d'istruzioni L1 sia in quella unified L2.

La K8 utilizza un interessante meccanismo per immagazzinare le informazioni di predizione con le istruzioni nella cache secondaria. Le linee nella cache secondaria sono protette dalla corruzione dei dati involontaria (ad esempio un colpo di particelle alfa tramite l'ECC o tramite la parità, in dipendenza che queste linee siano state rimosse dalla cache dei dati o da quella delle istruzioni. Siccome il controllo di parità occupa meno bit di quello ECC, le linee dalla cache d'istruzioni hanno pochi bit in avanzo. Questi bits vengono usati dal calcolo delle predizioni dei percorsi associati con quelli delle istruzioni. Il risultato finale è che il predittore di percorsi ha un grande tabella storica, quindi ha una migliore accuratezza.

Altre gerarchie

Altri processori hanno altri tipi di predittori. (ad esempio lo store-to-load bypass predictor nel DEC Alpha 21264), e altri svariati predittori specializzati sono facilmente pensabili da essere integrati nei futuri processori.

Questi predittori sono cache nel senso che immagazzinano informazioni che sono costose da calcolare. Alcune delle terminologie utilizzate nel discutere i predittori sono le stesse di quelle per le cache (si parla di hit nel predittore di percorsi), ma i predittori non sono generalmente pesati come parte della gerarchia delle cache.

La K8 mantiene le istruzioni e i dati delle cache coerenti nell'hardware, il che significa che un immagazzinamento in un'istruzione appena dopo l'immagazzinamento dell'istruzione cambierà l'istruzione seguente. Altri processori, come quelli nella famiglia Alpha e MPS, sono basati sul software per mantenere le cache d'istruzioni coerenti. Gli immagazzinamenti non sono garantiti di essere visti nel fiume d'istruzioni a meno che un programma chiami un'opzione del sistema operativo per assicurarsi della coerenza. L'idea è quella di risparmiare la complessità dell'hardware sull'assunzione che il codice automodificante è raro.

La gerarchia di cache si allarga se consideriamo il software come l'hardware. Il register file nel core di un processore può essere considerata una cache molto piccola, veloce i quali hit, fallimenti, e riempimenti sono previsti dal compilatore prima del tempo (vedi specialmente Loop nest optimization). I register file a volte hanno anch'essi una gerarchia: la Cray-1 (circa del 1976) aveva 8 registri scalari e 8 registri d'indirizzi che erano generalmente utilizzabili, aveva anche 64 registri scalari e 64 registri d'indirizzi di tipo "B". I registri di tipo "B" potevano essere caricati più velocemente di quelli nella memoria principale, in quanto il Cray-1 non aveva una cache di dati.

Implementazione

Dato che le letture dalla cache sono operazioni comuni che richiedono più cicli di clock, il percorso critico nel design dei processori è spesso il trasferimento di dati dalla cache a un'istruzione. Questo percorso è essenziale per ottimizzare le prestazioni della CPU, poiché un accesso veloce alla cache L1 è fondamentale per ridurre i ritardi. La cache più semplice è una cache direttamente mappata, dove l'indirizzo virtuale è calcolato da un sommatore e utilizzato per indicizzare una SRAM (Static Random Access Memory), dalla quale vengono letti i dati corrispondenti. Non è necessario alcun controllo di etichetta nel ciclo interno, poiché le etichette non devono essere lette fino a quando non viene verificato un cache hit. Se la verifica fallisce, la cache viene aggiornata e il processo riparte.

Le cache associative sono più complesse, poiché richiedono la lettura di alcuni dati per determinare quale punto della cache selezionare. Ad esempio, una cache level-1 set-associative N-way legge tutte le possibili etichette e dati in parallelo e seleziona quelli associati all'etichetta corrispondente. Le cache level-2 possono risparmiare potenza leggendo prima le etichette e selezionando quindi i dati dalla SRAM.

Il diagramma a destra illustra l'organizzazione degli indirizzi nella cache. Ad esempio, una cache 4KB, 2-way set-associative con linee da 64B utilizza 64 linee e legge due alla volta da una SRAM con 32 righe. Sebbene qualsiasi funzione degli indirizzi virtuali da 31 a 6 possa indicizzare etichette e dati SRAM, è più comune utilizzare i bit meno significativi.

Inoltre, una cache più moderna potrebbe essere di dimensioni diverse e utilizzare diverse tecniche, come indicizzazione virtuale, suggerimenti virtuali e indicizzazione fisica. Queste cache seguono un percorso di lettura simile, ma utilizzano diversi tipi di dati, come vhints anziché etichette, per determinare un cache hit.

Alcune implementazioni SPARC hanno migliorato le prestazioni delle loro cache L1 riducendo i ritardi del sommatore dell'indirizzo virtuale nei decoder SRAM.

Note

Voci correlate

Altri progetti

Wikibooks contiene testi o manuali sulla CPU cache
Wikimedia Commons contiene immagini o altri file sulla CPU cache

Collegamenti esterni

(EN) Evaluating Associativity in CPU Caches — Hill and Smith — 1989 — Introduces capacity, conflict, and compulsory classification.
(EN) Cache Performance for SPEC CPU2000 Benchmarks. — Hill and Cantin — 2003 — This reference paper has been updated several times. It has thorough and lucidly presented simulation results for a reasonably wide set of benchmarks and cache organizations.
(EN) Memory Hierarchy in Cache-Based Systems (PDF) (archiviato dall'url originale il 15 settembre 2009)., by Ruud van der Pas, 2002, Sun Microsystems, is a nice introductory article to CPU memory caching.
(EN) A Cache Primer (PDF) (archiviato dall'url originale il 25 luglio 2008). by Paul Genua, P.E., 2004, Freescale Semiconductor, another introductory article.