EntrataCache associativa. Cache associativa
· cache con mappatura diretta (placement);
· cache completamente associativa;
· cache associativa multipla o parzialmente associativa.
Cache mappata diretta(alloggio) è il massimo
tipo semplice respingente. L'indirizzo di memoria identifica univocamente la stringa
cache in cui verrà inserito il blocco di informazioni. Allo stesso tempo, è preferibile
Si presuppone che la RAM sia divisa in blocchi e ciascuno
a quale blocco nel buffer viene allocata solo una riga. Questo è un metodo di visualizzazione semplice ed economico da implementare. Il suo principale svantaggio è la rigida assegnazione di una riga nella cache a determinati blocchi OP. Pertanto, se un programma alterna l'accesso alle parole da due blocchi diversi mappati sulla stessa linea della cache, quella linea verrà costantemente aggiornata e la probabilità di un successo sarà bassa.
Cache completamente mappata permette di superare lo svantaggio del direct, permettendo il caricamento di qualsiasi blocco OP in qualsiasi linea della cache. La logica di controllo assegna due campi nell'indirizzo OP: un campo tag e un campo parola. Il campo tag corrisponde all'indirizzo del blocco OP. Per verificare che una copia di un blocco sia nella cache, la logica di gestione della cache deve controllare simultaneamente i tag di tutte le righe per vedere se corrispondono al campo del tag dell'indirizzo. La mappatura associativa fornisce flessibilità quando si seleziona una riga per un blocco appena scritto. Lo svantaggio fondamentale di questo metodo è la necessità di utilizzare una costosa memoria associativa.
Tipo multi-associativo o tipo di mappatura parzialmente associativa – Questo è uno dei possibili compromessi, che unisce i vantaggi dei metodi diretti e associativi. La memoria cache (sia tag che dati) è divisa in una serie di moduli. La dipendenza tra l'unità ed i blocchi OP è stretta come nel caso della mappatura diretta. Ma il posizionamento dei blocchi lungo le linee del modulo è arbitrario e viene utilizzato il principio associativo per trovare la linea desiderata all'interno del modulo. Questo metodo di visualizzazione è ampiamente utilizzato nei moderni microprocessori.
Mappatura dei settori OP nella memoria cache.
Questo tipo di mappatura è utilizzata in tutti i computer moderni e consiste nel fatto che l'intero OP viene suddiviso in settori costituiti da un numero fisso di blocchi consecutivi. Anche la memoria cache è divisa in settori contenenti lo stesso numero di righe. La posizione dei blocchi nel settore OP e nel settore cache è completamente identica. La mappatura di un settore nella memoria cache viene eseguita in modo associativo; qualsiasi settore dell'OP può essere posizionato in qualsiasi settore della cache. Pertanto, durante il funzionamento, l'ALU si rivolge all'OP alla ricerca del comando successivo, di conseguenza, un intero settore di informazioni dall'OP viene caricato nella cache (se non è presente alcun blocco contenente questo comando) e secondo il principio di località, grazie a ciò, aumenta notevolmente le prestazioni del sistema.
Modello di cache gerarchica
In genere, la memoria cache ha un'architettura multilivello. Ad esempio, su un computer con 32 KB di cache interna (nel core della CPU) e 1 MB di cache esterna (nel case della CPU o nella scheda madre), la prima sarebbe considerata cache di livello 1 (L1) e la seconda sarebbe considerata di livello 2 cache.esimo livello (L2). Nei moderni sistemi server, il numero di livelli di cache può arrivare fino a quattro, sebbene quello più comunemente utilizzato sia uno schema a due o tre livelli.
In alcune architetture di processori, la cache di livello 1 è divisa in una cache di istruzioni (InstructionCache, I-cache) e una cache di dati (DataCache, D-cache), e non necessariamente della stessa dimensione. Dal punto di vista della progettazione del circuito, è più semplice ed economico progettare I-cache e D-cache separate: il recupero dei comandi viene effettuato da I-box e il campionamento dei dati viene effettuato da E-box e F-box, sebbene in entrambi i casi vengono utilizzate la A-box e la C-box. Tutti questi blocchi sono grandi e fornire loro un accesso simultaneo e veloce a una cache è problematico. Inoltre, ciò richiederebbe inevitabilmente un aumento del numero delle porte di accesso, il che complicherebbe anche il compito di progettazione.
Poiché I-cache e D-cache devono fornire latenze di accesso molto basse (questo vale per qualsiasi cache L1), devono sacrificare la loro dimensione, solitamente compresa tra 16 e 32 KB. Dopotutto, minore è la dimensione della cache, più facile sarà ottenere basse latenze di accesso.
La cache di livello 2 è solitamente unificata, ovvero può contenere sia istruzioni che dati. Se è integrato nel core della CPU, parlano di S-cache (SecondaryCache, cache secondaria), altrimenti di B-cache (BackupCache, cache di backup). Nelle moderne CPU dei server, la dimensione della S-cache varia da uno a diversi megabyte e della aB-cache - fino a 64 MB. Se il design della CPU include una cache di livello 3 incorporata, viene chiamata T-cache (TernaryCache). Di norma, ogni livello successivo di memoria cache è più lento, ma di dimensioni maggiori rispetto al precedente. Se il sistema dispone di una cache B (come ultimo livello del modello di memoria cache), può essere controllata sia dalla CPU che dal set logico del sistema.
Se al momento dell'esecuzione di un determinato comando non sono presenti dati nei registri, verranno richiesti dal livello di memoria cache più vicino, ad es. dalla D-cache. Se non sono nella D-Cache, la richiesta viene inviata alla S-cache, ecc. Nel peggiore dei casi, i dati verranno consegnati direttamente dalla memoria. Tuttavia, è possibile uno scenario ancora più triste, quando il sottosistema di gestione della memoria virtuale sistema operativo(OS) riesce a inserirli nel file di scambio disco rigido. In caso di consegna da RAM la perdita di tempo per ottenere i dati necessari può variare da decine a centinaia di cicli della CPU, e se i dati sono sul disco rigido si può già parlare di milioni di cicli.
Associatività della cache
Una delle caratteristiche fondamentali della memoria cache, il livello di associatività, riflette la sua segmentazione logica. Il fatto è che la ricerca sequenziale in tutte le linee della cache alla ricerca dei dati necessari richiederebbe dozzine di cicli di clock e annullerebbe tutti i vantaggi derivanti dall'utilizzo della memoria integrata nella CPU. Pertanto, le celle RAM sono strettamente legate alle linee della cache (ogni linea può contenere dati da un insieme fisso di indirizzi), il che riduce significativamente il tempo di ricerca. A ciascuna posizione RAM può essere associata più di una riga di cache: ad esempio, n-waysetassociative significa che le informazioni su un determinato indirizzo RAM possono essere archiviate in n posizioni cache.
La selezione di una località può essere effettuata utilizzando diversi algoritmi, tra i quali i principi di sostituzione più utilizzati sono LRU (LeastRecentlyUsed, viene sostituito il record richiesto più recentemente) e LFU (LeastFrequentlyUsed, il record richiesto meno frequentemente), anche se sono previste delle modifiche di questi principi. Ad esempio, la memoria cache completamente associativa, in cui le informazioni situate in un indirizzo arbitrario nella RAM possono essere posizionate in una riga arbitraria. Un'altra opzione è la mappatura diretta, in cui le informazioni che si trovano in un indirizzo arbitrario nella RAM possono essere collocate in una sola posizione nella memoria cache. Naturalmente, questa opzione offre le prestazioni più elevate, poiché quando verifica la disponibilità delle informazioni, il controller dovrà "guardare" solo una riga della cache, ma è anche la meno efficace, poiché il controller non sceglierà la posizione "ottimale" quando si scrive. A parità di dimensione della cache, lo schema completamente associativo sarà il meno veloce, ma il più efficiente.
In pratica si trova una cache completamente associativa, ma, di regola, ha dimensioni molto ridotte. Ad esempio, la CPU Cyrix 6x86 utilizzava 256 byte di questa cache di istruzioni prima della cache L1 unificata da 16 o 64 KB. Spesso, uno schema completamente associativo viene utilizzato durante la progettazione di TLB (di cui parleremo più avanti), cache di indirizzi di ramo, buffer di lettura-scrittura, ecc. Di norma, i livelli di associatività di I-cache e D-cache sono piuttosto bassi (fino a a quattro canali) - il loro aumento non è pratico perché comporta maggiori ritardi di accesso e, in definitiva, ha un impatto negativo sulle prestazioni. Come compensazione, l'associatività della S-cache viene aumentata (solitamente fino a 16 canali), poiché i ritardi nell'accesso a questa cache non sono importanti. Ad esempio, secondo i risultati di studi sui problemi interi utilizzati di frequente, la D-cache a quattro canali da 16 KB dell'Intel Pentium III era sufficiente per coprire circa il 93% delle richieste e la I-cache a quattro canali da 16 KB era sufficiente per coprire il 99% delle richieste.
Riga della cache e dimensione del tag
Una caratteristica importante della memoria cache è la dimensione della riga. In genere, esiste un record di indirizzo per riga (chiamato tag), che indica a quale indirizzo nella RAM corrisponde la riga. Ovviamente, numerare i singoli byte non è pratico, poiché in questo caso il volume delle informazioni di servizio nella cache sarà molte volte maggiore del volume dei dati stessi. Pertanto, un tag di solito si basa su una riga, che di solito ha una dimensione di 32 o 64 byte (il massimo effettivo è 1024 byte) ed equivale a quattro (a volte otto) larghezze dell'FSB. Inoltre, ogni riga della cache è accompagnata da alcune informazioni per garantire la tolleranza agli errori: uno o più bit di parità o otto o più byte di rilevamento e correzione degli errori (ECC, ErrorCheckingandCorrecting), sebbene le soluzioni di massa spesso non ne utilizzino né l'uno né l'altro.
La dimensione di un tag di cache dipende da tre fattori principali: la dimensione della cache, la quantità massima di RAM memorizzabile nella cache e l'associatività della cache. Matematicamente, questa dimensione è calcolata dalla formula:
Stag=log2(Smem*A/Scache),
dove Stag è la dimensione di un tag della cache, in bit; Smem: quantità massima di RAM memorizzata nella cache, in byte; Scache: dimensione della memoria cache, in byte; A - associatività della cache, in canali.
Ciò significa che un sistema con 1 GB di RAM e 1 MB di cache associativa a doppio percorso richiederebbe 11 bit per tag. È interessante notare che la dimensione della riga della cache stessa non influisce in alcun modo sulla dimensione del tag, ma influisce inversamente sul numero di tag. Dovrebbe essere chiaro che non ha senso rendere la dimensione di una linea di cache inferiore alla larghezza del bus dati di sistema, ma aumentare la dimensione molte volte porterà a un eccessivo intasamento della memoria cache con informazioni non necessarie e un carico eccessivo su il bus di sistema e il bus di memoria. Inoltre, la quantità massima di memoria cache che può essere memorizzata nella cache non deve necessariamente corrispondere alla quantità massima possibile di RAM installata nel sistema. Se si verifica una situazione in cui è presente più RAM di quella che può essere memorizzata nella cache, la memoria cache conterrà le informazioni solo dal segmento inferiore della RAM. Questa era esattamente la situazione con la piattaforma Socket7/Super7. I chipset per questa piattaforma consentivano l'utilizzo di grandi quantità di RAM (da 256 MB a 1 GB), mentre il volume della cache era spesso limitato ai primi 64 MB (stiamo parlando della B-cache situata sulla scheda madre) a causa dell'utilizzo di economici chip SRAM tag da 8 bit (di cui 2 bit erano riservati per indicatori della validità e della modifica di una linea). Ciò ha portato ad un notevole calo delle prestazioni.
Perché vediamo un aumento costante delle prestazioni dei programmi a thread singolo? IN al momento Siamo in quella fase di sviluppo delle tecnologie dei microprocessori in cui l'aumento della velocità delle applicazioni a thread singolo dipende solo dalla memoria. Il numero di core cresce, ma la frequenza è fissa a 4 GHz e non fornisce alcun aumento di prestazioni.
La velocità e la frequenza del funzionamento della memoria sono la cosa principale attraverso la quale otteniamo "la nostra fetta di torta gratuita" (link). Questo è il motivo per cui è importante utilizzare la memoria nel modo più efficiente possibile e soprattutto veloce come una cache. Per ottimizzare un programma per un computer specifico, è utile conoscere le caratteristiche della cache del processore: numero di livelli, dimensione, lunghezza della riga. Ciò è particolarmente importante nel codice ad alte prestazioni: kernel di sistema, librerie matematiche.
Come determinare le caratteristiche di una cache automatica? (naturalmente cpuinfo non è considerato parsed, se non altro perché alla fine vorremmo ottenere un algoritmo che possa essere facilmente implementato in altri sistemi operativi. Comodo, no?) Questo è esattamente ciò che faremo ora.
Una piccola teoria
Attualmente esistono tre tipi di memoria cache ampiamente utilizzati: cache a mappatura diretta, cache associativa e cache multi-associativa.Cache di mappatura diretta
- una determinata linea di RAM può essere mappata su una singola linea di cache, ma molte possibili linee di RAM possono essere mappate su ciascuna linea di cache.Cache completamente associativa
- qualsiasi linea RAM può essere mappata su qualsiasi linea cache.Cache multi-associativa
- La memoria cache è divisa in diversi "banchi", ciascuno dei quali funziona come una cache a mappatura diretta, in modo che una linea RAM possa essere mappata non su una singola possibile voce di cache (come sarebbe il caso in un caso a mappatura diretta ), ma ad una delle numerose banche ; La selezione della banca viene eseguita in base all'LRU o ad altro meccanismo per ciascuna riga inserita nella cache.LRU - eliminazione della linea “inutilizzata da più tempo”, cache di memoria.
Idea
Per determinare il numero di livelli di cache, è necessario considerare l'ordine di accessi alla memoria in cui la transizione sarà chiaramente visibile. Diversi livelli di cache differiscono principalmente nella velocità di risposta della memoria. In caso di perdita della cache, la cache L1 cercherà i dati nei seguenti livelli di memoria e, se la dimensione dei dati è maggiore di L1 e inferiore a L2, la velocità di risposta della memoria sarà la velocità di risposta L2. L’affermazione precedente vale anche in casi generali.È chiaro che dobbiamo selezionare un test in cui vedremo chiaramente i fallimenti della cache e testarlo su varie dimensioni di dati.
Conoscendo la logica delle cache set-associative che operano utilizzando l'algoritmo LRU, non è difficile trovare un algoritmo in cui la cache “cade”, niente di complicato, passando attraverso la linea. Il criterio di efficienza sarà il tempo di un accesso alla memoria. Naturalmente è necessario accedere in sequenza a tutti gli elementi della linea, ripetendolo più volte per ottenere una media del risultato. Ad esempio, potrebbero esserci casi in cui una riga entra nella cache, ma per il primo passaggio carichiamo la riga dalla RAM e quindi otteniamo un tempo del tutto inadeguato.
Mi piacerebbe vedere qualcosa come dei passi che camminano lungo le linee lunghezze diverse. Per determinare la natura dei passaggi, si consideri un esempio di passaggio di linea per una cache diretta e associativa; il caso con una cache set-associativa sarà una media tra una cache a mappatura diretta e una cache associativa.
Cache associativa
Una volta che la dimensione dei dati supera la dimensione della cache,
Una cache completamente associativa fallisce ad ogni accesso alla memoria.
Cache diretta
Diamo un'occhiata alle diverse dimensioni delle linee. - mostra il numero massimo di miss che il processore spenderà per accedere agli elementi dell'array la prossima volta che passa attraverso la linea.
Come puoi vedere, il tempo di accesso alla memoria non aumenta bruscamente, ma all'aumentare del volume dei dati. Una volta che la dimensione dei dati supera la dimensione della cache, si verificheranno errori ad ogni accesso alla memoria.
Pertanto per una cache associativa il passo sarà verticale, mentre per una cache diretta aumenterà gradualmente fino a raddoppiare la dimensione della cache. Una cache multi-associativa sarà un caso medio, un “bump”, se non altro perché il tempo di accesso non può essere migliore di quello diretto.
Se parliamo di memoria, la più veloce è la cache, seguita dalla memoria operativa, la più lenta è lo swap, non ne parleremo in futuro. A loro volta, diversi livelli di cache (di norma, oggi i processori hanno 2-3 livelli di cache) velocità diversa risposta della memoria: maggiore è il livello, minore è la velocità di risposta. Pertanto, se una riga viene posizionata nella cache di primo livello (che, tra l'altro, è completamente associativa), il tempo di risposta sarà inferiore rispetto a quello di una riga significativamente più grande della dimensione della cache di primo livello. Pertanto, sul grafico del tempo di risposta della memoria rispetto alla dimensione della linea ci saranno diversi plateau: un plateau* di risposta della memoria e plateau causati da diversi livelli di cache.
*Plateau della funzione - ( i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Iniziamo l'implementazione
Per l'implementazione utilizzeremo C (ANSI C99).Il codice è stato scritto velocemente, il solito passaggio su righe di diversa lunghezza, inferiore a 10 MB, eseguito più volte. (Presenteremo piccole parti del programma che portano un carico semantico).
Per (i = 0; i< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
Guardiamo il grafico e vediamo un grande passo. Ma in teoria tutto funziona bene. Pertanto, è necessario capire: perché sta succedendo questo? E come risolverlo?
Ovviamente questo può accadere per due ragioni: o il processore non ha una cache di memoria, oppure il processore è così bravo a indovinare gli accessi alla memoria. Poiché la prima opzione è più vicina alla fantascienza, la ragione di tutto è una buona previsione delle chiamate.
Il fatto è che oggi, lungi dall'essere processori di fascia alta, oltre al principio di località spaziale, prevedono anche progressione aritmetica in ordine di accesso alla memoria. Pertanto è necessario randomizzare gli accessi alla memoria.
La lunghezza dell'array randomizzato dovrebbe essere paragonabile alla lunghezza della stringa principale per eliminare l'elevata granularità delle chiamate e la lunghezza dell'array non dovrebbe essere una potenza di due, per questo motivo si sono verificate "sovrapposizioni" - che potrebbe risultare in valori anomali. È meglio impostare la costante di granularità, anche se la granularità è un numero primo, in modo da evitare gli effetti delle sovrapposizioni. E la lunghezza di un array randomizzato è una funzione della lunghezza della stringa.
per (i = 0; i< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Dopo di che abbiamo sorpreso il tanto atteso “quadro” di cui abbiamo parlato all'inizio.
Il programma è diviso in 2 parti: test ed elaborazione dati. Sta a te decidere se scrivere uno script in 3 righe per eseguirlo o eseguirlo 2 volte manualmente.
Elencare il size.file su Linux
#includere
Elenco delle dimensioni dei file.da Windows
#includere
altrimenti k += 4*1024;
) restituisce 0; )
In generale, penso che tutto sia chiaro, ma vorrei chiarire alcuni punti.
L'array A è dichiarato volatile: questa direttiva ci garantisce che sarà sempre possibile accedere all'array A, ovvero non verrà "tagliato" né dall'ottimizzatore né dal compilatore. Vale anche la pena ricordare che l'intero carico computazionale viene eseguito prima che venga misurato il tempo, il che ci consente di ridurre l'influenza di fondo.
Il file viene tradotto in assembler su Ubuntu 12.04 e il compilatore gcc 4.6: i cicli vengono salvati.Troviamo tutti i punti in cui la derivata seconda è maggiore di zero (con qualche errore perché la derivata seconda, oltre ad essere calcolata numericamente, è molto rumorosa). Impostiamo la funzione in base al segno della derivata seconda della funzione sulla dimensione della cache. La funzione assume valore 1 nei punti in cui il segno della derivata seconda è maggiore di zero, e zero se il segno della derivata seconda è minore o uguale a zero.
I punti di “decollo” sono l’inizio di ogni passaggio. Inoltre, prima di elaborare i dati, è necessario rimuovere i singoli valori anomali, che non modificano il significato dei dati, ma creano un notevole rumore.
Elenco del file data_pr.c
#includere
altrimenti der_2[i] = 0;
//combina per (i = 0; i
TestPer ogni test verranno indicati CPU/SO/versione kernel/compilatore/chiavi di compilazione.
CPU Intel Pentium P6100 @2.00GHz / Ubuntu 12.04 / 3.2.0-27-generic / gcc -Wall -O3 size.c -lrt
L1 = 0,05 MB- L2 = 0,2 MB L3 = 2,7 MB Non elencherò tutto
buone prove
, parliamo meglio di "Rake"Parliamo di "rastrello"
Il rake è stato scoperto durante l'elaborazione dei dati su un processore server Intel Xeon 2.4/L2 = 512 kb/Windows Server 2008
Il problema risiede nel piccolo numero di punti che rientrano nell'intervallo di raggiungimento del plateau, di conseguenza il salto nella derivata seconda è impercettibile e viene considerato rumore;
È possibile risolvere questo problema utilizzando il metodo dei minimi quadrati o eseguire test identificando le zone di plateau.
- Vorrei sentire i vostri suggerimenti per risolvere questo problema.
- Riferimenti
Makarov A.V. Architettura del calcolatore e programmazione a basso livello.
Ulrich Drepper Quello che ogni programmatore dovrebbe sapere sulla memoria
Gli sviluppatori di cache hanno dovuto affrontare il problema che potenzialmente qualsiasi cella nell'enorme memoria principale poteva finire nella cache. Se l'insieme di dati utilizzato da un programma è sufficientemente grande, ciò significa che molte parti della memoria principale competeranno per ciascuna posizione della cache. Come riportato in precedenza, non è raro che il rapporto tra cache e memoria principale sia compreso tra 1 e 1000. 3.3.1 Associatività (Sarebbe possibile implementare una cache in cui ciascuna riga della cache possa memorizzare una copia di qualsiasi posizione di memoria. Si chiama). Per accedere a una linea di cache, il core del processore dovrebbe confrontare i tag di ciascuna linea di cache con il tag dell'indirizzo richiesto. Il tag dovrà memorizzare l'intero indirizzo, al quale non verrà assegnato un offset nella riga della cache (questo significa che il valore di S riportato nella figura del paragrafo 3.2 sarà zero).
Esistono cache implementate in questo modo, ma uno sguardo alla dimensione delle cache L2 attualmente in uso mostra che ciò non è pratico. Tieni presente che una cache da 4 MB con linee di cache da 64 B avrà 65.536 voci. Per ottenere prestazioni adeguate, la logica della cache deve essere in grado, nell'arco di pochi cicli, di selezionare tra tutte queste voci quella che corrisponde a un dato tag. I costi per l’attuazione di un simile schema sarebbero enormi.
Figura 3.5: Rappresentazione schematica di una memoria cache completamente associativa
Ogni riga della cache richiede un comparatore per eseguire un confronto tra tag di grandi dimensioni(notare che S è zero). La lettera accanto a ciascuna connessione indica la larghezza della connessione in bit. Se non viene specificato nulla, la larghezza della connessione è di un bit. Ciascun comparatore deve confrontare due valori, ciascuno dei quali è largo T bit. Quindi, in base al risultato, il contenuto della corrispondente riga della cache dovrebbe essere recuperato e reso disponibile. Per fare ciò, è necessario combinare tanti set di linee dati O quanti sono i bucket di cache. Il numero di transistor necessari per implementare un comparatore sarà elevato, in parte perché il comparatore deve funzionare molto rapidamente. Non è possibile utilizzare un comparatore iterativo. L'unico modo per risparmiare sul numero di comparatori è ridurne il numero utilizzando il confronto iterativo dei tag. Questo non è adatto per lo stesso motivo per cui i comparatori iterativi non sono adatti: richiederebbe troppo tempo.
Una cache completamente associativa è pratica per cache di piccole dimensioni (come la cache TLB in alcuni Processori Intelè completamente associativo), ma questa cache deve essere piccola, davvero piccola. Stiamo parlando di un massimo di diverse decine di record.
Per la cache L1i, la cache L1d e la cache superiore alto livelloè necessario un approccio diverso. Tutto quello che puoi fare è restringere la ricerca. Nel caso più estremo, ogni tag viene mappato esattamente su una voce della cache. Il calcolo è semplice: per una cache da 4 MB/64 B con 65.536 voci, possiamo accedere direttamente a ciascun elemento e utilizzare i bit di indirizzo da 6 a 21 (16 bit) per farlo. I 6 bit inferiori sono l'indice della riga della cache.
Figura 3.6: Illustrazione schematica di una cache a mappatura diretta
Come si può vedere dalla Figura 3.6, l'implementazione di tale cache a mappatura diretta (cache a mappatura diretta) può essere semplice e veloce. Richiede solo un comparatore, un multiplexer (ce ne sono due in questo diagramma poiché tag e dati sono separati, ma questo non è un requisito di progettazione rigoroso) e alcuni circuito logico per selezionare il contenuto che contiene righe cache valide. Il comparatore è complesso a causa dei requisiti di velocità, ma ora ne esiste solo uno; di conseguenza, puoi dedicare più impegno per renderlo più veloce. La vera complessità di questo approccio risiede nei multiplexer. Il numero di transistor in un semplice multiplexer cresce secondo la legge O(log N), dove N è il numero di linee cache. Ciò è accettabile, ma potrebbe risultare in un multiplexer lento, nel qual caso la velocità può essere aumentata investendo in transistor nei multiplexer e parallelizzando parte del lavoro per aumentare la velocità. Quantità totale i transistor cresceranno lentamente rispetto alla dimensione della cache, rendendola una soluzione molto interessante. Ma questo approccio ha uno svantaggio: funziona solo se gli indirizzi utilizzati nel programma sono distribuiti equamente rispetto ai bit utilizzati per la mappatura diretta. In caso contrario, e di solito è così, alcune voci della cache vengono utilizzate attivamente e quindi liberate ripetutamente, mentre altre vengono utilizzate poco o rimangono vuote.
Figura 3.7: Rappresentazione schematica di una cache multiassociativa
Questo problema può essere risolto utilizzando una memoria cache con associatività multipla (insieme associativo). La cache multiassociativa combina le funzionalità della cache ad associatività completa e della cache a mappatura diretta per evitare in gran parte gli svantaggi di queste soluzioni. La Figura 3.7 mostra un progetto di cache multi-associatività. La memoria per tag e dati è divisa in set, la cui selezione viene effettuata in base all'indirizzo. Questo è simile a una cache a mappatura diretta. Ma invece di utilizzare un elemento separato per ciascun valore di un set, lo stesso set viene utilizzato per memorizzare nella cache un numero limitato di valori. I tag di tutti gli elementi di un insieme vengono confrontati in parallelo, il che è simile al funzionamento di una cache completamente associativa.
Il risultato è una cache ragionevolmente resistente ai mancati risultati dovuti a una selezione scarsa o intenzionale di indirizzi con gli stessi numeri impostati contemporaneamente e la dimensione della cache non è limitata dal numero di comparatori che possono essere eseguiti in parallelo. Se la memoria cache aumenta (vedi figura), aumenta solo il numero di colonne, non il numero di righe. Il numero di righe aumenta solo se aumenta l'associatività della cache. I processori odierni utilizzano livelli di associatività fino a 16 e superiori per la cache L2. La cache L1 è generalmente impostata al livello 8.
Tabella 3.1: Impatto della dimensione della cache, dell'associatività e della dimensione della riga della cache
| Misurare memoria cache L2 |
Associatività | |||||||
|---|---|---|---|---|---|---|---|---|
| Visualizzazione diretta | 2 | 4 | 8 | |||||
| CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | |
| 512k | 27 794 595 | 20 422 527 | 25 222 611 | 18 303 581 | 24 096 510 | 17 356 121 | 23 666 929 | 17 029 334 |
| 1M | 19 007 315 | 13 903 854 | 16 566 738 | 12 127 174 | 15 537 500 | 11 436 705 | 15 162 895 | 11 233 896 |
| 2M | 12 230 962 | 8 801 403 | 9 081 881 | 6 491 011 | 7 878 601 | 5 675 181 | 7 391 389 | 5 382 064 |
| 4M | 7 749 986 | 5 427 836 | 4 736 187 | 3 159 507 | 3 788 122 | 2 418 898 | 3 430 713 | 2 125 103 |
| 8M | 4 731 904 | 3 209 693 | 2 690 498 | 1 602 957 | 2 207 655 | 1 228 190 | 2 111 075 | 1 155 847 |
| 16M | 2 620 587 | 1 528 592 | 1 958 293 | 1 089 580 | 1 704 878 | 883 530 | 1 671 541 | 862 324 |
Se disponiamo di una cache da 4 MB/64 B e di associatività a 8 vie, avremo 8192 set nella cache e saranno necessari solo 13 bit di tag per indirizzare i set di cache. Per determinare quale voce (se presente) contiene la riga di cache indirizzabile nel set di cache, sarà necessario confrontare 8 tag. Questo può essere fatto per molto breve tempo. Come si può vedere dalla pratica, questo ha senso.
La Tabella 3.1 mostra il numero di cache L2 mancate per alcuni programmi (in questo caso, il compilatore gcc, che è considerato dagli sviluppatori del kernel Linux il punto di riferimento più importante) come dimensione della cache, dimensione della riga della cache e valore di associatività multipla. Nella Sezione 7.2 introdurremo uno strumento per simulare la memoria cache necessaria per questo test.
Nel caso in cui non fosse già ovvio, la relazione tra tutti questi valori è che la dimensione della cache è uguale a
dimensione della linea della cache x associatività x numero di set
La mappatura degli indirizzi nella memoria cache viene calcolata come
O = log2 della dimensione della riga della cache
S = log2 del numero di set
secondo la figura nella sezione 3.2.
Fig.3.8: Dimensione della cache e livello di associatività (CL=32)
Riso. 3.8 rende i dati della tabella più comprensibili. La figura mostra i dati per una linea di cache di dimensione fissa pari a 32 byte. Se osservi i numeri per una determinata dimensione della cache, puoi vedere che l'associatività può effettivamente fare molto per ridurre i mancati risultati della cache. Per una cache da 8 MB, il passaggio dalla mappatura diretta a una cache associativa a 2 vie consente di risparmiare quasi il 44% della cache. Se viene utilizzata una cache multi-associativa, il processore può memorizzare nella cache un working set più grande rispetto al caso di una cache a mappatura diretta.
In letteratura a volte si legge che l'introduzione dell'associatività ha lo stesso effetto di raddoppiare la dimensione della cache. Questo, come visto nel caso del passaggio da una cache da 4 MB a una cache da 8 MB, è vero in alcuni casi estremi. Ma questo, ovviamente, non è vero con il conseguente aumento dell'associatività. Come si può vedere dai dati, un successivo aumento dell’associatività dà un guadagno significativamente minore. Non dobbiamo però ignorare completamente questo fatto. Nel nostro programma di esempio, l'utilizzo massimo della memoria è di 5,6 MB. Pertanto, con una dimensione della cache di 8 MB, gli stessi set di cache verranno utilizzati più volte (più di due volte). All'aumentare del working set, i risparmi possono aumentare perché, come possiamo vedere, con dimensioni della cache inferiori il vantaggio derivante dall'utilizzo dell'associatività sarà maggiore.
In generale, l'aumento dell'associatività della cache superiore a 8 sembra avere scarso effetto sui carichi di lavoro a thread singolo. Con l'avvento dei processori multi-core che utilizzano una cache L2 condivisa, la situazione sta cambiando. Ora sostanzialmente hai due programmi che accedono alla stessa cache, il che in pratica dovrebbe raddoppiare il vantaggio dell'associatività (o quadruplicarlo per i processori quad-core). Pertanto, possiamo aspettarci che all’aumentare del numero di core, aumenti l’associatività della cache condivisa. Poiché ciò diventa impossibile (l'associatività a 16 vie è già difficile da implementare), i progettisti di processori inizieranno a utilizzare la cache L3 condivisa e oltre, mentre la cache L2 sarà potenzialmente condivisa da alcuni sottoinsiemi di core.
Un altro effetto che possiamo vedere nella Figura 3.8 è il modo in cui l'aumento della dimensione della cache migliora le prestazioni. Questi dati non possono essere interpretati senza conoscere la dimensione del working set. Ovviamente, una cache grande quanto la memoria principale dovrebbe produrre risultati migliori rispetto a una cache più piccola, quindi in generale non c'è limite all'aumento della dimensione della cache e al raggiungimento di vantaggi significativi.
Come accennato in precedenza, la dimensione massima del working set è 5,6 MB. Questo valore non ci consente di calcolare la dimensione della memoria che fornirebbe il massimo beneficio, ma ci consente di stimare tale dimensione. Il problema è che tutta la memoria non viene utilizzata continuamente e quindi siamo in conflitto anche con una cache da 16 MB e un working set di 5,6 MB (ricordate il vantaggio di una cache associativa cache a 2 vie da 16 MB rispetto alla versione con visualizzazione diretta). Ma possiamo affermare con sicurezza che con un tale carico il vantaggio di una cache da 32 MB sarà insignificante. Ma chi ha detto che il working set debba rimanere invariato? Man mano che i carichi di lavoro crescono nel tempo, anche le dimensioni della cache dovrebbero aumentare. Quando si acquistano macchine e si decide quanta cache pagare, vale la pena misurare la dimensione del set di lavoro. Perché questo è importante può essere visto in Fig. 3.10.
Fig.3.9: Posizionamento della memoria utilizzata durante il test
Vengono eseguiti due tipi di test. Nel primo test gli elementi vengono elaborati in sequenza. Il programma di test utilizza il puntatore n, ma gli elementi dell'array sono correlati tra loro in modo da essere attraversati nell'ordine in cui appaiono in memoria. Questa opzione è mostrata nella parte inferiore della Fig. 3.9. C'è un backlink proveniente dall'ultimo elemento. Nella seconda prova ( parte superiore Figura) gli elementi dell'array vengono attraversati in ordine casuale. In entrambi i casi gli elementi dell'array formano una lista ciclica concatenata singolarmente.
In tale memoria, qualsiasi linea OP può essere posizionata ovunque nella memoria cache e in qualsiasi combinazione con altre linee. I circuiti di confronto combinatori CC1-CC4 (Fig. 6.4) analizzano simultaneamente tutti i tag di linea attualmente nella cache e li confrontano con l'indirizzo ricevuto dal bus degli indirizzi dal processore. Quando si verifica un riscontro nella cache, la riga viene letta nel bus dati (DB). In caso di cache miss la riga nella memoria cache viene sostituita con la riga necessaria dell'OP.
Il vantaggio di questa memoria è la sua elevata velocità di lettura. Lo svantaggio è la complessità dell'implementazione hardware. Pertanto, le cache completamente associative vengono spesso utilizzate in buffer specializzati, come il buffer di destinazione del ramo, con un numero limitato di righe.
3. Memoria cache multi-associativa
Questo tipo di memoria è intermedio tra i due discussi sopra. Combina la semplicità di una cache a mappatura diretta con la velocità della ricerca associativa.
La memoria cache è divisa in sottoinsiemi disgiunti (blocchi) di righe. Ciascuna riga della memoria principale può entrare solo in un sottoinsieme della cache. La mappatura diretta viene utilizzata per cercare i blocchi e la ricerca completamente associativa viene utilizzata per cercare all'interno di un sottoinsieme. Il numero di righe in un sottoinsieme di cache determina il numero di input (porte) della cache stessa.
Se 2 n linee di cache sono divise in 2 s sottoinsiemi disgiunti, allora gli S bit di RAM di ordine basso indicano in quale sottoinsieme (indice) deve essere condotta la ricerca associativa. Gli n-s bit più significativi degli indirizzi della memoria principale sono i tag.
Se S=0, otteniamo un sottoinsieme, che corrisponde a una memoria cache completamente associativa. Se S=n, otteniamo 2 n sottoinsiemi (ovvero, una riga - un sottoinsieme). Questa è una memoria cache a mappatura diretta. Se 1Sn-1, allora abbiamo una memoria cache set-associativa.
La Figura 6.5 mostra un esempio di cache in cui S=1, il che significa che ci sono due sottoinsiemi di cache. L'indirizzo fisico 0111, generato dal processore, è suddiviso in indice 1, pari alla cifra meno significativa, e tag 011. Utilizzando l'indice viene selezionato il secondo sottoinsieme di righe nella memoria cache, quindi viene effettuata una ricerca associativa tra le tag di linea del sottoinsieme selezionato. La riga 7 trovata con tag 011 viene trasmessa al bus dati (SD). La ricerca associativa viene eseguita uno 
temporaneamente per tutti i tag utilizzando gli schemi di confronto combinatorio CC1 e CC2.
Riso. 6.5. Cache multiassociativa
I processori moderni utilizzano memoria cache da 4 e 8 input. Un aumento del numero delle sue voci porta ad un rapido aumento della complessità dell'implementazione hardware di quella parte della cache che fornisce la ricerca associativa dei tag.
Funzionalità di registrazione e sostituzione delle informazioni nella memoria cache. Coerenza della cache
L'accesso in lettura può iniziare immediatamente sia alla cache che alla RAM. Quindi, se l'informazione manca dalla cache, nel momento in cui viene accertato questo fatto, parte del ciclo di accesso alla RAM sarà già stato completato, il che può migliorare le prestazioni. Se le informazioni sono nella cache, l'accesso alla RAM può essere interrotto.
Quando si accede in scrittura, vengono utilizzati due metodi: la scrittura viene eseguita solo nella cache o contemporaneamente sia nella cache che nella RAM. Questi metodi sono chiamati algoritmi inversione WB (Riscrivi) e Attraverso record WT (Write Through) rispettivamente. Il secondo è più semplice, ma anche più lento, sebbene garantisca che le copie delle stesse informazioni nella cache e nella RAM corrispondano sempre. La maggior parte dei primi processori Intel utilizzano questo algoritmo.
L'algoritmo di writeback WB è più veloce. Le informazioni vengono trasferite nella RAM solo quando una riga da un'altra pagina OP viene trasferita al posto di una determinata riga della cache o quando viene eseguito un comando per aggiornare il contenuto della cache. Questo algoritmo richiede una gestione più attenta, poiché a volte le copie delle stesse informazioni sono diverse nella cache e nell'OP. Inoltre, non tutte le righe cambiano mentre sono nella cache. Se non sono state apportate modifiche, non è necessario riscrivere la stringa nella RAM. Tipicamente usano il flag M (modificato) nella memoria dei tag. Viene reimpostato su "0" quando la riga viene inizialmente caricata nella cache e impostato su "1" quando le informazioni vengono scritte su di essa. Quando si scarica una riga dalla cache, la scrittura nell'OP viene eseguita solo quando il flag M è impostato su uno.
Quando si verifica un errore, il controller della cache deve selezionare una riga da sostituire. Per la visualizzazione diretta, le soluzioni hardware sono le più semplici. Viene testata l'hit su una sola linea e solo quella linea può essere sostituita. Con un'organizzazione della cache completamente associativa o multi-associativa, ci sono diverse linee da cui un candidato deve essere selezionato in caso di mancata selezione. Per risolvere questo problema, utilizzare le seguenti regole speciali, chiamate algoritmi di sostituzione .
FIFO (First In First Out – primo entrato – primo uscito);
LRU (Utilizzo meno recente - inutilizzato più a lungo di altri);
LFU (Least Frequently Used - usato meno spesso);
Casuale.
Il primo e l'ultimo metodo sono i più semplici da implementare, ma non tengono conto della frequenza con cui viene utilizzata una particolare riga della cache. In questo caso, è possibile eliminare una riga a cui si accederà in un futuro molto prossimo. La probabilità di errore per questi metodi è molto più elevata rispetto al secondo e al terzo.
Nell'algoritmo FIFO, la riga che entra per prima nella cache viene selezionata per la sostituzione. Ogni riga appena inserita nella cache viene aggiunta alla coda di questa coda. L'algoritmo non tiene conto del suo utilizzo effettivo. Ad esempio, le prime righe caricate potrebbero contenere dati richiesti durante l'intera operazione. Ciò provoca un ritorno immediato alla linea appena sostituita.
L'algoritmo LRU prevede che venga selezionata per la cancellazione la riga rimasta inutilizzata per il tempo più lungo. Ogni volta che si accede a una riga, il relativo timestamp viene aggiornato. Ciò potrebbe comportare costi significativi. Tuttavia, nella pratica viene utilizzato più spesso l'algoritmo LRU. Lo svantaggio è che se il programma esegue un ciclo lungo che si estende su molte righe, può accadere che la riga a cui non si accede da più tempo sarà effettivamente la successiva utilizzata.
Uno degli algoritmi vicini a LRU è l'algoritmo LFU, secondo il quale viene cancellata la riga utilizzata meno frequentemente. In questo caso è necessario contare il numero di accessi ad ogni linea e controllarla. Può succedere che la riga utilizzata meno intensamente sia quella che è stata appena scritta nella memoria cache e alla quale è stato effettuato l'accesso solo una volta (mentre alle altre righe è stato effettuato un accesso maggiore). Può essere rimosso, il che rappresenta uno svantaggio dell'algoritmo LFU.
Il contenuto della memoria cache cambia sotto il controllo del processore. In questo caso la memoria principale può rimanere invariata. Gli apparecchi esterni possono invece modificare i dati nell'OP in modalità di accesso diretto. In questo caso, la memoria cache non modifica i suoi dati. Di più la situazione è più complicata nei sistemi multiprocessore, quando più processori accedono alla memoria condivisa. Sorge un problema coerenza memoria cache.
Il sistema informatico ha memoria coerente , se ogni operazione di lettura su un indirizzo eseguita da qualsiasi dispositivo restituisce il valore dell'ultima copia su quell'indirizzo, indipendentemente da quale dispositivo ha scritto l'ultima. Il problema della coerenza è molto importante per i sistemi di copy-back. Usano protocolli speciali e a ciascun tag vengono aggiunti flag di modifica e affidabilità delle informazioni. Questi flag consentono o negano l'accesso ai dati.
Le opzioni note per mappare la memoria principale sulla memoria cache possono essere ridotte a tre tipi: diretto, pienamente associativo E parzialmente associativo.
A visualizzazione diretta indirizzo di linea io memoria cache su cui è possibile mappare il blocco J dall'OP, è determinato univocamente dall'espressione: io = J mod M, Dove M– il numero totale di righe nella memoria cache, ovvero per numero di riga della cache io ciascuno viene visualizzato M blocco OP, se il conteggio inizia dal blocco il cui numero è io.
La mappatura diretta è un metodo di mappatura semplice ed economico da implementare. Il suo principale svantaggio è la rigida assegnazione di una riga nella cache a determinati blocchi OP. Pertanto, se un programma accede alternativamente a parole da due blocchi diversi mappati sulla stessa linea di cache, questa linea sarà costantemente aggiornata e la probabilità di un successo sarà bassa.
Visualizzazione completamente associativa permette di superare lo svantaggio del direct, permettendo il caricamento di qualsiasi blocco OP in qualsiasi linea della cache. La mappatura associativa fornisce flessibilità quando si seleziona una riga per un blocco appena scritto. Lo svantaggio fondamentale di questo metodo è che richiede il controllo di tutte le righe della cache.
La mappatura parzialmente associativa è uno dei possibili compromessi, che combina i vantaggi dei metodi di mappatura diretta e associativa e, in una certa misura, è libera dai loro svantaggi. La memoria cache è divisa in v sottoinsiemi (insiemi), ciascuno dei quali contiene k stringhe (è consuetudine dire che un insieme ha k ingressi). La dipendenza tra i blocchi set e OP è la stessa della mappatura diretta: alle linee incluse nel set io, solo blocchi ben definiti di memoria principale possono essere mappati, secondo la relazione io = J mod v, Dove J– Indirizzo del blocco OP. Allo stesso tempo, il posizionamento dei blocchi lungo le linee del modulo è arbitrario e viene utilizzato il principio associativo per trovare la linea desiderata all'interno del modulo.
In casi estremi, quando v = M, k= 1, la mappatura insiemassociativa si riduce a una diretta, e quando v = 1,k = m- ad associativo.
A seconda del metodo per determinare la corrispondenza reciproca di una linea cache e di un blocco di memoria principale, si distinguono tre architetture di memoria cache:
· cache completamente associativa;
Cache a mappatura diretta
· cache associativa degli insiemi.
IN cache completamente associativa qualsiasi blocco di memoria principale può risiedere in qualsiasi linea di cache, oppure qualsiasi linea di cache può mapparsi a qualsiasi blocco di memoria principale. In questo caso, i bit più significativi dell'indirizzo dei dati memorizzati nella cache, meno i bit che determinano la posizione (offset) dei dati nella riga (blocco), vengono inseriti nella directory e utilizzati come tag. In tale architettura, per determinare se sono presenti dati nella cache a un particolare indirizzo, è necessario confrontare i bit di ordine superiore di quell'indirizzo con i tag di tutte le righe nella directory della cache. Se tale confronto viene eseguito in sequenza, ci vorrà troppo tempo e la memoria cache perderà significato a causa delle scarse prestazioni. Pertanto tale confronto deve essere eseguito in parallelo per tutti i tag. Questo requisito nel miglior modo possibile risposte associative della memoria, ovvero il tag deve essere archiviato nella memoria associativa dei tag della cache.
Tale organizzazione della memoria cache è un problema hardware complesso che può essere risolto solo per piccoli volumi, ovvero una cache completamente associativa, a causa della sua complessità, non può avere un volume grande e viene utilizzata, di regola, per scopi ausiliari. Ad esempio, i processori Intel utilizzano una cache completamente associativa nel blocco di paging per creare buffer di traduzione associativa TLB (Translation Look Aside Buffer), progettato per velocizzare l'accesso alle pagine molto utilizzate.
L'architettura opposta è cache della mappa diretta. In una cache a mappatura diretta, un blocco specifico di memoria principale può risiedere solo in una linea di cache strettamente definita. La memoria principale è convenzionalmente suddivisa in pagine, la cui dimensione coincide con la dimensione della memoria cache. L'architettura di mappatura diretta significa che ciascuna linea della cache può mappare solo il blocco ad essa corrispondente da qualsiasi pagina della memoria principale. I blocchi con gli stessi numeri di pagina finiscono nella stessa riga della cache. Di conseguenza, ogni riga della cache viene occupata da molti blocchi di memoria principale con gli stessi numeri all'interno della pagina. Una riga alla volta può contenere una copia di uno solo di questi blocchi. Il tag è il numero della pagina il cui blocco occupa la corrispondente riga della cache. In tale architettura, per determinare se nella cache sono presenti dati con un particolare indirizzo, è necessario confrontare il numero di pagina a cui appartiene questo indirizzo con il tag di quella riga nella directory della cache che corrisponde al blocco sulla pagina contenente l'indirizzo indicato, ovvero è necessario fare solo una cosa per il confronto.
La cache a mappatura diretta ha l'implementazione hardware più semplice, poiché la memoria cache ha la struttura di una normale memoria indirizzabile direttamente ed è necessario un solo dispositivo di confronto. Pertanto, tale cache può essere grande.
La soluzione intermedia tra una cache completamente associativa e una cache a mappatura diretta è cache associativa di set, che viene utilizzato principalmente nei moderni microprocessori. In una cache set-associativa, a differenza di una cache a mappatura diretta, ogni blocco di memoria principale può rivendicare una delle numerose linee di cache combinate in un set. Ciò aumenta la probabilità che il ricorso venga accolto. In modo semplificato, possiamo considerare che una cache associativa di insieme è costituita da più canali di mappatura diretta paralleli e coordinati, in cui righe con gli stessi numeri formano un insieme corrispondente. La linea impostata che rappresenta il blocco richiesto di memoria principale è determinata da un confronto di tag (come in una cache associativa) eseguito in parallelo su tutti i canali della cache. Ad ogni set è associato un attributo che specifica la riga del set da sostituire con un nuovo blocco in caso di cache miss. Il candidato per la sostituzione è solitamente la riga a cui non si accede da più tempo (algoritmo LRU - Least Recently Used). È anche possibile utilizzare un algoritmo di sostituzione FIFO o anche una sostituzione casuale, che è più semplice ma meno efficiente.