c++ - 扫描快速排序拆分

Question

我正在尝试使用 OpenMP 编写快速排序，但我陷入了拆分部分。文献上说这是一个并行的前缀操作。这是相关的部分:

  vector<int> under_pivot(values.size()), over_pivot(values.size());
  int count_under=0, count_over=0;
#pragma omp parallel for \
        reduction(+:count_under,count_over) \
        reduction(inscan,+:under_pivot,over_pivot)
  for (int i=0; i<values.size(); i++) {
    auto v = values[i];
#   pragma omp scan inclusive(under_pivot,over_pivot)
    {
      under_pivot[i] = count_under;
      over_pivot[i]  = count_over;
    }
    count_under += 1 ? v<pivot : 0;
    count_over  += 1 ? v>pivot : 0;
  }

(是的，我已经为 vector 定义了 + 运算符)。问题似乎是双重减少，如果我正确理解编译器错误:

quicksort.cxx:59:9: error: expected 'reduction' clause with the 'inscan' modifier
        reduction(+:count_under,count_over) \
        ^
quicksort.cxx:60:19: note: 'reduction' clause with 'inscan' modifier is used here
        reduction(inscan,+:under_pivot,over_pivot)
                  ^
1 error generated.

但我确实需要两次缩减，因为标量不在扫描中:扫描仅适用于数组。

具有完整代码的编译器资源管理器:https://godbolt.org/z/6xPrnGjMY

Answer 1

感谢@paleonix，这是正确的代码:

  int count_under=0, count_over=0;
  vector<int> under_pivot(values.size(),-1), over_pivot(values.size(),-1);
#pragma omp parallel for \
        reduction(inscan,+:count_under,count_over)
  for (int i=0; i<values.size(); i++) {
    under_pivot[i] = count_under;
    over_pivot[i]  = count_over;
#   pragma omp scan exclusive(count_under, count_over)
    {
      count_under += values[i]<pivot ? 1 : 0;
      count_over  += values[i]>pivot ? 1 : 0;
    }
  }
  int s = under_pivot.size();
  count_under = under_pivot.back()
    + ( under_pivot[s-2]==under_pivot[s-1] ? 1 : 0 );

  cout << "Splitting with " << count_under << " before the pivot\n";
  cout << "under: " << under_pivot << "\n";
  cout << "over:  " << over_pivot << "\n";

  vector<float> newvalues(values.size(),-1);
  for (int i=0; i<values.size(); i++) {
    auto v = values[i];
    int loc;
    try {
      if (v<pivot) {
        loc = under_pivot[i] ;
        newvalues.at(loc) = v;
      } else {
        loc = over_pivot[i]  + count_under;
        newvalues.at(loc) = v;
      }
    } catch (...) {
      cout << "element " << i << ": " << v << " maps to loc " << loc << "\n";
    }
  }

这似乎可行，但有几个奇怪的方面。例如，为什么归约变量在归约循环后为零？我尝试了 inclusive 扫描，结果除了垃圾什么都没有。

编辑 我有一个针对 count_under 的极端 hackish 解决方案，它补偿了一些奇怪的边界情况，但那是因为 clang13 在 scan 处理中有一个错误。让我找到一个更好的编译器。

无论如何，并行快速排序，我们来了.....