0

我正在使用python编写一个理想的气体模拟器，现在碰撞检测是程序中最密集的部分。不过目前，我只使用了我的 8 个内核中的一个。（我使用的是 i7 3770 @ 3.4GHz）

经过最少的谷歌搜索，我找到了 python (2.7.4) 的多处理模块。我已经试过了。经过一番思考，我意识到我唯一可以真正并行运行的是在这里，我循环遍历所有粒子以检测碰撞：

for ball in self.Objects:   
        if not foo == ball:
            foo.CollideBall(ball, self.InternalTimestep)

这里 foo 是我正在针对所有其他粒子进行测试的粒子。所以我试着这样做：

for ball in self.Objects:   
        if not foo == ball:
            p = multiprocessing.Process(target=foo.CollideBall, args=(ball, self.InternalTimestep))
            p.start()

虽然程序运行得更快了一点，但它仍然最大程度地使用了 1.5 个内核，其余的只是处于空闲状态，也没有检测到任何冲突！我已经读过，如果你一次创建太多进程（超过核心数量），那么你会得到一个积压（这是一个 196 个粒子的循环），所以这可能解释了速度比我预期的要低，但是它没有解释我仍然没有使用所有核心的事实！

反正就是太慢了！！！那么有没有一种方法可以创建 8 个进程，并且只有在运行的进程少于 8 个时才创建一个新进程？这甚至能解决我的问题吗？以及如何使用我所有的内核/为什么这段代码还没有？

我昨天才发现python中的多处理，所以恐怕必须向我说明任何答案。

感谢您的帮助！

- -编辑 - -

作为对 Carson 的回应，我尝试在 p.start 之后直接添加 p.join，这降低了程序的速度。不是每个周期花费 o.2 秒，而是每个周期花费 24 秒！

4

2 回答 2

3

据我了解，您可以针对所有其他粒子测试一个粒子，然后依次对每个粒子执行该操作。基于此，我想说您的问题是您尝试优化代码以在所有内核上工作，而不尝试优化代码本身。

相反，您可以对粒子进行分区，以便仅检查彼此靠近的粒子。这样做的一种可能方法是四叉树：参见http://en.wikipedia.org/wiki/Quadtree。

在第二步中，您可以并行化所有内容。对于四叉树，您手动解决最高级别并为每个子树创建一个新进程。通过这种方式，这些进程相互独立并且不会阻塞。我希望通过四叉树实现二次加速（考虑当前运行时间的平方根），并通过并行化实现进一步的线性加速（除以进程数）。

抱歉，我无法用 Python 拼写出来。

于 2013-11-05T09:38:44.353 回答
0

使用工作四叉树，您可以设置线程池（作为一个类）并定义分配给各个线程（另一个类，如果可能来自线程框架）的作业（另一个类）。在您的情况下，作业包含必须检查的四叉树节点列表。最初，每个顶级四叉树节点（2D 中的 4 个/3D 中的 8 个）驻留在自己的作业中。

因此，您最多可以有 4 个（分别为 8 个）线程，每个线程检查四叉树的一个独立子树。如果您需要更多线程来充分利用您的机器处理能力，您可以让线程将其部分作业放回线程池，如果它们遇到许多深层子树。

为此，我将使用 BFS（广度优先搜索）和作业中的四叉树节点列表。如果列表比预期的要长，我会把它的一部分放回线程池。数学/统计/随机方面的知识有助于找到预期长度的良好参数化。

我还编写了一个四叉树实现，它根据给定“世界”大小的预期对象数量和计算平均对象大小来参数化自身。

搜索开源项目 d-collide。虽然它在 C++ 中，但应该有一些有用的示例代码。但是请注意它的许可，因为它是 BSD 风格，所以没有太多要求。

我将其添加为第二个答案，因为第一个是关于优化您的代码以实现您的隐含目标：更好的运行时间（尽管它是通过更好的效率）

第二个答案是关于实现您的书面目标：更强的并行化。然而，四叉树启用了第二步，但不要指望第二次加速与第一步一样快。尤其是当涉及到许多对象时，没有什么比优化算法更好的了。但是不要迷失在微优化中：请参阅Canceling a Task is throwing an exception中的运行时讨论

于 2013-11-05T16:31:47.090 回答