Riduci overp fork/join OpenMP separando #omp parallelo e #omp per

Question

Sto leggendo il libro Un'introduzione alla programmazione parallela di Peter S. Pacheco. Nella Sezione 5.6.2, ha fornito un'interessante discussione sulla riduzione del sovraccarico di fork/join. Consideriamo l'algoritmo di ordinamento per trasposizione pari-dispari:

for(phase=0; phase < n; phase++){ 
    if(phase is even){ 
#  pragma omp parallel for default(none) shared(n) private(i) 
     for(i=1; i<n; i+=2){//meat} 
    } 
    else{ 
#  pragma omp parallel for default(none) shared(n) private(i) 
     for(i=1; i<n-1; i+=2){//meat} 
    } 
} 

L'autore sostiene che il codice di cui sopra ha un po 'alto fork/join in testa. Perché i fili sono biforcuti e uniti in ogni iterazione del ciclo esterno. Quindi, si propone la seguente versione:

# pragma omp parallel default(none) shared(n) private(i, phase) 
for(phase=0; phase < n; phase++){ 
    if(phase is even){ 
#  pragma omp for 
     for(i=1; i<n; i+=2){//meat} 
    } 
    else{ 
#  pragma omp for 
     for(i=1; i<n-1; i+=2){//meat} 
    } 
} 

Secondo gli autori, le seconde forche versione filettature prima dell'inizio ciclo esterno e riutilizzare le filettature per ciascuna iterazione, ottenendo prestazioni migliori.

Tuttavia, sono sospettoso della correttezza della seconda versione. A mio avviso, una direttiva #pragma omp parallel avvia un gruppo di thread e consente ai thread di eseguire il seguente blocco strutturato in parallelo. In questo caso, il blocco strutturato deve essere l'intero ciclo esterno for(phase=0 ...). Allora, non dovrebbe essere il caso in cui l'intero ciclo esterno viene eseguito quattro volte dato che vengono utilizzati 4 fili? Cioè, se n=10, allora 40 iterazioni verrebbero eseguite su 4 thread. Cosa c'è di sbagliato nella mia comprensione? E in che modo lo omp parallel (senza per) gioca con il seguente ciclo for come sopra?

Answer 1

La seconda versione è corretta.

Per la specifica OpenMP, una direttiva #pragma omp parallel for è solo un collegamento per #pragma omp parallel immediatamente seguita da #pragma omp for, come in

#pragma omp parallel 
{ 
    #pragma omp for 
    for(int i=0; i<N; ++i) { /*loop body*/ } 
} 

Se c'è qualche codice nella regione parallelo prima o dopo il costrutto di ciclo, sarà essere eseguito indipendentemente da ogni thread nella regione (a meno che non sia limitato da altre direttive OpenMP). Ma, #pragma omp for è un costrutto di condivisione del lavoro; il ciclo che segue tale direttiva è condiviso da da tutti i thread nella regione. Cioè è eseguito come un singolo ciclo che le iterazioni sono in qualche modo suddivise tra i thread. Pertanto, se la regione parallela sopra è eseguita da 4 thread, il ciclo verrà comunque eseguito solo una volta e non 4 volte.

Torna all'esempio della domanda: il ciclo di fase viene eseguito singolarmente da ciascun thread, ma #pragma omp for a ogni fase di iterazione indica l'inizio di un ciclo condiviso. Per n = 10, ogni thread entrerà in un loop condiviso 10 volte ed eseguirà una parte di esso; quindi non ci saranno 40 esecuzioni dei loop interni, ma solo 10.

Nota esiste una barriera implicita alla fine di #pragma omp for; significa che un thread che ha completato la sua parte di un ciclo condiviso non procederà finché tutti gli altri thread non completeranno anche le loro porzioni. Quindi, l'esecuzione è sincronizzata tra i thread. Questo è necessario per garantire la correttezza nella maggior parte dei casi; per esempio. nel tuo esempio questo garantisce che i thread funzionino sempre nella stessa fase. Tuttavia, se i cicli condivisi all'interno di una regione sono sicuri da eseguire simultaneamente, è possibile utilizzare una clausola per eliminare la barriera implicita e consentire ai thread di procedere immediatamente al resto dell'area parallela.

Si noti inoltre che tale elaborazione delle direttive di condivisione del lavoro è piuttosto specifica per OpenMP. Con altri framework di programmazione paralleli, la logica utilizzata nella domanda potrebbe essere corretta.

Infine, le implementazioni OpenMP intelligenti non uniscono i thread dopo che una regione parallela è stata completata; invece, i thread potrebbero essere occupati, attendere un po 'di tempo, quindi attendere fino a quando non viene avviata un'altra regione parallela. Questo viene fatto esattamente per prevenire alti costi generali all'inizio e alla fine delle regioni parallele. Quindi, mentre l'ottimizzazione suggerita nel libro rimuove ancora alcuni overhead (forse), per alcuni algoritmi il suo impatto sul tempo di esecuzione potrebbe essere trascurabile. L'algoritmo nella domanda è abbastanza probabile uno di questi; nella prima implementazione, le regioni parallele seguono rapidamente una dopo l'altra all'interno del ciclo seriale, pertanto i thread di lavoro OpenMP molto probabilmente saranno attivi all'inizio di una regione e verranno avviati rapidamente, evitando il sovraccarico di fork/join. Quindi non essere sorpreso se in pratica non vedi alcuna differenza di prestazioni dall'ottimizzazione descritta.