c# - 将单线程应用程序迁移到多线程、并行执行、蒙特卡洛模拟

Question

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

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

基本的算法是一大堆嵌套的for循环，中间是随机数调用和矩阵乘法，每次迭代返回一个double，它被添加到一个结果列表中，这个列表是周期性的对某些收敛标准进行排序和测试(在检查点，每 5% 的总迭代次数)如果可接受，程序将跳出循环并写入结果，否则它会继续到最后。

我希望开发人员能够权衡:

• 我应该使用新线程还是线程池
• 我应该看看 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 可能值得使用，但它只有一个没有 AddRange 的 Add 方法，所以我必须查看那里的结果并以线程安全的方式添加。来自使用过 Parallel.For 的人的任何见解，非常感谢。我暂时切换到 System.Random 进行调用，因为在使用我的 Mersenne Twister 实现调用 nextUniform 时出现异常，可能它不是线程安全的某个数组得到一个索引越界....

Answer 1

首先，您需要了解为什么您认为使用多线程是一种优化——但实际上并非如此。如果您有多个处理器，那么使用多线程将使您的工作负载完成得更快只有，并且最多比您有可用的 CPU 快很多倍(这称为加速).在传统意义上，工作并未“优化”(即工作量并未减少 - 事实上，对于多线程，由于线程开销，工作总量通常会增加)。

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

因此，如果您进行这种并行化，最终会得到 3 个线程:线程 1 运行 RNG，线程 2 生成正态分布，线程 3 执行其余的模拟。

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

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