Come funzionano le linee cache?

Question

Capisco che il processore porti i dati nella cache tramite le linee della cache, che - per esempio, sul mio processore Atom - portano circa 64 byte alla volta, indipendentemente dalle dimensioni dei dati effettivi letti.

La mia domanda è:

Immaginate che avete bisogno di leggere un byte dalla memoria, che a 64 byte sarà portato nella cache?

Le due possibilità che posso vedere sono che i 64 byte partono dal limite di 64 byte più vicino al di sotto del byte di interesse, oppure i 64 byte sono distribuiti attorno al byte in un modo predeterminato (ad esempio, metà sotto, metà sopra o tutto sopra).

Quale è?

Answer 1

Se la riga della cache contenente il byte o la parola che si sta caricando non è già presente nella cache, la CPU richiederà i 64 byte che iniziano al limite della linea cache (l'indirizzo più grande sotto quello necessario è multiplo di 64).

Moduli di memoria PC moderni trasferiscono 64 bit (8 byte) alla volta, in a burst of eight transfers, quindi un comando avvia una lettura o scrittura di una riga di cache completa dalla memoria. (La velocità di trasferimento SDRAM DDR1/2/3/4 è configurabile fino a 64B, le CPU selezioneranno le dimensioni del trasferimento burst per far corrispondere le dimensioni della cache, ma 64B è comune)

Come regola generale, se il processore non è possibile prevedere un accesso alla memoria (e precaricarlo), il processo di recupero può richiedere ~ 90 nanosecondi o ~ 250 cicli di clock (dalla CPU che conosce l'indirizzo alla CPU che riceve i dati).

Al contrario, un hit nella cache L1 ha una latenza di utilizzo del carico di 3 o 4 cicli, e un store-reload ha una latenza di inoltro del magazzino di 4 o 5 cicli su CPU x86 moderne. Le cose sono simili su altre architetture.

Ulteriori letture: Ulrich Drepper's What Every Programmer Should Know About Memory. Il consiglio di precaricamento del software è un po 'sorpassato: i moderni prefetcher HW sono più intelligenti e l'hyperthreading è molto meglio che in P4 giorni (quindi un thread prefetch è tipicamente uno spreco). Inoltre, il wiki del tag x86 ha molti collegamenti alle prestazioni per tale architettura.

Answer 2

I processori possono disporre di cache multilivello (L1, L2, L3) e differiscono per dimensioni e velocità.

Tuttavia, per capire che cosa va esattamente in ogni cache, è necessario studiare il predittore di ramo utilizzato da quel processore specifico e come le istruzioni/i dati del programma si comportano in modo contrario.

Leggi informazioni su branch predictor, CPU cache e replacement policies.

Questo non è un compito facile. Se alla fine della giornata tutto ciò che desideri è un test delle prestazioni, puoi utilizzare uno strumento come Cachegrind. Tuttavia, poiché si tratta di una simulazione, il suo risultato potrebbe differire in una certa misura.

Answer 3

Non posso dirlo con certezza dato che ogni hardware è diverso, ma in genere "64 byte partono dal limite 64 byte più vicino sotto" poiché si tratta di un'operazione molto veloce e semplice per la CPU.

Answer 4

Se le righe della cache sono larghe 64 byte, corrispondono a blocchi di memoria che iniziano su indirizzi divisibili per 64. I 6 bit meno significativi di qualsiasi indirizzo sono un offset nella riga della cache.

Così, per un dato byte, la linea di cache che deve essere recuperata può essere trovato cancellando i meno signficant sei bit dell'indirizzo, che corrisponde a arrotondando l'indirizzo più vicino che è divisibile per 64.

Anche se questo è fatto dall'hardware, possiamo mostrare i calcoli utilizzando alcune definizioni riferimento C macro:

#define CACHE_BLOCK_BITS 6 
#define CACHE_BLOCK_SIZE (1U << CACHE_BLOCK_BITS) /* 64 */ 
#define CACHE_BLOCK_MASK (CACHE_BLOCK_SIZE - 1) /* 63, 0x3F */ 

/* Which byte offset in its cache block does this address reference? */ 
#define CACHE_BLOCK_OFFSET(ADDR) ((ADDR) & CACHE_BLOCK_MASK) 

/* Address of 64 byte block brought into the cache when ADDR accessed */ 
#define CACHE_BLOCK_ALIGNED_ADDR(ADDR) ((ADDR) & ~CACHE_BLOCK_MASK) 

Answer 5

Innanzitutto un accesso alla memoria principale è molto costoso. Attualmente una CPU a 2 GHz (la più lenta una volta) ha 2G tick (cicli) al secondo. Una CPU (virtual core al giorno d'oggi) può recuperare un valore dai suoi registri una volta per tick. Poiché un nucleo virtuale è costituito da più unità di elaborazione (ALU - unità logica aritmetica, FPU ecc.), Può effettivamente elaborare alcune istruzioni in parallelo, se possibile.

Un accesso della memoria principale costa circa 70ns a 100ns (DDR4 è leggermente più veloce). Questa volta è fondamentalmente cercare la cache L1, L2 e L3 e poi colpire la memoria (inviare il comando al controller di memoria, che lo invia ai banchi di memoria), attendere la risposta e terminare.

100ns significa circa 200 tick. Quindi, in pratica, se un programma mancherebbe sempre delle cache che ogni accesso alla memoria, la CPU impiegherebbe circa il 99,5% del tempo (se legge solo la memoria) in attesa della memoria.

Per velocizzare le cose ci sono le cache L1, L2, L3. Usano la memoria direttamente sul chip e usano un diverso tipo di circuiti a transistor per memorizzare i bit dati. Ciò richiede più spazio, più energia ed è più costoso della memoria principale poiché una CPU viene solitamente prodotta utilizzando una tecnologia più avanzata e un guasto di produzione nella memoria L1, L2, L3 ha la possibilità di rendere la CPU priva di valore (difetto) le grandi cache L1, L2, L3 aumentano il tasso di errore che diminuisce la resa che diminuisce direttamente la ROI. Quindi c'è un enorme compromesso quando si tratta di dimensioni della cache disponibili.

(attualmente si creano più cache L1, L2, L3 per poter disattivare alcune parti per ridurre la possibilità che un difetto di produzione effettivo sia rappresentato dalle aree di memoria cache che restituiscono il difetto della CPU nel suo complesso).

Per dare un'idea temporizzazione (fonte: costs to access caches and memory)

• cache L1: 1 ns a 2ns (2-4 cicli)
• L2 cache: 3ns a 5ns (6-10 cicli)
• cache L3: 12ns a 20ns (24-40 cicli)
• RAM: 60ns (120 cicli)

Essendo mescolare diversi tipi di CPU queste sono solo stime, ma dare un go od idea cosa sta andando veramente quando viene recuperato un valore di memoria e potremmo avere un colpo o un errore in certi livelli di cache.

Quindi una cache accelera notevolmente l'accesso alla memoria notevolmente (60ns contro 1ns).

Recuperare un valore, archiviarlo nella cache per la possibilità di rileggerlo è positivo per le variabili a cui si accede spesso, ma per le operazioni di copia di memoria sarebbe ancora lento poiché si legge un valore, scrive il valore da qualche parte e non legge mai più il valore ... nessun hit della cache, dead slow (oltre a ciò può accadere in parallelo dato che abbiamo l'esecuzione fuori servizio).

Questa copia di memoria è così importante che ci sono diversi modi per accelerarlo.Nei primi tempi la memoria era spesso in grado di copiare la memoria al di fuori della CPU. È stato gestito direttamente dal controller di memoria, quindi un'operazione di copia di memoria non ha inquinato le cache.

Ma accanto a una semplice copia di memoria altri accessi seriali di memoria erano piuttosto comuni. Un esempio è l'analisi di una serie di informazioni. Avere un array di numeri interi e calcolare la somma, media, media o anche più semplice trovare un certo valore (filtro/ricerca) era un'altra classe molto importante di algoritmi eseguiti ogni volta su qualsiasi CPU generica.

Quindi analizzando il modello di accesso alla memoria era evidente che i dati vengono letti sequenzialmente molto spesso. C'era un'alta probabilità che se un programma legge il valore all'indice i, che il programma leggerà anche il valore i + 1. Questa probabilità è leggermente superiore alla probabilità che lo stesso programma legga anche il valore i + 2 e così via.

Quindi, dato un indirizzo di memoria, era (ed è ancora) una buona idea leggere avanti e recuperare valori aggiuntivi. Questo è il motivo per cui esiste una modalità boost.

L'accesso alla memoria in modalità boost significa che un indirizzo viene inviato e più valori vengono inviati in sequenza. Ogni valore addizionale inviato richiede solo circa 10ns (o anche più in basso).

Un altro problema era un indirizzo. L'invio di un indirizzo richiede tempo. Per indirizzare gran parte della memoria, è necessario inviare indirizzi di grandi dimensioni. Nei primi tempi ciò significava che il bus indirizzo non era abbastanza grande da inviare l'indirizzo in un singolo ciclo (tick) e più di un ciclo era necessario per inviare l'indirizzo aggiungendo più ritardo.

Una riga cache di 64 byte, ad esempio, significa che la memoria è divisa in blocchi di memoria distinti (non sovrapposti) di 64 byte di dimensione. 64 byte significa che l'indirizzo iniziale di ciascun blocco ha i sei bit di indirizzo più bassi da essere sempre zeri. Quindi, l'invio di questi sei zero bit ogni volta non è necessario aumentando lo spazio di indirizzamento 64 volte per qualsiasi numero di larghezza del bus di indirizzo (effetto di benvenuto).

Un altro problema risolve la riga della cache (oltre a leggere in anticipo e salvare/liberare sei bit sul bus degli indirizzi) è nel modo in cui la cache è organizzata. Ad esempio, se una cache viene suddivisa in blocchi (celle) a 8 byte (64 bit), è necessario memorizzare l'indirizzo della cella di memoria in cui questa cella cache contiene il valore. Se l'indirizzo fosse anche a 64 bit, significa che metà della dimensione della cache viene consumata dall'indirizzo risultante in un sovraccarico del 100%.

Poiché una linea cache è 64 byte e una CPU può utilizzare 64 bit - 6 bit = 58 bit (non è necessario memorizzare i bit zero troppo a destra) significa che è possibile memorizzare 64 byte o 512 bit con un sovraccarico di 58 bit (11% di spese generali). In realtà gli indirizzi memorizzati sono ancora più piccoli di questo, ma ci sono informazioni sullo stato (come la linea della cache valida e precisa, sporca e che deve essere riscritta nella ram ecc.).

Un altro aspetto è che abbiamo impostato la cache associativa. Non tutte le celle della cache sono in grado di memorizzare un determinato indirizzo ma solo un sottoinsieme di esse. Ciò rende ancora più piccoli i bit di indirizzo memorizzati necessari, consente l'accesso parallelo alla cache (è possibile accedere a ogni sottogruppo una sola volta ma indipendentemente dagli altri sottosistemi).

C'è ancora di più quando si tratta di sincronizzare l'accesso cache/memoria tra i diversi core virtuali, le loro unità di elaborazione multiple indipendenti per core e infine più processori su una scheda madre (che ci sono schede che ospitano fino a 48 processori e più).

Questa è fondamentalmente l'idea corrente del perché abbiamo linee cache. Il vantaggio di leggere in anticipo è molto alto e il caso peggiore di leggere un singolo byte fuori da una linea di cache e non leggere mai il resto è molto sottile poiché la probabilità è molto ridotta.

La dimensione della cache-line (64) è un saggia scambio scelto tra le più grandi linee di cache rende improbabile che l'ultimo byte di esso venga letto anche nel prossimo futuro, la durata che impiega a recuperare la linea di cache completa dalla memoria (e per riscriverla) e anche il sovraccarico nell'organizzazione della cache e la parallelizzazione dell'accesso alla cache e alla memoria.