c - 用 C 编写的快速排序中的赛车条件与 OpenMP 并行

Question

在这个快速排序实现中，我认为我正在运行的程序进入了我无法理解的竞争状态。所以我转向 SO 社区寻求指导。

如果我在 quicksort() 中的 for 循环之前删除“#pragma omp parallel for private(i)”，那么它会正确排序。

下面是一个排序示例和代码。

Unsorted
3 6 7 5 3 5 6 2 9 1

Sorted
0 1 2 3 3 5 6 7 9 5 



    size_t average (size_t a, size_t b)
    {
            return (a + b) / 2;
    }

    void swap (int *array, size_t x, size_t y)
    {
            int tmp;
            tmp = array[x];
            array[x] = array[y];
            array[y] = tmp;
    }

    void quicksort (int *array, int left, int right)
    {
            int i, last;

            if (left >= right)
            {
                    return;
            }

            swap (array, left, average(left, right));
            last = left;

            #pragma omp parallel for private(i)
            for (i = left + 1; i <= right; i++)
            {
                    if (array[i] < array[left] )
                    {
                            #pragma omp critical
                            {
                                    last++;
                            }
                            swap(array, last, i);
                    }
            }

            swap (array, left, last);

            #pragma omp parallel sections
            {
                    #pragma omp section
                    {
                            quicksort(array,left,last-1);
                    }

                    #pragma omp section
                    {
                            quicksort (array, last+1, right);
                    }
            }
    }

Answer 1

您在该循环中执行的交换操作彼此深度依赖。此处无法获得并行性。

但是对于您使用两个并行部分开发的分支并行性，这应该不是必需的。你有这方面的性能问题吗？