并行迭代器

Question

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

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

为此可以使用迭代器吗？迭代器应该如何看起来像启用并行访问？你会建议在这种情况下使用迭代器还是反对？

Answer 1

OpenMP并行循环不能很好地与迭代器一起玩。你需要在你的图表类上实现一个索引机制（operator[]）。

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

Answer 2

这是读写器问题的变体。

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

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

您需要决定写入该结构对程序的意义，算法明智，然后适当地实现读取/写入锁定。

Answer 3

让我展开我的评论。除非您的目标是跨平台兼容性，并且您希望代码也可以编译并使用MS Visual C++，否则您可以通过使用显式OpenMP任务来抵消为图对象提供“线性”迭代器的复杂性。 OpenMP 3.0中引入了显式任务（因此即使在2012年，它也不受MSVC的支持，它只符合更早的规范）。任务是可以并行执行的代码块。它们由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行走树时，它会产生排队的任务。在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区域内使用明确的任务同步。

Answer 4

如果它们是树木，那么你可能会想要在欧拉巡回遍历​​上比“迭代器”更多地考虑扫描。 http://en.wikipedia.org/wiki/Euler_tour_technique

我希望我有斯捷潘诺夫的书在我面前。我记得他简短地触及它。

Answer 5

我在Java中遇到了完全相同的问题。我已经实现的解决方案使用了hashmaps的hashmap。我还是不明白，为什么在标准库，不要让我们做多线程的迭代器...... 你可以阅读我的问题，我的回答（用链接的Java代码）一起在这里：

Scalable way to access every element of ConcurrentHashMap<Element, Boolean> exactly once