Il codice di progettazione si adatta alla cache della CPU?

https://stackoverflow.com/questions/1822295

10-07-2019
|

Domanda

Quando scrivo simulazioni, il mio amico dice che gli piace provare a scrivere il programma abbastanza piccolo da adattarsi alla cache. Questo ha qualche significato reale? Capisco che la cache è più veloce della RAM e della memoria principale. È possibile specificare che si desidera eseguire il programma dalla cache o almeno caricare le variabili nella cache? Stiamo scrivendo simulazioni, quindi qualsiasi guadagno in termini di prestazioni / ottimizzazione è un enorme vantaggio.

Se sei a conoscenza di buoni collegamenti che spiegano la memorizzazione nella cache della CPU, indicami in quella direzione.

Soluzione

Almeno con una tipica CPU desktop, non puoi davvero specificare molto sull'utilizzo della cache direttamente. Puoi comunque provare a scrivere codice compatibile con la cache. Dal lato del codice, questo spesso significa che lo svolgimento di loop (per un solo esempio ovvio) è raramente utile: espande il codice e una CPU moderna in genere riduce al minimo il sovraccarico del looping. In genere è possibile fare di più dal lato dati, per migliorare la località di riferimento, proteggere da false condivisioni (ad esempio due parti di dati di uso frequente che tenteranno di utilizzare la stessa parte della cache, mentre altre parti restano inutilizzate).

Modifica (per rendere alcuni punti un po 'più espliciti):

Una CPU tipica ha un numero di cache diverse. Un moderno processore desktop avrà in genere almeno 2 e spesso 3 livelli di cache. Con (almeno quasi) accordo universale, "livello 1" è la cache "più vicina" agli elementi di elaborazione e i numeri salgono da lì (il livello 2 è successivo, il livello 3 dopo quello, ecc.)

Nella maggior parte dei casi, (almeno) la cache di livello 1 è divisa in due metà: una cache di istruzioni e una cache di dati (Intel 486 è quasi l'unica eccezione di cui sono a conoscenza, con una sola cache per entrambi istruzioni e dati - ma è così completamente obsoleto che probabilmente non merita molto pensiero).

Nella maggior parte dei casi, una cache è organizzata come un insieme di "righe". Il contenuto di una cache viene normalmente letto, scritto e tracciato una riga alla volta. In altre parole, se la CPU utilizzerà i dati di qualsiasi parte di una riga della cache, l'intera riga della cache viene letta dal successivo livello di archiviazione inferiore. Le cache più vicine alla CPU sono generalmente più piccole e hanno linee di cache più piccole.

Questa architettura di base porta alla maggior parte delle caratteristiche di una cache che contano nella scrittura del codice. Per quanto possibile, vuoi leggere qualcosa nella cache una volta, fare tutto con esso, quindi passare a qualcos'altro.

Ciò significa che, mentre stai elaborando i dati, in genere è meglio leggere una quantità relativamente piccola di dati (abbastanza piccola da adattarsi alla cache), eseguire il più possibile l'elaborazione di tali dati, quindi passare alla prossimo blocco di dati. Algoritmi come Quicksort che suddividono rapidamente grandi quantità di input in pezzi progressivamente più piccoli lo fanno più o meno automaticamente, quindi tendono ad essere abbastanza compatibili con la cache, quasi indipendentemente dai dettagli precisi della cache.

Questo ha anche delle implicazioni per il modo in cui scrivi il codice. Se hai un ciclo come:

for i = 0 to whatever
   step1(data);
   step2(data);
   step3(data);
end for

In genere è meglio mettere insieme quanti più passaggi insieme è possibile fino alla quantità che si adatta alla cache. Nel momento in cui trabocca la cache, le prestazioni possono / diminuiranno drasticamente. Se il codice per il passaggio 3 sopra era abbastanza grande da non rientrare nella cache, in genere sarebbe meglio spezzare il loop in due pezzi come questo (se possibile):

for i = 0 to whatever
    step1(data);
    step2(data);
end for

for i = 0 to whatever
    step3(data);
end for

Lo svolgersi dei loop è un argomento piuttosto controverso. Da un lato, può portare a un codice molto più intuitivo per la CPU, riducendo il sovraccarico di istruzioni eseguite per il ciclo stesso. Allo stesso tempo, può (e generalmente fa) aumentare la dimensione del codice, quindi è relativamente ostile alla cache. La mia esperienza personale è che nei benchmark sintetici che tendono a fare piccole quantità di elaborazione su grandi quantità di dati, guadagni molto dallo srotolamento continuo. Nel codice più pratico in cui si tende ad avere più elaborazioni su un singolo pezzo di dati, si guadagna molto meno - e l'overflow della cache che porta a una grave perdita di prestazioni non è affatto raro.

Anche la cache dei dati ha dimensioni limitate. Ciò significa che generalmente si desidera che i dati vengano impacchettati nel modo più denso possibile, in modo che il maggior numero possibile di dati si adatti alla cache. Solo per un esempio ovvio, una struttura di dati collegata con i puntatori deve guadagnare un bel po 'in termini di complessità computazionale per compensare

Altri suggerimenti

Ecco un link a un ottimo paper su cache / ottimizzazione della memoria di Christer Ericsson (di God of War I / II / III fama). Ha un paio d'anni ma è ancora molto rilevante.

Un documento utile che ti dirà più di quanto avresti mai voluto sapere sulle cache è What Every Programmer Dovrebbe conoscere la memoria di Ulrich Drepper. Hennessey lo copre in modo molto approfondito. Christer e Mike Acton hanno scritto un sacco di cose buone anche su questo.

Penso che dovresti preoccuparti più della cache dei dati che della cache delle istruzioni: nella mia esperienza, i miss di dcache sono più frequenti, più dolorosi e più utili.

AGGIORNAMENTO: 13/01/2014 Secondo questo progettista di chip senior, i fallimenti della cache sono ora IL fattore preponderante dominante nelle prestazioni del codice, quindi siamo sostanzialmente indietro alla metà degli anni '80 e 286 chip veloci in termini di colli di bottiglia relativi alle prestazioni di carico, archivio, numero intero aritmetica e cache mancate.

Un corso intensivo di hardware moderno di Cliff Click @ Azul . . . . .

--- ora torniamo al tuo programma regolarmente programmato ---

A volte un esempio è meglio di una descrizione di come fare qualcosa. In questo spirito, ecco un esempio particolarmente riuscito di come ho modificato un po 'di codice per utilizzarlo meglio nelle cache dei chip. Ciò è stato fatto qualche tempo fa su una CPU 486 e quest'ultima è passata a una CPU Pentium di prima generazione. L'effetto sulle prestazioni è stato simile.

Esempio: Mappatura degli abbonati

Ecco un esempio di una tecnica che ho usato per adattare i dati nella cache del chip con utilità per scopi generali.

Avevo un vettore a doppio galleggiante lungo 1.250 elementi, che era una curva epidemiologica con code molto lunghe. Il "interessante" parte della curva aveva solo circa 200 valori univoci, ma non volevo un test if () su 2 lati per creare un pasticcio della pipeline della CPU (quindi le code lunghe, che potevano usare come pedice i valori più estremi del Monte Carlo il codice verrebbe espulso) e avevo bisogno della logica di predizione del ramo per una dozzina di altri test condizionali all'interno del "hot-spot" nel codice.

Ho optato per uno schema in cui ho usato un vettore di ints a 8 bit come pedice nel doppio vettore, che ho ridotto a 256 elementi. I minuscoli ints avevano tutti gli stessi valori prima di 128 davanti a zero e 128 dopo zero, quindi, tranne per i valori medi di 256, tutti puntavano sul primo o sull'ultimo valore nel doppio vettore.

Ciò ha ridotto i requisiti di archiviazione a 2k per i doppi e 1.250 byte per gli script a 8 bit. Ciò ha ridotto i 10.000 byte fino a 3.298. Poiché il programma ha trascorso il 90% o più del suo tempo in questo ciclo interno, i 2 vettori non sono mai stati espulsi dalla cache di dati 8k. Il programma ha immediatamente raddoppiato le sue prestazioni. Questo codice è stato colpito ~ 100 miliardi di volte nel processo di calcolo di un valore OAS per oltre 1 milione di mutui.

Dato che le code della curva venivano raramente toccate, è molto probabile che solo i 200-300 elementi del vettore int piccolo fossero effettivamente tenuti nella cache, insieme ai 160-240 doppi medi che rappresentano 1/8 di percento di interesse . È stato un notevole aumento delle prestazioni, realizzato in un pomeriggio, su un programma che avevo trascorso oltre un anno a ottimizzare.

Sono d'accordo con Jerry, come è stata anche la mia esperienza, che inclinare il codice verso la cache delle istruzioni non è altrettanto efficace dell'ottimizzazione per la / e cache / e dei dati. Questo è uno dei motivi per cui penso che le cache comuni di AMD non siano utili quanto le cache separate di dati e istruzioni di Intel. IE: non vuoi istruzioni per l'archiviazione della cache, in quanto non è molto utile. In parte ciò è dovuto al fatto che i set di istruzioni CISC sono stati originariamente creati per compensare la grande differenza tra velocità della CPU e della memoria e, fatta eccezione per un'aberrazione alla fine degli anni '80, è praticamente sempre vero.

Un'altra tecnica preferita che utilizzo per favorire la cache dei dati e salvare la cache delle istruzioni è l'utilizzo di molti bit-in nelle definizioni della struttura e le dimensioni dei dati più piccole possibili in generale. Per mascherare un int a 4 bit per contenere il mese dell'anno, o 9 bit per contenere il giorno dell'anno, ecc. Ecc., È necessario che la CPU utilizzi le maschere per mascherare gli interi host utilizzati dai bit, il che riduce il dati, aumenta efficacemente le dimensioni della cache e del bus, ma richiede più istruzioni. Mentre questa tecnica produce codice che non funziona altrettanto bene su benchmark sintetici, su bu

Principalmente questo servirà come segnaposto fino a quando non avrò il tempo di rendere giustizia a questo argomento, ma volevo condividere quella che considero una pietra miliare davvero rivoluzionaria: l'introduzione di istruzioni dedicate sulla manipolazione dei bit nel nuovo microprocessore Intel Hazwell.

È diventato dolorosamente ovvio quando ho scritto del codice qui su StackOverflow per invertire i bit in un array da 4096 bit che oltre 30 anni dopo l'introduzione del PC, i microprocessori non dedicano molta attenzione o risorse ai bit, e che Spero che cambi. In particolare, mi piacerebbe vedere, per cominciare, il tipo bool diventare un tipo di dati bit reale in C / C ++, invece del byte ridicolmente dispendioso che è attualmente.

Nuove istruzioni di manipolazione dei bit di Hazwell

AGGIORNAMENTO: 29/12/2013

Di recente ho avuto occasione di ottimizzare un buffer ad anello che tiene traccia delle 512 diverse richieste degli utenti delle risorse su un sistema con granularità di millisecondi. C'è un timer che spara ogni millisecondo che ha aggiunto la somma delle richieste di risorse della fetta più attuale e sottratto le richieste della fetta del millesimo tempo, comprendente le richieste di risorse che sono vecchie di 1.000 millisecondi.

I vettori di Testa, Coda erano l'uno vicino all'altro in memoria, tranne quando prima la Testa, e poi la Coda si avvolgevano e ricominciavano dall'inizio dell'array. La sezione di riepilogo (a rotazione) tuttavia si trovava in un array fisso, allocato staticamente, che non era particolarmente vicino a nessuno dei due e non era nemmeno allocato dall'heap.

Pensandoci e studiando il codice alcuni particolari hanno attirato la mia attenzione.

Le richieste in arrivo sono state aggiunte contemporaneamente alla sezione Head e alla sezione Summary, proprio una accanto all'altra in righe di codice adiacenti.
Quando il timer è stato attivato, la coda è stata sottratta dalla sezione Riepilogo e i risultati sono stati lasciati nella sezione Riepilogo, come previsto
La seconda funzione chiamata quando il timer ha sparato ha fatto avanzare tutti i puntatori che servono l'anello. In particolare.... La testa sovrascrisse la coda, occupando così la stessa posizione di memoria La nuova coda occupava le successive 512 posizioni di memoria o racchiudeva
L'utente desiderava una maggiore flessibilità nel numero di richieste gestite, da 512 a 4098, o forse di più. Ho ritenuto che il modo più efficace e sicuro per fare ciò fosse quello di allocare sia le 1000 fasce orarie sia la falda di riepilogo tutte insieme come un blocco contiguo di memoria in modo che sarebbe impossibile per la fetta di Riepilogo finire con una lunghezza diversa rispetto alle altre 1.000 fasce orarie.
Dato quanto sopra, ho iniziato a chiedermi se potevo ottenere più prestazioni se, invece di avere la sezione Riepilogo rimasta in una posizione, l'ho avuta " roam " tra la Testa e la Coda, quindi era sempre proprio accanto alla Testa per aggiungere nuove richieste, e proprio accanto alla Coda quando il timer scattava e i valori della Coda dovevano essere sottratti dal Sommario.

Ho fatto esattamente questo, ma poi ho trovato un paio di ottimizzazioni aggiuntive nel processo. Ho modificato il codice che ha calcolato il riepilogo progressivo in modo che lasciasse i risultati nella coda, anziché nella sezione Riepilogo. Perché? Perché la funzione successiva stava eseguendo un memcpy () per spostare la sezione di riepilogo nella memoria appena occupata dalla coda. (strano ma vero, la coda conduce la testa fino alla fine dell'anello quando si avvolge). Lasciando i risultati della somma in Tail, non ho dovuto eseguire il memcpy (), ho dovuto solo assegnare pTail a pSummary.

In modo simile, il nuovo Head occupava la vecchia posizione di memoria della slice di riepilogo ormai obsoleta, quindi di nuovo, ho appena assegnato pSummary a pHead e azzerato tutti i suoi valori con un memset a zero.

Aprendo la strada fino alla fine del ring (in realtà un tamburo, 512 tracce di larghezza) era la coda, ma io o

La maggior parte dei compilatori C / C ++ preferisce ottimizzare per dimensione piuttosto che per "velocità". Cioè, il codice più piccolo generalmente viene eseguito più velocemente del codice non srotolato a causa degli effetti della cache.

Se fossi in te, mi assicurerei di sapere quali parti del codice sono hotspot, che definisco

un circuito chiuso che non contiene alcuna chiamata di funzione, perché se chiama una funzione, il PC trascorrerà la maggior parte del suo tempo in quella funzione,
che rappresenta una frazione significativa dei tempi di esecuzione (come > = 10%) che puoi determinare da un profiler. (Ho appena provato lo stack manualmente.)

Se si dispone di un tale hotspot, dovrebbe rientrare nella cache. Non sono sicuro di come gli dici di farlo, ma sospetto che sia automatico.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow