如何在whilemp和while循环中并行化openmp？

Question

我想学习使用OpenMP并行编程和我感兴趣的几个while循环里面并行以下do 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循环。那么，请你描述一下我可以如何平行化我在这里提供的这个循环？

EDIT

我已经改变了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支持，因为循环次数（循环行程计数）不是确定性的（否则很容易将它们转换为for循环）。因此，不可能在线程之间分配迭代。另外，While循环使用最后一次迭代的结果来检查一个条件是很常见的。这称为后写后读或真相关并且不能并行化。

如果您尝试将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