基于多核并行的非线性方程蒙特卡洛计算方法

薛小超　王克　朱朋海

摘要：随着社会生产生活的发展，对计算机的依赖越来越大，要解决庞大计算量的实际问题就需要高性能的计算机以及高速的计算方法。在应用蒙特卡洛方法求解非线性方程组时，利用多线程技术，串行改并行，使用WinAPI、OpenMP、MPI三种并行模式得出三种最优的并行计算方法。根据数值试验分析了各种计算模式的优缺点，发现MPI并行模式计算速度最快，最终得以结论并行计算模式可以推广到各种数值计算问题。

关键词：并行计算；多线程；WinAPI；OpenMP；MPI

中图分类号：TP301.6 文献标识码：A 文章编号：1009-3044（2014）21-5115-05

针对下面提出的山高问题，本质上就是求解非线性方程组，而对于非线性方程组数值解法发展迅速，如迭代法、Newton法、同伦算法、人工智能算法[1]等。这些算法优点突出，对于同伦算法、人工智能算法有很高的精度，计算速度非常快，看上去是完美的，但美中不足的是这些算法都为串行算法，缺少多核CPU并行手段，经过并行之后的算法求解非线性方程组能够极大地缩短计算时间，提高效率。为此专门利用三种最常用的并行模式，精心改造并挑选出三种最优的并行计算方法。

第一种并行模式：使用WinAPI[2]创建新线程即线程函数，然后通过API接口进行多线程调度完成并行；第二种并行模式：使用OpenMP[2]并行语言，通过设置参数与线程数，利用库函数循环并行化，实现算法并行计算；第三种并行模式：MPI[2] 并行是一种基于消息传递的并行语言，各进程具有独立的堆栈和代码段，多个程序独立进行，从而利用多节点或者多CPU模拟多节点实现并行计算，这也是MPI并行最快的原因。就这样我们可以串行该并行，得到优化算法，不仅解决非线性方程问题还拓展到其它数值问题。

1 问题提出

山高的估计：假如你站在山顶且身上带着一只具有跑表功能的计算器，你也许会出于好奇心想用扔下一块石头听回声的方法来估计山的高度，假定你能准确地测定时间，你又怎样来推算山崖的高度呢，请你分析这一问题[3]。

2 问题分析

除地球吸引力外，对石块下落影响最大的当属空气的阻力。根据流体力学知识，此时可设空气阻力正比于石块下落的速度，阻力系数为常数，因而，由牛顿第二定律可得[3]：

3 串行算法求解

串行算法是最基本的实现方法。其实现的核心是fun的绝对值与fun0的比较，每产生一个fun就与fun0比较，绝对值小的赋值给fun0，直到完成循环。具体的算法实现：

4 并行算法求解

4.1 WinAPI并行实现

首先利用WinAPI生成线程函数，编写线程函数完成单一工作量，主函数中调用该线程函数，根据线程数目调用相应的CPU进行计算，保证CPU运行正常，负载量均衡。最后将计算结果合并、比较得到需要的结果。

在Windows实现多线程并行计算时会产生数据竞争（Data racing），数据竞争导致计算出现错误，计算结果有时相差很大。错误的原因归结为多线程同时访问同一区域，读写操作冲突。为此采用同步技术，利用临界区与线程号分配任务解决此问题。

对于此问题，临界区作用于非线性方程组求解。临界区是一种针对多线程对同一区域访问混乱而设置的保护机制。它的作用在于当并行时，多线程访问次序因临界区而有序，互相不干扰，计算结果也就不会影响，是一个很好的屏障。

5 分析与讨论

开发验证工具：计算机Intel Core i7 八核处理器，开发工具Microsoft Visual Studio 2010，Microsoft Windows 版本[6.2.9200] 2012 Microsoft Corporation。

结果分析与比较：对串行和并行的方法进行数值实验，为了分析的方便，数值实验的计算步数为20，000，000。数值实验结果如下呈现：

四线程并行计算：

在表中，计算时间取平均值所得，以串行计算时间除以每种并行方式计算所用时间作为加速比，加速比理论值为4[4]（八线程加速比为8） 。由于实际调用线程及数据规约都会有时间损耗，导致加速比小于理想值。

由上面数据可知，WinAPI与OpenMP结果差不多，这与实际相符合，OpenMP是对WinAPI多线程的封装，两者在实现理论上一致。OpenMP算法简单，使用方便，但总体来说并不稳定。

MPI是基于通信的并行实现，它以独特的实现方式在目前并行计算的发展趋势下体现出强大的生命力。当然在进行主从式、并列式以及流水线式等方式的实现时，对于大数据传输要考虑数据传输时间，合理调整程序。 另外通过试验比较，可以看出MPI计算速度最快，所用时间最少，因而加速比最接近理论值，增多节点数目相信计算效果会更好，所以MPI并行模式最适合求解大规模问题。

6 结束语

通过求解非线性方程组，可以看出蒙特卡洛方法在处理数值计算问题中发挥着重要的作用，将蒙特卡洛方法并行化可以极大地节省时间，提高效率，并且并行方法中的MPI方法并行处理时体现了很大的优势。类似的我们还可以通过并行手段解决其它的数值计算问题。

参考文献：

[1] 夏林林，户晗蕾，吴开腾，等.非线性方程组数值方法的研究进展[J].内江师范学院学报，2013（10）：12-17.

[2] 多核系列教材编写组.多核程序设计[M].北京：清华大学出版社，2007.

[3] 建模-百度文库[EB/OL].（2012-11-14）. http：//wenku.baidu.com/view/3ba882323968011ca300919f.html.

[4] 朱建伟，刘荣.多线程并行快速求解e值的六种方法[J].现代计算机，2013（17）：15-20.

[5] 刘荣，朱建伟，李富合，等.基于四种并行计算模式的自然对数底并行计算方法[J].电脑知识与技术，2013（14）：3415-3419.