migliorare la località e ridurre l'inquinamento della cache in un'implementazione di ricostruzione di immagini mediche

Question

Sto facendo una ricerca per la mia Università relativa a un algoritmo di ricostruzione di immagini per uso medico.

Sono bloccato in qualcosa fino a 3 settimane, ho bisogno di migliorare le prestazioni del seguente codice:

for (lor=lor0[mypid]; lor <= lor1[mypid]; lor++) 
{ 
    LOR_X = P.symmLOR[lor].x; 
    LOR_Y = P.symmLOR[lor].y; 
    LOR_XY = P.symmLOR[lor].xy; 
    lor_z = P.symmLOR[lor].z; 
    LOR_Z_X = P.symmLOR[lor_z].x; 
    LOR_Z_Y = P.symmLOR[lor_z].y; 
    LOR_Z_XY = P.symmLOR[lor_z].xy; 

    s0 = P.a2r[lor]; 
    s1 = P.a2r[lor+1]; 

    for (s=s0; s < s1; s++) 
    { 
    pixel  = P.a2b[s]; 
    v   = P.a2p[s]; 

    b[lor] += v * x[pixel]; 

    p   = P.symm_Xpixel[pixel]; 
    b[LOR_X] += v * x[p]; 

    p   = P.symm_Ypixel[pixel]; 
    b[LOR_Y] += v * x[p]; 

    p   = P.symm_XYpixel[pixel]; 
    b[LOR_XY] += v * x[p]; 


    // do Z symmetry. 
    pixel_z = P.symm_Zpixel[pixel]; 
    b[lor_z] += v * x[pixel_z]; 


    p   = P.symm_Xpixel[pixel_z]; 
    b[LOR_Z_X] += v * x[p]; 


    p   = P.symm_Ypixel[pixel_z]; 
    b[LOR_Z_Y] += v * x[p]; 

    p   = P.symm_XYpixel[pixel_z]; 
    b[LOR_Z_XY] += v * x[p]; 

    } 

} 

per chi vuole conoscere, il codice implementa la funzione in avanti MLEM e tutti le variabili sono FLOAT.

Dopo diversi test, ho notato che il grosso ritardo era su questa parte del codice. (lo sai, la regola 90 - 10).

In seguito, ho usato Papi (http://cl.cs.utk.edu/papi/) per misurare le mancanze della cache L1D. Come pensavo, Papi conferma che le prestazioni diminuiscono a causa di una maggiore quantità di miss, in particolare per l'accesso casuale al vettore b (di enormi dimensioni).

Leggere informazioni su Internet Conosco solo due opzioni per migliorare le prestazioni finora: migliorare la localizzazione dei dati o ridurre l'inquinamento dei dati.

a fare il primo miglioramento, cercherò di modificare il codice per essere cache di conoscenza, proprio come è stato propossed da Ulrich Drepper su Ciò che ogni programmatore dovrebbe conoscere la memoria (www.akkadia.org/drepper/ cpumemory.pdf) A.1 Matrix moltiplicazione.

Credo che il blocco della SpMV (moltiplicazione di matrice-vettore multiplo) migliorerà le prestazioni.

D'altra parte, ogni volta che il programma ha tentato di accedere al vettore b, abbiamo avuto l'inquinamento della cache .

C'è un modo per caricare un valore dal vettore b con l'istruzione SIMD senza utilizzare la cache?

Inoltre, è possibile utilizzare una funzione come void _mm_stream_ps (float * p, __m128 a) per memorizzare un valore float sul vettore b senza inquinare la cache?

Non riesco a utilizzare _mm_stream_ps perché memorizza sempre 4 float ma l'accesso al vettore b è chiaramente casuale.

Spero di essere chiaro nel mio dilemma.

Ulteriori informazioni: v è il valore della colonna di un archivio Sparse Matrix con formato CRS. Mi rendo conto che si potrebbe fare un'altra ottimizzazione se provassi a cambiare il formato CRS ad altri, tuttavia, come ho detto prima, avevo fatto diversi test per mesi e so che la diminuzione delle prestazioni è legata all'accesso casuale al vettore b. da 400.000.000 L1D Misses posso andare a 100 ~ Manca quando non immagazzino nel vettore b.

Grazie.

Answer 1

Direi, al primo tentativo di aiutare un po 'il compilatore.

• Dichiarare i limiti per il ciclo esterno come const prima del ciclo.
• dichiarare tutte le variabili che si possono (tutto il LOR_..) come variabili locali, qualcosa come: float LOR_X = P.symmLOR[lor].x; o size_t s0 = P.a2r[lor];
• Questo anche, in particolare, per il ciclo variabili se vi capita di avere moderna, C99 compatibile, compiler: for (size_t s=s0; s < s1; s++)
• Carico e deposito separati per il tuo b vettore . Le posizioni degli articoli a cui si accede, lì, non dipendono da su s.Quindi creare una variabile locale per contenere il valore reale per tutti i casi distinti che si maneggiate prima il ciclo interno, aggiornare queste variabili locali all'interno della interno ciclo, e memorizzare i risultati dopo il ciclo interno .
• Forse separare il loop interno in diversi. I calcoli dell'indice sono relativamente economici, quindi il tuo sistema potrebbe riconoscere meglio l'accesso allo streaming ad alcuni dei tuoi vettori .
• Guarda all'assemblatore che il tuo compilatore produce e identifica il codice per il ciclo interno. Sperimenta un bit per spostare il carico "lontano" del numero e memorizza da quel ciclo.

Edit: dopo aver riletto la risposta di gravitron e il tuo commento, la cosa importante qui è davvero per dichiarare le variabili come locali possibile e per verificare l'assemblatore che il compilatore riesce ad avere i carichi di cache-missing e memorizza al di fuori del ciclo interno.

Answer 2

Una semplice ottimizzazione per ridurre l'accesso casuale al vettore b sarebbe quella di non scrivere mai nel vettore b all'interno del ciclo for.

Caricare invece tutti i valori necessari dal vettore B in variabili temporanee, eseguire l'intero ciclo interno per l'aggiornamento di queste variabili temporanee, quindi riportare le variabili temporanee nel vettore B.

Le variabili temporanee si troveranno nella peggiore delle ipotesi sulle stesse linee di cache, a seconda del compilatore e dell'ambiente si può anche suggerire al compilatore di utilizzare i registri per queste variabili.

Answer 3

non voglio nemmeno far finta che io so quello che il codice sta facendo :) Ma una possibile causa di qualche accesso di memoria extra è aliasing: se il compilatore non può essere sicuro che b, x, e le varie matrici P.symm non sovrapporre, quindi scrivere su b influenzerà il modo in cui è possibile pianificare la lettura da x e da P.symm. Se il compilatore è particolarmente pessimista, potrebbe persino forzare il recupero dei campi di P dalla memoria. Tutto ciò contribuirà alle mancanze della cache che stai vedendo. Due semplici modi per migliorare questo sono:

1. Usa __restrict su b. Ciò garantisce che b non si sovrapponga agli altri array, pertanto le scritture non influiranno sulle letture (o sulle scritture) da altri array.

2. cose riordino in modo che tutta la legge da P.symm 's sono di prima, allora la legge da x, poi finalmente tutti gli scrive a b. Questo dovrebbe suddividere alcune delle dipendenze nelle letture e il compilatore pianifica le letture da P.symm in parallelo, quindi le letture da x in parallelo, e si spera di fare le scritture a b sensibilmente.

Un altra cosa stilistica (che contribuirà con il punto # 2) è quello di non riutilizzare le variabili così p così tanto. Non c'è motivo per cui non puoi avere, ad es. p_x, p_y, p_xy, ecc. E renderà più facile riordinare il codice.

Una volta che tutto è a posto, è possibile iniziare a spruzzare le istruzioni di prefetch (ad esempio __builtin_prefetch su gcc) in anticipo rispetto alle carenze di cache note.

Spero che questo aiuti.

Answer 4

Queste sono buone risposte, e vorrei chiedere perché così tanto indicizzazione? per valori di indice che non cambiano molto localmente?

Inoltre, non ti ucciderebbe per fare alcune pause casuali per vedere dove è in genere.