如何在OpenMP中并行化do while和while循环？

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循环的情况。所以，你能描述一下我如何并行化我提供的这些循环吗？

编辑: 我已将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;
            }
        }
    }

速度比非并行化的代码慢。请帮我找出问题所在。

谢谢。

- the_naive

---

“length” 的典型值是多少？ - damienfrancois

在使用OpenMP之前，先简单想一想任务是否可以并行完成。可以将其类比为你有几个人可以分配任务给他们，即线程。那么，在while循环中应该怎么做呢？while循环中到底有哪些内容可以并行处理呢？对于for循环，我们可以轻松地说“for循环遍历了一个索引，针对每个索引，计算都可以并行处理”。这样我们就能给每个线程分配一个索引，或者让它们从一个桶里取出一个索引，处理完后再取下一个。但是像这样一个while(true){ if(condition){break;} do_stuff; }的循环中，并没有通用的概念可以依靠。 - Aziuth

关于排序，使用归并排序怎么样？将数组分成T个区间，每个区间由一个线程处理，然后按顺序合并。合并的时间复杂度为O(N)，对区间进行归并排序的时间复杂度通常为O(NlogN)，但是它们是独立的，因此可以并行处理。对于大规模的N，合并过程被区间内部的排序所主导。如果你只是想要并行排序，可以使用现有的库，而不必自己实现。使用好的库可以获得更好的性能。如果你只是想把它作为练习，那就另当别论了。 - Aziuth

（请注意，“可以并行处理”是一个理论概念 - 对于大型数组，您将遇到它们共享同一缓存的问题。这就是为什么您需要库的*主要原因，编写这些库的人知道这个问题，可能会甚至说明您应该使用多少线程 - 很可能不是您的计算机可以创建的最大数量，并且取决于您的处理器和缓存类型。） - Aziuth

Answer 1

首先，使用OpenMP并行循环排序算法非常难以并行化。这是因为循环的迭代次数不确定，而是取决于每次迭代读取的输入集值。

我认为像data[left] <= pivot这样的循环条件不会很好地工作，因为OpenMP库不知道如何精确地将迭代空间在线程之间分区。

如果您仍然对并行排序算法感兴趣，则建议首先阅读文献，了解那些由于可扩展性而真正值得实现的算法。如果您只想学习OpenMP，请从更简单的算法开始，例如桶排序，其中桶的数量是众所周知且不经常更改的。

关于您尝试并行化的示例，OpenMP不直接支持while循环，因为迭代次数（循环旅程计数）不确定（否则，很容易将它们转换为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 

- Jorge Bellon