CPU cache

Da Wikipedia, l'enciclopedia libera.
Confronto tra memoria RAM e memoria CPU cache

La CPU cache è la cache utilizzata dalla CPU di un computer per ridurre il tempo medio d'accesso alla memoria. La cache è tipicamente un tipo di memoria di dimensioni ridotte, ma molto veloce, che mantiene copie dei dati ai quali si fa più frequentemente accesso nella più capiente memoria principale. 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.

Immagine di un moderno processore. La cache è la struttura regolare marrone presente nella parte inferiore del processore. Notare che la cache e le sue strutture di controllo occupano metà dello spazio del processore

Il diagramma in alto a destra mostra due memorie. Ogni posizione di memoria ha un dato (una linea di cache), che tra diversi tipi di cache varia tra 8 e 512 byte. La dimensione della cache è normalmente più grande di quella di un accesso normale, che tipicamente varia tra 1 e 16 byte. Ogni posizione di memoria ha un indice, cioè un identificatore univoco utilizzato per riferirsi a quella specifica posizione. L'indice di una posizione in memoria principale è chiamato indirizzo di memoria. Ogni posizione nella cache ha un'etichetta 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.

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 ed 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 talune 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[modifica | modifica wikitesto]

Per poter fare 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 di 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 ad un altro programma di usare la CPU mentre un primo programma sta aspettando l'arrivo di dati dalla memoria principale.

Associatività[modifica | modifica wikitesto]

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 la politica di rimpiazzamento è libera di scegliere in quale linea di cache caricare il dato, la cache è 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 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.

Cache miss[modifica | modifica wikitesto]

Con fallimento della cache (in inglese cache miss) ci si riferisce ad un intento fallito 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 ad 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à di 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 ad 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 di 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[modifica | modifica wikitesto]

Con cache colpita (in inglese cache hit) ci si riferisce invece ad 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[modifica | modifica wikitesto]

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 di indirizzi.
  • Aliasing: Più indirizzi virtuali possono riferirsi ad 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 di 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 di istruzioni, ma invece una TLB.

L'esistenza di 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 ed 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 ad 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

Anche l'etichettatura virtuale (Virtual tagging) è possibile. 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 una perfetta 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 di 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 di 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 del 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 una etichetta virtuale, e vengono utilizzati per selezionare il modo della cache tramite cui prelevare un dato e una 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[modifica | modifica wikitesto]

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 posso 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 ed 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 ed 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 ad un solo colore virtuale, allora non vi sono virtual alias, ed il processore può usare cache virtually indexed senza la necessità di controlli su extra virtual alias durante la gestione del fallimento. Alternativamente il S.O. può svuotare una pagina dalla cache quantunque cambi da un colore virtuale ad un altro. Come menzionato prima, questo approccio fu usato da qualche recente progettazione SPARC e RC/6000.

Gerarchia delle cache in un processore moderno[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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. Per un semplice esempio: Classic RISC Pipeline. 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[modifica | modifica wikitesto]

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 di un HP PA7200 fu un cache piccola, fully-associative. Processori posteriori, come gli AMD Athlon, Athlon XP e Athlon 64 utilizzano la cache secondaria molto grande come una victim cache, per evitare ripetizioni di immagazzinamenti del contesto sulla cache primaria.

Trace cache[modifica | modifica wikitesto]

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 di istruzioni immagazzinando tracce di 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 di istruzioni dinamiche. Un blocco base consiste in un gruppo di 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 delle 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 una Instruciont pipeline, il program counter corrente insieme ad 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 line di traccia finisce o fino a che vi sia una misprediction nella pipeline. Se c'è un fallimento, una nuova traccia inizia ad essere creata. Il vantaggio rispetto alle normali cache per il codice è che non vengono mantenute in cache tutte le istruzioni successive ad 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é la prossima volta che una istruzione sia richiesta, non debba essere decodificata un'altra volta.

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 è una 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 una 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. Questi svantaggi hanno portato l'Intel a non utilizzare la trace cache nelle sue ultime architetture: l'Intel Core e l'Intel Core 2.

Vedi il testo Smith, Rotenberg and Bennett s paper in Citeseer.

Cache multilivello[modifica | modifica wikitesto]

Il secondo motivo è il fondamentale compromesso tra la cache latency ed l'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 ad utilizzare anche tre livelli di cache nel chip. Per esempio nel 2003, Itanium II iniziò ad 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 256MB 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 ad 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 exclusive è che memorizzano più dati. Questo vantaggio aumenta con cache più grandi (le implementazioni Intel x86 invece no). Un vantaggio delle cache inclusive è che quando device esterni o altri processori in un sistema multiprocessore desiderano rimuovere una linea di cache dal processore, devono far controllare al processore solo la cache L2. Nelle gerarchie di cache che non usano l'inclusione, le cache L1 devono essere controllate anch'esse. C'è una correlazione tra la associatività delle cache L1 e L2: se le cache L2 non hanno almeno tanti modi come tutte le L1 insieme, l'effettiva associatività delle cache L1 risulta confinata.

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 ad 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 di un chip separato dalla CPU, e come nel 2004, ha un capacità dai 2MB ai 256MB. Queste cache costeranno ben oltre i $1000 da costruire, ed 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[modifica | modifica wikitesto]

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 (dettagli).

Esempio di gerarchia, la K8

La K8 ha 4 cache specializzate: una cache di istruzioni, una di istruzioni TLB, una cache di dati ed una di dati TLB. Ognuna di queste cache è specializzata:

  1. La cache di 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, ed ogni dato danneggiato può essere sostituito da un dato fresco dalla memoria (che ha sempre una copia aggiornata delle istruzioni).
  1. La TLB di istruzioni tiene copia delle informazioni nella page table (PTE). Ogni ciclo di recupero di 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 di indirizzi virtuali con differenti dimensioni di PTE.
  1. 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 di istruzioni, questa TLB è suddivisa in due tipi di informazioni.
  1. 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 data 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 di istruzioni e dati di secondo livello, che immagazzinano solo mappature di PTE da 4KB. Sia le cache di 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 di 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 ed altre tabelle che predicono gli obbiettivi dei percorsi e salti. Alcune di queste informazioni vengono associate con delle istruzioni, sia nella cache di 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 di istruzioni hanno pochi bit in avanzo. Questi bits vengono usati dal calcolo delle predizioni dei percorsi associati con quelli delle istruzioni. La risultato finale è che il predittore di percorsi ha un grande tabella storica, quindi ha una migliore accuratezza.

Altre gerarchie[modifica | modifica wikitesto]

Altri processori hanno altri tipi di predittori. (ad esempio lo store-to-load bypass predictor nel DEC Alpha 21264), ed 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 una 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 di istruzioni coerenti. Gli immagazzinamenti non sono garantiti di essere visti nel fiume di istruzioni a meno che un programma chiami una 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 di indirizzi che erano generalmente utilizzabili, aveva anche 64 registri scalari e 64 registri di 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[modifica | modifica wikitesto]

Dato che le letture dalla cache sono operazioni piuttosto comuni che impiegano più di un solo ciclo, la ricorrenza da un caricamento di una istruzione alla istruzione stessa tende ad essere il percorso più critico nella buona progettazione dei processori, cosicché i dati in questo percorso perdano il minor tempo possibile. Come risultato la cache L1 è il componente più sensibile alle latenze sul chip.

La cache più semplice è una cache virtually indexed direct-mapped. L'indirizzo virtuale è calcolato con un sommatore, la parte più significativa dell'indirizzo viene estratta ed utilizzata per indicizzare una SRAM, la quale ritorna i dati immagazzinati. Il data viene allineato a livello di byte in un byte shifter, e da lì è passato alla successiva operazione. Non c'è alcuna necessità di alcun controllo di etichetta nel loop interno—infatti, le etichette non necessitano nemmeno di essere lette. Più tardi nella pipeline, ma prima che l'istruzione sia effettivamente caricata, l'etichetta per dei dati caricati deve essere letta, e controllata con l'indirizzo virtuale per rassicurarsi che ci fosse stato un cache hit. In caso di fallimento, la cache viene aggiornata con la linea richiesta e la pipeline viene fatta ripartire.

Una cache associativa è molto più complicata, siccome alcuni elementi di dati devono essere letti per determinare quale punto della cache selezionare, una cache level-1 set-associative N-way solitamente legge tutti le possibili N etichette ed N dati in parallelo, dopo di che sceglie i dati associati con l'etichetta corrispondente. Le cache Level-2 a volte risparmiano potenza leggendo prima l'etichetta, cosicché solo un elemento di dato venga letto dalla SRAM.

Read path for a 2-way associative cache

Il diagramma a destra serve a chiarire il modo in cui i vari campi degli indirizzi vengono utilizzati. Il diagramma mostra le SRAM, indicizzazioni e multiplexing per una cache virtually tagged e virtually indexed 4KB, 2-way set-associative con 64 B linee, una lettura di larghezza a 32b e 32b di virtual address.

Siccome la cache è da 4KB e ha linee da 64B, ci sono giusto 64 linee nella cache, e ne leggiamo due per volta da una etichetta SRAM la quale ha 32 righe, ognuna con un paio di etichette da 21 bit. Sebbene qualsiasi funzione di indirizzi virtuali bit 31 attraverso 6 può essere usata per indicizzare etichette e dati SRAM, è più semplice usare i bit meno significativi.

Similmente, siccome la cache è da 4KB e ha un percorso di lettura da 4B, e legge due modi per ogni indirizzo, i dati SRAM sono da 512 righe larghi 8 byte.

Una cache più moderna potrebbe essere da 16KB, 4-way set-associative, virtually indexed, virtually hinted, e physically tagged, con linee da 32B, letture da 32b e indirizzi fisici da 36 bit. La ricorrenza di lettura di percorsi per questi tipi di cache assomigliano molto al percorso di sopra. Invece di etichette, vengono letti vhints, e confrontati con un sottoinsieme di indirizzi virtuali. Più tardi nella pipeline, l'indirizzo virtuale viene tradotto in un indirizzo fisico dalla TLB, e la etichetta fisica viene letta (giusto una, siccome il vhint fornisce quale modo della cache da leggere). Finalmente l'indirizzo fisico è confrontato con l'indirizzo dell'etichetta per determinare se sia avvenuto un hit.

Alcune implementazioni SPARC hanno migliorato la velocità delle loro cache L1 di pochi ritardi collassando il sommatore dell'indirizzo virtuale nei decoder SRAM. Vedi Sum addressed decoder.

Voci correlate[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica