并行迭代器
我正在设计一个供并行代码(使用OpenMP)使用的C++数据结构(用于图形)。
假设我想要一个方法，可以在所有元素(节点)上进行迭代。当然，这个迭代将被并行化。
有没有可能使用迭代器来达到这个目的？支持并行访问的迭代器应该是什么样子的？在这种情况下，您建议使用迭代器还是不使用迭代器？
回答 5
Stack Overflow用户
发布于 2012-11-05 21:42:10
OpenMP并行循环不能很好地处理迭代器。你需要在你的图形类上实现一个索引机制(operator[]接受一个整型参数)。
如果您确实想使用OpenMP 3.0迭代器支持，请确保您有一个随机访问迭代器。将其实现为指向节点或边的指针是最简单的选择。
Stack Overflow用户
发布于 2012-11-06 17:24:12
让我扩展一下我的评论。除非您的目标是跨平台兼容性，并且希望您的代码也能编译和使用MS Visual C++，否则可以通过使用显式OpenMP任务来抵消为图形对象提供“线性”迭代器的复杂性。显式任务是在MSVC3.0中引入的(因此OpenMP不支持它，因为它只符合一个更早的规范，即使在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遍历这三个节点，并为每个节点创建一个任务。只有在parallel区域内使用(静态作用域)，或者在从parallel区域(直接或间接)调用的代码中使用(动态作用域)时，task构造才有效。当traverse_and_make_tasks遍历树时，它会生成排队的任务。在parallel区域的末尾有一个隐式的任务调度点，这大致意味着在执行完所有任务之前，不会在区域结束后继续执行。还可以使用#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区域内显式任务同步的使用。
Stack Overflow用户
发布于 2012-11-05 21:46:27
这是读取器/写入器问题的变体。
但是如果它是可变的，那么迭代器可能会与对结构所做的更改发生冲突。一种解决方案是为每个迭代器创建一个只读的、不可变的结构副本，但在创建迭代器之后，该迭代器将不会注册对结构所做的任何更改。第二种解决方案是实现写时复制，这将导致对结构的所有写操作都创建一个新对象，当前运行的迭代器在旧对象上运行。
您需要从算法的角度确定对该结构的写入对程序意味着什么，然后适当地实现读/写锁定。
https://stackoverflow.com/questions/13233274
复制相似问题
腾讯云开发者
