5

我正在设计一个 C++ 数据结构（用于图形），供并行代码（使用 OpenMP）使用。

假设我想要一个方法可以对所有元素（节点）进行迭代。当然，这个迭代将被并行化。

是否可以为此目的使用迭代器？迭代器应该如何实现并行访问？在这种情况下，您会建议还是反对使用迭代器？

4

5 回答 5

6

OpenMP 并行循环不能很好地与迭代器配合使用。您需要operator[]在图形类上实现索引机制（采用整数参数）。

如果您确实想使用 OpenMP 3.0 迭代器支持，请确保您有一个随机访问迭代器。将其实现为指向节点或边的指针是最简单的选择。

于 2012-11-05T13:42:10.443 回答
3

让我扩展我的评论。除非您以跨平台兼容性为目标，并且您希望您的代码也可以编译和使用 MS Visual C++，否则您可以通过使用显式 OpenMP 任务来抵消为图形对象提供“线性”迭代器的复杂性。OpenMP 3.0 中引入了显式任务（因此 MSVC 不支持它，它只符合更早的规范，即使在 2012 年也是如此）。任务是可以并行执行的代码块。它们由task构造创建：

... other code ...
#pragma omp task
{
   ... task code ...
}
... other code ...

每当执行流程到达标记区域时，就会创建一个新的任务对象并将其放入任务队列中。然后在某个时间点，空闲线程从队列中抓取一个任务并开始执行它。任务与 OpenMP 部分很相似，因为它们继承了它们的环境，并且它们可以以与代码的串行版本不同的顺序运行。

通过任务，可以实现递归算法，也可以轻松使用不提供随机迭代器的 C++ 容器。例如，二叉树的遍历可以像这样使用任务执行：

// Helper routine to traverse a tree and create one task for each node
void traverse_and_make_tasks(tree_node *tn)
{
   if (tn == NULL)
      return;

   // Create a task to process the node
   #pragma omp task
   {
      very_long_computation(tn->value);
   }

   traverse_and_make_tasks(tn->left);
   traverse_and_make_tasks(tn->right);
}

... main code ...

// Disable dynamic teams
omp_set_dynamic(0);

#pragma omp parallel
{
   #pragma omp single nowait
   {
      traverse_and_make_tasks(tree->root_node);
   }
}

（需要禁用动态团队以防止 OpenMP 运行时过于智能并parallel单线程执行区域）

这是一种非常常见的任务模式，称为单一/串行生产者。每当执行进入该parallel区域时，单个线程就会执行single构造中的代码。traverse_and_make_tasks它用三个的根节点调用。traverse_and_make_tasks遍历三个并为每个节点创建一个任务。该task构造仅在parallel区域内使用（静态范围）或在从区域内（直接或间接）调用的代码parallel（动态范围）中使用时才有效。随着traverse_and_make_tasks树的走动，它产生排队的任务。在结束时parallelregion 有一个隐式的任务调度点，这大致意味着在所有任务都执行完之前，执行不会超过 region 的末尾。也可以使用 将显式点放在平行区域内#pragma omp taskwait。它的工作方式类似于barrier- 执行“块”，直到所有任务都已处理完毕。

另一种常见的模式是并行生成器，其中任务是并行生成的。上面的示例代码可以通过对 的简单修改轻松转换为并行生产者traverse_and_make_tasks：

void traverse_and_make_tasks(tree_node *tn)
{
   if (tn == NULL)
      return;

   #pragma omp task
   traverse_and_make_tasks(tn->left);
   #pragma omp task
   traverse_and_make_tasks(tn->right);

   // Create a task to process the node
   very_long_computation(tn->value);
}

这个版本的代码在每个节点上创建了两个任务——一个处理左后代，一个处理右后代。如果这是串行代码，它将自下而上遍历树。然而，在并行情况下，任务排队会或多或少地导致从上到下的遍历。

还有许多其他可能的使用任务的场景。也可以在非递归情况下使用它们来处理不提供随机迭代器的容器，这是工作共享构造所要求的for：

typedef container_type::iterator citer;

container_type container;
... push some values in the container ...

#pragma omp parallel
{
   #pragma omp single nowait
   {
      for (citer it = container.begin(); it != container.end(); it++)
         #pragma omp task
         process(*it);
   }

   #pragma omp taskwait

   // process more
   #pragma omp single nowait
   {
      for (citer it = container.begin(); it != container.end(); it++)
         #pragma omp task
         process_more(*it);
   }
}

此示例还说明了在parallel区域内使用显式任务同步。

于 2012-11-06T09:24:11.607 回答
1

这是读写器问题的一种变体。

这取决于该结构是否可变。如果没有，那么你就走吧，尽可能多地并行阅读。

但如果它是可变的，那么迭代器可能会与对结构所做的更改发生冲突。例如，迭代器可能会到达当前正在删除的元素。一种解决方案是为每个迭代器制作一个只读的、不可变的结构副本，但是在创建迭代器之后，该迭代器不会注册对结构所做的任何更改。第二种解决方案是进行写时复制实现，这将导致对结构的所有写入创建一个新对象，当前运行的迭代器在旧对象上运行。

您需要根据算法确定对该结构的写入对您的程序意味着什么，然后适当地实现读/写锁定。

于 2012-11-05T13:46:26.520 回答
1

如果它们是树，您可能会想更多地考虑 Euler Tour Traversals 上的扫描而不是“迭代器”。http://en.wikipedia.org/wiki/Euler_tour_technique

我希望我面前有斯捷潘诺夫的书。我记得他曾短暂地谈到过它。

于 2012-11-15T21:17:01.453 回答
0

我在Java中遇到了完全相同的问题。我实施的解决方案使用“hashmaps 的 hashmap”。我仍然不明白为什么标准库不允许我们进行多线程迭代器...您可以在此处阅读我的问题以及我的答案（带有指向 Java 代码的链接）：

一次访问 ConcurrentHashMap<Element, Boolean> 的每个元素的可扩展方式

于 2013-11-23T15:38:04.460 回答