8

我的任务是采用现有的单线程蒙特卡罗模拟并对其进行优化。这是 ac# 控制台应用程序，没有 db 访问它从 csv 文件加载数据一次并在最后写出来，所以它几乎只是 CPU 绑定，也只使用大约 50mb 的内存。

我已经通过 Jetbrains dotTrace 分析器运行它。在总执行时间中，大约 30% 用于生成均匀随机数，24% 将均匀随机数转换为正态分布随机数。

基本算法是大量嵌套的 for 循环，以随机数调用和矩阵乘法为中心，每次迭代返回一个双精度数，将其添加到结果列表中，该列表定期排序并测试一些收敛标准（在检查每 5% 的总迭代计数点）如果可以接受，程序会跳出循环并写入结果，否则继续到最后。

我希望开发人员参与进来：

  • 我应该使用新的 Thread v ThreadPool
  • 我应该看看Microsoft Parallels 扩展库吗
  • 我应该看看AForge.Net Parallel.For，http://code.google.com/p/aforge/任何其他库吗？

由于我从未编写过任何并行或多线程代码，因此非常欢迎一些指向上述教程的链接。

  • 生成大量正态分布随机数的最佳策略，然后使用这些随机数。应用程序永远不会在此状态下使用统一随机数，它们总是被转换为正态分布，然后被消耗掉。
  • 用于随机数生成的良好快速库（并行？）
  • 当我采用这种并行方式时的内存考虑，我需要多少额外的东西。

当前应用程序需要 2 小时进行 500,000 次迭代，业务需要将其扩展到 3,000,000 次迭代并每天调用多次，因此需要进行大量优化。

特别想听听使用过Microsoft Parallels Extension或AForge.Net Parallel的人的意见

这需要相当快地进行生产，因此.net 4 beta 已经发布，即使我知道它已经内置了并发库，我们可以考虑在它发布后稍后迁移到 .net 4。目前服务器有.Net 2，我已经提交了我的开发盒有的.net 3.5 SP1 的升级以供审查。

谢谢

更新

我刚刚尝试了 Parallel.For 实现，但它产生了一些奇怪的结果。单线程：

IRandomGenerator rnd = new MersenneTwister();
IDistribution dist = new DiscreteNormalDistribution(discreteNormalDistributionSize);
List<double> results = new List<double>();

for (int i = 0; i < CHECKPOINTS; i++)
{
 results.AddRange(Oblist.Simulate(rnd, dist, n));
}

到：

Parallel.For(0, CHECKPOINTS, i =>
        {
           results.AddRange(Oblist.Simulate(rnd, dist, n));
        });

在模拟内部有许多对 rnd.nextUniform() 的调用，我想我得到了许多相同的值，这可能会发生，因为这现在是并行的吗？

也可能是 List AddRange 调用不是线程安全的问题？我看到这个

System.Threading.Collections.BlockingCollection 可能值得使用，但它只有一个 Add 方法，没有 AddRange 所以我必须查看那里的结果并以线程安全的方式添加。非常感谢使用 Parallel.For 的人的任何见解。我暂时切换到System.Random进行调用，因为我在使用 Mersenne Twister 实现调用 nextUniform 时遇到异常，也许它不是线程安全的，某个数组的索引越界......

4

3 回答 3

13

首先，您需要了解为什么您认为使用多线程是一种优化——事实上，事实并非如此。仅当您有多个处理器时，使用多线程才能使您的工作负载更快地完成，然后最多可以比您有可用的 CPU 快几倍（这称为加速）。工作不是传统意义上的“优化”（即工作量没有减少 - 事实上，对于多线程，工作总量通常会因为线程开销而增加）。

因此，在设计应用程序时，您必须找到可以并行或重叠方式完成的工作。可能可以并行生成随机数（通过在不同的 CPU 上运行多个 RNG），但这也会改变结果，因为你会得到不同的随机数。另一种选择是在一个 CPU 上生成随机数，并在不同的 CPU 上生成其他所有内容。这可以为您提供 3 的最大加速，因为 RNG 仍将按顺序运行，并且仍会占用 30% 的负载。

所以如果你进行这种并行化，你最终会得到 3 个线程：线程 1 运行 RNG，线程 2 产生正态分布，线程 3 完成其余的模拟。

对于这种架构，生产者-消费者架构是最合适的。每个线程将从队列中读取其输入，并将其输出生成到另一个队列中。每个队列都应该是阻塞的，因此如果 RNG 线程落后，规范化线程将自动阻塞，直到有新的随机数可用。为了提高效率，我会在线程间传递 100（或更大）数组中的随机数，以避免对每个随机数进行同步。

对于这种方法，您不需要任何高级线程。只需使用常规线程类，没有池，没有库。您唯一需要的是（不幸的是）不在标准库中的是阻塞 Queue 类（System.Collections 中的 Queue 类不好）。Codeproject提供了一个外观合理的实现；可能还有其他人。

于 2009-07-12T18:48:40.603 回答
1

List<double>绝对不是线程安全的。请参阅System.Collections.Generic.List 文档中的“线程安全”部分。原因是性能：添加线程安全不是免费的。

您的随机数实现也不是线程安全的；在这种情况下，多次获得相同的数字正是您所期望的。让我们使用以下简化模型rnd.NextUniform()来了解正在发生的事情：

  1. 从对象的当前状态计算伪随机数
  2. 更新对象的状态，以便下一次调用产生不同的数字
  3. 返回伪随机数

现在，如果两个线程并行执行这个方法，可能会发生这样的事情：

  • 线程 A 计算步骤 1 中的随机数。
  • 线程 B 和步骤 1 一样计算一个随机数。线程 A 还没有更新对象的状态，所以结果是一样的。
  • 线程 A 在步骤 2 中更新对象的状态。
  • 线程 B 像第 2 步一样更新对象的状态，践踏 A 的状态更改，或者可能给出相同的结果。

正如你所看到的，你可以做的任何推理来证明rnd.NextUniform()作品不再有效，因为两个线程相互干扰。更糟糕的是，像这样的错误取决于时间，并且在某些工作负载或某些系统上可能很少以“故障”的形式出现。调试噩梦！

一种可能的解决方案是消除状态共享：给每个任务自己的随机数生成器，用另一个种子初始化（假设实例不以某种方式通过静态字段共享状态）。

另一个（劣质）解决方案是在您的类中创建一个包含锁定对象的字段，如下所示：MersenneTwister

private object lockObject = new object();

MersenneTwister.NextUniform()然后在你的实现中使用这个锁：

public double NextUniform()
{
   lock(lockObject)
   {
      // original code here
   }
}

这将阻止两个线程并行执行 NextUniform() 方法。您Parallel.For可以通过类似的方式解决列表中的问题：将Simulate调用和AddRange调用分开，然后在调用周围添加锁定AddRange。

我的建议：尽可能避免在并行任务之间共享任何可变状态（如 RNG 状态）。如果没有共享可变状态，则不会发生线程问题。这也避免了锁定瓶颈：您不希望您的“并行”任务等待一个根本不并行工作的随机数生成器。特别是如果 30% 的时间花在获取随机数上。

将状态共享和锁定限制在您无法避免的地方，例如在聚合并行执行的结果时（如在您的AddRange调用中）。

于 2009-07-13T10:56:22.597 回答
0

线程将变得复杂。您必须将程序分解成逻辑单元，每个逻辑单元都可以在各自的线程上运行，并且您必须处理出现的任何并发问题。

并行扩展库应该允许您通过将一些 for 循环更改为Parallel.For循环来并行化您的程序。如果您想了解这是如何工作的，Anders Hejlsberg 和 Joe Duffy 在他们的 30 分钟视频中提供了一个很好的介绍：

http://channel9.msdn.com/shows/Going+Deep/Programming-in-the-Age-of-Concurrency-Anders-Hejlsberg-and-Joe-Duffy-Concurrent-Programming-with/

线程与线程池

ThreadPool，顾名思义，就是一个线程池。使用 ThreadPool 获取线程有一些优势。线程池通过为您的应用程序提供由系统管理的工作线程池，使您能够更有效地使用线程。

于 2009-07-12T18:48:50.777 回答