Jak wykonać równoległość do pętli while i while w openmp?

Question

Próbuję uczyć się programowania równoległego z OpenMP i jestem zainteresowany parallelizing następujące do while pętlę z kilku while pętli wewnątrz niego:

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

Nie rzeczywiście zorientowali się, jak parallelize while i do while w pętlach, nie można znaleźć żadnego zasobu, w którym opisuje on w sposób szczegółowy równoległościanie pętli while i do while. Znalazłem instrukcje dla pętli for, ale nie mogłem założyć, że pętle z tego powodu są while i do while. Czy mógłbyś opisać, w jaki sposób mogę zrównoleglić te pętle, które tutaj podałem?

EDIT

I przekształca pętli do następnego kodu, w którym stosuje się tylko for pętli do while.

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

Ten kod działa poprawnie i daje prawidłowy wynik, ale kiedy próbowałem parallelize części wyżej podanej kodu poprzez zmianę dwóch pierwszych for pętle na następujące kwestie:

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

Prędkość jest gorszy niż nierównoległy kod. Pomóż mi zidentyfikować mój problem.

Dzięki

Answer 1

Przede wszystkim algorytmy sortowania są bardzo trudne do parallelize z OpenMP równoległych pętli. Wynika to z faktu, że liczba wyzwolonych pętli nie jest deterministyczna, ale zależy od wartości zestawu wejściowego, które są odczytywane w każdej iteracji.

Nie sądzę, że warunki w pętli, takie jak data[left] <= pivot, będą dobrze działać, ponieważ biblioteka OpenMP nie wie dokładnie, jak podzielić przestrzeń iteracyjną między wątki.

Jeśli nadal interesują Cię algorytmy sortowania równoległego, proponuję najpierw zapoznać się z literaturą, aby zobaczyć te algorytmy, które naprawdę warto wdrożyć ze względu na ich skalowalność. Jeśli chcesz po prostu nauczyć się OpenMP, proponuję zacząć od łatwiejszych algorytmów, takich jak bucket-sort, gdzie liczba wiaderek jest dobrze znana i nie często się zmienia.

W odniesieniu do przykładu, który próbujesz zrównoleglić, pętle while nie są bezpośrednio obsługiwane przez OpenMP, ponieważ liczba iteracji (liczba wyzwolonych pętli) nie jest deterministyczna (w przeciwnym razie można je łatwo przekształcić w pętle for). Dlatego nie jest możliwe rozpowszechnianie iteracji wśród wątków. Ponadto często sprawdza się w pętlach podczas sprawdzania warunku przy użyciu wyniku ostatniej iteracji. Jest to nazywane Read-after-Write lub true-dependency i nie może być zrównoleglone.

Twój problem spowolnienia może zostać złagodzony, jeśli spróbujesz zminimalizować liczbę klauzul omp parallel. Ponadto spróbuj przenieść je ze wszystkich swoich pętli. Te klauzule mogą tworzyć i łączyć dodatkowe wątki używane w równoległych częściach kodu, co jest kosztowne.

Nadal można synchronizować wątki wewnątrz bloków równoległych, aby wynik był podobny.W rzeczywistości wszystkie wątki domyślnie czekają na końcu na końcu klauzuli omp for, dzięki czemu jest jeszcze łatwiej.

#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