Mandelbrot集并行算法的MPI实现

来源 :电脑知识与技术 | 被引量 : 0次 | 上传用户:heck502
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:分析了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格式阅读原文。
其他文献
摘要:Visual Basic作为一种流行的编程软件,以其易学得到初学者的青睐并被广泛应用,本文从Visual Basic在数据库的应用方面总结出几点经验,以期为开发出高效、美观的数据库应用程序提供一些便利。  关键词:接口对象法;数据控件法;统一数据访问;ADO  中图分类号:TP311.13文献标识码:A 文章编号:1009-3044(2007)04-10932-02  Visual Basi
期刊
摘要:本文讨论了如何使用VB编程,通过穷举法解除EXCEL文档和WORD文档的密码。并在破解过程中加入了中断,以方便用户随时中断破解过程。  关键词:穷举法;解密;EXCEL文档;WORD文档;密码  中图分类号:TP317.1 文献标识码:A文章编号:1009-3044(2007)04-11028-03    1 引言  Excel和Word提供了多种方法限制访问用户文档,以免未经授权者的查看和
期刊
摘要:本文介绍了遗传算法的基本知识,并利用遗传算法解决TSP(旅行商)问题,在此基础上,用免疫遗传算法进行优化对比。  关键词:遗传算法;TSP旅行商问题;免疫算法  中图分类号:TP311文献标识码:A 文章编号:1009-3044(2007)04-11047-01    1 引言  生物通过许多代的进化才能更好的繁殖,适应了不断改变的外界环境因素而生存。遗传算法利用生物基础,将特定问题转化成生
期刊
摘要:主要介绍了实验用电流表如何运用OpenGL在VC++.NET环境下的设计与实现问题。最后实现了电流表的三维可视化以及通过鼠标实现电流表的缩放和移动功能,还实现了电流表指针随电流而准确及时变化的功能。  关键词:OpenGL;电流表;仿真  中图分类号:TP391文献标识码:A文章编号:1009-3044(2007)04-11043-02    1 引言  物理学是一门实验科学,学生不仅可以从
期刊
摘要:粒子群算法原理简单,易于实现,是进化算法中优化效率很高的算法。针对确定环境下的问题优化,提出采用粒子群算法对其进行优化求解。通过对确定性环境下的Benchmark函数的算法仿真研究,表明粒子群算法在确定性问题优化中具有快速收敛性和精确性的特点。  关键词:粒子群算法;确定性问题;优化  中图文类号:TP301 文献标识码:A文章编号:1009-3044(2007)04-11027-01   
期刊
摘要:将现有MPI并行程序移植到网格环境下有着非常现实的意义,本文介绍了网格计算的概念和MPI并行计算模型,阐述了将现有的MPI并行程序移植到Globus网格环境下的重要性,并针对这类移植的一种折中方案——MPICH-G2进行了研究、实验,总结了这种方案的特点和相关技术。  关键字:网格计算;并行计算;MPI;Globus  中图分类号:TP393文献标识码:A文章编号:1009-3044(200
期刊
摘要:该文以BCH(67,53)为例,提出了一种改进的,适合在FPGA上实现的BCH译码算法,并用Xilinx公司Virtext2pro器件实现了BCH(67,53)码的译码。该算法基于BM迭代,与传统的BCH译码算法相比,具有硬件实现简单,运算速度快,消耗资源少等优势。经仿真验证,对于码组中任意小于等于两比特的随机错误都可以给予纠正,且运行可靠。目前,该BCH译码器已成功地应用在DVB-T(数字
期刊
摘要:Python是一种敏捷开发项目经常采用的语言。本文介绍了在Python敏捷项目中结合类似epydoc文档系统,使在doctest单元测试同时能够产生同步的最新文档,比如常用的功能说明文档等,在敏捷开发中常被称作敏捷文档。  关键词:Python;敏捷开发;敏捷文档;doctest;单元测试;执行文档;epydoc   中图分类号:TP311文献标识码:A文章编号:1009-3044(2007
期刊
摘要:随着电子商务的流行,开始出现了移动商务,在移动中处理商务成为现实。如何高效地实现移动商务,成为一个新的研究课题。本文研究了基于XML和J2ME的无线联机定购系统的实现,并且设计了一个飞机票定购系统。本系统使用J2ME平台的移动信息配置文件(MIDP)和第三方的XML解析器来实现,应用程序分为两个部分:客户端和服务器端。  关键词:J2ME;XML;HTTP;XML解析器  中图分类号:TP3
期刊
摘要:对一个程序用Labview等语言的分别实现的研究,是为了使读者了解许多软件都可以达到相同或相似的结果。通过具体的程序设计,使大家知道软件设计方法的差异性,可以根据自己喜欢的方式,选择语言。  关键词:软件;Labview;Matlab;语言  中图分类号:TP311文献标识码:A文章编号:1009-3044(2007)04-11060-02    1 引言  比较两个无符号数的大小,并求其平
期刊