Come parallelizzare fare while e while loop in openmp?

Question

che sto cercando di imparare la programmazione parallela con OpenMP e sono interessato a parallelizzare il do while ciclo seguente con diversi while ciclo al suo interno:

do { 
     while(left < (length - 1) && data[left] <= pivot) left++; 
     while(right > 0 && data[right] >= pivot) right--; 

     /* swap elements */ 
     if(left < right){ 
      temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
     } 

    } while(left < right); 

Non ho effettivamente capito come parallelizzare while e do while loop, non è stato possibile trovare alcuna risorsa in cui descrive specificamente come parallelizzare i loop while e do while. Ho trovato istruzioni per i loop for, ma non ho potuto fare alcuna ipotesi per i loop while e do while da quello. Quindi, potresti descrivere come posso parallelizzare questo loop che ho fornito qui?

EDIT

mi hanno trasformato il ciclo do while al seguente codice in cui viene utilizzato solo for loop.

for(i = 1; i<length-1; i++) 
{ 
    if(data[left] > pivot) 
    { 
     i = length; 
    } 
    else 
    { 
     left = i; 
    } 

} 

for(j=length-1; j > 0; j--) 
{ 
    if(data[right] < pivot) 
    { 
     j = 0; 
    } 
    else 
    { 
     right = j; 
    } 
} 

/* swap elements */ 
if(left < right) 
{ 
    temp = data[left]; 
    data[left] = data[right]; 
    data[right] = temp; 
} 

int leftCopy = left; 
int rightCopy = right; 

for(int leftCopy = left; leftCopy<right;leftCopy++) 
{ 
    for(int new_i = left; new_i<length-1; new_i++) 
    { 
     if(data[left] > pivot) 
     { 
      new_i = length; 
     } 
     else 
     { 
      left = new_i; 
     } 
    } 

    for(int new_j=right; new_j > 0; new_j--) 
    { 
     if(data[right] < pivot) 
     { 
      new_j = 0; 
     } 
     else 
     { 
      right = new_j; 
     } 
    } 
    leftCopy = left; 
    /* swap elements */ 
    if(left < right) 
    { 
     temp = data[left]; 
     data[left] = data[right]; 
     data[right] = temp; 
    } 
} 

Questo codice funziona bene e produce il risultato corretto, ma quando ho cercato di parallelizzare le parti di codice sopraindicato, cambiando i primi due for loop alla seguente:

#pragma omp parallel default(none) firstprivate(left) private(i,tid) shared(length, pivot, data) 
    { 
#pragma omp for 
     for(i = 1; i<length-1; i++) 
     { 
      if(data[left] > pivot) 
      { 
       i = length; 
      } 
      else 
      { 
       left = i; 
      } 
     } 
    } 


#pragma omp parallel default(none) firstprivate(right) private(j) shared(length, pivot, data) 
    { 
#pragma omp for 
     for(j=length-1; j > 0; j--) 
     { 
      if(data[right] < pivot) 
      { 
       j = 0; 
      } 
      else 
      { 
       right = j; 
      } 
     } 
    } 

La velocità è peggio del codice non parallelizzato. Per favore aiutami a identificare il mio problema.

Grazie

Answer 1

Innanzitutto, algoritmi di ordinamento sono molto difficili da parallelizzare con OpenMP cicli paralleli. Questo perché il conteggio dei cicli non è deterministico ma dipende dai valori impostati di input che vengono letti ogni iterazione.

Non credo che le condizioni del ciclo come data[left] <= pivot funzionino correttamente, poiché la libreria OpenMP non sa esattamente come suddividere lo spazio di iterazione tra i thread.

Se sei ancora interessato agli algoritmi di ordinamento parallelo, ti suggerisco di leggere prima la letteratura, per vedere quegli algoritmi che vale davvero la pena implementare a causa della loro scalabilità. Se vuoi semplicemente imparare OpenMP, ti suggerisco di iniziare con algoritmi più semplici come bucket-sort, in cui il numero di bucket è ben noto e non cambia frequentemente.

Riguardo all'esempio che si tenta di parallelizzare, i loop while non sono direttamente supportati da OpenMP perché il numero di iterazioni (conteggio dei cicli) non è deterministico (altrimenti è facile trasformarle in cicli for). Pertanto, non è possibile distribuire le iterazioni tra i thread. Inoltre, è frequente che durante lo svolgimento di cicli di controllo si verifichi una condizione utilizzando il risultato dell'ultima iterazione. Si chiama Read-after-Write o con dipendenza reale e non può essere parallelizzato.

Il problema di rallentamento potrebbe essere alleviato se si tenta di ridurre al minimo il numero di clausole omp parallel. Inoltre, prova a spostarli da tutti i tuoi loop. Queste clausole possono creare e unire i thread aggiuntivi utilizzati nelle parti parallele del codice, che è costoso.

È ancora possibile sincronizzare i thread all'interno di blocchi paralleli, in modo che il risultato sia simile.In effetti, tutti i thread si attendono reciprocamente alla fine di una clausola omp for per impostazione predefinita, in modo che ciò renda le cose ancora più semplici.

#pragma omp parallel default(none) firstprivate(right,left) private(i,j) shared(length, pivot, data) 
{ 
    #pragma omp for 
    for(i = 1; i<length-1; i++) 
    { 
     if(data[left] > pivot) 
     { 
      i = length; 
     } 
     else 
     { 
      left = i; 
     } 
    } 

    #pragma omp for 
    for(j=length-1; j > 0; j--) 
    { 
     if(data[right] < pivot) 
     { 
      j = 0; 
     } 
     else 
     { 
      right = j; 
     } 
    } 
} // end omp parallel