CPU cache: differenze tra le versioni

Versione delle 14:01, 17 lug 2025

Versione attuale delle 11:57, 1 ago 2025

(15 versioni intermedie di 3 utenti non mostrate)

Riga 1:

{{NN|informatica|febbraio 2013}}

{{organizzare|La voce è trattata in maniera eccessivamente specialistica. BisognereCbbe semplificarla per non renderla troppo simile a quanto si trova su un manuale specialistico di informatica e migliorarne la leggibilità per un utente non tecnico|Informatica|Maggio 2018}}

{{Aggiornare|argomento=informatica|commento=Buona parte della voce è ferma al 2004, e parla pure al futuro...}}

{{Correggere|informatica|settembre 2019}}

{{vedi anche|Memoria cache}}

La Cache è un tipo di [[RAM|memoria RAM]] di piccole dimensioni, progettata per essere molto veloce ma anche più costosa rispetto ad altri tipi di memoria. Con l’aumento delle prestazioni dei processori e l’uso crescente di tecnologie avanzate come l’[[intelligenza artificiale]] e il [[cloud computing]], la cache continua a giocare un ruolo fondamentale. Quando si parla di "lato prestazioni", si intende che la cache aiuta il computer o il dispositivo a lavorare più rapidamente: conserva temporaneamente le informazioni e i dati usati più spesso, permettendo al [[processore]] di accedervi immediatamente senza doverli recuperare da memorie più lente o da internet. Questo rende le operazioni più veloci, migliora l’[[efficienza energetica]] e garantisce una migliore esperienza d’uso, anche con applicazioni moderne e complesse. <ref name=":0">{{Cita libro|titolo="Computer Architecture: A Quantitative Approach" di John L. Hennessy e David A. Patterson (5ª edizione, Morgan Kaufmann, 2012, e successive ristampe aggiornate).}}</ref>

== Caratteristiche ==

Riga 11 ⟶ 8:

Nel diagramma a sinistra sono illustrate due memorie: la memoria principale e la cache. La cache è una memoria molto più veloce, ma anche più piccola, usata per conservare temporaneamente i dati più usati dal processore.

Ogni posizione della cache contiene un dato chiamato linea di cache (o blocco di cache), che attualmente può variare da 512 [[byte]] a 8 [[Megabyte|MB]], a seconda del tipo e livello di cache. Al contrario, la memoria principale ha dimensioni molto più grandi, in genere tra 1 e 16 [[Gigabyte|GB]] o più, ma è anche più lenta.<ref name=":0" />

Ogni posizione in memoria è identificata da un numero univoco chiamato indice (o indirizzo di memoria). Nella cache, a ogni linea è associata un’etichetta (o tag), che indica a quale indirizzo della memoria principale corrisponde quel dato.

Riga 17 ⟶ 14:

Quando il processore ha bisogno di un'informazione, controlla prima se si trova nella cache. Se la trova (si parla di cache hit), l’accesso è molto veloce. Se invece non è presente (si parla di cache miss), il dato viene preso dalla memoria principale, che è più lenta, e copiato nella cache per usi futuri.

Finché la maggior parte dei dati richiesti si trovano nella cache, il tempo medio per accedere alla memoria (latenza) resta basso, vicino a quello rapidissimo della cache. Questo si traduce in prestazioni migliori per il sistema. 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. <ref name=":0" />

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

Riga 23 ⟶ 20:

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.

Quando si verifica una cache miss — cioè il processore richiede un dato assente dalla cache — viene creata una nuova voce che contiene l’etichetta (o ''tag'') e una copia del dato recuperata dalla memoria principale. L’operazione è più lenta rispetto all’accesso diretto alla cache, perché richiede il trasferimento del dato e, spesso, la sostituzione di un dato ormai inutile. <ref name=":0" />

Per decidere quale dato eliminare per far posto al nuovo, la cache adotta una regola detta [[Euristica (informatica)|euristica]] di rimpiazzamento: si tratta di un metodo approssimato per cercare di prevedere quali dati saranno meno utili in futuro. Tuttavia, anche nel 2025, nessuna euristica è perfetta, soprattutto perché le cache hardware devono basarsi su meccanismi semplici da implementare nei circuiti elettronici. Per esempio, una delle politiche più diffuse è la [[Least Recently Used|LRU]], che rimuove il dato utilizzato meno recentemente, con l’idea che sia il meno probabile da riutilizzare a breve.

Riga 31 ⟶ 28:

Ogni nuovo dato deve quindi essere caricato e gestito con l’ulteriore costo di rimuovere dati obsoleti, e questo può rallentare il sistema. In certi casi, il tempo complessivo impiegato per questo processo può essere addirittura superiore a quello richiesto per leggere direttamente il dato dalla memoria principale.

In altre parole, anche oggi una cache più grande non garantisce sempre prestazioni migliori: in scenari particolari può generare più cache miss che cache hit, con un impatto negativo sulla velocità complessiva del sistema. <ref name=":0" />

== Alcuni dettagli operativi ==

Riga 37 ⟶ 34:

Quando si verifica una cache miss — ovvero quando il processore richiede un dato non presente nella cache — è necessario liberare spazio per poter memorizzare il nuovo dato. Questo comporta l’eliminazione di uno dei dati già presenti nella cache. La scelta di quale dato rimuovere è guidata da una regola detta politica di rimpiazzamento (replacement policy).

Lo scopo di questa politica è stimare quale dato sia meno probabile che venga riutilizzato a breve, così da poterlo sostituire senza compromettere le prestazioni complessive del sistema. Tuttavia, questa previsione è intrinsecamente complessa, in particolare per le cache hardware, che devono adottare strategie semplici, rapide e facilmente implementabili a livello di circuito.<ref name=":0" />

Sono state sviluppate diverse politiche di rimpiazzamento, ciascuna con punti di forza e debolezze, ma nessuna in grado di garantire risultati ottimali in ogni contesto operativo. Una delle più diffuse è la [[Least Recently Used|LRU]] (Least Recently Used), che rimuove il dato utilizzato meno di recente, basandosi sull’ipotesi che un dato non usato da tempo difficilmente verrà richiesto di nuovo a breve. Pur non essendo ideale in ogni scenario, questa soluzione rappresenta un buon compromesso tra semplicità ed efficacia.

Quando un dato viene modificato nella cache, deve essere prima o poi aggiornato anche nella [[Memoria (informatica)#Memoria primaria|memoria principale]], per mantenere la coerenza tra i due livelli di memoria. Il momento in cui avviene questa operazione dipende dalla cosiddetta politica di scrittura (write policy).

In una cache di tipo write-through, ogni modifica effettuata nella cache viene immediatamente replicata anche nella memoria principale. Questo garantisce una maggiore coerenza tra i dati, ma può rallentare le prestazioni a causa dell’elevato numero di accessi alla memoria. Al contrario, in una cache write-back, la scrittura nella memoria principale non avviene subito. I dati modificati restano temporaneamente nella cache e vengono segnati come "sporchi" tramite un apposito indicatore, chiamato dirty bit. Solo quando quella specifica linea di cache deve essere sostituita — ad esempio per far posto a nuovi dati — il contenuto aggiornato viene scritto nella memoria principale. Questo approccio riduce il numero di scritture, migliorando l’efficienza, ma richiede un meccanismo più complesso per garantire la coerenza. In un sistema write-back, una cache miss può generare due accessi alla memoria: uno per scrivere il dato modificato (se segnalato dal dirty bit) e uno per leggere il nuovo dato richiesto. <ref name=":0" />

Esistono anche politiche ibride, che cercano un compromesso tra efficienza e coerenza. Un esempio è una cache write-through con buffer di scrittura, dove le scritture vengono inserite temporaneamente in una coda, per poi essere inviate alla memoria principale in modo più efficiente, ad esempio raggruppandole o gestendole in momenti di basso traffico sul [[Bus (informatica)|bus di sistema]]. <ref>{{Cita libro|titolo=Robert C. Steinke & Gary J. Nutt, A Unified Theory of Shared Memory Consistency, Journal of the ACM, Volume 51, Issue 6, 2004.}}</ref>

In un sistema [[multiprocessore]], è possibile che i dati contenuti nella memoria principale, di cui esiste una copia nella cache, vengano modificati da altri processori. In questi casi, le copie locali nella cache possono diventare obsolete o incoerenti. Per evitare errori di calcolo, i sistemi devono garantire che tutte le cache coinvolte lavorino con dati aggiornati. A tal fine vengono utilizzati appositi protocolli di coerenza, che regolano la comunicazione tra le cache per mantenere l’allineamento corretto dei dati. <ref>{{Cita libro|titolo=ijay Nagarajan, Daniel J. Sorin, Mark D. Hill & David A. Wood – A Primer on Memory Consistency and Cache Coherence, Second Edition (Morgan & Claypool Publishers, 2020)}}</ref>

Un altro aspetto critico è il tempo necessario per leggere un dato dalla memoria, noto come latenza di lettura. Questo tempo influisce direttamente sulle prestazioni del processore: se la CPU deve attendere troppo a lungo l’arrivo di un dato, rischia di fermarsi temporaneamente, entrando in uno stato chiamato stallo della CPU. Tale situazione è particolarmente dannosa nelle CPU moderne, capaci di eseguire centinaia di istruzioni nel tempo impiegato per caricare un singolo dato da una memoria lenta. Per ridurre l’impatto degli stalli, sono state sviluppate tecniche di ottimizzazione che permettono alla CPU di sfruttare il tempo d’attesa. Ad esempio, alcuni microprocessori adottano l’[[esecuzione fuori ordine]] (out-of-order execution), che consente di portare avanti operazioni successive a quella in attesa, purché siano indipendenti dal dato mancante. Altri processori implementano il [[multithreading]] simultaneo, come nel caso della tecnologia [[HyperThreading]] di [[Intel]], che consente a un secondo flusso di istruzioni (thread) di utilizzare l’unità di calcolo mentre il primo è in attesa dei dati. In questo modo, si riduce lo spreco di cicli di CPU, migliorando l’efficienza del sistema. <ref name=":0" />

Per ridurre l’impatto degli stalli, sono state sviluppate tecniche di ottimizzazione che permettono alla CPU di sfruttare il tempo d’attesa. Ad esempio, alcuni microprocessori adottano l’[[Esecuzione fuori ordine|esecuzione fuori ordine]] (out-of-order execution), che consente di portare avanti operazioni successive a quella in attesa, purché siano indipendenti dal dato mancante.

Altri processori implementano il [[multithreading]] simultaneo, come nel caso della tecnologia [[HyperThreading]] di [[Intel]], che consente a un secondo flusso di istruzioni (thread) di utilizzare l’unità di calcolo mentre il primo è in attesa dei dati. In questo modo, si riduce lo spreco di cicli di CPU, migliorando l’efficienza del sistema.

== Associatività ==

[[File:Cache,associative-fill-both.png|thumb|upright=2.0|Quali posizioni di memoria possono essere caricate in quali posizioni della cache]]

La politica di rimpiazzamento determina dove, nella cache, può essere memorizzata una copia di un dato della memoria principale. Se il dato può essere inserito in qualsiasi linea, la cache è detta fully associative. Se invece può essere collocato solo in una linea specifica, si parla di cache direct mapped. Un compromesso tra i due approcci è la cache set associative, dove ogni dato può essere inserito in una delle linee di un gruppo (set). Ad esempio, la cache dati di primo livello dell’[[Athlon]] di [[AMD]] è 2-way set associative, cioè ogni dato può risiedere in due linee distinte del set corrispondente. <ref name=":0" />

Se ogni posizione della memoria principale può essere memorizzata in due linee diverse della cache (come nel caso di una cache 2-way set associative), è naturale chiedersi quali siano queste due posizioni. Il metodo più comune per stabilirlo è quello illustrato nel diagramma a lato: i bit meno significativi dell’indirizzo di memoria vengono usati per determinare a quale set appartiene il dato. A ciascun set corrispondono due linee di cache disponibili. Un vantaggio di questo schema è che, conoscendo già parte dell’indirizzo (quella usata per selezionare il set), le etichette (tag) salvate in cache possono essere più brevi, poiché non devono ripetere l’informazione già codificata. Questo comporta un uso più efficiente della memoria cache e una riduzione del tempo necessario per confrontare i tag durante l’accesso. <ref name=":0" />

Sono stati proposti schemi alternativi di organizzazione della cache per ridurre le collisioni, cioè i casi in cui più dati competono per la stessa posizione. Un esempio è la skewed cache, in cui il metodo di selezione del set varia tra le diverse vie (ways). Nella way 0, l’indice è calcolato con il metodo tradizionale (ad esempio usando i bit meno significativi dell’indirizzo), mentre nella way 1 l’indice è ottenuto tramite una [[funzione di hash]]. Una buona funzione di hash distribuisce in modo più uniforme gli indirizzi, riducendo il rischio che dati frequentemente usati entrino in conflitto tra loro, come può accadere con la mappatura diretta.Lo svantaggio di questo approccio è il ritardo aggiuntivo dovuto al calcolo della funzione di hash. Inoltre, può diventare più complesso gestire l’eliminazione delle linee obsolete, perché le diverse vie possono usare criteri di assegnazione diversi, rendendo meno efficiente il tracciamento dell’utilizzo recente (ad esempio nel caso di strategie come la Least Recently Used, o LRU). <ref>{{Cita libro|titolo=Norman P. Jouppi

Improving direct-mapped cache performance by the addition of a small fully-associative cache and skewed-associative caches, Proceedings of the 17th Annual International Symposium on Computer Architecture (ISCA), 1990.}}</ref>

In generale, il grado di associatività della cache rappresenta un compromesso tra prestazioni e complessità. Maggiore associatività significa che ogni dato può essere memorizzato in più posizioni all’interno di un set, riducendo la probabilità di cache miss. Tuttavia, questo comporta anche un maggiore costo in termini di tempo, energia e spazio, poiché il sistema deve controllare più posizioni a ogni accesso.

Un principio empirico largamente accettato è che raddoppiare l’associatività (ad esempio passando da una cache direct-mapped a una 2-way o 4-way set associative) produce benefici simili a raddoppiare la dimensione della cache in termini di aumento del tasso di successo (hit rate). Tuttavia, oltre il 4-way, i vantaggi tendono a ridursi, e associatività più elevate vengono usate soprattutto per gestire casi specifici come il virtual aliasing (descritto nella sezione dedicata alla Traduzione degli Indirizzi). <ref name=":1">{{Cita libro|titolo=Hennessy, John L. e Patterson, David A.

Computer Architecture: A Quantitative Approach, 6ª edizione, Morgan Kaufmann, 2017 (ultima edizione aggiornata).}}</ref>

Uno dei vantaggi delle cache a mappatura diretta è la possibilità di eseguire operazioni in modo speculativo in modo semplice e rapido. Una volta calcolato l’indirizzo di memoria, è subito noto quale linea della cache potrebbe contenere il dato richiesto. Questo consente al processore di leggere preventivamente quella linea e iniziare a lavorare sul dato, anche prima di verificare se l’etichetta (tag) memorizzata corrisponda effettivamente all’indirizzo richiesto. <ref name=":1" />

Questo principio può essere esteso anche alle cache associative, sebbene con maggiore complessità. In questi casi, un sottoinsieme dell’etichetta, chiamato comunemente hint, può essere usato per selezionare provvisoriamente una delle linee candidate all’interno del set associato all’indirizzo. La CPU può così iniziare ad utilizzare temporaneamente quel dato, in parallelo alla verifica completa dell’etichetta. Questa tecnica speculativa è particolarmente utile quando viene impiegata insieme ai meccanismi di traduzione degli indirizzi, permettendo alla CPU di anticipare l'accesso ai dati, riducendo i ritardi dovuti alla latenza di memoria. <ref name=":1" />

Questa tecnica speculativa è particolarmente utile quando viene impiegata insieme ai meccanismi di traduzione degli indirizzi, permettendo alla CPU di anticipare l'accesso ai dati, riducendo i ritardi dovuti alla latenza di memoria.

== Cache miss ==

Con il termine cache miss (in italiano fallimento della cache) si indica una situazione in cui il processore tenta di leggere o scrivere un dato nella cache, ma quel dato non è presente, e deve quindi essere recuperato dalla memoria principale, con un conseguente aumento della latenza. Se la cache miss riguarda una lettura di istruzioni, il processore è costretto ad attendere il caricamento dell’istruzione dalla memoria principale, entrando in uno stato di stallo. Se invece la cache miss avviene durante il caricamento di un dato, il rallentamento può essere meno grave, perché il processore può continuare a eseguire altre istruzioni non dipendenti da quel dato, almeno fino a quando l'operazione che lo richiede diventa eseguibile. Tuttavia, in molti casi, i dati caricati vengono utilizzati immediatamente dopo l’istruzione di caricamento, il che rende comunque l’attesa penalizzante. Le cache miss in scrittura, infine, sono generalmente meno problematiche, perché le scritture vengono bufferizzate: il processore può proseguire l’esecuzione mentre i dati vengono scritti in secondo piano, salvo che il buffer non si riempia. Da notare che non esistono cache miss in scrittura per le cache istruzioni, in quanto le istruzioni sono solitamente di sola lettura e non vengono mai scritte direttamente nella cache da parte del processore.<ref name=":1" />

Per ridurre la frequenza delle cache miss, è stato svolto un ampio lavoro di analisi sul comportamento della cache, con l’obiettivo di identificare la combinazione ottimale di dimensione, associatività, dimensione dei blocchi e altri parametri. Per studiare queste variabili, i ricercatori utilizzano le sequenze di accesso alla memoria prodotte dai programmi di [[benchmark (informatica)|benchmark]], salvate sotto forma di tracce di indirizzi (address traces). Su queste tracce vengono simulate diverse configurazioni di cache, per valutare come ciascun parametro influenzi il numero di [[cache hit|accessi riusciti]] e di cache miss. <ref name=":1" />

Tuttavia, comprendere l’effetto combinato di tutte queste variabili può risultare complesso. Un contributo fondamentale è stato fornito da Mark Hill, che ha proposto una classificazione delle cache miss in tre categorie principali, note come le "tre C":

Riga 80 ⟶ 76:

* Conflict misses (miss da conflitto): si verificano quando due o più dati che potrebbero coesistere nella cache si contendono la stessa posizione, costringendo la cache a sovrascrivere dati ancora utili. Sono tipici delle cache non completamente associative. Questi possono essere ulteriormente suddivisi in:

* * Mapping misses, dovuti alla struttura stessa della cache (es. direct mapped);

* * Replacement misses, causati dalla scelta della politica di rimpiazzamento, che può espellere un dato che sarebbe stato riutilizzato a breve. <ref name=":1" />

[[File:Cache,missrate.png|thumb|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 [http://www.cs.wisc.edu/multifacet/misc/spec2000cache-data/ Cache performance of SPEC CPU2000]. 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.

Riga 91 ⟶ 87:

Nel grafico che rappresenta la frequenza dei capacity misses, si può osservare una brusca diminuzione tra i 32 KB e i 64 KB di dimensione della cache. Questo comportamento suggerisce che il [[working set]] del benchmark — ovvero l’insieme di dati usati attivamente in un dato periodo — sia di circa 64 KB. Un progettista, esaminando questo risultato, potrebbe essere fortemente incentivato a scegliere una dimensione della cache appena superiore a 64 KB, così da ridurre significativamente i fallimenti. Al contrario, impostare la cache appena al di sotto di questo valore comporterebbe un aumento netto della frequenza di cache miss.È inoltre importante notare che, in questa simulazione, nessun livello di associatività rende una cache da 32 KB efficace quanto una cache da 64 KB con associatività 4-way, o una cache direct-mapped da 128 KB. Ciò evidenzia come la dimensione della cache sia spesso più determinante dell’associatività, almeno oltre certi limiti.

Infine, si osserva che tra i 64 KB e 1 MB di dimensione, esiste una notevole differenza di prestazioni tra le cache direct-mapped e quelle fully-associative. Questa differenza è dovuta principalmente alla frequenza dei [[conflict miss]], cioè ai fallimenti causati dal fatto che più dati si contendono la stessa posizione nella cache. Secondo i dati disponibili nei primi anni 2000, le cache di secondo livello (L2) integrate direttamente sul [[circuito integrato|chip]] del processore tendevano a rientrare proprio in questo intervallo di dimensioni. Le cache più piccole, infatti, sono abbastanza rapide da essere utilizzate come cache di primo livello (L1), mentre quelle molto grandi risultano troppo costose e complesse da integrare fisicamente sul chip. Ad esempio, il processore [[Itanium 2]] montava una cache di terzo livello (L3) da 9 MB, che all’epoca era la più grande cache on-chip disponibile sul mercato. Dal punto di vista dell’efficienza, questi dati mostrano che una cache di secondo livello beneficia notevolmente di una maggiore associatività, in quanto questa riduce sensibilmente i conflitti tra dati e quindi la frequenza di cache miss, migliorando le prestazioni complessive del sistema.

Il vantaggio dell’alta associatività nelle cache era già noto alla fine degli [[anni 1980|anni ottanta]] e all’inizio degli [[anni 1990|anni novanta]]. Tuttavia, all’epoca i progettisti di CPU incontravano limitazioni fisiche e tecnologiche: non era possibile integrare cache di grandi dimensioni direttamente sul chip, né c’era sufficiente larghezza di banda per gestire una cache altamente associativa posta fuori dal processore. Per superare queste difficoltà, furono esplorate diverse soluzioni architetturali. Il processore [[MIPS]] R8000, ad esempio, utilizzava SRAM off-chip dedicate e costose, dotate di comparatori di etichette e driver ad alte prestazioni, per implementare una cache associativa 4-way da 4 MB. Il successivo MIPS R10000, invece, utilizzava SRAM comuni per conservare le etichette, ma richiedeva due cicli di clock per accedere ai dati e verificare l’etichetta, a causa della maggiore complessità. Per ridurre la latenza di accesso, il R10000 introdusse una tecnica di predizione: al momento della richiesta di un dato, cercava di anticipare quale delle vie della cache avrebbe contenuto l’informazione corretta, avviando in parallelo il controllo completo delle etichette. Questa strategia permetteva di accelerare l’accesso nella maggior parte dei casi, nonostante le limitazioni hardware del periodo.

Riga 111 ⟶ 107:

* Granularità: Lo spazio degli indirizzi virtuali è suddiviso in blocchi chiamati pagine. Ad esempio, uno spazio virtuale di 4 GB può essere suddiviso in 1.048.576 pagine da 4 KB ciascuna, ognuna gestita separatamente. Alcuni sistemi supportano anche pagine di dimensioni variabili; per ulteriori dettagli si veda la voce [[memoria virtuale]].

In origine, i primi sistemi dotati di [[memoria virtuale]] risultavano piuttosto lenti, poiché per ogni accesso alla memoria era necessario consultare la [[page table]], che risiedeva nella memoria principale. Questo comportava un doppio accesso alla memoria per ogni operazione, riducendo sensibilmente le prestazioni. Per ovviare a questo limite, fu introdotta la Translation Lookaside Buffer ([[Translation Lookaside Buffer|TLB]]), una piccola cache specializzata che memorizza temporaneamente le mappature più recenti tra indirizzi virtuali e fisici. Di fatto, la TLB fu la prima cache hardware utilizzata nei computer, ancor prima delle cache dedicate ai dati o alle istruzioni.

La distinzione tra indirizzi virtuali e indirizzi fisici solleva la questione su quali debbano essere utilizzati per gli indici e le etichette della cache. Utilizzare indirizzi virtuali consente una maggiore velocità, perché evita di attendere la traduzione da parte della [[memory management unit|MMU]] prima di accedere alla cache. Questo è particolarmente importante per ridurre la latenza di caricamento dalla memoria principale, un fattore critico per le prestazioni della CPU. Per questo motivo, molte cache di primo livello (L1) sono progettate per essere indicizzate usando indirizzi virtuali, permettendo alla MMU di eseguire in parallelo la ricerca nella TLB e l'accesso ai dati presenti nella cache.

Riga 137 ⟶ 133:

Tuttavia, ci sono alcune complessità da considerare:

* I controlli di coerenza e la rimozione delle voci nella cache si basano sugli indirizzi fisici. Perciò, l’hardware deve disporre di un meccanismo per convertire l’indirizzo fisico in una posizione della cache. Questo comporta che la cache memorizzi sia le etichette virtuali sia quelle fisiche. Al contrario, una cache con etichettatura fisica (physically tagged) gestisce solo etichette fisiche, semplificando il progetto.

* Quando una traduzione dall’indirizzo virtuale a quello fisico viene rimossa dalla [[Translation Lookaside Buffer|TLB]], le informazioni corrispondenti nella cache devono essere invalidate (cioè svuotate o aggiornate). Inoltre, se la cache contiene dati relativi a pagine non più mappate dalla TLB, questi dati devono essere rimossi quando cambiano i permessi di accesso a tali pagine nella [[page table]].

Il sistema operativo può permettere che più alias virtuali dello stesso indirizzo fisico siano presenti contemporaneamente nella cache, tramite una tecnica chiamata page coloring, che sarà descritta più avanti. Alcuni processori RISC, come quelli delle famiglie SPARC e RS/6000, hanno adottato questo approccio. Tuttavia, recentemente questa pratica è stata meno utilizzata, perché il costo hardware per rilevare e rimuovere gli alias virtuali si è ridotto, mentre la complessità e l’impatto sulle prestazioni del software necessario per implementare un page coloring preciso sono aumentati.

Riga 148 ⟶ 144:

Alcuni processori, come quelli recenti della famiglia SPARC, utilizzano cache che combinano sia etichette virtuali sia etichette fisiche. In questo tipo di cache, le etichette virtuali sono impiegate per selezionare il modo (ossia la linea o il blocco da verificare), mentre le etichette fisiche servono a determinare se l’accesso è un successo (cache hit) o un fallimento (cache miss). Questa soluzione unisce il vantaggio di una bassa latenza tipica delle cache con etichette virtuali alla semplicità di gestione del software garantita dalle cache con etichette fisiche. Tuttavia, comporta un costo maggiore dovuto alla necessità di mantenere etichette duplicate.Durante i casi di fallimento della cache, i modi alternativi della linea devono essere controllati per eventuali alias virtuali e, se necessario, le corrispondenze errate devono essere eliminate per mantenere la coerenza.

L'areaL’area extradi memoria aggiuntiva (e qualchela relativa latenza) puòassociata essereall’uso mitigatadi mantenendoetichette ''virtualvirtuali hints''può conessere ognimitigata informazioneimpiegando delladei cachevirtual hints invece che condelle etichette virtuali complete. Questi hints sonorappresentano un sottoinsieme, o un hash, di un'etichettadell’etichetta virtuale, e vengono utilizzati per selezionare il modo della cache tramiteda cui prelevareleggere uni datodati e un'la relativa etichetta fisica. ConIn una cache virtuallycon taggedetichette virtuali, cipuò potrebbe essereverificarsi una corrispondenza ditra virtual hinthints ma una non corrispondenzatra dietichette etichetta fisica,fisiche: in questotal caso, la informazionel’informazione nella cache conassociata laall’hint corrispondenza dell'hintcoincidente deve essere rimossa, cosicchéaffinché gli accessi allasuccessivi cacheallo dopo il riempimento della cache in questostesso indirizzo avranno solamentetrovino una sola corrispondenza di hint. SiccomePoiché glii hintvirtual hannohints minoricontengono meno bit dellerispetto alle etichette virtuali distinguerlicomplete, distinguono meno efficacemente gli indirizzi. unoDi dall'altroconseguenza, una cache conbasata hintsu virtualivirtual soffrehints ditende a soffrire più mancanzefrequentemente di mancanze dovute a conflitti di(conflict misses) rispetto a una cache acon etichette virtuali complete.

ForseUn laesempio riduzione finaleestremo di hintriduzione virtualidei puòvirtual esserehints trovatasi nelosserva nei processori Pentium 4 (core Willamette ande Northwood cores). In questi processorimodelli, l'hintl’hint virtuale è effettivamenteridotto dia soli 2 bit, ementre la cache è organizzata come una 4-way set associative. InIl effetti,processore l'hardware mantieneimplementa una semplice permutazione datra gli indirizzi virtuali ae gli indirizzi didella cache, cosicchétale nessunda CAMrendere siasuperfluo necessariol’uso di un Content-Addressable Memory (CAM) per selezionare quelloil giustomodo deicorretto quattroda modicui direcuperare i dati. Questo approccio consente una selezione rapida del blocco in cache, pur mantenendo i vantaggi recuperodell’associatività.

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

Le cache fisicamente indicizzate di grandi dimensioni (tipicamente le cache di secondo livello) possono presentare un problema noto: il sistema operativo, anziché le applicazioni, determina quali pagine di memoria possano collidere all’interno della cache. Differenze nell’allocazione delle pagine tra diverse esecuzioni dello stesso programma possono modificare i pattern di collisione nella cache, con conseguenti variazioni significative nelle prestazioni. Tali variazioni rendono difficile ottenere misurazioni di benchmark stabili e riproducibili, portando spesso gli ingegneri a sollecitare interventi da parte degli sviluppatori del sistema operativo per mitigare 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<!-- help -->. 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.

Per comprendere il problema, si consideri una CPU dotata di una cache di secondo livello (L2) da 1 MB, direct-mapped e indicizzata fisicamente, in combinazione con una memoria virtuale suddivisa in pagine da 4 KB. In questo scenario, 256 pagine fisiche consecutive si mappano su posizioni consecutive nella cache, fino a completare un ciclo e tornare alla posizione iniziale. Ogni pagina fisica può quindi essere associata a un "colore", compreso tra 0 e 255, che rappresenta la sua posizione potenziale nella cache. Di conseguenza, due pagine con colori diversi non si sovrappongono nella cache, mentre pagine con lo stesso colore possono entrare in conflitto, causando evizioni e influenzando le prestazioni del sistema.

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

Un programmatore che desideri sfruttare al meglio la [[cache]] del processore può organizzare gli accessi alla [[memoria]] del programma in modo da ridurre al minimo i [[cache miss]] di tipo capacitivo, ovvero quei casi in cui la quantità di dati supera lo spazio disponibile nella cache. Una strategia efficace è limitare l’uso della memoria attiva a una dimensione contenuta (ad esempio 1 MB) per volta, così che l'intero set di dati possa essere contenuto nella cache senza causare sostituzioni continue. Tuttavia, anche mantenendo bassa la quantità di dati, bisogna evitare i [[cache miss]] di conflitto, che si verificano quando diverse porzioni di memoria competono per le stesse linee della cache a causa della struttura della mappatura. Un modo per affrontare questo problema consiste nell’assegnare colori virtuali alle pagine di memoria usate dal programma, in modo simile a come vengono assegnati i colori fisici alle pagine fisiche in alcuni sistemi. Il programmatore può così pianificare l'accesso alla memoria affinché due pagine con lo stesso colore virtuale non vengano utilizzate nello stesso momento, evitando così che si mappino sulla stessa porzione della cache.

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]]).

Esiste un'ampia letteratura su questo tipo di ottimizzazioni, in particolare nell’ambito del [[High Performance Computing]] (HPC), dove sono frequentemente utilizzate tecniche come la Loop nest optimization per migliorare l'efficienza dell’accesso ai dati e sfruttare meglio la gerarchia di memoria.

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.

Va infine considerato che, anche se le pagine virtuali attive sono diversificate, il [[sistema operativo]] potrebbe assegnare loro pagine fisiche in modo casuale o uniforme. Questo comporta un’elevata probabilità che due pagine abbiano lo stesso colore fisico e quindi occupino la stessa posizione nella cache, causando conflitti. Questo effetto statistico è descritto dal Birthday paradox.

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.

La soluzione staa questo problema consiste nel fare in modo che il [[sistema operativo]] tenti di assegnare pagine fisiche coloratecon diversamentecolori afisici differenti a colori virtuali differenti, una tecnica chiamatanota come ''page coloring''. Questa tecnica mira a ridurre i [[cache miss]] di conflitto, migliorando l’efficienza nell’uso della [[cache]]. Sebbene la mappaturacorrispondenza attualeesatta datra colori virtuali ae fisici siapossa irrilevantesembrare poco rilevante per le prestazioni complessive del sistema, mappature disparitroppo sonoirregolari o non uniformi risultano difficili da tracciaregestire e hanno piccolioffrono benefici, quindilimitati. Per questa ragione, la maggior parte degli approcci alla colorazione delle pagine tentacerca semplicemente di teneremantenere pagineuna fisichecoerenza tra il colore fisico e virtualiquello coloratevirtuale, nelloassegnando pagine fisiche dello stesso modocolore a pagine virtuali corrispondenti.

Se il sistema operativo riesce a garantire che ogni pagina fisica venga associata a un solo colore virtuale, si evitano i cosiddetti ''virtual alias'', ovvero situazioni in cui più indirizzi virtuali puntano alla stessa locazione fisica. In questo caso, il [[processore]] può utilizzare una cache con virtual indexing senza dover eseguire controlli aggiuntivi per gestire alias multipli durante la rilevazione di cache miss. In alternativa, il sistema operativo può forzare lo svuotamento (''flush'') di una pagina dalla cache ogni volta che essa cambia da un colore virtuale a un altro. Questo metodo è stato utilizzato in alcune architetture recenti, come quelle basate su [[SPARC]] o [[IBM RS/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.

I [[processori]] moderni adottano una gerarchia di [[cache]] multilivello (tipicamente L1, L2 e L3) per ridurre la latenza nell’accesso alla memoria principale e migliorare le prestazioni complessive del sistema. Questa struttura nasce da due necessità fondamentali: la crescente distanza in termini di velocità tra CPU e RAM, e il bisogno di gestire in modo efficiente l’accesso concorrente nei sistemi multicore. La cache L1 è la più piccola e veloce, situata direttamente all’interno di ciascun [[core]] del processore; viene spesso divisa in una sezione per i dati e una per le istruzioni. La cache L2 è più capiente e leggermente più lenta, mentre la cache L3, ancora più ampia, è generalmente condivisa tra tutti i core del chip. Questa gerarchia consente di conservare localmente i dati usati più frequentemente (''data locality''), riducendo il numero di accessi alla RAM e migliorando l’efficienza energetica. Nei sistemi più recenti, l’organizzazione delle cache è progettata per adattarsi a carichi di lavoro eterogenei, grazie a tecniche come il page coloring o l’indicizzazione virtuale delle cache, che riducono i conflitti e migliorano l’utilizzo dello spazio disponibile. In contesti ad alte prestazioni, come l’[[High Performance Computing]] o i sistemi con architettura chiplet, la gerarchia delle cache è ottimizzata anche per gestire la comunicazione tra core e acceleratori, attraverso reti su chip (Network on Chip) e cache condivise a bassa latenza.

La progettazione moderna mira a mantenere un equilibrio tra velocità, capacità e coerenza, con meccanismi intelligenti di prefetching, gestione degli alias virtuali e strategie di coerenza tra cache multilivello.

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

Il primo motivo che ha portato allo sviluppo di una gerarchia di [[cache]] nei processori moderni è legato al funzionamento delle [[CPU]] con [[pipeline]]. In queste architetture, la memoria viene interrogata in più fasi della pipeline, durante il recupero delle istruzioni, nella traduzione degli indirizzi da virtuali a fisici e nel recupero dei dati. Per evitare conflitti e colli di bottiglia, la soluzione più efficiente consiste nell'utilizzare cache fisiche separate per ciascuno di questi punti, così che nessuna risorsa debba servire più operazioni contemporaneamente. Questo approccio consente un'elevata parallelizzazione delle fasi di esecuzione, migliorando le prestazioni complessive del processore.

Di conseguenza, la pipeline di una CPU moderna tende a includere almeno tre cache distinte: una cache per le istruzioni (instruction cache), una per i [[dati]] (data cache) e una per la [[Translation Lookaside Buffer]] (TLB), utilizzata per la traduzione rapida degli indirizzi di memoria. Ciascuna di queste cache è specializzata in un compito specifico e ottimizzata per il tipo di accesso che deve gestire. Questa suddivisione consente di ridurre la latenza, aumentare la velocità di esecuzione e garantire un accesso più efficiente alla memoria principale all'interno di architetture sempre più complesse e multi-thread.

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

Riga 177 ⟶ 181:

=== 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.''"

Uno degli esempi più avanzati di specializzazione della [[cache]] è rappresentato dalla trace cache, utilizzata nei microprocessori [[Pentium 4]]. Si tratta di un meccanismo progettato per aumentare la [[larghezza di banda]] nel recupero delle istruzioni (''fetch''), memorizzando sequenze di istruzioni già decodificate, pronte per un rapido riutilizzo.

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.

Il concetto di trace cache è stato introdotto da Eric Rotenberg, Steve Bennett e [[Jim Smith]] nel loro articolo del 1996: ''Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching''.

A differenza delle cache tradizionali, la trace cache può contenere istruzioni già eseguite o pronte per l'esecuzione, organizzate in gruppi detti tracce. Queste possono rappresentare blocchi di base (cioè sequenze di istruzioni consecutive senza salti, che terminano con una ramificazione) oppure tracce dinamiche. Le tracce dinamiche sono percorsi di esecuzione effettivamente seguiti dal programma: includono solo le istruzioni realmente eseguite e omettono quelle saltate a causa di ramificazioni condizionali. Questa struttura consente al processore di recuperare rapidamente istruzioni da più blocchi consecutivi, evitando l’interruzione causata da salti condizionali o diramazioni nel flusso del programma. In questo modo, la trace cache contribuisce a migliorare l’efficienza del recupero delle istruzioni e a ridurre la latenza nell’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 tracce memorizzate nella trace cache sono identificate tramite il [[program counter]] della prima istruzione e da un insieme di predizioni sulle ramificazioni. Questo consente di conservare diverse versioni di tracce che iniziano dallo stesso indirizzo, ognuna corrispondente a differenti esiti delle ramificazioni condizionali.

Le Trace cache vengono anche impiegate in processori quali l'[[Pentium 4|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.

Durante la fase di prelievo delle istruzioni nell'instruction pipeline, il processore controlla nella trace cache se esiste una traccia corrispondente al program counter attuale e alle predizioni di salto. Se la ricerca ha esito positivo (hit), le istruzioni vengono fornite direttamente dalla trace cache, evitando di doverle recuperare dalla memoria o da una cache convenzionale. La trace cache continua ad alimentare la fetch unit fino al termine della traccia o fino a una misprediction, cioè quando la previsione su una ramificazione si rivela errata. In quel caso, si avvia la costruzione di una nuova traccia.

Rispetto alle cache tradizionali, la trace cache offre un vantaggio importante: non conserva istruzioni che seguono una ramificazione non presa o un salto incondizionato. Questo evita di occupare spazio con istruzioni che non verranno eseguite, migliorando l'efficienza complessiva.

Nei processori come l’[[Intel Pentium 4]], le trace cache vengono utilizzate anche per memorizzare micro-operazioni già decodificate (derivate da istruzioni complesse dell’architettura x86), permettendo di evitarne la decodifica nelle successive esecuzioni.

L'idea che sta alla base della trace cache ènasce chedall’esigenza neidi ottimizzare le prestazioni dei processori [[CISC]] che, internamente, utilizzanotraducono le istruzioni complesse in micro-operazioni più semplici simili a quelle di un'architettura [[Reduced instruction set computer|RISC]], come ilavviene nel [[Pentium 4]]. In questi casi, la fase di decodifica delle istruzioni èrisulta un'operazione estremamenteparticolarmente onerosa, ein iltermini suodi risultatotempo dovrebbe essere sfruttato ale megliorisorse. UtilizzareUtilizzando una trace cache, insi luogoevita di unaripetere normalela cachedecodifica haper proprioistruzioni questogià vantaggio:eseguite, nonriducendo dovercosì decodificareil un'istruzionecarico giàsul incontrataprocessore durantee l'esecuzione di unmigliorando programmal’efficienza.

UltimamenteTuttavia, lal’impiego della trace cache nonha godemostrato dialcuni moltilimiti favoriche ane causahanno diridotto alcunil’adozione nelle architetture più difettirecenti. IlIn primomolti ècasi, che moltele istruzioni RISCCISC sonovengono tradotte in una singolasola istruzionemicro-operazione CISCRISC in un solosingolo ciclo di clock,. e leLe istruzioni più complesse, che necessitano dirichiedono più cicli die clock per essere tradotte ingenerano più istruzioni di tipo RISCmicro-operazioni, sono relativamente poche e poco frequenti,rare. perQuesto cuiriduce il vantaggio effettivoprestazionale 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. Quindirispetto a parità di dimensioni una trace cache contiene molte meno istruzioni di una cache normaletradizionale.

Un ulteriore limite è legato alla rappresentazione delle istruzioni. Nelle architetture come quella di Intel, le istruzioni CISC hanno lunghezza variabile (da 1 a 6 byte, ovvero tra 8 e 48 bit), mentre le micro-operazioni RISC derivate hanno lunghezza fissa (ad esempio, 118 bit nel Pentium 4). Di conseguenza, a parità di spazio occupato in memoria, una trace cache riesce a contenere meno istruzioni rispetto a una cache convenzionale, limitandone ulteriormente l’efficacia.

Vedi il testo {{cita testo|url=http://citeseer.ist.psu.edu/rotenberg96trace.html|titolo=Smith, Rotenberg and Bennett s paper|accesso=30 novembre 2019|dataarchivio=3 aprile 2008|urlarchivio=https://web.archive.org/web/20080403043445/http://citeseer.ist.psu.edu/rotenberg96trace.html|urlmorto=sì}} In [[Citeseer]].

Vedi il testo {{cita testo|url=http://citeseer.ist.psu.edu/rotenberg96trace.html|titolo=Smith, Rotenberg and Bennett 's paper|accesso=30 novembre 2019|dataarchivio=3 aprile 2008|urlarchivio=https://web.archive.org/web/20080403043445/http://citeseer.ist.psu.edu/rotenberg96trace.html|urlmorto=sì}} Inin [[CiteseerCiteSeer]].

== 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 II|Pentium 2]], [[Pentium III|3]], e [[Pentium 4|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'[[Advanced Micro Devices|AMD]] [[Athlon Classic|Athlon]]) hanno cache exclusive in cui è garantito che i dati siano al massimo in una delle cache L1 o L2.

Le [[cache]] multilivello introducono un nuovo modello nella gestione dei dati. In molti processori moderni, come quelli della famiglia [[Intel Core]] (dalla generazione [[Sandy Bridge]] in poi) e alcuni [[Architettura ARM|ARM]] avanzati, i dati presenti nella cache [[L1]] sono sempre contenuti anche nella cache [[L2]]. Questo tipo di organizzazione è detta inclusive.Al contrario, altri processori, come quelli della serie AMD Ryzen, adottano cache exclusive, dove ogni dato risiede al massimo in una sola delle due cache, o nella [[L1]] o nella [[L2]], ma mai in entrambe contemporaneamente.

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 [[Architettura x86|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.

Il vantaggio delle cache exclusive è che possono immagazzinare una quantità maggiore di dati totali, un beneficio che diventa più evidente all’aumentare delle dimensioni delle cache. Tuttavia, questa caratteristica non è comune nelle implementazioni [[x86]] di [[Intel]]. D’altra parte, il vantaggio principale delle cache inclusive è che, in un sistema [[multiprocessore]], quando un dispositivo esterno o un altro processore deve invalidare una linea di cache, può controllare soltanto la cache L2 per decidere se eliminarla, senza dover verificare anche la L1. In sistemi senza inclusione, invece, è necessario controllare entrambe le cache L1 e L2, rendendo il processo più complesso.

Inoltre, esiste una relazione tra l’[[associatività]] delle cache L1 e L2: affinché l’associatività effettiva della cache L1 non venga limitata, la cache L2 deve avere almeno un numero di modi (set associativi) pari o superiore al totale delle cache L1 nel sistema.

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 la gerarchia multilivello delle [[cache]], si può prendere come esempio l’architettura AMD [[Athlon 64]], nota anche come ''architettura K8''. La K8 utilizza quattro tipi di cache specializzate: una cache d’[[istruzione]], una [[Translation Lookaside Buffer|TLB]] d’istruzioni, una cache di dati e una TLB di dati. Ogni cache ha un ruolo specifico: La cache d’istruzioni mantiene copie di linee di memoria da 64 byte e recupera 16 byte per ciclo. Ogni byte in questa cache è memorizzato con 10 bit anziché 8, con i bit extra usati per indicare i limiti delle istruzioni (un esempio di precodifica). Questa cache utilizza un codice di parità per il controllo degli errori, che è meno pesante di un codice [[Error-correcting code|ECC]]; eventuali dati corrotti vengono ricaricati dalla memoria principale. La TLB d’istruzioni conserva le informazioni delle (PTE) e traduce gli indirizzi virtuali in indirizzi fisici durante il recupero delle istruzioni. È suddivisa in due sezioni: una per le mappature da 4 KB e una per mappature da 2 o 4 MB, facilitando un confronto completamente associativo in ciascuna sezione. La TLB dei dati ha due copie identiche che permettono di eseguire due traduzioni di indirizzi per ciclo, con la stessa suddivisione in base alla dimensione delle pagine. La cache dei dati memorizza linee da 64 byte ed è organizzata in 8 banchi da 8 KB ciascuno, capaci di fornire due dati da 8 byte per ciclo se presi da banchi diversi. Le etichette (tag) sono duplicate per gestire questi accessi simultanei. La K8 include anche cache di secondo livello (L2) per le TLB di istruzioni e dati, che immagazzinano solo mappature di pagine da 4 KB. Sia le cache L1 (dati e istruzioni) che le TLB sono rimpiazzate dalla cache L2, che è exclusive rispetto alle L1: una linea può risiedere solo in una tra cache L1 dati, cache L1 istruzioni o cache L2. La K8 gestisce anche informazioni di [[Predizione delle diramazioni|branch prediction]] associate alle istruzioni, immagazzinate sia nella cache L1 istruzioni sia nella cache L2 unificata. Per migliorare la predizione, utilizza bit extra in linee di cache protette da [[parità]] o [[Error-correcting code|ECC]], permettendo una migliore accuratezza grazie a una più ampia memoria storica dei percorsi di esecuzione.

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 [[Translation Lookaside Buffer|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 [[Parity|parità]] piuttosto che una [[Error-correcting code|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 [[Predizione delle diramazioni|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'[[Error-correcting code|ECC]] o tramite la [[Parità (informatica)|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 hannoutilizzano altridiversi tipi di predittori. (adAd esempio, loil store-to-load bypass predictor nel DEC Alpha 21264), eè altriun svariaticaso predittorispecifico, specializzatie si sonoprevedono facilmente pensabiliulteriori dapredittori esserespecializzati da integratiintegrare neinelle futurifuture processoriarchitetture.

Questi predittori sonofunzionano cachein nelmodo sensosimile alle cache, chepoiché immagazzinano informazioni cheil sonocui costosecalcolo daè calcolare.costoso Alcunein delletermini terminologiedi utilizzatetempo nelo discutererisorse. iAlcuni predittoritermini sonousati lenella stessedescrizione didei quellepredittori, per le cache (si parla dicome hit nel predittore di percorsi), masono mutuati dalla terminologia delle cache. Tuttavia, i predittori non sonovengono generalmente pesaticonsiderati come parte della gerarchia delle cache.

LaL’architettura K8 mantiene le cache di istruzioni e i dati delle cache [[Cache coherency|coerenti]] nell'direttamente via hardware, ilgarantendo che significauna chescrittura unin immagazzinamentomemoria invenga un'istruzionesubito appenariflessa doponel l'immagazzinamentoflusso dell'istruzionedelle cambierà l'istruzioneistruzioni seguentesuccessive. Altri processori, come quelli nelladelle famigliafamiglie Alpha e MPSMIPS, sonoaffidano basatiinvece sulal software peril compito di mantenere lela coerenza tra cache d'istruzionid’istruzioni coerentie dati. GliIn immagazzinamentiquesti casi, una scrittura in memoria non sonoè garantitiautomaticamente divisibile essereal vistiflusso neldi fiume d'istruzioni a meno che unil programma chiaminon un'opzioneutilizzi delesplicitamente sistemaun’istruzione operativoo peruna assicurarsichiamata dellaal coerenza.sistema L'ideaoperativo èper quella di risparmiareassicurare la complessità dell'hardware sull'assunzione che il [[codice automodificante]] è rarocoerenza.

Questa scelta si basa sull’assunzione che il [[codice automodificante]] sia un fenomeno raro, permettendo di ridurre la complessità hardware necessaria per mantenere automaticamente la coerenza delle cache.

La gerarchia didelle cache si allargaestende se consideriamo il software come l'hardwareparte dell’hardware. Il register file nel core di un processore può essere consideratavisto come una cache molto piccola, e veloce, i qualicui hit, fallimenti,miss e riempimenti sono previstigeneralmente gestiti dal compilatore primain del tempoanticipo (vedi specialmentein particolare [[Loop nest optimization]]). I register file apossono volteavere hannoa anch'essiloro volta una gerarchia: ad esempio, la [[Cray-1]] (circaintorno delal 1976) avevadisponeva di 8 registri scalari e 8 registri d'indirizzid’indirizzi chedi eranouso generalmente utilizzabiligenerale, avevaoltre anchea 64 registri scalari e 64 registri d'indirizzid’indirizzi di tipo "B". IQuesti registri di tipo "B" potevano essere caricati più velocementerapidamente dirispetto quelli nellaalla memoria principale, inpoiché quanto illa Cray-1 non avevadisponeva di una cache didati datitradizionale.

== Implementazione == <!-- paragrafo rivisitato il 23/03/2024. Mancano sempre le fonti e le note -->

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.

Dato che le letture dalla cache sono operazioni frequenti che richiedono più cicli di clock, il percorso critico nel design dei processori è spesso il trasferimento dei dati dalla cache all’unità di esecuzione delle istruzioni. Questo passaggio è cruciale per ottimizzare le prestazioni della CPU, poiché un accesso rapido alla cache [[L1]] è fondamentale per ridurre i ritardi.

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.

La cache più semplice è la cache direttamente mappata, dove una porzione dell’indirizzo virtuale viene calcolata tramite un sommatore e usata per indicizzare una memoria SRAM (Static Random Access Memory). I dati corrispondenti sono quindi letti direttamente da quella posizione. In questo schema, non è necessario un controllo delle etichette (tag) durante il ciclo interno di accesso, perché le etichette vengono verificate solo in un secondo momento per confermare un cache hit. Se la verifica fallisce (miss), la cache viene aggiornata e l’accesso ripetuto.

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.

Le cache associative sono più complesse, poiché richiedono la lettura simultanea di alcunipiù etichette e dati per determinare quale punto della cachelinea selezionare. Ad esempio, una cache level-1 set-associative di primo livello (L1), N-way, legge in parallelo tutte le possibili etichette e dati indi paralleloun eset, selezionascegliendo quelli associatiche all'etichettacorrispondono corrispondenteall’indirizzo richiesto. Le cache level-2di secondo livello (L2) possono risparmiareottimizzare potenzail consumo energetico leggendo prima le etichette e poi selezionando quindi i dati dalla SRAM solo se necessario.

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.

Il diagramma a destra illustra l'organizzazionel’organizzazione degli indirizzi nellain cache. Ad esempio, una cache 4KBdi 4 KB, 2-way set-associative con linee da 64B64 utilizzabyte è composta da 64 linee e leggepuò leggere due allalinee voltacontemporaneamente da una SRAM conorganizzata in 32 righe. Sebbene qualsiasi funzione deglidei indirizzibit virtualidell’indirizzo davirtuale compresi tra 31 ae 6 possa essere usata per indicizzare etichette e dati SRAM, èin piùgenere comunesi utilizzareutilizzano i bit meno significativi per migliorare l’efficienza.

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

Inoltre, una cacheCache più modernamoderne potrebbepossono essere diavere dimensioni diversevariabili e utilizzare diverseadottare tecniche differenti, come indicizzazionel’indicizzazione virtuale, suggerimenti virtuali (vhints) e indicizzazione fisica. QuestePur cache seguonoseguendo un percorso di lettura simile, maqueste cache utilizzano diversi tipi di dati, come i vhints anzichéal posto delle etichette, per determinare un cache hit.

Alcune implementazioni dell’architettura [[SPARC]] hanno miglioratoottimizzato le prestazioni delle loro cache L1 riducendo i ritardi delassociati sommatoreal dell'indirizzocalcolo dell’indirizzo virtuale nei decoder delle SRAM.

== Note ==

<references/>