满迪　陈华　周涛

摘要：Laplace变换是一种解决常系数偏微分方程初边值问题的常用方法，在此，利用离散化方法和蒙特卡罗算法求解Laplace变换，运用多线程技术，结合高性能并行计算中WinAPI，OpenMP的并行模式获得最优计算方法。通过数值结果可以看出，蒙特卡罗OpenMP方法速度最慢，效率最低，基于离散算的WinAPI方法计算速度最快，并行效率最高，最终获得结论的并行计算模式应用到其他初值问题。

关键词： Laplace变换；OpenMP；WinAPI；蒙特卡罗算法

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）23-0223-03

1 概述

拉普拉斯变换是工程数学常用的一种积分变换，在工程技术和理论研究等诸多方面有较广泛的应用，特别是对于求解常系数线性偏微分方程的初边值问题。本文基于离散化的思想和蒙特卡罗算法对某一常见函数进行Laplace变换，利用两种并行模式改造并精选出最优的并行计算处理方法。

蒙特卡罗方法是一种随机模拟方法，它以统计理论方法和概率为基础，是使用随机数或伪随机数来解决实际计算问题的方法。OpenMP是一种面向共享内存及分布式共享内存的多处理器多线程并行编程语言，是能用于显示指导多线程、共享内存并行的应用程序编程接口，并利用封装好的函数来进行并行计算；WinAPI并行模式是通过编写线程函数，利用Windows系统中的API接口进行多线程调度来实现并行。通过对数值实验的串并行算法的计算速度，加速效果进行比较，得出并行优化后的计算方法。并进一步考虑将计算中高效的并行方法应用到其他数值问题。

2 拉普拉斯变换描述

3.1 API实现

首先在进程内创建线程，它是CPU调度和分配的基本单位。利用WINAPI定义线程函数，在线程函数内分配该线程所要进行的任务，然后将线程函数导入到创建好的线程中运行，计算机通过API接口，针对创建的线程数目，调度相同数目的CPU进行计算，最后将各线程的计算结果合并得到最终结果。

程序中使用多线程时，很多情况下是一些线程进行某些处理操作，而其他线程必须对其处理结果进行了解，若不采取适当措施，其他线程会在线程处理任务结束前就去访问处理结果，因此产生了数据竞争。为避免数据竞争，我们使用临界区进行数据同步，临界区独占对某些共享资源的访问，它只允许一个线程对共享资源进行访问。若有多个线程想同时访问临界区，那么在一个线程进入临界区后其他线程将被挂起。在本问题的实现过程中，将求和运算拖入临界区，来避免频繁介入临界区。

3.2 OpenMP实现

利用parallel for循环并行化

采用工作分配的执行方式，利用parallel for循环语句将总的工作量按照一定的方式分配到各个线程，最后将所有线程的结果汇总。Parellel for 是对一个完整的for循环进行分割，它根据线程数大小按工作量平均分配，每个线程的工作量为总的工作量/线程数。为了避免产生数据竞争，采用的方法是对竞争变量私有化，添加私有量private（n），再对执行完的程序利用reducation语句进行归约操作，用来更好的收集任务结果。

4 蒙特卡罗算法求解

4.1 蒙特卡罗算法

4.3 基于OpenMp并行算法实现

我们在串行程序的基础上通过OpenMP进行并行处理。求解该问题需要计算N个值，然后对N个值进行求和。在计算N个值得过程中数据之间没有依赖关系，所以我们采用四个线程将任务进行分配。在计算每个值之前我们都需要随机产生一个介于积分区间的随机数，为了减少共享内存带来的时间消耗，我们将这个随机数设定为每个线程的私有变量private（x）。然后利用规约reduction（+：s）将N个值进行求和运算，得到最终结果。

5 分析与结论

上述结果可以看出利用离散化方法所花费的时间整体比较少，在串行的基础上对它进行并行实现，使得效率进一步提高。OpenMP的加速比达到2.5396，API的加速比达到3.113。利用蒙特卡洛算法计算过程中所用时间比较长。主要因为蒙特卡洛算法主要针对的是多重积分的计算，而该问题是一重积分的运算所以效率较低。但蒙特卡洛算法的串行和并行算法相比较可以看出并行算法效率较高，加速比达到2.498。综合上述结果可以看出基于离散方法的API并行效率最高。

6 结语

对于Laplace变化，可以看出基于离散算法的API的并行效率最高，蒙特卡洛OpenMP效率最低。OpenMP编程模型比较适合迭代的并行计算。类似的我们还可以通过并行手段解决其他的并行计算问题。

参考文献：

[1] 朱建伟，刘荣.多线程并行快速求解e值得六种方法[J].现代计算机，2013（6）.

[2] 薛小超，王克，朱朋海.基于多核并行的非线性方程蒙特卡洛计算方法[J].电脑知识与技术，2014（7）.

[3] 刘辉玲，叶峰.计算多重积分的均匀随机数蒙特卡罗法的实现[J]电脑知识与技术，2008（12）.

[4] 张继伟.基于MPI的并行拉普拉斯变换算法及其应用研究[D].湖北大学，2011.