15

我正在考虑编写一个物理模拟软件,其中每个物理元素都将在其自己的线程中进行模拟。

这种方法有几个优点。它在概念上将非常接近现实世界的运作方式。将系统扩展到多台机器会容易得多。

但是,要使其正常工作,我需要确保所有线程都以相同的速度运行,并对“相同”进行相当自由的解释。说在彼此的 1% 以内。

这就是为什么我不一定需要类似 Thread.join() 的解决方案。我不想要一些超级控制的学校情妇来确保所有线程定期相互同步。我只需要能够要求运行时(无论它是什么——可能是 Java、Erlang 或最适合这个问题的任何东西)以或多或少相等的速度运行线程。

任何建议将不胜感激。

更新 2009-03-16

我要感谢所有回答这个问题的人,特别是那些回答基本上是“不要这样做”的人。由于大家的评论,我现在更好地理解了我的问题,我不太确定我应该按照最初的计划继续。尽管如此,我觉得彼得的回答是对问题本身的最佳回答,这就是我接受它的原因。

4

14 回答 14

13

如果没有协调,你就无法真正做到这一点。如果一个元素最终需要比另一个元素更便宜的计算(以一种可能不明显的方式)怎么办?

你不一定需要一个超级控制器——你可以只为每个线程保留某种计步器,并有一个全局计数器来指示“最慢”线程。(当每个线程都完成了一些工作时,它必须检查它是否落后于其他线程,如果是,则更新计数器。)如果一个线程注意到它比最慢的线程有很长的路要走,它可以简单地等待(可能在显示器上)。

只是经常这样做,以避免由于共享数据争用而产生过多的开销,我认为它可以很好地工作。

于 2009-03-13T09:19:29.243 回答
12

你需要某种同步。CyclicBarrier类有你需要的:

一种同步辅助工具,它允许一组线程相互等待以达到共同的障碍点。CyclicBarriers 在涉及固定大小的线程组的程序中很有用,这些线程组必须偶尔相互等待。屏障被称为循环的,因为它可以在等待线程被释放后重新使用。

在每个“滴答”之后,您可以让所有线程等待其他线程,这会更慢。当剩余的线程到达屏障时,它们都会继续。

于 2009-03-13T11:06:16.600 回答
6

线程意味着完全独立地运行,这意味着以任何方式同步它们总是很痛苦的。在您的情况下,您需要一个中央“时钟”,因为没有办法告诉虚拟机每个线程应该获得相同数量的......呃......它应该得到什么?相同数量的RAM?可能没关系。相同数量的CPU?您的所有对象是否都非常相似,以至于每个对象都需要相同数量的汇编指令?

所以我的建议是使用一个中央时钟向每个进程广播时钟滴答。每个进程中的所有线程都读取滴答声(应该是绝对的),计算与他们看到的最后一个滴答声的差异,然后相应地更新其内部模型。

当一个线程完成更新时,它必须让自己进入睡眠状态;等待下一个滴答声。在 Java 中,在“tick received”锁上使用 wait() 并使用“notifyAll()”唤醒所有线程。

于 2009-03-13T09:22:04.870 回答
4

我建议尽可能不要使用线程,因为如果您不小心,它们只会在以后添加问题。在进行物理模拟时,您可以使用数十万个离散对象进行更大的模拟。你不可能在我知道的任何操作系统上创建这么多线程,即使你可以,它也会像狗屎一样运行!

在您的情况下,您可以创建多个线程,并在每个线程中放置一个事件循环。“主”线程可以对执行进行排序并向每个工作线程发布“进程”事件以唤醒它并使其完成一些工作。这样,线程将休眠,直到您告诉它们工作。

您应该能够让主线程以允许所有工作线程在下一次滴答之前完成的速率进行滴答。

我不认为线程是您问题的答案,除了并行化成少量工作线程(等于机器中的内核数),每个线程对一系列物理对象进行线性排序。您仍然可以以这种方式使用主/事件驱动的方法,但您会消除很多开销。

于 2009-03-13T10:40:23.323 回答
3

请不要。线程是一种允许并行执行外观的 O/S 抽象。对于多核和多核 CPU,O/S 可以(但不必)在不同的核之间分配线程。

我认为最可行的可扩展性愿景是使用工作线程,其尺寸与您拥有的内核数量大致匹配,并在它们之间分配工作。一个粗略的草案:定义一个类 ActionTick 来更新一个粒子,并让工作线程从一个共享队列中选择 ActionTicks 来处理。即使有这样的解决方案,我也看到了一些挑战。

  1. 线程开销:您会在不同的工作线程之间获得上下文切换开销。线程本身很昂贵(如果实际上不像进程那样具有破坏性):使用不同的线程池大小测试性能。在内核数量之外添加更多线程往往会降低性能!
  2. 同步成本:你会遇到几个竞争点:一个人访问工作队列,但更糟糕的是,访问模拟世界。您需要界定每个 ActionTick 的效果或实施大量锁定/解锁。
  3. 优化物理的困难。您想要界定每个 ActionTick 所查看的对象/粒子的数量(距离截断?模拟空间的 3D 树细分?)。根据模拟领域的不同,您可以通过检查项目子集中是否需要任何更改来消除大量工作。在对工作项进行排队之前进行这些优化更容易,而不是作为分布式算法。但是,您的模拟的那部分成为潜在的可扩展性瓶颈。
  4. 复杂。线程和并发在解决方案中引入了几罐蠕虫。始终首先考虑其他选项——但如果您需要它们,请在创建自己的工作项调度、锁定和执行策略之前尝试线程......

警告:我没有使用过任何大型模拟软件,只是一些业余爱好者的代码。

于 2009-03-13T10:02:15.227 回答
3

正如您所提到的,有很多“不要这样做”的答案。大多数似乎将线程读取为 Java 使用的操作系统线程。既然您在帖子中提到了 Erlang,我想发布一个更以 Erlang 为中心的答案。

使用进程(或参与者、微线程、绿色线程,有时称为)对这种模拟进行建模并不一定需要任何同步。从本质上讲,我们有几个(很可能是数千或数十万)需要模拟的物理对象。我们希望尽可能逼真地模拟这些对象,但可能还涉及某种实时方面(但不一定,您在问题中没有提到这一点)。

一个简单的解决方案是为每个对象生成一个 Erlang 进程,向所有对象发送刻度,并在继续下一个刻度之前收集模拟结果。这实际上是同步所有内容。当然,它更多的是确定性解决方案,并且不保证任何实时属性。进程如何相互通信以获取计算所需的数据也很重要。您可能需要以巧妙的方式对它们进行分组(碰撞组等),为休眠对象设置休眠进程(Erlang 对此有很好的支持)等以加快速度。

要获得实时属性,您可能需要限制流程执行的计算(以交易准确性换取速度)。这也许可以通过在等待答案的情况下发送滴答声来完成,并让对象进程使用它们当前的位置和您需要的其他数据回复每个滴答声(即使它可能只是当时的近似值)。正如DJClayworth所说,这可能会导致模拟中累积错误。

我想从某种意义上说,问题实际上是关于是否有可能利用并发的力量在这里获得某种优势。如果您需要同步,这是一个非常强烈的信号,表明您不需要每个物理对象之间的并发。因为您基本上通过等待其他进程来浪费大量计算时间。您可能会在计算过程中使用并发,但我认为这是另一个讨论。

注意:这些想法都没有考虑到实际的物理计算。这不是 Erlang 的强项,也许可以在 C 库或任何你喜欢的东西中执行,具体取决于你想要的特征类型。

注意:我不知道任何情况下已经这样做了(尤其是不是我),所以我不能保证这是合理的建议。

于 2009-04-07T14:38:04.083 回答
2

即使有完美的软件,硬件也会阻止你这样做。硬件线程通常没有公平的性能。在很短的时间内,如果线程在 +-10% 的性能范围内运行,你就很幸运了。

当然,这些是异常值。一些芯片组将在省电模式下运行一些内核,而另一些则不会。我相信其中一台 Blue Gene 研究机器具有硬件线程的软件控制调度而不是锁。

于 2009-03-13T11:50:08.603 回答
2

默认情况下,Erlang 会尝试将其进程均匀地分布在可用线程上。默认情况下,它还将尝试在所有可用处理器上运行线程。因此,如果您有足够多的可运行 Erlang 进程,那么您将获得相对均衡的平衡。

于 2009-03-13T13:59:42.597 回答
1

我不是线程专家,但线程的全部意义不是它们彼此独立 - 并且是不确定的吗?

于 2009-03-13T09:19:03.847 回答
1

我认为你对你说的问题有一个基本的误解:

从概念上讲,它将非常接近现实世界的运作方式

现实世界根本不会以类似线程的方式工作。大多数机器中的线程不是独立的,实际上甚至不是同时的(OS将使用上下文切换)。当有很多IO或等待发生时,它们提供最大的价值。

最重要的是,随着更复杂的事情发生,现实世界不会“消耗更多资源”。想一想两个物体从高处落下的区别,一个平稳落下,另一个执行某种复杂的翻滚运动……

于 2009-03-13T09:26:56.997 回答
1

我会制作一种“时钟生成器”——并在那里注册每个新对象/线程。当 delta-t 过去时,时钟将通知所有已注册的对象。但是,这并不意味着您需要为每个对象使用单独的线程。理想情况下,您将拥有与处理器一样多的线程。从您的设计角度来看,您可以通过 Executor 或线程池将对象任务的执行分开,例如,当对象接收到滴答事件时,它会进入线程池并自行安排执行。

于 2009-03-13T11:20:33.133 回答
0

为了实现这一目标,必须发生两件事。您必须确保每个 CPU 核心拥有相同数量的线程,并且您需要某种同步。

这种同步可能相当简单,例如在执行计算时检查每个线程的“循环完成”变量,但您无法避免它。

于 2009-03-13T09:21:23.780 回答
0

在控制电机工作时,我使用了一些数学来将速度保持在稳定状态。该系统具有PID控制、比例、积分和微分。但这是模拟/数字系统。也许可以类似地使用来确定每个线程必须运行多长时间,但我能给你的最大提示是所有线程都将有一个时钟同步。

于 2009-03-13T12:13:34.350 回答
0

我首先要承认我不是线程专家,但这听起来是一种非常错误的模拟方式。正如其他人已经评论过的那样,拥有太多线程在计算上是昂贵的。此外,如果您打算做我认为您正在考虑做的事情,您的模拟可能会产生随机结果(如果您正在制作游戏,则可能无关紧要)。

我会使用一些用于计算模拟的离散步骤的工作线程。

于 2009-03-13T16:02:35.390 回答