将单线程应用迁移到多线程、并行执行、蒙特卡罗模拟。

Question

将单线程应用迁移到多线程、并行执行、蒙特卡罗模拟。

c#multithreadingparallel-processingthreadpool

8

我被委托优化一个现有的单线程蒙特卡罗模拟。这是一个C#控制台应用程序，没有数据库访问，它从CSV文件中加载数据一次，并在最后写出数据，因此它基本上只受CPU限制，也只使用了约50MB的内存。

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

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

我希望开发人员能参与以下讨论：

我应该使用新线程vs线程池吗？
我应该查看Microsoft Parallels Extension library吗？
我应该查看AForge.Net Parallel.For，http://code.google.com/p/aforge/ 还有其他的库吗？

关于上述问题的一些教程链接将会很受欢迎，因为我从未编写过任何并行或多线程代码。

生成大量正态分布随机数的最佳策略，以及如何消耗这些随机数。应用程序在此状态下从不使用均匀分布的随机数，它们总是被转换成正态分布然后被消耗。
用于随机数生成的好的快速库（并行？）
内存考虑因素：当我进行并行处理时，我需要多少额外的内存。

当前应用程序对500,000次迭代需要2小时，业务需求要将其扩展到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));
}

To:

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时出现异常，也许它不是线程安全的，某个数组正在获得索引超出范围的异常。

- m3ntat

你在哪台机器上运行它？升级硬件可以获得所需速度提升的一部分。 - s_hewitt

这是在 AMD Opteron 275 上运行的，我想有 4 个 CPU，不确定有多少个核心。Windows Server 2003 SP2 32 位。 - m3ntat

3个回答

1

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

你的随机数实现也不是线程安全的；在这种情况下多次获取相同的数字是预期的行为。让我们使用以下简化版的 rnd.NextUniform() 模型来了解发生了什么：

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

现在，如果两个线程并行执行此方法，则可能会发生如下情况：

线程 A 计算一个随机数，就像第一步那样。
线程 B 计算一个随机数，就像第一步那样。线程 A 还没有更新对象的状态，因此结果是相同的。
线程 A 更新对象的状态，就像第二步那样。
线程 B 更新对象的状态，就像第二步那样，覆盖 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调用）。

- Wim Coenen

太棒了，谢谢你的回复！那很有道理。现在问题是我应该使用add range还是找到一个线程安全的集合，允许我累加随机数列表（双倍），添加顺序不重要，但我确实需要定期对结果进行排序并在特定百分位上抓取结果，并检查收敛标准以测试模拟的早期终止，我需要为每个Parallel.For路径运行此操作，如果满足则立即取消所有Parallel执行，因为不需要进一步处理，有任何想法吗？ - m3ntat

我暂时没有答案。定期状态检查和取消挂起/运行的并行任务是一个大主题；我建议您发布一个新问题。 - Wim Coenen

虽然，查看http://blogs.msdn.com/pfxteam/archive/2009/05/22/9635790.aspx。 - Wim Coenen

0

线程将会变得复杂。您需要将程序分解为逻辑单元，每个单元都可以在自己的线程上运行，并处理出现的任何并发问题。

Parallel Extension Library 应该允许您通过将一些 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/

线程 vs. 线程池

线程池，顾名思义，是一组线程的池子。使用线程池来获取您的线程具有一些优势。线程池可以通过提供由系统管理的工作线程池，更有效地使用线程，从而使您的应用程序更加高效。

- Robert Harvey

嗯，我认为使用线程池不会比手动处理线程更复杂 - 我想这是你想说但遗漏了的内容？在比较线程池和手动处理线程时，线程池更高效（因为它回收已完成的线程，线程创建很昂贵），并且更容易使用 - 特别是如果利用委托。话虽如此，我无法将其与Parallel库进行比较 - 只是不想让线程池受到负面评价 :-) - STW

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Martin v. Löwis · Accepted Answer

首先你需要明白为什么你认为使用多个线程是优化，但事实上并不是。只有在拥有多个处理器的情况下，使用多线程才会使工作负载更快地完成，而且最多仅比可用的CPU数量快那么多倍（这被称为“加速比”）。工作并没有在传统意义上被“优化”（即工作量并没有减少——事实上，由于线程开销的缘故，使用多线程通常会导致总工作量增加）。

因此，在设计应用程序时，您必须找到可以以并行或重叠方式完成的工作块。可能可以并行生成随机数（通过在不同的CPU上运行多个随机数生成器），但这也会改变结果，因为您会得到不同的随机数。另一个选项是将随机数生成放在一个CPU上，其他一切都在不同的CPU上。这样最多可以提高3倍速度，因为RNG仍然是按顺序运行，并且仍然占据30%的负载。

因此，如果选择并行化，您将得到3个线程：线程1运行RNG，线程2生成正态分布，线程3执行剩余的模拟。

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

对于这种方法，您不需要任何高级线程技术。只需使用正常的线程类，不需要池，也不需要库。唯一需要的是（不幸的是）标准库中没有的阻塞队列类（System.Collections 中的队列类不行）。Codeproject 提供了一个看起来不错的实现，可能还有其他实现。