9

我一直在修补 BSP 树一段时间，也在玩线程。将三角形添加到 BSP 树时，就有机会创建一个新线程以并行处理数据。

插入（三角形，bspnode）
{
  ……
  else if(三角形跨越 bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    插入（前端，bspnode.front）
    插入（背板，bspnode.back）
  }
  ……
}

上面的两个插入操作可以由两个线程执行，并且由于它们不会修改相同的数据，因此可以使用廉价的同步。

插入（三角形，bspnode）
{
  ……
  else if(三角形跨越 bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    句柄 = beginthread（插入（后件，bspnode.front））
    插入（前端，bspnode.back）
    如果（句柄）
    {
      等待线程（句柄）
    }
    别的
    {
      插入（后端，bspnode.front）
    }
  }
  ……
}

这种新方法尝试创建一个线程以并行完成操作，但如果无法创建线程也不应该失败（它将简单地恢复到原始算法）。

这是一种合理的编程习惯，还是我不正确地使用线程？我还没有找到任何关于这种技术的文献。我喜欢它倾向于充分利用我的 CPU（2 个内核），并且理论上可以扩展到任意数量的可用处理器。我不喜欢这可能会严重浪费 CPU 和内存。

4

3 回答 3

13

如果处理的某些部分正在等待外部的某些东西（用户输入、I/O、其他一些处理），那么线程会很棒——等待的线程可以继续等待，而没有等待的线程会继续等待。

但是，对于处理密集型任务，实际上比处理器多的线程会产生开销。看起来你的线程正在做所有的“CPU工作”，所以我会坚持每个核心一个线程——不过，测试以找到最佳数量。

产生的最大开销来自上下文切换（冻结一个线程并加载下一个线程的执行上下文），以及线程使用不同内存执行任务时的缓存未命中（如果您的线程可以有效地使用 CPU 缓存）。

于 2008-10-03T14:03:01.450 回答
2

您最好的选择是创建一个线程池，然后“透明地”使用它来添加节点。

例如，在程序启动时创建 2 个线程，让它们等待信号量或事件。当您有要添加的节点时，您将数据弹出到队列中，然后触发信号量。这唤醒了将数据从队列中弹出并执行处理的线程之一。（确保对队列的访问是线程安全的 - 最好与关键部分完全同步）。

由于在将数据复制到队列和运行额外线程方面有更多开销，因此应用程序的整体性能会变慢，但如果您以前在单核上运行，现在将在 2 核上运行。如果线程加工成本高。

于 2008-10-03T14:29:32.910 回答
0

当然，例如，Quicksort 可以很容易地进行多线程编程，并在多核系统上获得一些较大的性能提升，而在非多线程系统上获得一些小的性能损失。请记住，您现在添加了两次开销 - 一次用于堆栈保存递归，一次用于线程，因此如果您正在执行大量递归，那么它可能比非多线程方法更快地压倒系统。

于 2008-10-03T14:36:00.150 回答