Che cosa è importante quando si ottimizza la cache della CPU (in C)?

11

Leggere questi due domande , vedo che la comprensione del caching della CPU il comportamento può essere importante quando si gestiscono grandi quantità di dati in memoria. Mi piacerebbe capire come funziona la cache per aggiungere un altro strumento alla mia casella degli strumenti di ottimizzazione.

Quali sono i punti chiave riguardo al modo in cui funziona la cache della CPU, quindi posso scrivere codice che la utilizza in modo ragionevole? In relazione a ciò, c'è un modo per codificare il codice per vedere se l'uso scarso della cache sta rallentando le cose?

    
posta Timothy Jones 19.12.2011 - 01:38
fonte

4 risposte

16
  • Mantieni i tuoi dati piccoli se possibile
  • Mantieni le cose a cui si accede insieme (o subito dopo l'altro) l'una accanto all'altra nella memoria
  • Scopri i parametri di ottimizzazione del compilatore
  • Leggi ciò che ogni programmatore dovrebbe sapere sulla memoria per maggiori dettagli di quanti tu possa mai volere
risposta data 19.12.2011 - 10:32
fonte
12

La complessità di questo problema è stata al di là della comprensione umana in questi giorni. (È stato così fin dagli ultimi 5 anni.) Combinalo con il parallelismo a corto-vettoriale (SIMD) e hai la sensazione di non aver speranza che l'ottimizzazione del codice a mano non sia più economicamente fattibile - non che non sia possibile, ma sarebbe non essere più redditizio.

L'approccio attuale consiste nel fare affidamento sull'insegnamento dei computer su come ottimizzare, eseguendo variazioni del codice che calcolano le stesse risposte con strutture diverse (cicli, struttura dati, algoritmi) e valutando automaticamente le prestazioni. Le regole per le trasformazioni di codice sono specificate con un modello matematico molto rigoroso, in modo che sia qualcosa che entrambi gli scienziati del computer possono capire e che i computer possono eseguire.

Quello che segue è un link pubblicato da Larry OBrien in uno dei suoi risposte

.

link

    
risposta data 19.12.2011 - 09:48
fonte
2

È abbastanza possibile capire e ottimizzare per le cache. Inizia con la comprensione dell'hardware e continua con il controllo del sistema. Minore è il controllo sul sistema, meno probabile sarà il successo. Linux o Windows che eseguono un mucchio di applicazioni / thread che non sono inattivi.

La maggior parte delle cache sono in qualche modo simili nelle loro proprietà, usano una parte del campo dell'indirizzo per cercare hit, hanno una profondità (modi) e una larghezza (linea della cache). Alcuni hanno buffer di scrittura, alcuni possono essere configurati per scrivere o bypassare la cache nelle scritture, ecc.

Devi essere perfettamente consapevole di tutte le transazioni di memoria in corso che stanno colpendo quella cache (alcuni sistemi hanno istruzioni indipendenti e cache di dati che semplificano l'attività).

È possibile rendere inutilizzabile una cache non gestendo la memoria con attenzione. Ad esempio, se hai più blocchi di dati che stai elaborando, sperando di tenerli nella cache, ma sono in memoria a indirizzi che sono anche multipli rispetto al controllo hit / miss delle cache, ad esempio 0x10000 0x20000 0x30000, e hai più di a parte i modi nella cache, si può finire molto rapidamente per creare qualcosa che gira abbastanza lentamente con la cache, più lentamente di quanto farebbe con la cache disattivata. Ma cambiala in forse 0x10000, 0x21000, 0x32000 e questo potrebbe essere sufficiente per sfruttare al massimo la cache, riducendo gli sfratti.

La linea di fondo, la chiave per l'ottimizzazione di una cache (beh, oltre a conoscere abbastanza bene il sistema) è quella di mantenere tutti gli elementi di cui hai bisogno per le prestazioni nella cache allo stesso tempo, organizzando i dati in modo tale che sia possibile avere tutto nella cache in una volta. E impedire che cose come l'esecuzione di codice, interruzioni e altri eventi regolari o casuali rimuovano parti significative di questi dati che stai utilizzando.

Lo stesso vale per il codice. È un po 'più difficile anche se è necessario controllare le posizioni in cui il codice vive per evitare collisioni con altro codice che si desidera mantenere nella cache. Durante il test / profilazione di qualsiasi codice che passa attraverso una cache che aggiunge una singola riga di codice qua e là o anche un singolo nop, tutto ciò che sposta o cambia gli indirizzi in cui il codice vive da uno compila all'altro per lo stesso codice, cambia dove le linee della cache rientrano in quel codice e cambiano ciò che viene sfrattato e cosa no per le sezioni critiche.

    
risposta data 14.01.2012 - 17:16
fonte
1

Entrambi nwong e le risposte di di Michael Borgwardt danno buoni consigli.

Inoltre, fidati in primo luogo delle ottimizzazioni del compilatore su questi problemi.

Se si utilizza un compilatore GCC recente, è possibile utilizzare (con parsimonia) la sua funzione __builtin_prefetch . Vedi questa risposta sullo stackoverflow.

    
risposta data 19.12.2011 - 10:42
fonte

Leggi altre domande sui tag