Как распараллелить do while и while loop в openmp?

Question

Я пытаюсь научиться параллельное программирование с OpenMP, и я заинтересован в распараллеливание следующий do while цикл с несколькими while петли внутри него:

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

Я на самом деле не понял, как распараллелить while и do while петли, не удалось найти какой-либо ресурс, где он конкретно описывает, как распараллелить while и do while. Я нашел инструкции для петель for, но я не мог сделать никаких предположений для while и do while циклов. Итак, не могли бы вы описать, как я могу распараллелить эти циклы, которые я здесь представил?

РЕДАКТИРОВАТЬ

Я превратил do while петли в следующем код, где используются только for цикла.

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

Этот код прекрасно работает и дает правильный результат, но когда я попытался распараллеливание части выше указанного кода, путем изменения первых двух for петли на следующее:

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

Скорость хуже, чем нераспарализованный код. Пожалуйста, помогите мне определить мою проблему.

Благодаря

Answer 1

Прежде всего, алгоритмы сортировки очень трудно распараллеливания с OpenMP параллельных циклов. Это связано с тем, что счетчик циклов не является детерминированным, но зависит от входных заданных значений, которые читаются на каждой итерации.

Я не думаю, что условия цикла, такие как data[left] <= pivot, будут хорошо работать, поскольку библиотека OpenMP не знает точно, как разделить пространство итерации между потоками.

Если вы все еще заинтересованы в параллельных алгоритмах сортировки, я предлагаю вам сначала прочитать литературу, чтобы увидеть те алгоритмы, которые действительно стоит реализовать из-за их масштабируемости. Если вы просто хотите изучить OpenMP, я предлагаю вам начать с более простых алгоритмов, таких как bucket-sort, где количество ведер хорошо известно и не часто меняется.

Что касается примера, который вы пытаетесь распараллелить, то циклы while напрямую не поддерживаются OpenMP, поскольку количество итераций (количество циклов отключения) не является детерминированным (в противном случае их легко преобразовать в циклы). Поэтому невозможно распределить итерации между потоками. Кроме того, для циклов while проверяется условие, использующее результат последней итерации. Это называется Read-after-Write или true-dependency и не может быть распараллелен.

Возможно, проблема с замедлением может быть уменьшена, если вы попытаетесь свести к минимуму количество статей omp parallel. Кроме того, попробуйте переместить их из всех ваших петель. Эти предложения могут создавать и присоединяться к дополнительным потокам, которые используются в параллельных частях кода, что дорого.

Вы все еще можете синхронизировать потоки внутри параллельных блоков, чтобы результат был аналогичным.Фактически, все потоки ждут друг друга в конце предложения omp for по умолчанию, так что это делает вещи еще проще.

#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