Problema di velocità con enorme array C utilizzando 64 bit Visual C

Question

Ho bisogno di leggere una quantità enorme di dati in un buffer (circa 20gig). Ho 192gb di DDram molto veloce disponibile, quindi nessun problema con le dimensioni della memoria. Tuttavia, sto trovando che il seguente codice si esegue più lentamente e più lentamente tanto più diventa nel buffer. Il profiler di Visual C mi dice che il 68% del tempo di esecuzione di 12 minuti è nelle istruzioni 2 all'interno del ciclo in myFunc(). Sto facendo funzionare win7, 64bit su un dell molto veloce con 2 cpu, 6 core fisici ciascuno (24 core logici), e tutti e 24 i core sono completamente al massimo durante l'esecuzione di questo.

#define TREAM_COUNT 9000 
#define ARRAY_SIZE ONE_BILLION 

#define offSet(a,b,c,d) (((size_t) ARRAY_SIZE * (a)) + ((size_t) TREAM_COUNT * 800 * (b)) + ((size_t) 800 * (c)) + (d)) 

void myFunc(int dogex, int ptxIndex, int xtreamIndex, int carIndex) 
{ 
    short *ptx = (short *) calloc(ARRAY_SIZE * 20, sizeof(short)); 

    #pragma omp parallel for 
    for (int bIndex = 0; bIndex < 800; ++bIndex) 
      doWork(dogex, ptxIndex, carIndex); 
} 

void doWork(int dogex, int ptxIndex, int carIndex) 
{ 

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex) 
    { 
     short ptxValue  = ptx[ offSet(dogex, ptxIndex, treamIndex, carIndex) ]; 
     short lastPtxValue = ptx[ offSet(dogex, ptxIndex-1, treamIndex, carIndex) ]; 

     // .... 
    } 

} 

Answer 1

Il codice ha assegnato 20 blocchi di un miliardo di corti. Su una casella di Windows a 64 bit, una breve int è 2 byte. Quindi l'allocazione è di ~ 40 gigabyte.

Si dice che ci sono 24 core e sono tutti al massimo. Il codice così com'è non sembra mostrare alcun parallelismo. Il modo in cui il codice viene parallelizzato potrebbe avere un profondo effetto sulle prestazioni. Potrebbe essere necessario fornire ulteriori informazioni.

-

Il tuo problema di fondo, ho il sospetto, ruota attorno limiti comportamento della cache e di accesso alla memoria.

Innanzitutto, con due CPU fisiche di sei core ciascuna, si saturerà completamente il bus di memoria. Probabilmente hai comunque un'architettura NUMA, ma non c'è alcun controllo nel codice su dove si alloca il tuo calloc(), ad esempio potresti avere un sacco di codice memorizzato nella memoria che richiede più hop da raggiungere).

Hyperthreading è attivato. Questo dimezza efficacemente le dimensioni della cache. Dato che il codice è legato al bus di memoria, piuttosto che al limite di elaborazione, l'hyperthreading è dannoso. (Detto questo, se il calcolo è costantemente al di fuori dei limiti della cache, questo non cambierà molto).

Non è chiaro (dal momento che un po '/ molto?

Quello che vedo in come offset() è caculato è che il codice richiede costantemente la generazione di nuove ricerche da virtuale a indirizzo fisico, ognuna delle quali richiede qualcosa come quattro o cinque accessi di memoria. Questo è kiling performance, da solo.

Il mio consiglio di base sarebbe di suddividere l'array in blocchi di dimensione cache di livello 2, dare un blocco a ciascuna CPU e lasciarlo elaborare quel blocco. Puoi farlo in parallelo. In realtà, potresti essere in grado di utilizzare l'hyperthreading per precaricare la cache, ma questa è una tecnica più avanzata.

Answer 2

Questa ottimizzazione sarà sbarazzarsi delle moltiplicazioni lenti:

... 
    int idx1 = offSet(dogex, ptxIndex, 0, carIndex); 
    int idx2 = offSet(dogex, ptxIndex-1, 0, carIndex); 

    for (int treamIndex = 0; treamIndex < ONE_BILLION; ++treamIndex) 
    {    
     short ptxValue  = ptx[ idx1 ]; 
     short lastPtxValue = ptx[ idx2 ]; 
     idx1+=800; 
     idx2+=800;    ... 

Answer 3

Si dovrebbe cercare di accedere matrice in modo più lineare, se possibile. Ciò probabilmente causa una quantità eccessiva di errori di cache.

Answer 4

Penso che il problema di questo codice sia il suo modello di accesso alla memoria. Il fatto che ogni filo accede alla memoria in grandi (2 * 800 bytes) incrementi ha 2 conseguenze negative:

1. All'inizio tutte le discussioni accedono alla stessa porzione di memoria, che viene precaricato nella cache L2/L3 ed è efficiente usato da ogni thread. Successivamente, i thread procedono con una velocità leggermente diversa e accedono a diversi pezzi di memoria, il che risulta nel cestinare la cache (un thread carica i dati nella cache ed elimina i dati da lì, che non erano ancora letti da altri thread, che ne avevano bisogno).Di conseguenza, lo stesso pezzo di memoria viene letto più volte nella cache (nel peggiore dei casi, 12 volte, dal numero di thread in una CPU). Poiché il bus di memoria è relativamente lento, questo rallenta l'intero programma.
2. La cache L1 viene utilizzata anche in modo non efficiente: solo una piccola parte dei dati in ogni riga della cache viene utilizzata dai core della CPU.

La soluzione è quella di consentire a ciascun filo di accedere alla memoria in sequenza (come scambio c e d argomenti della offSet(a,b,c,d) macro).