c++ - C++中OpenMP编程嵌套循环的锁策略

Question

昨天我用一个大数据集(2000万个节点)测试了我的景观进化程序，毫无疑问，运行速度是 Not Acceptable 。在调试过程中，我注意到是某个函数拖慢了整个系统。所以我想给它添加多线程进程。

但是，该函数本身是一个带有指针迭代器的嵌套循环，我相信在此过程中必须锁定一些数据。

基本上我想做的是计算每个节点的贡献面积。贡献面积，顾名思义，是上游节点所有面积的乘积(总和)。

这是这两个函数的代码，

for( curnode = nodIter.FirstP(); nodIter.IsActive();
    curnode = nodIter.NextP() )  //iterating thru a linked-list of pointers to active stream nodes (*IsActive* returns a  bool value)
{
  CalcDRArea( curnode, curnode->getVArea() ); //calls another function and pass a pointer to current node  as well as a value of its VArea
}

---

void CalcDRArea( NodeClass *curnode, double addedArea )
{
  // As long as the current node is neither a boundary nor non-valid, add
  // _addedArea_ to its total drainage area and advance to the next node downstream

  while( (curnode->ReachBoundary() == NonBoundary) &&
        (curnode->valid()!=Nonvalid) )
  {
       curnode->AddDrArea( addedArea );  //*AddDrArea* is a simple inline function *`"drarea +=value"`*

    curnode = curnode->getDownStreammNeighbor();      // *getDownstrmNbr()* reruns a pointer to the downstream node
  }

}

这是节点及其流动方向的简单说明

A     B     C     D  
   \  |  /        |
E     F     G     H
      |           |
I     Q     K     L
      |        / 
M     N     O     P
//letters are stream nodes and slashes are their flowing directions

我的计划是在第一个函数 for 循环 的开头使用 OpenMP 实现多线程。理想情况下，它将创建多个线程来分别计算每个节点。

但是，如上图所示，后续进程可以处理流

A-> F -> Q -> N 
B-> F -> Q -> N 
C-> F -> Q -> N 

很简单，但是在多线程的情况下肯定会出问题。

根据我刚刚从 OpenMP 的文档中读到的内容，flush 和 lock 可能是执行此操作的正确方法，但我现在和那里仍然一无所知可能仍然是此循环中的其他潜在问题(例如 OpenMP 的 gcc 版本不支持“!=”)。

====更新====== 有两种区域:vArea，即每个节点的区域； drArea 是当前节点的面积与其所有上游节点的面积之和。 我想知道是否可以将当前函数更改为:

for( active node iterator）  
{
    if（currentNode.hasDownStreamNode）
    {
       downStreamNode.drArea += currentNode.vArea + currentNode.DrArea;
    }
    CurrentNode.drArea += currentNode.varea;
}

Answer 1

在担心并行性之前，您应该首先选择一个更好的算法。尽管在这种情况下实际上是一个与另一个一起去。

您想要一个复杂度为 O(N) 的动态规划解决方案，而不是当前的复杂度为 O(n^2) 的方法。直觉很简单，只需在树中的每个叶节点上调用以下方法:

def compute_value(node):
     if node.DrArea != 0: return node.DrArea
     total = node.vArea
     for n in node.upstream_nodes():
          total += compute_value(n)
     node.DrArea = total
     return node.DrArea

要了解为什么这样更有效，让我们看一下您的示例。现在你将 A 的值添加到 F、Q 和 N。然后你对 B 和 C 做同样的事情。所以你有 12 个添加操作。 另一方面，递归方法首先计算 A、B 和 C 的值，然后我们根据已知的 A、B 和 C 值计算 F。Q 从 F 计算，依此类推。所以这只有 8 个加法。基本上每个节点只将它的 total 值添加到它的所有子节点，而不是遍历整个子树并只添加它自己的值。

对于一个简单的顺序算法，您可以继续使用一个节点列表迭代地实现这个算法，这些节点的前辈都已经过评估(所以不是从叶子开始，而是从根节点开始)。这里最简单的并行实现是只使用并发队列和原子添加操作，尽管每个处理器使用一个普通队列和一些工作窃取在实践中可能是一个非常好的主意。