Mandelbrot集并行算法的MPI实现

摘要：分析了MPI环境下算法设计的特点，描述了在MPI环境下实现mandelbrot集的三种算法，并对它们进行了比较。

关键词：Mandelbrot；并行算法；mpi

中图分类号：TP312文献标识码：A文章编号：1009-3044(2007)04-11055-02

1 Mandelbrot集

Mandelbrot集[1]是复数平面中的点集，当对一个函数迭代计算时，这些点将处于准稳定状态 （将增加或减小，但不会超过某一限度），通常该函数是：

式中zk+1是复数z=a+bi(其中i= )的第k+1次迭代，zk是z的第k次迭代，c是确定该点在复数平面中位置的复数值。z的初值为0。迭代将一直进行下去，直至z的幅值大于2(这表明z最终将变为无穷大)或是迭代次数已达到某种任意规定的限度。

2 Mandelbrot集并行算法的设计

设有n台并行机参与计算，计算任务被划分到n台并行机上。 在此，共有三种并行算法模式，在模式一中，第i台并行机计算第i,i+n,i+2n, …块竖着的长方形区域；在模式二中，第i台并行机计算第i,i+n,i+2n, …块横着的长方形区域；在模式三中，第i台并行机计算第i,i+n,i+2n, …块正方形区域。

3 Mandelbrot集并行算法的实现环境

本程序以Linux系统为平台，应用消息传递并行编程环境MPI[2]进行网络并行编程。MPI是消息传递接口(Message Passing Interface)的简称，它作为一种标准已为各大并行机制造商所支持，MPI程序可不加修改地在所有的并行机上运行。MPI是一个函数库，它采用Fortran和C语言进行绑定。MPI是一种消息传递编程模型，广泛应用于多类并行机的模式，它适用于SIMD、MIMD、SPMD和MPMD等并行机类型。MPI作为消息传递编程模型的代表和事实上的标准，有多种实现版本，MPICH是其中一种，且MPICH 随MPI标准的更新相应推出新版本，本文算法采用MPICH-1.2.5。

4 试验结果及分析

4.1 试验结果

试验显示图像如下：

图4 Mandelbrot集图像

试验数据如下：

表1 试验数据

4.2 分析

图5 试验数据曲线

对Mandelbrot计算的确切分析是非常复杂的，这是因为每个象素需进行多少此迭代事先并不知道。每个像素的迭代次数是n的某一函数，但不会超过max。因此顺序时间为：ts

并行程序基本上有三个阶段：通信，计算和通信。

阶段1：通信

首先，向每一个从进程发送信号，向s个从进程的每一个发送一个数据项；即tcomm1+s(tstartup+tdata)，向每个从进程发送分离消息导致了重复的启动时间。

阶段2：计算

然后各个从进程并行地完成它们的Mandelbrot计算；即tcomp≤ ，假设像素在所有处理器中平均分配。至少会有某些像素将需要最大的迭代次数，而且它们将在整个时间中占主要部分。

阶段3：通信

在最后阶段，用单个发送将结果传送回主进程：tcomm2= (tstartup+tdata)。将结果合并成少数消息就可减少启动时间的开销。

综合起来，并行时间将由下式给定：tp= +( +s)(tstartup+tdata)。式中的处理器总是由p=s+1给定。如果max很大可能到的加速比将为p-1。

但是在实际的试验中，由上图可知，模式一与模式二之间，远算的时间之间并不存在很大的差别，但模式一、模式二与模式三之间存在的差别就比较大，这之间的差别体现在，在模式一、模式二中，每个并行机计算的都是一个长方形区域，在每个长方形区域中，对于其中的每个数，计算量的大小并不是均衡的，计算的时间上存在着较大的区别，当对于计算量大的区域，计算的时间就比较长，在传输给主进程的过程中，从进程之间就要产生一个较长的等待时间，但对于模式三，由于实行了正方形区域，每个并行机计算一个点，从整体上看，基本实现了数据均分，即每个并行器所计算的时间消耗量相差无几，在传输给主进程的过程中，并没有产生太大的时间等待。

对于每个模式，曲线的走向最后都趋于平滑，这是因为随着并行机数量的增加，虽然减少了每个并行机的计算时间，但是通信时间却和计算时间的差别在逐渐减少，可以预见，随着并行机器数量的增加，远算时间仅有较小区别。

5 结束语

现实世界中许多现象都表现出并行性，众多问题的求解过程都有并行的可能性，但由于人们习惯用SISD计算模型上的思维，使得编写并行机执行程序变得不合常规，其实，底意识的并行才更接近问题。MPI程序的SPMD编程模式给人们进行并行思维以很好的训练，MPI的通信机制为人们在连网工作站上编写并实现并行程序提供了舞台，使得问题求解变得更加自然。

参考文献：

[1]BARRY WILKINSON，MICHAEL ALIEN, 陆鑫达, 等译. 并行程序设计[M]. 北京：机械工业出版社，2002.

[2]都志辉. 高性能计算并行编程技术――MPI并行程序设计[M]. 北京：清华大学出版社，2001.

本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。