在递归函数上的OpenMP并行化

Question

我正在尝试使用并行化来提高绘制具有层次排序对象的3D场景的刷新率。场景绘制算法首先递归地遍历对象树，并从中构建绘制场景所需的有序数据的有序数组。然后它多次遍历该数组以绘制对象/覆盖等。从我读到的OpenGL不是一个线程安全的API，我假设数组遍历/绘图代码必须在主线程上完成，但我我想我可能能够并行化填充数组的递归函数。关键问题是必须按照对象在场景中出现的顺序填充数组，因此所有将给定对象与数组索引相关联的功能必须按正确的顺序完成，但是一旦分配了数组索引，我可以使用工作线程填充该数组元素的数据（这不一定是一个简单的操作）。所以这是我想要的伪代码。我希望你能理解xml-ish线程语法。

recursivepopulatearray(theobject)
{
  <main thread>
  for each child of theobject
  {
     assign array index
     <child thread(s)>
       populate array element for child object
     </child thread(s)>
     recursivepopulatearray(childobject)
  }
  </main thread>
}

那么，是否可以使用OpenMP执行此操作，如果是这样，怎么做？是否有其他并行化库可以更好地处理这个问题？

附录：回应 Davide's请求进一步澄清，让我详细解释一下。假设场景的排序如下：

-Bicycle Frame
  - Handle Bars 
  - Front Wheel
  - Back Wheel
-Car Frame
  - Front Left Wheel
  - Front Right Wheel
  - Back Left Wheel
  - Back Right Wheel

现在，这些对象中的每一个都有很多与之相关的数据，即位置，旋转，大小，不同的绘图参数等。另外，我需要在这个场景上进行多次传递才能正确绘制它。一个通道绘制对象的形状，另一个通道绘制描述对象的文本，另一个通道绘制对象之间的连接/关联（如果有）。无论如何，如果我必须多次访问它，从这些不同的对象中获取所有绘图数据是相当慢的，所以我决定使用一个通道将所有数据缓存到一维数组中，然后实际所有绘图传递只看数组。问题在于，因为我需要以正确的顺序进行OpenGL推送/弹出，所以数组必须处于代表树层次结构的正确深度优先搜索顺序中。在上面的示例中，必须按如下方式对数组进行排序：

index 0: Bicycle Frame
index 1: Handle Bars 
index 2: Front Wheel
index 3: Back Wheel
index 4: Car Frame
index 5: Front Left Wheel
index 6: Front Right Wheel
index 7: Back Left Wheel
index 8: Back Right Wheel

因此，必须正确地序列化数组的顺序，但是一旦我正确地分配了该顺序，我就可以并行化数组的填充。例如，一旦我将自行车框架分配给索引0并将把手杆分配给索引1，一个线程可以为自行车框架填充数组元素，而另一个线程则为句柄条填充数组元素。

好的，我想澄清这一点，我已经回答了我自己的问题，所以感谢Davide。所以我发布了自己的答案。

Answer 1

这是一段应该有效的修改过的伪代码。

populatearray(thescene)
{
  recursivepopulatearray(thescene)

  #pragma omp parallel for
  for each element in array
    populate array element based on associated object
}

recursivepopulatearray(theobject)
{
  for each childobject in theobject
  {
     assign array index and associate element with childobject
     recursivepopulatearray(childobject)
  }
}

Answer 2

我认为你应该更好地澄清你的问题（例如，必须连续完成什么以及为什么这样做）

OpenMP（与许多其他并行化库一样）确实不保证各个并行部分的执行顺序，并且因为它们是真正并行的（在多核机器上）可能存在竞争条件如果不同的部分写相同的数据。如果你的问题没问题，你肯定可以使用它。

Answer 3

gbjbaanb提及，您可以轻松完成此操作 - 它只需要一个pragma语句来并行化它。

但是，有几点需要注意：

首先，你提到这里的订单很重要。如果您需要在展平层次结构时保留排序，那么并行化（在此级别）将会出现问题。你可能会完全失去你的订单。

此外，并行化递归函数存在许多问题。举一个极端的例子 - 假设你有一台双核机器，你有一棵树，其中每一个“父母”节点有4个孩子。如果树很深，那么你非常非常快地“过度并行化”。这个问题，通常会使事情变得更糟，而不是更好，表现更明智。

如果您要这样做，您应该放置一个级别参数，并且只能并行化前几个级别。以我的4个孩子每个父母为例，如果你并行化前两个级别，你已经将它分成16个并行块（从4个并行块调用）。

从你提到的内容来看，我将这一部分保留为序列，而不是你所提到的第二部分：

＆quot;然后它遍历该数组多次以绘制对象/叠加等。“

这听起来像是一个理想的并行化地点。

Answer 4

并行化子线程，只需在循环之前放置一个pragma：

#pragma omp parallel for
for (i=0; i < elements; i++) 
{
}

完成工作。

现在，你是对的，你不能让任何线程库以完全并行的方式在另一个之前做一点（显然！），而openMP没有'lock'或'wait'功能（它确实如此）有一个'等待所有完成'关键字 - 屏障），它不是为了模拟一个线程库，但它确实允许你存储“外部”的值。并行部分，并将某些部分标记为“仅单线程”（Ordered关键字），这样可以帮助您在并行循环中分配索引，而其他线程正在分配元素。

查看入门指南

如果您使用的是Visual C ++，则还需要在编译器构建设置中设置/ omp标志。