Più livelli di parallelismo usando OpenMP - Possibile? Inteligente? Pratico?

Question

Attualmente sto lavorando su una libreria sparse matrix/math/iterative solver C++, per uno strumento di simulazione che gestisco. Avrei preferito utilizzare un pacchetto esistente, tuttavia, dopo un'indagine approfondita, non è stato trovato nessuno adatto al nostro simulatore (abbiamo esaminato flens, it ++, PetSC, eigen e molti altri). La buona notizia sono i miei risolutori e le strutture a matrice sparsa sono ora molto efficienti e robuste. La cattiva notizia è che ora sto esaminando la parallelizzazione usando OpenMP e la curva di apprendimento è un po 'ripida.

Il dominio che risolviamo può essere suddiviso in sottodomini, che si uniscono in un formato a blocchi diagonali. Quindi il nostro schema di archiviazione si presenta come una matrice di matrici quadrate più piccole (blocchi []) ciascuna con un formato appropriato per il sottodominio (ad es. Archiviazione righe compresse: CRS, Archiviazione diagonale compressa: CDS, Denso, ecc.), e una matrice di sfondo (attualmente in uso CRS) che tiene conto della connettività tra sottodomini.

Il "punto caldo" nella maggior parte dei (tutti?) Risolutori iterativi è l'operazione di moltiplicazione di Matrix Vector, e questo è vero per la mia libreria. Pertanto, ho concentrato i miei sforzi sull'ottimizzazione delle mie routine MxV. Per la struttura diagonale blocco, il codice pseudo di M * x = b sarebbero le seguenti:

b=background_matrix*x 
start_index = 1; 
end_index = 0; 
for(i=1:number of blocks) { 
    end_index=start_index+blocks[i].numRows(); 
    b.range(start_index, end_index) += blocks[i] * x.range(start_index, end_index); 
    start_index = end_index+1; 
} 

dove background_matrix è lo sfondo (CRS) matrice, blocchi è la matrice di matrici sub-dominio, e .Range restituisce la parte del vettore da un indice iniziale a un indice finale.

Ovviamente il ciclo può essere (ed è stato) parallelizzato, poiché le operazioni sono indipendenti da altre iterazioni del ciclo (gli intervalli non sono sovrapposti). Dato che abbiamo 10-15 blocchi in un tipico sistema, 4+ thread effettivamente fanno una differenza significativa.

L'altro posto in cui la parallelizzazione è stata considerata una buona opzione è l'operazione MxV per ogni schema di archiviazione sottodominio (chiamate nelle righe 1 e 6 nel codice precedente). C'è molto da fare sulla parallelizzazione delle operazioni MxV con Matrice CRS, CDS e densa. In genere, una bella spinta si vede con 2 thread, con ritorni molto più bassi con l'aggiunta di più thread.

Sto immaginando uno schema, in cui verranno utilizzati 4 thread nel loop block per il codice precedente e ognuno di questi thread utilizzerà 2 thread per i risolti del sottodominio. Tuttavia, non sono sicuro di come, usando OpenMP, si gestisca il pool di thread: è possibile limitare il numero di thread in un ciclo aperto per loop? Questo parallelismo a più livelli è qualcosa che nella pratica ha un senso? Eventuali altri pensieri su quello che ho proposto qui sarebbe apprezzato (e grazie per la lettura fino alla fine!)

Answer 1

Si prega di notare che tutto ciò che descrivo dipende dall'implementazione.

È possibile limitare il numero di thread in un ciclo aperto per ciclo?

Sì. Ci sono diversi modi per farlo. Impostare omp_set_nested(1); e utilizzare qualcosa come #pragma omp parallel for num_threads(4) o simile nel ciclo esterno e la direttiva #pragma omp parallel for num_threads(2) nel proprio ciclo interno.Questo dovrebbe darti 8 thread (a seconda dell'implementazione, potresti anche impostare OMP_THREAD_LIMIT se hai meno di 8 core)

In alternativa, puoi srotolare manualmente i tuoi loop, ad es. usando qualcosa come

#pragma omp parallel sections { 
    #pragma omp section 
    do your stuff for the first part, nest parallel region again 
    #pragma omp section 
    and so on for the other parts 
} 

È possibile fare la stessa cosa a volte in modo più efficiente in OpenMP 3.0 con #pragma omp task.

Oppure si avviano 8 thread e si ottiene il numero di thread corrente all'interno della sezione parallela e pianificato manualmente in base al numero di thread.

Infine, se si dispone di un ciclo perfettamente annidato (un ciclo è perfettamente annidato, se l'assegnazione effettiva avviene solo nel ciclo più interno), è possibile riscrivere tutto in un unico ciclo. In pratica impacchetta i tuoi due iteratori i e j in un unico iteratore grande (i, j). Si noti che ciò potrebbe ridurre la località e quindi diminuire le prestazioni

Questo parallelismo a più livelli è qualcosa che nella pratica ha senso?

Dipende, e devi scoprire te stesso. In generale, il parallelismo a più livelli rende il tuo problema più scalabile. La pianificazione, tuttavia, può essere più complicata. Questo paper potrebbe essere interessante.

Per quanto riguarda l'impostazione manuale del numero di thread: il vantaggio principale di impostare il numero di thread è che è possibile utilizzare una conoscenza specifica del problema durante la pianificazione. In tal modo, è possibile ridurre il sovraccarico e ottenere una maggiore localizzazione del codice in esecuzione e quindi più colpi di cache e meno I/O di memoria principale.

Lo svantaggio principale di impostare manualmente il numero di thread nel parallelismo nidificato è che i thread nel ciclo più interno potrebbero attendere o meno la barriera implicita, mentre è possibile eseguire ulteriori operazioni (example). Inoltre, il parallelismo a grana grossa non si adatta bene. Quindi se il ciclo esterno ha un tempo di esecuzione molto diverso all'interno del ciclo, si desidera pianificare in modo più flessibile rispetto alla semplice suddivisione in 4 thread.

Altri pensieri

avete però di fare la MXV con SIMD. A seconda dell'architettura, questo può dare un aumento di velocità di 2-4. Ho cercato su google questo presentation per te.

Per MxV, loop tiling, register and cache blocking e le tecniche correlate possono aumentare la località dei dati e ridurre altri problemi, ad es. condivisione falsa. Questo book, capitolo 11 (è possibile visualizzarlo in anteprima) potrebbe fornire alcune idee aggiuntive su come ristrutturare l'accesso ai dati.

Answer 2

Perché non chiedere agli esperti oltre a OpenMP.org

ed accedere a: http://openmp.org/forum/viewforum.php?f=3