c++ - 如何在 openmp 中并行执行 while 和 while 循环？

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 不直接支持循环，因为迭代次数(循环次数)不是确定性的(否则，很容易将它们转换为 for 循环)。因此，不可能在线程之间分配迭代。此外，while 循环通常使用上一次迭代的结果来检查条件。这称为写后读 或真正的依赖性，无法并行化。

如果您尽量减少 omp parallel 的数量，您的减速问题可能会得到缓解条款。此外，尝试将它们移出所有循环。这些子句可能会创建并加入在代码的并行部分中使用的额外线程，这是非常昂贵的。

您仍然可以在并行 block 内同步线程，因此结果是相似的。事实上，所有线程都在 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