并行算法设计课件

《并行算法设计课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并行算法设计主要内容基本知识及现状并行计算性能评测并行算法的一般设计方法并行算法的基本设计技术并行算法的一般设计过程例子现代计算机的共同特点：并行性现代计算机的共同特点：并行性并行:古老的思想!“...并行计算并不是什么新的思想,只是将它扩展应用于计算机而已.作者也不认为这种扩展应用会存在什么无法克服的困难.但也不要期待有效的并行编程方法与技术能够在一夜之间诞生.期间还需要有许多的工作和实验要做.毕竟,今天的编程技术(串行)是若干年来艰苦的探索才取得的.现在编程工作似乎成了一种令人单调乏味的工作,事实上,并行编程的出现将会使重新恢复编程工作者们的探索精神...”(Gill,S.(19

2、58),“ParallelProgramming,”TheComputerJournal,vol.1,April,pp.2-10.)ParallelProgrammingwithMPIbyPeterPacheco(2000)综述——为什么要做并行计算从系统的角度：集成系统资源，以满足不断增长的对性能和功能的要求从应用的角度：适当分解应用，以实现更大规模或更细致的计算并行计算的功能?降低单个问题求解的时间.增加问题求解规模.提高吞吐率(多机同时执行多个串行程序).并行计算?资料来源:TimMattsonIntelCo.Com.ScienceLab.RudolfEigenmannPurd

3、ueUni.SchoolofElec.andComp.Eng.分而治之!并行计算现状(硬件)共享内存SMP并行计算机对称多处理器或共享内存处理器多个处理器通过系统总线或者交叉开关共享一个或者多个内存模块优点：使用简单，维护方便缺点：受系统总线带宽限制，只能支持少量处理器（十几个）并行编程方式：通常OpenMP，也可用消息传递(PVM/MPI)及HPF代表机型：SGIPowerChanlenge;SUNE10000等并行计算现状(硬件)分布内存MPP型计算机MassivelyParalleledProcessors的简称指由大量具有局部内存的计算节点通过高速系统网络连接而成的并行处理系

4、统MPP系统的系统网络通常具有某种拓扑结构（Tree,Mesh,Torus,Hypercuber）并行计算现状(硬件)DSM型并行计算机分布共享内:DistributedSharedMemory多个物理上具有独立内存的处理单元，通过高速网络连接在一起逻辑上作为共享内存并行机使用不同处理单元间内存的共享通过特殊的硬件/软件实现具有比SMP型计算机更好的可扩展性（超过100个CPU）代表机型：SGIOrigina2000/3000并行计算现状(硬件)SMP/DSM机群多台SMP型/DSM型并行机通过互联网络连接而成目前国内外最高性能的并行机大多是这种结构并行计算现状(硬件)微机/工作站机

5、群微机机群(PCcluster,又称BeowulfCluster）,工作站机群(NOW,NetworkofWorkstations):将联网的多台微机/工作站组织诚意台并行机。适用于中等规模的并行系统，(数百个处理器)根据机群中使用的机型分为同构型和议购型两种根据使用方式可分为专用型和兼用型，前者指专门用于并行计算。价格便宜、配置灵活，但规模及并行效率收网络设备的制约，配以适当的系统工具可以达到MPP的以适当的系统工具可以达到MPP的使用效果并行计算现状(软件):“并行软件开发远远落后于并行系统体系结构的发展.”:“与串行软件相比,并行软件数量少,功能原始.”----悲观者并行计

6、算现状:编程环境落后的并行编译器,调试器vs.通用先进的串行编程环境.自动并行编译器远远满足不了程序并行化的要求.:算法并行模型的多样化vs.串行编程中的唯一模型:冯.诺依曼模型对串行机而言,解法=唯一串行算法+计算程序(通用)对并行机而言,解法=某种并行算法+有针对性的计算程序(很难通用):人稀少而初级的并行编程人员vs.成熟而经验丰富的串行程序员并行计算现状:“并行编程正处理蓬勃发展时期,机遇与挑战并存.”----乐观者并行计算现状(并行编程模式)自动并行与手工并行在SMP/DSM并行机上编译系统通常具有一定的对用户程序进行自动并行化的能力但需人工干预（制导语句，命令行选

7、项），针对循环（细粒度)并行分布式内存并行机上不具备，需人工编写并行程序并行算法的设计和并行程序的编制成为大规模并行机应用的主要障碍。并行计算现状(并行编程模式)OpenMP:串行程序的循环语句前插入特定的制导语句，告知编译系统一些有助于对其进行并行的信息，以及/或是强制编译系统按照指定的方式将其并行化主要是SMP/DSM，某些MPP也开始发展结合编译系统的自动并行化功能使用某些自动化工具，可对程序结构及数据流分析，自动插入适当的OpenMP语句优点：简单