论文部分内容阅读
摘要:分析了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格式阅读原文。
关键词: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格式阅读原文。