Wie parallel zu machen, während while und while loop in openmp?

Question

Ich versuche, die parallele Programmierung mit OpenMP zu lernen, und ich bin daran interessiert, die folgende do while Schleife mit mehreren while Schleife im Inneren in Parallelisierung:

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); 

Ich habe tatsächlich aus nicht begriffen, wie while und do while parallelisieren Schleifen, konnte keine Ressource finden, wo es speziell beschreibt, wie while und do while Schleifen zu parallelisieren. Ich habe Anweisungen für for Schleifen gefunden, aber ich konnte keine Annahme für while und do while Schleifen daraus machen. Könnten Sie bitte beschreiben, wie ich diese Schleifen, die ich hier zur Verfügung gestellt habe, parallelisieren kann?

EDIT

Ich habe die do while Schleife zu dem folgenden Code umgewandelt, in dem nur for Schleife verwendet wird.

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; 
    } 
} 

Dieser Code funktioniert gut und korrekte Ergebnis produziert, aber wenn ich versucht, die Teile der oben angegebenen Code parallelisieren, indem Sie die ersten beiden for Schleifen auf die folgende Veränderung:

#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; 
      } 
     } 
    } 

Die Geschwindigkeit ist schlechter als der nicht parallelisierte Code. Bitte helfen Sie mir, mein Problem zu identifizieren.

Dank

Answer 1

Zunächst einmal sind Sortieralgorithmen sehr hart mit OpenMP parallelen Schleifen parallelisieren. Dies liegt daran, dass die Anzahl der Schleifenauslöser nicht deterministisch ist, sondern von den Eingabe-Set-Werten abhängt, die bei jeder Iteration gelesen werden.

Ich glaube nicht, Schleifenbedingungen wie data[left] <= pivot wird gut funktionieren, da OpenMP-Bibliothek nicht genau wissen, wie Sie den Iterationsraum unter den Threads partitionieren.

Wenn Sie immer noch an parallelen Sortieralgorithmen interessiert sind, empfehle ich Ihnen, zuerst die Literatur zu lesen, um die Algorithmen zu sehen, die aufgrund ihrer Skalierbarkeit wirklich sinnvoll sind. Wenn Sie nur OpenMP lernen möchten, sollten Sie mit einfacheren Algorithmen wie bucket-sort beginnen, bei denen die Anzahl der Buckets gut bekannt ist und sich nicht häufig ändert.

In dem Beispiel, das Sie versuchen zu parallelisieren, werden while Schleifen nicht direkt von OpenMP unterstützt, da die Anzahl der Iterationen (Loop Trip Count) nicht deterministisch ist (andernfalls ist es einfach, sie in for Schleifen umzuwandeln). Daher ist es nicht möglich, die Iterationen auf die Threads zu verteilen. Darüber hinaus ist es üblich, dass while-Schleifen nach einer Bedingung suchen, die das Ergebnis der letzten Iteration verwendet. Dies wird Read-after-Write oder True-Abhängigkeit genannt und kann nicht parallelisiert werden.

Ihr Verlangsamungsproblem könnte gemildert werden, wenn Sie versuchen, die Anzahl der omp parallel Klauseln zu minimieren. Versuchen Sie außerdem, sie aus allen Ihren Schleifen zu entfernen. Diese Klauseln können die zusätzlichen Threads erstellen und verbinden, die in den parallelen Teilen des Codes verwendet werden, was teuer ist.

Sie können weiterhin Threads in parallelen Blöcken synchronisieren, sodass das Ergebnis ähnlich ist.Tatsächlich warten alle Threads am Ende einer omp for-Klausel standardmäßig auf einander, so dass dies die Sache noch einfacher macht.

#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