6

我正在尝试使用并行化来提高绘制具有分层排序对象的 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的要求,让我再详细解释一下。假设场景是这样排序的:

-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

因此,数组的顺序必须正确序列化,但是一旦我正确分配了该顺序,我就可以并行化数组的填充。例如,一旦我将 Bicycle Frame 分配给索引 0 并将 Handle Bars 分配给索引 1,一个线程可以填充 Bicycle Frame 的数组元素,而另一个线程填充 Handle Bars 的数组元素。

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

4

4 回答 4

1

我认为你应该更好地澄清你的问题(例如,究竟必须连续做什么以及为什么)

OpenMP(像许多其他并行化库一样)不保证各个并行部分的执行顺序,并且由于它们是真正并行的(在多核机器上),如果不同的部分写入相同的数据,可能会出现竞争条件。如果这对您的问题没问题,那么您当然可以使用它。

于 2009-05-07T17:24:16.387 回答
1

正如gbjbaanb 所提到的,您可以轻松地做到这一点 - 它只需要一个 pragma 语句来并行化它。

但是,有几点需要注意:

首先,您提到这里的顺序至关重要。如果您需要在扁平化层次结构中保留顺序,则并行化(在此级别)将是有问题的。您可能会完全失去您的订单。

此外,并行化递归函数有很多问题。举一个极端的例子——假设你有一台双核机器,并且你有一棵树,其中每个“父”节点都有 4 个子节点。如果树很深,你很快就会“过度并行化”问题,通常会使事情变得更糟,而不是更好,性能明智。

如果您要这样做,您可能应该放置一个级别参数,并且只并行化前几个级别。以我的 4 child-per-parent 示例为例,如果您并行化前 2 个级别,您已经将其分解为 16 个并行块(从 4 个并行块调用)。

从您提到的内容来看,我将把这部分留作连续的,并专注于您提到的第二部分:

“然后它会多次遍历该数组以绘制对象/叠加层等。”

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

于 2009-05-07T17:30:57.353 回答
0

要并行化子线程,只需在循环前添加一个编译指示:

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

任务完成。

现在,你是对的,你不能让任何线程库以完全并行的方式先做一点(显然!),并且 openMP 没有“锁定”或“等待”功能(它确实有一个“ wait for all to finish' 关键字 - Barrier),它不是为模拟线程库而设计的,但它确实允许您将值存储在并行部分“外部”,并将某些部分标记为“仅单线程”(Ordered 关键字)所以这可以帮助您在并行循环中分配索引,而其他线程正在分配元素。

查看入门指南

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

于 2009-05-07T17:17:42.347 回答
0

这是一段修改过的伪代码,应该可以工作。

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)
  }
}
于 2009-05-07T19:49:06.380 回答