Memoria cache: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
fix vari +W |
|||
Riga 1:
{{C|La voce è trattata in maniera eccessivamente specialistica. Bisognerebbe 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}}
{{F|informatica|maggio 2018}}
{{W|informatica|gennaio 2019|commento=eccesso di grassetti, eccesso di elenchi puntati (malformattati), mancanza di corsivi per i termini gergali/anglofoni (che sarebbero da ridurre)}}
La '''memoria cache''' (in inglese ''cache memory'', ''memory cache'' o ''[[CPU]] cache''), in [[informatica]], è una [[memoria (informatica)|memoria]] veloce (rispetto alla [[Memoria (informatica)#Memoria primaria|memoria principale]]), relativamente piccola, non visibile al [[software]] e completamente gestita dall'[[hardware]], che memorizza i dati più recentemente usati della [[Memoria (informatica)#Memoria primaria|memoria principale]] (MM - Main Memory) o memoria di lavoro del sistema.
Line 7 ⟶ 8:
== Caratteristiche ==
{{Approfondimento
| titolo=CPU cache
| contenuto="CPU cache" è un termine non comune ed è raramente o per niente usato sia in letteratura che negli ambienti industriali tra gli esperti del settore. Per esempio, nei documenti relativi ai brevetti (USA), il termine ''"CPU cache"'' è usato meno del 2% dei casi<ref>[http://www.freepatentsonline.com/result.html?query_txt=%22CPU+cache%22&sort=relevance&srch=top&search= FPO IP Research & Communities]</ref> rispetto al termine "Cache Memory" (83%)<ref>[http://www.freepatentsonline.com/result.html?query_txt=%22Cache+memory%22&sort=relevance&srch=top&search= FPO IP Research & Communities]</ref> e "Memory Cache" (15%)<ref>[http://www.freepatentsonline.com/result.html?query_txt=%22Memory+cache%22&sort=relevance&srch=top&search FPO IP Research & Communities]</ref>. La Cache Memory è una funzione associata ad una memoria e non ad uno specifico utente di questa funzione. Questa funzione può essere usata da una [[CPU]], o in [[#Shared Cache|Shared Cache]] da un gruppo di CPU o [[#Sistemi Multi-core|Core]] o [[#Directory-based - Message-passing|Nodi]], o anche associata a un gruppo di memorie remote nei sistemi [[#Directory-based - Message-passing|NUMA]], o in generale da qualsiasi ''device'' che può accedere ad una memoria principale. Il termine "CPU cache" è perciò troppo restrittivo e quindi inappropriato (vedi per es. [[#Cache Remota|Cache remota]] - cache delle memorie remote).
}}{{
Il termine ''"cache"'' deriva dal francese e significa "nascosto".
{{
=== Funzionamento ===
La logica funzionale della memoria cache è il seguente:
# nelle operazioni di lettura della memoria principale (MM), per prima cosa il gestore della cache verifica se il dato è memorizzato nella cache;
# in caso di esito positivo (Hit) il dato è direttamente e velocemente trasferito dalla cache al processore senza coinvolgere la MM;
Line 28 ⟶ 26:
* Località temporale (temporal locality): dati recentemente usati hanno un'alta probabilità di essere nuovamente usati a breve. Una cache memorizza solo un sottoinsieme dei dati della MM - ''the most recent-used - i dati più recentemente usati'' (MRU). I dati letti dalla MM sono temporaneamente memorizzati in cache. Se il processore richiede lo stesso dato, questo è fornito dalla cache. La cache è efficiente perché loop brevi di istruzioni e routine (piccoli programmi) sono strutture comuni di programmi e generalmente diverse operazioni sono eseguite sugli stessi dati e variabili.
* Località spaziale (spatial locality): se un dato viene referenziato, è molto probabile che dati adiacenti siano a breve a loro volta acceduti. Istruzioni e i dati sono trasferiti dalla MM alla cache in blocchi fissi (cache blocks), noti come cache lines (linee di cache). La dimensione della linea di cache è nel range di 4-512 byte<ref name="POWER4">The POWER4 Processor Introduction and Tuning Guide par. 2.4 - {{cita web |url=http://web.eecs.utk.edu/~terpstra/power4/p4Tuning.pdf |titolo=Copia archiviata |accesso=26 settembre 2014 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20141206042322/http://web.eecs.utk.edu/~terpstra/power4/p4Tuning.pdf |dataarchivio=6 dicembre 2014 }}</ref>, cosicché più di un dato da processare (4/8 byte) è memorizzato in ciascuna cache entry (indirizzo di cache). Dopo il primo accesso alla MM, tutti i dati relativi alla linea di cache sono disponibili nella cache stessa. Molti programmi sono altamente sequenziali. La successiva istruzione generalmente è all'indirizzo successivo di memoria. I dati sono generalmente strutturati e i dati in queste strutture sono normalmente memorizzati in posizioni continue di memoria (stringhe di dati, tabelle, ecc.). Grandi linee di cache aumentano la località spaziale ma aumenta anche il numero di dati invalidati in casi di rimpiazzo della linea (vedi [[#Replacement Policy (Politica di Rimpiazzo - deallocazione della linea di cache)|Replacement policy]]).
=== Efficienza ===
L'efficienza della cache è misurata in termini di "Hit Rate". L'Hit Rate rappresenta la percentuale di Hit, ovvero il dato trovato in cache, rispetto al numero totale degli accessi alla cache. Il contrario di "Hit" è denominato "Miss". L'efficienza della cache dipende da diversi elementi quali la dimensione della cache, la dimensione della linea di cache, il tipo, l'architettura e dalle applicazioni. Una buona figura di rendimento, per applicazioni commerciali, può essere compresa nel range di 80-95 % di hit<ref name="SMP analysis">Architecture Analysis of Tightly Coupled Multiprocessor Systems - F. Zulian Honeywell (Bull Italia 1987)</ref>.
== Struttura di base ==
Ci sono tre strutture di base per le cache:
* Cache Fully Associative (cache completamente associativa)
* Cache Direct Mapped (cache mappata direttamente)
Line 44 ⟶ 38:
=== Cache Fully Associative ===
[[File:Fully Associative Cache.svg|thumb|right|upright=2.1|Fully Associative Cache]]
Ogni blocco di memoria può essere memorizzato in qualsiasi posizione della cache. È chiamata "fully associative" (completamente associativa) perché ogni dato memorizzato in cache è associato al suo indirizzo completo di memoria.
Line 53 ⟶ 46:
=== Cache Direct Mapped ===
[[File:Direct Mapped Cache.svg|thumb|right|upright=2.1|Direct Mapped Cache]]
Nella cache Direct Mapped - Mappata Direttamente ogni blocco di memoria può essere memorizzato in una sola entry di cache. La entry (cioè la posizione di cache) dove memorizzare il blocco è ''direttamente derivata'' dall'indirizzo di memoria (da cui il nome "Direct-Mapped" - mappata direttamente).
Line 66 ⟶ 58:
=== Cache Set Associative ===
La cache Set Associative (o ''multi-via-direct-mapped'' ) è una combinazione dei due approcci precedenti ed è usata per ridurre il conflitto tra sinonimi.
Questa cache è composta da un set di identiche cache Direct Mapped, indirizzate nello stesso identico modo, cosicché per ciascuna entry è disponibile un "set" (gruppo, way-vie) di alternative linee di cache per memorizzare più di un sinonimo. I sinonimi possono essere memorizzati in qualsiasi set delle entry selezionate, in funzione dell'algoritmo di '''''''[[#Replacement Policy (Politica di Rimpiazzo - deallocazione della linea di cache)|politica di rimpiazzo]]''''''' utilizzata, generalmente '''LRU'''.
Line 74 ⟶ 65:
In dipendenza dalla politica di rimpiazzo "[[#Replacement Policy (Politica di Rimpiazzo - deallocazione della linea di cache)|Replacement policy]]" adottata, la Directory può o no contenere anche i '''''Replacement bits''''' (bit di rimpiazzo) per selezionare la linea di cache candidata per il rimpiazzo.
=== ''Replacement
Quando è disponibile più di una entry per memorizzare un dato, come nel caso di cache Fully Associative e Set Associative, la entry che dovrà essere rimpiazzata è selezionata in base alla "Replacement policy" adottata.
Ci sono differenti politiche<ref>{{cita web|url=http://www.ece.uah.edu/~milenka/docs/milenkovic_acmse04r.pdf|titolo=Performance Evaluation of Cache Replacement Policies for the SPEC CPU2000 Benchmark Suite|formato=PDF}}</ref>.
Line 111 ⟶ 101:
== Tipi di cache ==
Ci sono due tipi di cache:
* Instruction cache (cache delle istruzioni)
* Data cache (cache dei dati)
==== Cache istruzioni e cache dati ====
Nella MM sono memorizzati due tipi di informazioni, le istruzioni (anche chiamate codice) e dati (come operandi o di stack - vedi [[Stack cache]])
Line 130 ⟶ 117:
=== Cache inclusiva ed esclusiva ===
La cache può essere inclusiva o esclusiva:
* '''Inclusiva'''<span style="color"> ''significa che il contenuto della cache L1 è incluso anche nella cache L2, cioè L1 è un sottoinsieme della L2''.</span>
Line 147 ⟶ 132:
* '''Esclusiva''' (o '''non Inclusiva''') <span style="color">''significa che il dato può essere memorizzato solo in una cache''.</span>
:* L2 cache contiene solo linee di cache copy-back (scritte indietro da L1 a L2), che sono state ''espulse'' dalla L1 a causa di conflitti di miss (''victim'' lines - linee vittime). Questo tipo di cache viene perciò anche chiamata '''''"victim cache"'''''
:: (Nota - La dimensione della cache globale è la somma delle dimensioni di tutte e due le cache).
Line 159 ⟶ 143:
* '''Inclusività vs Esclusività''': L'inclusività è preferibile nei sistemi [[#SMP - Symmetric Multiprocessor System|multiprocessori]]/[[#Sistemi Multi-core|multi-core]] bus-based, cioè basati sul bus per la coerenza dei dati, altrimenti il controllo di coerenza deve essere fatto in tutte le cache (vedi sotto [[#Interferenze tra Snoopy e Attività del Processore|Interferenze tra Snoopy e Attività del Processore]]). L'inclusività semplifica la coerenza delle cache. L'aspetto negativo della cache inclusiva è che la cache L2 contiene dati ridondanti, questo significa una riduzione della dimensione della cache globale. Questo è vero solo se le dimensioni delle cache L1 e L2 sono comparabili. Spesso la dimensione di L2 è un ordine di grandezza rispetto a L1, perciò la riduzione del hit-rate dovuto alla riduzione della dimensione globale può essere molto bassa (qualche percento), considerando anche che nel range di 80-95 % di hit-rate, aumentando la dimensione, il guadagno del hit-rate tende rapidamente ad essere piatto<ref name="SMP analysis" />. Le stesse considerazioni possono essere fatte per la cache L3 rispetto a L2 (vedi per esempio Shanghai (AMD) vs Nehalem-EP (Intel)<ref name="Shanghai - Nehalem-EP">Comparing Cache Architectures and Coherency Protocols on x86-64 Multicore SMP Systems - http://people.freebsd.org/~lstewart/articles/cache-performance-x86-2009.pdf</ref>).
== ''Write
La ''write policy'' - o politica di scrittura - determina come vanno gestite le scritture in memoria di dati memorizzati in cache. Generalmente solo la D-Cache è interessata, perché normalmente le istruzioni non sono auto-modificanti, e in caso di auto-modifica, il software forza la scrittura di questo codice (Istruzioni) solo in memoria senza coinvolgere la cache (vedi ad esempio [[AMD64]] ''Self-Modifying Code''<ref name="AMD642">Architecture Programmer’s Manual "3.9.4 Cache Operation" - http://developer.amd.com/wordpress/media/2012/10/24593_APM_v21.pdf</ref>)
Ci sono due tipi di politiche:
: - ''Write through''
: - ''Write-back'' (o ''copy back'')
==== ''Write through'' (scrittura passante) ====
* Il dato viene scritto contemporaneamente sia in cache che in memoria o in cache e poi in memoria (da cui il nome)
==== ''Write-
* Il dato è aggiornato solamente nella cache. Viene riscritto in memoria solo quando è necessario, per esempio in casi di "rimpiazzo" (sovrascrittura) della linea di cache o quando richiesto da altre cache. Questo riduce il traffico di memoria e di bus perché il successivo aggiornamento della linea di cache viene fatto solo nella cache senza coinvolgere la memoria. Nella Directory della cache, in questi casi viene attivato (settato) il bit "'''D'''" o "'''M'''" ('''D'''irty = sporco o '''M'''odificato) - (vedi sotto [[#Stati della cache|Stati della Cache]]).
In caso di miss in scrittura si hanno due differenti soluzioni:
==== ''Write
: '''''Write allocate on miss''''' (allocazione in scrittura su miss) detta anche '''''Fetch-on-write''''' (acquisire per scrivere) o '''''RWITM''''' ('''R'''ead '''W'''ith '''I'''ntent '''T'''o '''M'''odify - lettura con intenzione di modifica) o '''''Read for Write''''' - lettura per scrittura
* In caso di miss in scrittura, la linea di cache è letta prima dalla [[Memoria (informatica)#Memoria primaria|memoria principale]] o da una cache in caso di [[#Operazioni di Coerenza Snoopy|Cache Intervention]] (intervento di cache), poi è aggiornata (modificata) in cache con il nuovo dato (scrittura parziale della linea: byte, halfword, word o doubleword - 8, 16, 32 o 64 bit, dipendente dal parallelismo operativo intrinseco del processore)
==== ''Write no-
* Il dato è scritto direttamente in MM "by-passando" la cache
: - ''Write allocate'' è normalmente associata al ''write-back''. Write ''no-allocate'' può essere o non associata al ''write-through''.
== Livelli di cache ==
In un sistema può essere usata più di una cache. Le cache sono organizzate in livelli gerarchici. Sono possibili sino a quattro livelli, L1-L4 o più<ref>Intel Iris Pro 5200 Graphics Review: Core i7-4950HQ Tested - http://www.anandtech.com/show/6993/intel-iris-pro-5200-graphics-review-core-i74950hq-tested/3</ref>. Una cache più grande ha un hit-rate migliore ma un tempo di latenza maggiore. Una cache multi-livello garantisce un accesso veloce con un alto hit-rate. Generalmente la cache multi-livello opera verificando prima la cache più piccola di più basso livello, il Livello 1 (L1). Se si ha hit il processore procede velocemente. Se la cache più piccola dà miss, viene controllata la successiva cache più grande (L2), e così via fino al più alto livello. Il miglioramento della tecnologia permette sufficiente spazio per implementare una piccola cache L1 all'interno del [[Circuito integrato|chip]] del processore. Una cache interna è più veloce di una esterna, ma ha un più basso hit rate dovuto alla sua minore dimensione, tipicamente nel range tra 8KB a 64KB. Per aumentare la dimensione globale della cache e così l'hit rate, si usa una cache L2 maggiore strettamente accoppiata al processore. Una dimensione tipica della cache L2 è nel range da 64KB a 8MB. La cache L2 può essere esterna o interna al [[Circuito integrato|chip]] o al [[package (elettronica)|package]] del processore. In questo ultimo caso perciò può essere usata una ulteriore cache L3 esterna ancora maggiore (4-256MB). Nei sistemi multi-core la L3 può essere implementata in un MCM ([[:en:Multi-chip module|Multi-chip module]]) (vedi per es. [[POWER5]] IBM, AMD [[:en:Bulldozer (microarchitecture)|Bulldozer]]). Normalmente la L1 è una cache Set Associative separata Istruzioni e Dati. La cache L2 può essere unificata o separata, come pure essere una cache Direct Mapped o Set Associative. Lo stesso per la cache L3.
[[File:Multi-level Cache Hierarchy diagram.svg|thumb|right|upright=1.2|Gerarchia delle Cache Multi-livello]]'''Funzione gerarchica delle cache multi-livello'''
Line 208 ⟶ 185:
:::: - usata qualche volta come ''[[#Cache inclusiva ed esclusiva|Victim cache]]'' di L3 nei processori grafici ([[Graphics Processing Unit|GPU]])<ref>{{Cita news|nome=Anand Lal|cognome=Shimpi|url=http://www.anandtech.com/show/6993/intel-iris-pro-5200-graphics-review-core-i74950hq-tested/3|titolo=Intel Iris Pro 5200 Graphics Review: Core i7-4950HQ Tested|accesso=28 febbraio 2017}}</ref>.
== Cache
Le architetture '''''[[:en:Superscalar|Superscalar processor]]''''' (processori superscalari = multi unità operative) sono in grado di eseguire simultaneamente istruzioni in parallelo (sfruttando il parallelismo intrinseco delle istruzioni ''[[stream (informatica)|stream]] / [[multithread]]'' - flusso continuo/multi ramificazioni). In questo genere di processori ci sono diversi unità funzionali dello stesso tipo con dei circuiti addizionali per il "dispaccio" delle istruzioni alle varie unità. Nella maggior parte di questi sistemi "superscalar" includono più di una unità aritmetica-logica (unità per operazioni aritmetiche e logiche). Per esempio in [[POWER3|IBM POWER3]]<ref>RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide - {{cita web |url=http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf |titolo=Copia archiviata |accesso=27 luglio 2006 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20060721115557/http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf |dataarchivio=21 luglio 2006 }} (Ch. 2.1 pp. 7-8)</ref> sino a otto istruzioni, due floating point (virgola mobile), due load/store (lettura/scrittura = spostamento dati - in inglese "move"), tre fixed point - (virgola fissa), due singolo ciclo, un multi-ciclo e un "branch" (istruzione di salto - le istruzioni vengono eseguite in modo sequenziali sino a trovare un'istruzione di "salto" che salta ad una nuova sequenza) che possono essere eseguite nello stesso ciclo. Le istruzioni disponibili sono inviate ''[[Esecuzione fuori ordine|fuori ordine]]'' (''[[:en:Out-of-order execution|out of order]]'') dalle code di uscita, consentendo a queste istruzioni di essere eseguite fuori ordine per mezzo dell'uso della tecnica dei ''[[Rinominazione dei registri|Register renaming]]'' (Rinominazione dei registri) per la sincronizzazione e il riordino dei risultati.
Line 216 ⟶ 192:
Ci sono diverse soluzioni<ref>Comparing Multiported Cache Schemes - http://www.researchgate.net/publication/221134115_Comparing_Multiported_Cache_Schemes/file/32bfe50fb1759c4f80.pdf</ref><ref>On High-Bandwidth Data Cache Design for Multi-Issue Processors - http://web.eecs.umich.edu/~taustin/papers/MICRO30-bwcache.pdf</ref>:
* Cache
* Cache
* Multiple copie
* Multi-porte
* Soluzione ibrida
=== Cache
La D-cache L1 è divisa in banchi multipli con indirizzi indipendenti.
Ci sono due approcci:
Line 231 ⟶ 206:
==== Indirizzamento lineare ====
I banchi sono indirizzati in parallelo tramite un [[#Directory-based - Message-passing|crossbar]] (connessioni dirette incrociate). L'indirizzo è lineare, cioè il successivo indirizzo dell'ultimo indirizzo di un banco è il primo indirizzo del banco successivo. I banchi sono selezionati in sequenza tramite l'uso dei bit più significativi (MSB) dell' "Index" dell'indirizzo (per esempio, con 8 banchi, i tre bit 21-19 dell'esempio in [[#Cache Direct Mapped|''Cache addressing'']]). I banchi multipli possono supportare multiple richieste per ciclo quando queste non indirizzano lo stesso banco.
L'approccio multi-banco può essere efficiente per applicazioni che hanno una scarsa località spaziale dei dati (dati statisticamente indipendenti), ma per applicazioni con una buona località spaziale, come negli accessi consecutivi, accessi simultanei multipli non sono permessi causa "conflitti di banco" (bank collision - collisioni di banchi)
==== ''Cache interleaving'' (cache interlacciata) ====
[[File:8-way Cache Interleaving.svg|thumb|right|upright=2.4|8-way Cache Interleaving]]
Linee di cache consecutive sono memorizzate su banchi consecutivi. L'indirizzamento delle linee di cache è "interlacciato" (distribuito orizzontalmente) tra i banchi come mostrato nella fig. a lato. I banchi sono selezionati tramite i bit più meno significativi dell' "Index" dell'indirizzo (per esempio, con una 8-way interleaving (interlacciamento a 8 vie), i bit 10-8 dell'esempio sopra in [[#Cache Direct Mapped|''Cache addressing'']]). Comunemente il numero di banchi varia da due, quattro od otto (vedi ad es. [[POWER3|IBM POWER3]]<ref>BM RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide (Ch 7.1 p. 89) - {{cita web |url=http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf |titolo=Copia archiviata |accesso=27 luglio 2006 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20060721115557/http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf |dataarchivio=21 luglio 2006 }}</ref>), chiamati ''two-way'', ''four-way'' o ''eight-way'' ''interleaving'' rispettivamente.
La cache interleaving da vantaggi specialmente nelle operazioni su stringhe di dati multipli. Per esempio, avendo una cache two-way interleaving (indirizzo pari nel Banco 0 e dispari nel Banco 1) e due programmi (threads) che operano su due stringhe indipendenti, il primo programma può accedere al Banco 0 mentre il secondo al Banco 1. Nel successivo accesso, il primo programma può accedere al Banco 1 mentre il secondo al Banco 0, e così via alternativamente. In caso di "conflitto di banchi" (bank collision), cioè accesso simultaneo allo stesso banco, un programma all'inizio deve aspettare un ciclo, poi può iniziare. Anche negli accessi casuali simultanei multipli questo sistema offre vantaggi, dipendente dal numero di banchi. La probabilità di conflitto diminuiscono all'aumentare del numero di banchi.
Esempio di interleaving: la cache L1 di POWER3<ref>BM RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide Ch. 2.1 p. 7 - ch 7.1 p.89 - {{cita web |url=http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf |titolo=Copia archiviata |accesso=27 luglio 2006 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20060721115557/http://www.redbooks.ibm.com/redbooks/pdfs/sg245155.pdf |dataarchivio=21 luglio 2006 }}</ref> con interleaving a 8-vie è in grado di servire due "load" (letture), una "store" (scrittura) e una rilettura (reload) di una linea di cache per ciclo.
===
Porte multiple permettono di fare accessi paralleli multipli alla cache nello stesso ciclo di clock, che operano in modo indipendente fra loro<ref name="POWER4" /><ref name="POWER4 protocol">"POWER4 System Microarchitecture", http://www.cc.gatech.edu/~bader/COURSES/UNM/ece637-Fall2003/papers/TDF02.pdf</ref>.
Line 250 ⟶ 221:
Perciò questa soluzione può essere usata per solo poche porte, normalmente due per le letture e una per le scritture (es. [[Protocolli di coerenza della cache (esempi)#Protocollo POWER4 IBM|POWER4 IBM]]).
=== Multiple copie (''mirroring'' o ''cloning'') ===
Cache con "n" identiche copie (cloni) con indirizzamento simultaneo indipendente. Limitazioni: copie replicate senza benefici di spazio di memorizzazione. Inoltre le richieste di scrittura devono essere fatte simultaneamente su tutte le copie, cosicché nessuna altra richiesta può essere inviata in parallelo. Poiché circa il 30% di accessi alla memoria sono scritture<ref>John L. Hennessy and David A. Patterson. CompzLter Architecture: A Quantitative Approach, 2nd Edition. Morgan Kaufmann Publishers Inc., 1996.</ref>, questa soluzione ha dei severi limiti.
=== Multi-porte Virtuali (time division multiplexing - divisione di tempo distribuita) ===
La "time division multiplexing" è una tecnica che può essere anche riferita come "cache over-clocking" cioè clock con frequenza maggiorata. Funzionamento della cache con frequenza 2x (3x, 4x) della frequenza del processore in modo che la cache può essere acceduta due (tre, quattro) volte per ciclo (clock).
=== Soluzione ibrida ===
Combinazione della soluzione cache interleaving con multi-porte. I banchi multipli interleaving permettono accessi paralleli a basso costo mentre le porte multiple riducono i conflitti di banco.
== Coerenza della cache (
I processori possono condividere una cache comune. Le cache condivise generalmente sono usate per la coerenza dei dati nei sistemi [[#Sistemi Multi-core|multi-core]] (Multi-chip) e per la riduzione dei costi. Nei sistemi come il [[Sistema multiprocessore simmetrico|multiprocessore simmetrico (SMP)]], il [[multi core]] e il [[Non-Uniform Memory Access|cc-NUMA]], dove viene usata una cache dedicata per ogni [[processore]], [[Core (informatica)|core]] o [[#Directory-based - Message-passing|nodo]], si può verificare un problema di coerenza, o coerenza, dei dati quando uno stesso dato è memorizzato in più di una cache e si verifica che un dato viene modificato in una cache. Può essere risolto in due modi:
# invalidando tutte le copie delle altre cache (broadcast-invalidate - diffusione invalidazione);
Line 272 ⟶ 239:
Gli schemi si possono classificare in base a:
* Schema Snoopy Vs Directory e Vs Shared caches;
* Protocollo Write through vs Write-back (basati sull'ownership o proprietà);
Line 280 ⟶ 246:
Tre approcci sono addottati per mantenere la coerenza dei dati:
# '''Bus watching o Snooping''': generalmente usato per i sistemi SMP o [[Sistema multiprocessore simmetrico|Sistema Multiprocessore Simmetrico]]/[[#Sistemi Multi-core|multi-core]] basati sul bus;
# '''Directory-based - Message-passing''': basati sulla directory e scambio di messaggi; possono essere usati in tutti i sistemi, ma tipicamente nei sistemi [[#Directory-based - Message-passing|cc-NUMA]] e nei sistemi [[#Sistemi Multi-core|multi-core]] estesi;
Line 286 ⟶ 251:
=== Bus watching o Snooping ===
[[File:SMP - Symmetric Multiprocessor System.svg|thumb|right|upright=1.8|SMP - Symmetric Multiprocessor System]]
Protocollo usato nei sistemi con bus, come ad esempio nei sistemi SMP. Sistema operante sotto un unico [[Sistema Operativo|sistema operativo]] con due o più processori omogenei e con una [[Memoria (informatica)#Memoria primaria|memoria principale]] centralizzata condivisa. Ciascun processore ha una propria cache che agisce come ponte tra il processore e la memoria principale. La connessione è fatta usando un [[bus di sistema]] (system bus) o un [[#Directory-based - Message-passing|crossbar]] (xbar, connessioni incrociate)<ref name="AMD Opteron" /> o un mix dei due precedenti sistemi, bus per gli indirizzi e [[#Directory-based - Message-passing|crossbar]] per i dati (data crossbar)<ref name="Crossbar dati">Multi-processor system with shared memory - http://www.freepatentsonline.com/5701413.html</ref><ref>Method for transferring data in a multiprocessor computer system with crossbar interconnecting unit - http://www.google.it/patents/EP0923032A1?cl=en</ref><ref>Specification and Verification of the PowerScale Bus Arbitration Protocol: An Industrial Experiment with LOTOS, Chap. 2, Pag. 4 – ftp://ftp.inrialpes.fr/pub/vasy/publications/cadp/Chehaibar-Garavel-et-al-96.pdf</ref>.
Il limite maggiore di questi sistemi è il traffico e la larghezza di banda di memoria (quantità di dati al sec.). La banda può essere aumentata usando un largo canale dati, un crossbar dati, la [[:en:Interleaved memory|memory interleaving]] e la transazioni di dati fuori ordine (out of order data transaction). Il traffico può essere ridotto usando una cache ch agisce da filtro verso la memoria condivisa. La cache è quindi un elemento essenziale nei sistemi SMP con memoria condivisa (shared-memory). Nei sistemi multiprocessori con cache separate che condividono una memoria comune, uno stesso dato può essere memorizzato in più di una cache. Un problema di
==== Stati della cache ====
* <span style="color">'''M'''</span>=Modified (modificato) o <span style="color">'''D'''</span>=Dirty (sporco/alterato) o <span style="color">'''DE'''</span>=Dirty-Exclusive (sporco esclusivo) o <span style="color">'''EM'''</span>=Exclusive Modified (esclusivo modificato)
** modificato o sporco, cioè modificato solo in una cache - write-back in caso di rimpiazzo (replacement); il dato è memorizzato in una sola cache, ma il dato in memoria non è aggiornato (invalido);
* <span style="color">'''O'''</span>=Owner (proprietario/responsabile) o <span style="color">'''SD'''</span>=Shared Dirty (sporco condiviso) o <span style="color">'''M'''</span>=Shared Modified (sporco modificato) o <span style="color">'''T'''</span>=Tagged (etichettato/contrassegnato)
** modificato, potenzialmente condiviso, proprietario - write-back in caso di rimpiazzo; il dato può essere memorizzato in più di una cache, ma il dato in memoria non è aggiornato (invalido). Solamente una cache è "owner" (proprietario), le altre cache sono marcate "shared" (condivise). In caso di una richiesta di lettura sul bus, il dato viene fornito dall'owner anziché dalla memoria.
* <span style="color">'''E'''=</span>''Exclusive'' o <span style="color">'''R'''=</span>''Reserved'' o <span style="color">'''VE'''</span>=''Valid-Exclusive'' o <span style="color">'''EC'''</span>=''Exclusive Clean'' <span style="color">o '''Me'''</span>=''Exclusive''
** esclusivo o riservato o valido esclusivo o esclusivo pulito; il dato è memorizzato solo in una cache e ''clean'' (pulito, cioè valido) in memoria.
* <span style="color">'''S'''</span>=''Shared'' (condiviso) o <span style="color">'''V'''</span>=''Valid'' (valido) o <span style="color">'''SC'''</span>=''Shared Clean'' (condiviso pulito)
** Dato potenzialmente condiviso con altre cache. Il dato può essere clean o dirty. Il termine "clean" in SC è fuorviante perché può essere anche dirty (vedi [[Protocolli di coerenza della cache (esempi)#Protocollo Dragon (Xerox)|Protocollo Dragon]])
* <span style="color">'''I'''</span>=''Invalid''
** Linea di cache invalida. Se la linea di cache non è presente (tag non corrispondente) è equivalente a linea invalida, perciò dato invalido significa dato presente ma invalido oppure non presente in cache
* <span style="color">'''F'''</span>=''Forward'' (in avanti) o <span style="color">'''R'''</span>=''Recent'' (recente)
** stati addizionali del protocollo [[Protocolli di coerenza della cache (esempi)#Protocollo MESI|MESI]]. L'ultimo dato letto. È uno speciale stato "Valido" che è l'owner per ''dati condivisi non modificati'', usato in alcuni protocolli estesi di MESI (MERSI o R-MESI IBM<ref name="MERSI" /><ref>{{Cita pubblicazione|nome=Ravi Kumar|cognome=Arimilli|data=30 novembre 1999|titolo=Cache-coherency protocol with recently read state for data and instructions|numero=US5996049 A|accesso=28 febbraio 2017|url=http://www.google.com/patents/US5996049|nome2=John Steven|cognome2=Dodson|nome3=John Michael|cognome3=Kaiser}}</ref>, MESIF - Intel<ref name="Intel QuickPath">An Introduction to the Intel® QuickPath Interconnect - http://www.intel.ie/content/dam/doc/white-paper/quick-path-interconnect-introduction-paper.pdf</ref><ref>{{Cita pubblicazione|nome=Herbert H. J.|cognome=Hum|data=26 luglio 2005|titolo=Forward state for use in cache coherency in a multiprocessor system|numero=US6922756 B2|accesso=28 febbraio 2017|url=http://www.google.com/patents/US6922756|nome2=James R.|cognome2=Goodman}}</ref>). Lo stato R/F è usato per permettere l' "Intervention" quando il dato è "Valido" ma condiviso con le altre cache. Questa cache è responsabile per l'intervention (shared intervention). Su una richiesta di lettura del bus, il dato viene fornito da questa cache invece che dalla memoria. MERSI e MESIF sono lo stesso protocollo solo con una differente terminologia (F al posto di R). Qualche volta R è riferito anche come "Shared Last " - ultimo condiviso (S<sub>L</sub>)<ref name="POWER4 protocol" /><ref>BM PowerPC 476FP L2 Cache Core Databook - {{cita web |url=https://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/8D5342097498C81A852575C50078D867/$file/L2CacheController_v1.5_ext_Pub.pdf |titolo=Copia archiviata |accesso=1º novembre 2016 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20141218185642/https://www-01.ibm.com/chips/techlib/techlib.nsf/techdocs/8D5342097498C81A852575C50078D867/$file/L2CacheController_v1.5_ext_Pub.pdf |dataarchivio=18 dicembre 2014 }}</ref>. Lo stato R (Recent) è usato non solamente nel protocollo MERSI = R-MESI ma in diversi altri protocolli. Questo stato può essere usato in combinazione con altri stati. Per esempio [[Protocolli di coerenza della cache (esempi)#Protocollo RT-MESI|RT-MESI]], HR-MESI, HRT-MESI, [[Protocolli di coerenza della cache (esempi)#Protocollo HRT-ST-MESI|HRT-ST-MESI]]<ref name="HRT-MESI">Cache Ccoherency Protocol Including an HR State - IBM patent - https://www.google.com/patents/US6275908</ref><ref>{{Cita pubblicazione|nome=Ravi Kumar|cognome=Arimilli|data=25 dicembre 2001|titolo=Cache coherency protocol with tagged state for modified values|numero=US6334172 B1|accesso=28 febbraio 2017|url=http://www.google.com/patents/US6334172|nome2=John Steven|cognome2=Dodson|nome3=Jerry Don|cognome3=Lewis}}</ref>. Tutti i protocolli che usano questo stato saranno riferiti come R-MESI type.
* <span style="color">'''H'''</span>=''Hover'' - '''H-MESI''' (stato addizionale del protocollo MESI)<ref>{{Cita pubblicazione|nome=Ravi Kumar|cognome=Arimilli|data=Aug 14, 2001|titolo=Cache coherency protocol including an HR state|numero=US6275908 B1|accesso=28 febbraio 2017|url=http://www.google.com/patents/US6275908|nome2=John Steven|cognome2=Dodson|nome3=Jerry Don|cognome3=Lewis}}</ref>
** Lo stato Hover (H) (sospeso) permette a una cache di mantenere un indirizzo nella directory anche se il corrispondente valore della linea di cache è una copia invalida. Se il valore corrispondente appare sul bus (Tag dell'indirizzo coincidente) dovuto ad una "Read" o "Write" valida, il dato della linea di cache è aggiornato con una copia valida e il suo stato è cambiato in S. Questo stato può essere usato in combinazione con altri stati, per es. HR-MESI, HT-MESI, HRT-MESI, [[Protocolli di coerenza della cache (esempi)#Protocollo HRT-ST-MESI|HRT-ST-MESI]]<ref name="HRT-MESI" /><ref name="R-MESI">Cache-coherency protocol with recently read state for data and instructions - IBM patent - http://www.google.com/patents/US5996049</ref><ref name="RT-MESI">Cache Coherency Protocol with Tagged State for Modified Values - IBM patent - http://www.google.com/patents/US6334172</ref>
==== Interferenze tra Snoopy e
L'attività dello Snoopy richiede l'accesso alla Directory della cache e può essere in conflitto con gli accessi concorrenti del processore. Questa interferenza fa aumentare la latenza della cache.
Per ridurre o eliminare questa interferenze possono essere usate tre soluzioni:
* Cache multi-livello inclusive
* Cache
* Dual-
#
#
#
==== Operazioni di coerenza Snoopy ====
L'attività dello Snoopy richiede l'accesso alla Directory della cache e può essere in conflitto con gli accessi concorrenti del processore. Questa interferenza fa aumentare la latenza della cache. Per ridurre o eliminare questa interferenze possono essere usate tre soluzioni:
Line 341 ⟶ 295:
# Due o più livelli di cache '''''"inclusive"''''' riducono queste interferenze perché circa 85-90%<ref name="SMP analysis" /> degli accessi del processore (per i dati) è fatto al livello più basso di cache.
# Cache '''''"Separate"''''' Istruzioni e Dati riducono l'interferenza perché lo snoopy normalmente è fatto solamente sulla cache Dati (vedi [[#Write Policy|Write Policy]]), perciò i conflitti sulle Istruzioni vengono eliminati.
# Lo snoopy spende la maggior parte del suo tempo a monitorare un traffico parassita. Una "'''''dual-Port Directory'''''" (Directory con due porte) o "'''''dual-Cache'''''" (cache con due porte - Directory+Dati) o un "'''''dual-Directory'''''" (doppia Directory)<ref
Si distinguono tre operazioni: transazioni di bus, caratteristiche dei dati e operazioni di cache:
* '''Transazioni di bus''': le principali operazioni sono:
** [[#Write Through (scrittura passante)|Write Through]]: la linea di cache è aggiornata sia in cache che in MM o solo in MM (write no-allocate); semplice da implementare, alta occupazione di banda. Va bene per scritture singole.
Line 358 ⟶ 311:
** '''Intervention-broadcasting''': (Intervento con aggiornamento distribuito): in caso di una transazione di intervento, una cache con stato '''H''' ([[#H-MESI|H-MESI]]) aggiorna la sua copia invalida con il valore inviato sul bus e il suo stato è cambiato in '''S'''<ref name="R-MESI" />
** '''Write Invalidate vs broadcast: w'''rite Invalidate è migliore in caso di scritture multiple, tipicamente scritture parziali, fatte da un processore prima che la linea di cache sia letta da un altro processore. Write-broadcast (aggiornamento) è migliore quando si ha un produttore singolo a molti consumatori del dato, ma è peggiore quando una cache è aggiornata con un dato che non sarà più successivamente utilizzato (inutile aumento di traffico sul bus e aumento delle [[#Interferenze tra Snoopy e Attività del Processore|interferenze di cache]]). L'invalidazione è la soluzione comune.
* '''Caratteristiche dei dati''': ci sono tre caratteristiche dei dati di cache:
** '''Validità''': Qualsiasi linea di cache non invalida, cioè stati MOES / D-SD-R-V
** '''Esclusività''': il dato è valido solo su una cache (dato non condiviso) in stato '''M''' (D) o '''E''' (R), con la MM non aggiornata (dirty) in caso di '''M''' (D) e aggiornata (clean) in caso di '''E''' (R);
** '''Ownership - Proprietà'''<ref>Non deve essere confusa la definizione più restrittiva di "owner" data nel protocollo in MOESI con questa più generale definizione</ref>: la cache che è responsabile di fornire il dato richiesto in sostituzione della MM (Intervento). - Dipendente dal protocollo, la cache che deve fare l'intervento può essere '''S'''-'''E'''-'''M''' in MESI [[Protocolli di coerenza della cache (esempi)#Protocollo Illinois|Illinois]], o '''R'''/'''F'''-'''E'''-'''M''' in [[Protocolli di coerenza della cache (esempi)#Protocollo MERSI (IBM) / MESIF (Intel)|R-MESI type / MESIF]] o '''M''' (D) o '''O''' (SD) o anche '''E''' (R) (dipendente dall'implementazione) nel tipo MOESI, (es. [[AMD64]],<ref name="MOESI Sweazey" />, [[Protocolli di coerenza della cache (esempi)#Protocollo Bull HN ISI|Bull HN ISI]]<ref name="Bull HN ISI" /> - vedi operazione di "Read Miss" sotto).
* '''Operazioni di cache''': le operazioni delle cache sono:
** '''Read Hit:''' il dato è letto dalla cache. Lo stato rimane inalterato; poiché questa è una operazione ovvia, in seguito non sarà più considerata, anche nei diagrammi di transazione di stato
Line 405 ⟶ 356:
* [[Protocolli di coerenza della cache (esempi)#Protocollo MESI|MESI]] {{Spazi|64}} Pentium II<ref name="MESI">Pentium Pro and Pentium II System Architecture pg. 160 - Di T. Shanley - http://books.google.it/books?id=MLJClvCYh34C&pg=PA160&lpg=PA160&dq=Pentium+protocol+cache&source=bl&ots=gaOu-EvaTy&sig=QQEM1krp-H_0KUhi5Ti2bmxU2kU&hl=it&sa=X&ei=Zt6KT7icG8TE4gShzaDwCQ&ved=0CDcQ6AEwAg#v=onepage&q=Pentium%20protocol%20cache&f=false</ref>, PowerPC, Intel Harpertown (Xeon 5400)
* MOSI {{Spazi|63}} [[Protocolli di coerenza della cache (esempi)#Protocollo Berkeley (DEC)|Berkeley]]<ref name="Various protocols" />
* [[Protocolli di coerenza della cache (esempi)#Protocollo MOESI
{{spazi|79}} '''Terminologia usata'''
Line 422 ⟶ 373:
* [[Protocolli di coerenza della cache (esempi)#Protocollo RT-ST-MESI|RT-MESI]] {{spazi|57}} T=Tagged - IBM<ref name="RT-MESI" />
* [[Protocolli di coerenza della cache (esempi)#Protocollo RT-ST-MESI|HRT-ST-MESI]] {{spazi|49}} H=Hover, R=Recent,T=Tagged, ST=Shared-Tagged - IBM<ref name="HRT-MESI" /><ref name="RT-MESI" />
* Protocollo [[Protocolli di coerenza della cache (esempi)#Protocollo POWER4 IBM|POWER4 IBM]] {{spazi|31}} T-Mu-Me-M-S-S<sub>L</sub>-I (L2 sette stati)<ref name="POWER4 protocol" />
Line 438 ⟶ 388:
{{spazi|79}} <span style="color">'''I'''</span>=Invalido - (<span style="color">'''I'''</span>)
=== Directory-based - Message-passing ===
È noto che i [[#SMP - Symmetric Multiprocessor System|sistemi SMP]] hanno una limitata scalabilità. La memoria ''[[#Cache Multi-Banco e Multi-Porta|multi-banco]]'' e il ''crossbar dati''<ref name="Crossbar dati" /> permettono accessi paralleli alla memoria. L'uso di grandi cache riduce il traffico sul bus di sistema ma non le ''write invalidate'' (scrittura con invalidazione) o ''write-broadcast'' (scrittura con distribuzione). La maggiore limitazione è che l'indirizzo di memoria deve essere monitorato (snoopy) usando un unico bus.
Per superare questa limitazione, viene adottata una nuova architettura chiamata "'''''cc-NUMA '''''".
Line 448 ⟶ 395:
Il sistema cc-NUMA è un insieme di sistemi SMP chiamati "'''Nodi'''" connessi via una ''rete di connessione'' che può essere un ''link'' (collegamento) formato da un singolo o doppio anello bidirezionale o multi-anello, connessioni punto-punto<ref name="AMD Opteron" /><ref name="Intel QuickPath" /> o un mix di queste (vedi ad es. sistemi [[:en:IBM Power Systems|IBM Power Systems]]<ref name="POWER4 protocol" /><ref name="IBM POWER Systems">IBM POWER Systems Overview - https://computing.llnl.gov/tutorials/ibm_sp/</ref>), intercessione via bus (es. NUMAq<ref>SourceForge - http://lse.sourceforge.net/numa/faq/system_descriptions.html</ref>), ''crossbar'', ''segmented bus'' (bus segmentato - [[Non-uniform memory access|NUMA]] Bull HN ISI ex [[Honeywell]]<ref>Bull HN F. Zulian - A. Zulian patent - Computer system with a bus having a segmented structure - http://www.freepatentsonline.com/6314484.html</ref>), ''[[:en:Mesh networking|Mesh router]]'', ecc..
Esempi di interconnessione:
[[File:Double-reverse ring.svg|thumb|left|upright=1.2|Double-reverse ring]]
[[File:Segmented Bus.svg|thumb|right|upright=1.3|Segmented Bus]]
Line 455 ⟶ 401:
<blockquote class="toccolours" style="float: none;">
<span style="color"> {{spazi|2}} La caratteristica principale del sistema cc-NUMA è di avere un''''''unica memoria globale condivisa e distribuita in ciascun nodo'''''
</blockquote>
Line 468 ⟶ 414:
La differenza del tempo di accesso fra una memoria locale ed una remota può anche essere di un ordine di grandezza, in dipendenza del tipo di connessione (più veloce nel segmented bus, crossbar e interconnessione punto-punto, più lenta con la connessione ad anelli seriali).
==== Cache
Terminologia:
Line 505 ⟶ 450:
<blockquote class="toccolours" style="float: none;">
{{spazi|2}} * La '''cache remota''' memorizza i dati letti dalle memorie remote degli altri nodi.<br />
{{spazi|2}} * La '''directory della memoria locale''' tiene traccia dei dati e del loro stato, letti dalla propria memoria locale,
{{spazi|4}} che sono memorizzati nelle cache remote degli altri nodi<ref>SourceForge - http://lse.sourceforge.net/numa/faq/</ref>.
</blockquote>
Ci sono quattro possibili situazioni per un nodo:
Line 519 ⟶ 464:
===== Lettura della memoria locale =====
[[File:cc-NUMA Local Memory Read.svg|thumb|right|upright=1.2|cc-NUMA Local Memory Read and Invalidate]]
*Una transazione di lettura di memoria locale di uno stesso nodo è monitorata e gestita nello stesso modo come in un normale sistema SMP.
*L3 miss
**In caso di L1-L3 miss, la transazione è monitorata sul System Bus del proprio nodo da tutte le altre cache L3 e dalla "directory della memoria locale", in questo caso per verificare se il dato da leggere è presente nelle altre cache remote e in quali nodi. La directory della memoria locale è vista e gestita come una directory di un'extra cache e più precisamente come una "shared directory" (directory condivisa) di tutte le cache remote di tutti i nodi remoti. L'unica differenza rispetto alle cache L3 (formata da directory+dati) è che il campo dati e il "Tag" della cache non sono memorizzati nello stesso nodo della directory, ma distribuito sugli altri nodi. La comunicazione tra la directory della memoria locale e le cache remote è fatta tramite una connessione "Message-passing" (inviando un messaggio), punto-punto o distribuito usando il vettore "Indicator bit" (il campo dei bit indicatori dei nodi).
**In caso di stato '''E''' (esclusivo) nella directory della memoria locale, un messaggio è inviato all'unica cache remota del nodo dove il dato è memorizzato in attesa della risposta perché la cache potrebbe essere "Dirty".
***Se il dato è ''Dirty'', il dato è inviato indietro alla "home" e gestita come se provenisse da una cache locale con l'eccezione che lo "Shared-Dirty" non è permesso tra nodi nel protocollo tipo MOESI. Potrebbe essere permesso solo con protocollo tipo T-Mesi con l' "owner" solo nella "home" (migrazione del "Dirty-Owner" nella home) ma normalmente il "Dirty-intervention" e il "Shared-clean intervention" tra nodi non è usato (vedi ad es. [[Protocolli di coerenza della cache (esempi)#Protocollo POWER4 IBM|Protocollo POWER4 IBM]])
***Lo stato della cache remota e lo stato delle cache L1-L3 associate sono settate "Shared" e lo stato della directory della memoria locale è cambiato in '''S'''
**Se il dato è memorizzato in una cache L3 "owner" locale, il dato è fornito da questa cache (che può essere "shared-clean owner" o "dirty-owner")
**altrimenti dalla memoria locale
===== Scrittura della memoria locale =====
*Hit Shared in L3
**Se c'è hit '''S''' in L3 una transazione di "Invalida" è inviata sul bus del proprio nodo per invalidare tutte le altre copie. Se nella directory della memoria locale ci sono alcuni nodi con lo stato '''S''', una transazione di invalida è inviata, tramite l'indicatore di nodo della home directory, a ciascun nodo avente una copia
*Hit Esclusiva in L3
**La scrittura è fatta localmente in L1-L3 (per l'inclusività) come normalmente. Le cache sono settate (or rimangono) "Dirty"
*Miss
**Come con una "[[#Lettura della memoria locale|lettura della memoria locale miss]]" con un comando di invalida ([[#Write Allocate (scrittura con allocazione)|RWITM]]), poi come con una "write hit-esclusiva"
===== Lettura della memoria remota =====
[[File:cc-NUMA Remote Memory Read.svg|thumb|right|upright=1.2|cc-NUMA Remote Memory Read]]
*Miss
**Una transazione di lettura di memoria locale (per un dato remoto) è monitorata da tutte le cache L3 e dalla cache remota del proprio nodo.
**Se c'è una cache L3 "owner", il data è fornito da questa cache
**altrimenti se "hit" nella cache remota del nodo, il dato è fornito da questa cache
**altrimenti una richiesta di lettura remota è inviata sul nodo "home" del dato. La "home" gestisce questa richiesta nello stesso modo come per una richiesta interna. L'unica differenza è che il dato è inviato invece al nodo richiedente. La cache richiedente è settata "Shared"
***In caso di dato "Dirty" in un altro nodo differente dalla "home", la "home" richiede il dato a questo nodo, come descritto nella operazione di [[#Lettura della memoria locale|"lettura della memoria locale miss"]] nel caso di stato '''E''' nella directory dalla memoria locale, poi il dato è inviato al nodo richiedente. Esempio: il nodo "A" richiede il dato alla "home" "B". "B" richiede il dato al nodo "C" che ha il dato "Dirty". Il nodo "C" invia il dato alla "home" nodo "B" (copy back), "B" lo rispedisce al nodo "A". I nodi "A" e "C" sono settati "Shared" come pure la directory dell memoria locale.
***Ci sono altre possibili varianti: per es. il nodo "C" manda il dato al nodo "B" (home) e simultaneamente al nodo richiedente "A" (vedi ''DASH''<ref name="DASH" /> e ''Intel QuickPath" Interconnect''<ref name="Intel QuickPath" />).
===== Scrittura della memoria remota =====
*Hit "Exclusive" in L3
**Il dato è processato localmente come in normale [[#Scrittura della memoria locale|"scrittura hit-esclusiva locale"]]
**Una transazione di invalida è mandata alla "home" del dato e resta in attesa per il consenso di scrittura. La "home" rinvia la transazione di invalidazione a tutti i nodi aventi il dato e poi invia il consenso di scrittura al nodo richiedente. Due scritture simultanee su differenti nodi sono così sincronizzate.
*Miss
**Come in una [[#Lettura della memoria remota|"Lettura remota miss"]] con un comando di invalida ([[#Write Allocate (scrittura con allocazione)|RWITM]]), poi come in una [[#Scrittura della memoria locale|"scrittura hit-esclusiva locale"]]
=== Shared cache ===
Tipicamente usato nei sistemi Multi-core per la coerenza e per riduzione dei costi (in termini di spazio).
==== Sistemi [[
Il ''multi-core'' ("multipli processori integrati"), denominato anche ''chip multiprocessors'', ''multicore chips'', e ''many-core chips'', è uno speciale genere di multiprocessore dove tutti i processori sono sullo stesso [[Circuito integrato|chip]] MCM ([[Multi-Chip Module]])<ref>http://scholar.google.it/scholar_url?url=http://minds.wisconsin.edu/bitstream/handle/1793/60554/TR1593.pdf%3Fsequenc&hl=it&sa=X&scisig=AAGBfm3Tfz0tL0HBvHhv_6mCWgvMIZhsxg&oi=scholarr&ei=pXGmVPnBAsn7Uti3g7AL&ved=0CCEQgAMoADAA</ref><ref>http://scholar.google.it/scholar_url?url=http://www.itu.dk/people/jhh/thesis/references/36%2520-%2520Chip%2520Makers%2520Turn%2520to%2520Multicore%2520Processors.pdf&hl=it&sa=X&scisig=AAGBfm26PHbY3VJRZqQtLux3ac90MmK1rQ&oi=scholarr&ei=pXGmVPnBAsn7Uti3g7AL&ved=0CCIQgAMoATAA</ref>
[[File:L2 Shared Cache.svg|thumb|left|upright=.9|L2 Shared Cache]]
[[File:L3 Shared Cache.svg|thumb|right|upright=.9|L3 Shared Cache]]
Line 599 ⟶ 524:
===== cc-NUMA in Sistemi [[Multi-core]] =====
Sistemi Multi-core possono essere connessi assieme per formare un sistema NUMA.
La coerenza è garantita tramite message-passing tra le L3 shared-cache dei vari nodi (vedi ad es.Intel Nehalem<ref name="Nehalem2" />, [[AMD Opteron]]<ref name="AMD Opteron">AMD Opteron Shared Memory MP Systems - http://www.cse.wustl.edu/~roger/569M.s09/28_AMD_Hammer_MP_HC_v8.pdf</ref><ref name="Intel QuickPath" /><ref>Cache Coherence Techniques for Multicore Processors - Michael R. Marty - http://research.cs.wisc.edu/multifacet/theses/michael_marty_phd.pdf</ref>, MCM Interconnections [[POWER5|POWER5 IBM]]<ref name="POWER4" /><ref name="IBM POWER Systems" /><ref>Of NUMA on POWER7 in IBM - http://www-03.ibm.com/systems/resources/pwrsysperf_P7NUMA.pdf</ref>, ecc.)
== Indirizzamento Virtuale, Fisico e Pseudo Virtuale ==
=== MMU ===
L' '''[[Memory management unit|MMU]]''' (Memory Management Unit) è l'unità di gestione degli accessi di MM. Le funzioni principali sono:
* Traduzione degli indirizzi da virtuali in fisici
* Gestione dei miss del TLB
* Controllo dei permessi di accesso alla linea di cache e alla memoria:
: 1. - Supervisor/User
: 2. - protezione delle scritture
=== TLB ===
La [[memoria virtuale]] è lo spazio visto da un processo. Generalmente questo spazio è molto più grande della memoria fisica. Questo spazio è segmentato in pagine di dimensione prefissata. La ''[[page table]]'' (tabella delle pagine), generalmente caricata in memoria, tiene traccia di dove le pagine virtuali vengono caricate nella memoria fisica. Il '''TLB''' ([[Translation Lookaside Buffer]] - memoria di traduzione a lato) o [[page table|Page Table cache]] o ''page-translation caches'' - cache di traduzione delle pagine) è una cache della [[page table|Page Table]], cioè solamente un sottoinsieme del suo contenuto è memorizzato nel TLB. Il TLB, come per la cache di memoria può essere "separato" ''Istruzioni'' (ITLB) e ''Dati'' (DTLB) o "unificato" , come pure essere Direct Mapped o Set Associative o Fully Associative. Generalmente l'organizzazione segue l'organizzazione della cache associata, ma può essere organizzata in modo indipendente da questa (vedi [[Translation Lookaside Buffer|TLB]]). Come per la cache, per aumentarne l'efficienza può essere usato anche un secondo livello di TLB aggiungendo un L2 TLB (es. Intel Nehalem<ref name="Nehalem2" />).
Line 627 ⟶ 544:
Ci sono pro e contro per entrambe le implementazioni, ma generalmente l'indirizzamento fisico è quello normalmente usato.
=== Indirizzamento
In fig. sotto un esempio di indirizzo virtuale con 4 GB di spazio virtuale, 4 MB cache, 4 KB di dimensione di pagina e 256 B di dimensione della linea di cache.
[[File:Virtual Space Address Structure.svg|thumb|left|upright=1.9|Virtual Space Address Structure]]
[[File:Virtual Addressing.svg|thumb|right|upright=2.3|Virtual Addressing]]
Line 643 ⟶ 558:
Ci sono tre possibili soluzioni:
# Flushing (letteralmente sciacquatura = invalidazione) della cache ad ogni [[context switch]] (cambiamento di contesto),
# Aggiungere in cache un '''ID''' (ASID - Address Space IDentifier) o un '''Context Number''' (CTX) o '''Process Number''' (identificatore dello spazio indirizzi, numero di contesto o numero di processo), per distinguere i vari processi/contesti<ref>High-speed memory and memory management system - Sun Microsystems - http://www.google.com.tr/patents/US4550368</ref>.
# Aggiungere in cache il corrispondente indirizzo fisico che deve essere confrontato con l'indirizzo fisico ottenuto dal [[Translation Lookaside Buffer|TLB]] (acceduto in parallelo - "look aside" - visto a lato), per verificare la corretta associazione virtuale-fisica dell'indirizzo (indirizzamento '''''Virtual Index - Physical TAG''''' - VIPT).
===== Problema di coerenza =====
Poiché differenti indirizzi logici di differenti contesti possono riferisci allo stesso indirizzo fisico (dati condivisi), più di una posizione di memoria potrebbe memorizzare lo stesso dato, causando un problema di coerenza in caso di scrittura. Solamente una posizione di memoria sarebbe aggiornata.
Ci sono due soluzioni principali<ref>Virtual-Address Caches - http://www.ece.umd.edu/class/enee646.F2007/Cekleov1.pdf</ref>
# '''Prevenzione dei sinonimi''' (synonym prevention)
#: - Tramite il software prevenire od evitate i sinonimi
# '''Rilevamento dinamico dei sinonimi''' (dynamic synonym detection)
#: - Supporto hardware per aiutare il software di tutti o del principale "task" (programma) di mantenimento della
<u>In ogni caso la cache deve sempre essere invalidata quando la mappatura virtuale-fisica viene cambiata, per es. nel caso di rimpiazzo della pagina - [[page replacement]]</u>.
=== Indirizzamento
[[File:Physical Addressing.svg|thumb|right|upright=2.0|Physical Addressing]]
Nell'indirizzamento fisico, per prima cosa viene indirizzato il [[Translation Lookaside Buffer|TLB]] (*) usando l'indirizzo virtuale '''L-MSB''' + '''LPA''', poi l'indirizzo fisico ('''PPA''') ottenuto dal [[Translation Lookaside Buffer|TLB]] più PPA Offset è usato per indirizzare la cache. Solamente la parte dell'indirizzo virtuale che differisce dall'indirizzo fisico è convertita, cioè "L.MSB" e "LPA".
Line 673 ⟶ 583:
(*) - All'inizio la dimensione della cache era piccola ed uguale alla dimensione della pagina, perciò "index" (l'indice) virtuale e fisico erano coincidenti e il TLB era acceduto in parallelo (a lato - look aside, da cui il nome) solamente per verificare gli MSB, come nell'[[#Indirizzamento Virtuale|indirizzamento virtuale]].
=== Indirizzamento
*Soluzione usata nei sistemi [[#en:Honeywell|Honeywell]] [[#en:Groupe Bull|Bull]] Italia<ref name="Pseudo virtual add.">Cache memory having pseudo virtual addressing - Honeywell Bull Italia - https://www.google.com/patents/US5165028</ref> - F. Zulian - US Patent N. 5.165.028
*Questa soluzione offre tutti i vantaggi di entrambe le precedenti soluzioni.
<blockquote class="toccolours" style="float: none;">
Line 706 ⟶ 615:
== Note ==
<references/>
== Bibliografia ==
* {{en}} Handy, Jim. ''The Cache Memory Book''. Academic Press, Inc., 1998. ISBN 0-12-322980-4
== Voci correlate ==
* [[Cache]]
* [[ccNUMA]]
| |||