c++ - std::map 上的自定义 omp 减少
问题描述
所以我遇到的问题或多或少如下:
我有一组相对较大的数据,其中始终包含一对标识符和一个与之相关的值。因此,存在相对较少的不同但任意的标识符。
在 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 缩减?
解决方案
所以我自己找到了答案:有两种方法可以做到这一点,一种是自定义缩减,另一种是关键部分。其中我目前推荐后者,主要是因为前者在当前的 clang 编译器上被破坏(v9.0.0,修复已经在主干/主控器中)。
OpenMP 并行用于自定义缩减
解决问题的第一种方法是使用 OpenMP 缩减,通常如下所示:
// this does not work for maps!
#pragma omp parallel for reduction(+: mymap)
这段代码不会编译,因为+
没有为std::map
.
相反,我们将不得不定义我们自己的归约。快速查看一些 OpenMP 规范 ( https://www.openmp.org/spec-html/5.0/openmpsu107.html ) 揭示了用于定义自定义缩减的以下语法:
#pragma omp declare reduction(reduction-identifier : typename-list :
combiner) [initializer-clause] newline
- 减少标识符:这是我们可以为我们的自定义减少指定的名称。
- typename-list:这是一个定义了这个缩减的类型名的列表。对我们来说这是
std::map<size_t, double>
- combiner:这是表达式,它进行实际的归约。它将
omp_in
andomp_out
作为输入,并且应该将组合结果存储在omp_out
. 对于简单的+
归约,这是omp_out += omp_in
. - 初始化子句:这是一个可选的表达式,应该是
initializer(expression)
. 如果它缺失,则归约变量的线程本地副本默认初始化。如果 is 存在,则表达式必须具有 的形式omp_priv = initializer
。omp_priv = function-name(argument-list)
它也可能使用omp_orig
,它对应于归约变量的初始值。 - 在 pragma 的末尾需要一个换行符。
在这种情况下,我们想要添加两个具有相同键的映射的值。这可以在这样的函数中完成:
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;
}
}
如前所述,线程局部变量通常是默认初始化的。std::map
然而,对于默认初始化是不希望的。相反,每个线程局部变量都应该使用已经存在的映射进行初始化。这可以在初始化程序内部指定,因此我们的 pragma 如下所示:
#pragma omp declare reduction( \
mapAdd : \
std::map<size_t, double> : \
mapAdd(omp_out, omp_in) \
) \
initializer (omp_priv=omp_orig)
它可以用于omp parallel for
上面的:
#pragma omp parallel for reduction(mapAdd : mymap)
for (size_t i = 0; i < typeDoubleVec.size(); ++i) {
mymap.at(typeDoubleVec[i].first) += typeDoubleVec[i].second;
}
不足之处
这不适用于当前的 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
在自定义缩减中使用 lambdas
标准中未指定在自定义 OpenMP 缩减中使用 lambda(根据https://gcc.gnu.org/bugzilla/show_bug.cgi?id=60228)。因此,我不建议这样做。但是,它确实适用于当前的 intel 编译器,并且将适用于 clang 编译器的下一个版本(9.0.1 或 10)。GCC 还不支持它(参见:https ://gcc.gnu.org/bugzilla/show_bug.cgi?id=60228 )。
使用临界区
避免减少需要的一种方法是在非常基本的级别上重现它们,即我们为每个线程创建一个本地副本,然后在关键部分内手动累积结果。这样做的好处是,它更容易阅读,但比通过自定义缩减的解决方案更慢,因为没有实现扇入。
这种方法的解决方案如下所示:
template <class vectype, class typevectype>
std::map<size_t, double> foo(const vectype &typeDoubleVec,
const typevectype &typevec) {
std::map<size_t, double> mymap;
// ensure that mymap has all elements of myvec.
for (auto &elem : typevec) {
Does anyone know how to speed this up with OpenMP? The way I see this working is that you need a custom OpenMP reduction?
mymap[elem];
}
#pragma omp parallel default(none) shared(typeDoubleVec, mymap)
{
// we create a local copy of mymap for each thread!
auto localmap = mymap;
#pragma omp for
// iterate over the vector and add them to the local map
for (size_t i = 0; i < typeDoubleVec.size(); ++i) {
localmap.at(typeDoubleVec[i].first) += typeDoubleVec[i].second;
}
#pragma omp critical
// sum up the local map to the global map using a critical section
mapAdd(mymap, localmap);
}
return mymap;
}
编码
使用自定义缩减的代码可以在https://gist.github.com/SteffenSeckler/404c214bcccf506d261264672e2b9341找到
使用https://gist.github.com/SteffenSeckler/91943b881677f3cbe7b2d7d475471ee8的关键部分的代码
附言
感谢您将其拆分为 Q+A 的反馈
推荐阅读
- android - 制作动画时如何将视图置于前面?
- android - 穿戴 OS 动画 Android
- xamarin.forms - 如何在不阻塞用户界面的情况下从 Web 服务带来的数据创建 TabbedPage?
- android - 在实施 firebase 后,许多导入语句突然变得未使用并且无法解析许多符号
- botframework - Microsoft Healthbot API 获取场景堆栈信息
- javascript - 在函数中调用 React Hook “useSelector”
- save - PIL 使用没有文件名的文件对象保存
- c++ - 在 msvc 调试模式下堆栈中有 cdcdcdcd 是否正常
- mysql - 如何使用外键执行 MySQL 批量插入并在无效时设置为 NULL
- ruby - 如何优化 HTTP::Headers.normalize_header?