std::map 上的自定义 Omp 减少

Question

所以我遇到的问题大致如下：

我有一个相对较大的数据集，其中始终包含一对标识符和与其相关的值。因此，存在相对较少的不同但任意的标识符。

在 C++ 中，这可能看起来像一个std::vector<std::pair<size_t, double> >.

我现在想要生成一个std::map，它告诉我们每个标识符的所有值的总和，因此在本例中为std::map<size_t, double>。

所以对于输入

std::vector<std::pair<size_t, double>> typeDoubleVec{{1, 2.}, {3, 4.}, {1, 3.}, {3, 5.}, {2, 1.}};

我想要一张等于：

std::map<size_t, double> result{{1, 5.}, {2, 1.}, {3, 9.}}

完成这项工作的函数如下所示。因此，第二个输入向量指定存在哪些标识符：

std::map<size_t, double> foo(const std::vector<std::pair<size_t, double>> &typeDoubleVec, const std::vector<size_t> &typeVec) {
  // create the map that contains our return values.
  std::map<size_t, double> mymap;

  // ensure that mymap contains all identifiers.
  for (auto &elem : typeVec) {
    mymap[elem];
  }

  // iterate over the elements
  for (size_t i = 0; i < typeDoubleVec.size(); ++i) {
    mymap.at(typeDoubleVec[i].first) += typeDoubleVec[i].second;
  }
  return mymap;
}

有谁知道如何使用 OpenMP 加快速度？我认为这种工作方式是您需要自定义 OpenMP 缩减？

Answer 1

所以我自己找到了答案：有两种方法可以做到这一点，一种是自定义缩减，第二种是关键部分。其中我目前推荐后者，主要是因为前者在当前的 clang 编译器上被破坏了（v9.0.0，修复已经在 trunk/master 中）。

OpenMP 并行用于自定义缩减

解决该问题的第一种方法是使用 OpenMP 缩减，通常如下所示：

// this does not work for maps!
#pragma omp parallel for reduction(+: mymap)

这段代码被剪断将无法编译，因为+没有为std::map.

相反，我们必须定义我们自己的减少。快速浏览一些 OpenMP 规范 ( https://www.openmp.org/spec-html/5.1/openmpsu117.html#x152-1790002.21.5.7 ) 揭示了以下用于定义自定义缩减的语法：

#pragma omp declare reduction(reduction-identifier : typename-list : 
combiner) [initializer-clause] newline

• 还原标识符：这是我们可以为自定义还原指定的名称。
• typename-list：这是定义此缩减的类型名称列表。对我们来说这是std::map<size_t, double>
• 组合器：这是执行实际归约的表达式。它将omp_in和omp_out作为输入，并将组合结果存储在 中omp_out。对于简单的+约简，这是omp_out += omp_in。
• 初始化子句：这是一个可选表达式，应采用 形式initializer(expression)。如果缺少，则默认初始化归约变量的线程本地副本。如果存在，则表达式必须具有omp_priv = initializeror 的形式omp_priv = function-name(argument-list)。它还可能使用omp_orig，它对应于归约变量的初始值。
• 编译指示末尾需要换行符。

在本例中，我们想要将两个具有相同键的映射的值相加。这可以在如下函数中完成：

#pragma omp declare reduction(reduction-identifier : typename-list : 
combiner) [initializer-clause] newline

如前所述，线程局部变量通常是默认初始化的。然而，对于std::map默认初始化来说，这是不需要的。相反，每个线程局部变量应该使用已经存在的映射进行初始化。这可以在初始化程序内部指定，因此我们的编译指示如下所示：

void mapAdd(std::map<size_t, double> &inout, std::map<size_t, double> &in) {
  for (auto initer = in.begin(), outiter = inout.begin(); initer != in.end(); ++initer, ++outiter) {
    outiter->second += initer->second;
  }
}

它可以用于omp parallel for上面的：

#pragma omp declare reduction(                             \
                              mapAdd :                     \
                              std::map<size_t, double> :   \
                              mapAdd(omp_out, omp_in)      \
                             )                             \
                    initializer (omp_priv=omp_orig)

不足之处

这不适用于当前的 clang 编译器。它编译得很好，但它产生了一个分段错误，经过一番研究，我发现这不是我的错，而是一个编译器错误，因为相同的程序在当前的 gcc 和 intel 编译器上工作。

此外，当在模板函数内部声明 OpenMP 缩减时，clang 编译器会出现问题（未定义的引用），因为它不会实例化 OpenMP 缩减内部所需的所有函数。

另请参阅以下问题：

• clang：（修复）使用自定义 openmp 减少的段错误：https://bugs.llvm.org/show_bug.cgi ?id=44134
• clang：（已修复）openmp 的编译问题声明减少了模板函数：https://bugs.llvm.org/show_bug.cgi ?id=44133

在自定义归约中使用 lambda

标准中未指定自定义 OpenMP 缩减内部 lambda 的使用（根据https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60228）。因此我不建议这样做。然而，它确实可以与当前的英特尔编译器一起使用，并且可以与下一个版本的 clang 编译器（9.0.1 或 10）一起使用。GCC 尚不支持它（请参阅： https: //gcc.gnu.org/bugzilla/show_bug.cgi? id =60228）。

使用关键部分

避免减少需求的一种方法是在非常基本的级别上重现它们，即我们为每个线程创建一个本地副本，然后在关键部分内手动累积结果。这样做的优点是，它更容易阅读，但可能比通过自定义缩减的解决方案慢一些，因为没有实现扇入。

采用这种方法的解决方案如下所示：

#pragma omp parallel for reduction(mapAdd : mymap)
  for (size_t i = 0; i < typeDoubleVec.size(); ++i) {
    mymap.at(typeDoubleVec[i].first) += typeDoubleVec[i].second;
  }

代码

使用自定义缩减的代码可以在https://gist.github.com/SteffenSeckler/404c214bcccf506d261264672e2b9341找到

使用关键部分的代码位于https://gist.github.com/SteffenSeckler/91943b881677f3cbe7b2d7d475471ee8

聚苯乙烯

感谢您将其分为 Q+A 的反馈