还剩3页未读,继续阅读
文本内容:
有关并行算法专业指导老师班级学号姓名日期广西工学院计算机学院有关并行算法
一、并行计算技术概述60年月初期,由于晶体管技术与存储器技术的进展导致并行计算机的消失,这一时期的典型代表就是IBM360o创建和使用并行计算机的主要缘由是由于并行计算机是解决箪处理器速度瓶颈的最好方法之一并行计算机是由一组处理单元组成的,这组处理单元通过相互之间的通信与协作.以更快的速度共同完成一项大规模的计算任务因此,并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制并行计算机体系结构的进展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面就单台计算机系统而言.采纳SMP技术是扩展其佳能的比较有效的方法.它可以将系统中的多个操作系统分布在多个处理器上执行以获得并行处理的效果SMP技术可以通过多线程并行来提高性能通过采纳并行多线程技术,服务器可以通过SMP技术同时处理多个应用恳求.使得这些程序获得了更好的运行效果,而且在前式机的专业应用软件中,并行多线程技术的采纳也日益增多伴随SMP技术的消失.带来此外的问题,那就是当应用增加时.虽然可以通过增加处理器的方法来扩展系统力量,但是,一方面需要有扩展连接处理器的系统总线的超群技术,并不是每个系统厂商都能做到,另一方面由于对共享资源的竞争所造成的系统瓶颈.使得单机系统的性能呈非线性增长因此,当应用增加超过单机系统的承受力量时,就采纳集群系统CLUS-rlERo在集群系统中,每台服务器处理各自的工作,供应各自的服务当需要更高的的性能以适应更多的应用肘,既可以升级原有的服务器增加更多的处理器、内存和存储等,又可以在集群系统中增加新的服务器更进一步,集群系统在平衡和扩展整个计算机应用系统的工作负载的同时一,也为用户供应了高性能和高可用性1977年DEC公司推出了以VAX为结点机的松散耦合的集群系统.并胜利地耦VMS操作系统移植到该系统上20世纪90年月后随着RISC技术的进展运用和高性能网络产品的消失集群系统在性能价格比C8t/Perfonuance、【il扩展性ala-bility、可用性Availability等方面都显示出了很强的竞争力,尤其是它在对现有单机上的软硬件产品的继承和对商用软硬件最新讨论成果的快速运用,从两方面表现出传统MPP无法比拟的优势这里所介绍的高性能计算环境,从程序开发角度主要分为以下两类一大类是共享内存系统,包括并行向量机PVPPar-allelVectorPnx:eswr>分布式共享存储多处理机DSM.Dis-tributiedSharedMemory和对称多处理饥SMPSymmer/calMuhiPmcessing等结构,其特点是多个处理器拥有物理上共享的内存,如HP的SuperDome.我们国家曙光1号SGIPowerChal-lenge等;另•一大类是分布存储系统DMP如大规模并行处理机MPP.MassivelyParallelProcessor和集群系统Cluster其特点是系统由多个物理上分布的结嬴组成,每个结点拥有自己的内存.
二、什么是并行算法并行算法parallelcomputing是指,在并行机上,将一个应用分解成多个子任务安排给不同的处理器,各处理器之间相互协调,并行地执行子任务,从而达到加速求解速度或者求解大规模应用问题的目的开展并行计算,必需具备三个节本条件并行机并行机至少包含两台或两台以上处理机,这些处理机通过通过互联网相互连接,相互通信应用问题必需具有并行度也就是说,应用可以分解为多个子任务,这些子任务可以并行地执行,将一个应用分解为多个子任务的过程,称为并行算法的设计并行编程在并行机供应的并行编程环境上,详细实现并行算法,编制并行程序,并运行该程序,从而达到并行求解应用问题的目的
三、并行算法的基本原理并行计算是同时使用多种计算资源解决计算问题的过程并行计算的主要目的是快速解决大型且简单的计算问题此外还包括采用非本地资源,节省成本一使用多个“廉价”计算资源取代大型计算机,同时克服单个计算机上存在的存储器限制传统地,串行计算是指在单个计算机具有单个中心处理单元上执行软件写操作CPU逐个使用一系列指令解决问题,但其中只有一种指令可供应随时并准时的使用并行计算是在串行计算的基础上演化而来,它努力仿真自然世界中的事务状态一个序列中众多同时发生的、简单且相关的大事为采用并行计算,通常计算问题表现为以下特征1将工作分别成离散部分,有助于同时解决;2随时并准时地执行多个程序指令;3多计算资源下解决问题的耗时要少于单个计算资源下的耗时并行计算是相对于串行计算来说的,所谓并行计算分为时间上的并行和空间上的并行时间上的并行就是指流水线技术,而空间上的并行则是指用多个处理器并发的执行计算并行计算的主要讨论内容大致可分为四个方面1并行计算机的并行性抽取,充分理解和抽取当前并行计算机体系结构的高性能特征提出有用的并行计算模型和并行计算评价方法2并行计算设计与分析,设计高效率的并行算法,将应用问题分解为可并行计算的多个子任务3并行实现技术,主要包含并行程序设计和并行性能优化4并行应用,这是并行计算讨论的最终目的
四、并行计算机的分类SIMD机器是指单指令流多数据流并行机,也即指系统中各功能部件或处理机对多组数据执行相同的指令流或操作SIMD机器在任何时刻只有一条指令在执行所以该类计算机的主要特征是同步的、确定的它适合于指令/操作级并行MIMD并行机是指多指令流多数据流并行机,也即指系统中的各处理机在各自唯一的数据流上执行各自的指令流,与其它处理机无关MIMD的一个特例是单程序、多数据计算,即全部处理机执行同一程序,而由进程指标加以参数化,从而完成对不同数据的操作分布存储MIMD并行多处理机,该系统中每台处理机都有自己的局部存储器,构成一个单独的节点,节点之间通过互连网络相互连接每台处理机只能直接访问局存,不能访问其它处理机的存储器,它们之间的协调以消息传递的方式进行分布共享存储MIMD并行机,分布共享存储结构也称为非全都内存访问结构,是指系统中的每台处理机都有自己的局部存储器,但这些局存组合起来形成了一个统一的共享地址空间
五、并行计算机的体系结构并行计算机体系结构是指并行处理系统主要是分布式系统中处理机或节点机之间的互连方式,它直接影响并行算法的实现效率并行计算机体系机构分类1总线结构;2网格结构;3超立方体结构总线结构中个处理机共享同一条物理线路,同一时刻只允许也有一个处理机发送消息,当有多个处理机同时发送消息时,将使用仲裁机制打算消息发送挨次从而导致通信开销的增大网络结构,也就是二维阵列,可以分为环绕连接和无环绕连接两种方式,n*n网格结构的网络直径为2n-lo超立方体结构,n=2%个节点可构成一个q维超立方体若用q位二进制数对节点进行编号,则超立方体结构中有两个节点相连的充分必要条件是节点的编号有且仅有一个不同
六、并行算法的分类依据基本运算对象的不同可分为以下两种数值并行算法,主要是指为数值计算设计的并行算法,如矩阵运算、多项式求解、解线性方程组等非数值并行算法,是指为基于关系运算的一类诸如排序、选择、分类、搜寻及图论等方面的非数值计算问题设计的并行算法依据并行进程间执行挨次关系的不同可分为以下几种同步并行算法,是指某些进程必需等待别的进程的一类并行算法,异步并行算法,是指诸进程的执行一般不必相互等待的一类并行算法,进程间的通信一般是通过动态地读、取修改共享存储器的全局变量如通常运行在MIMD机模型上的并行算法独立并行算法,进程间执行是完成独立的,计算的整个过程不需要任何通信,例如气象预报应用中通常需要同时计算多个模型,以保证预报的实时性
七、并行算法的性能问题
1、硬件性能指标a重要的性能指标是CPU和输入/输出的速度以及互连网络的性能b互连网络的性能有两个重要的指标延时Latency和带宽Bandwidth延迟时间是指从CPU发送分组至接收到响应的时间间隔对分带宽、聚集带宽和平均带宽依据CPU力量算
2、软件性能指标最关键的性能指标是加速比speedup一个程序在有n个处理器的计算机运行和在只有一个处理器的计算机上运行相比快多少倍抱负的加速比不行能达到的部分缘由是几乎全部的程序都有串行部分假定一个程序在单处理器计算机上运行需要T秒,其中一部分是串行代码,所占比例记为f那么剩余的1-f就是可以并行的后一部分代码运行在n个CPU上而且没有任何其它开销,那么在最抱负的状况下,执行时间可以从1-fT削减到1-fT/no串行部分加并行部分的整个执行时间就是fT+1-fT/no加速比就是原来程序的执行时间除以新的程序的执行时间
八、并行程序的开发模式.共享内存模式共享内存并行模式编程相对较为简洁,程序员不用考虑数据在内存中的位置,进程管理及同步操作由系统完成但是用这种方式编制的程序通常并行效率不高,由于它属于细粒度并行,主要针对循环进行并行处理此外共享内存并行模式只能运行在共享内存类型的计算机系统上在共享内存模型中,一个并行程序由多个共享内存的并行任务组成,数据的交换通过隐含地使用共享数据来完成此编程模式一般仅衙指定可以并行执行的循环,而不需考虑计算与数据如何划分.以及如何进行任务间通信,编译器会自动完成上述功能目前业界流行的共享内存模型开发标准是OpenMPoOpenMP定义了一套编译指导语句,用于指定程序的并行性、数据的共享,私有等信其目标是为SMP系统供应可移植、可扩展的开发接口IntelDECSiliconGraphics.KuchAssociates和IBM早在15午前就联合定义了OpenMP早期标准.新的OpenMP标准由OpenMPArchitectureReviewBoard于1997年推出,现在已进展到
2.0版.消息传递模式在消息传递模式中,一个并行程序由多个并行任务组成每个并行任务拥有自己的数据并对其进行计算操作任务之间数据的交换是通过显式的消息传递语句来完成的消息传递的并行方式虽然是在分布式内存的计算机结构基础上进展而来的但是几乎全部类型的计算机都支持这种并行模式,因此更具通用性消息传递方式的并行属于粗粒度并行,程序员负责进程管理、消息传递及同步.并行的工作量要大于共享内存并行模式但同时程序员可以掌握的也更多,可以通过认真考虑任务安排并行算法等方式对程序进行优化因而获得较高的并行效率国际上采纳消息传递方式的应用软件远远多于采纳共享内存并行模式的应用软件国内的高性能计算用户也大多采纳消息传递的并行方式开发自己的应用程序现在广泛使用的消息传递模型有两个PVM和MPIoPVM即ParallelVutualMachine并行虚拟机与MPI即MessagePas8-ingIntedace消息传递界面PVM与MPI所供应的功能大致相同.但两者的侧重点有所不同PVM强调在异构环境下的可移植性和互操作性程序之间可以相互通信,并支持动态的资源管理和肯定程度的容错而MP!更强调性能,不同的MPI实现之间缺乏互操作性,本身也不支持容错可以通过特地的容错软件来支持容错一般而言,使用MPI比较适合于开发MPP或同构集群上的并行应用,可以有较高的通信性能而PVM更适合于异构的集群系统
九、目前流行的并行程序设计的方法及其优缺点MPIMPIMessagePassingInterface消息传递接口是MPI论坛发布的一个库,而不是一门实现语言,支持C/C++/Fortran是一种消息传递编程模型,为进程间通信服务MPI供应了一种与平台无关,可以被广泛使用的编写消息传递程序的标准用它来编写消息传递程序,不仅有用、可移植、高效和敏捷,而且和当前已有的实现没有太大的变化优点可以在集群上使用,也可以在单核/多核CPU上使用,它能协调多台主机间的并行计算,因此并行规模上的可伸缩性很强,能在从个人电脑到世界T0P10的超级计算机上使用缺点第一,基于消息传递,需要显示划分和分布计算任务,显示进行消息传递与同步且不易增量开发串行程序的并行性;其次,使用进程间通信的方式协调并行计算,这导致并行效率较低、内存开销大、不直观、编程麻烦OpenMPOpenMPOpenMultiProcessing是由OpenARB发布的一种用于并行编程的法律规范,是建立在串行语言上的扩展,目前可以在C/C+VFortran中使用OpenMP由三部分组成:编译指导compilerdirective运行库runtimelibrary和环境变量environmentvariableso其语言模型基于以下假设执行单元是共享一个地址空间的线程,即OpenMP是基于派生/连接fork/join的编程模型Fork/join并行机制并行区前,串行命令派生出多条并行命令并行执行,执行到并行区末等待,等全部并行任务都结束,再转到串行执行OpenMP有两种常用的并行开发形式一是通过简洁的fork/join对串行程序并行化;二是采纳单程序多数据对串行程序并行化优点第一,共享存储模型,使得程序员不必进行数据划分和分布,使得开发并行程序比较简洁;其次,更适合于SMP系统;第三,主要面对循环级的并行开发,可以简洁地实现增量性的并行化缺点第一,OpenMP只适用于SMP结构;其次,OpenMP主要开发循环级的并行程序,受此限制,对某些应用并不适合;第三,OpenMP的编写、正确性调试和性能调度简单IntelIPPIntelIPPIntegratedPerformancePrimitivesIntel集成性能基元是Intel函数库的其次代Intel为每种新的多核处理器都发布一个IPP函数库C/C++API专用于多核架构,供应了调度优化的函数库,其中涉及的领域有数学、信号处理、音频视频、图像处理与编码、字符串、密码学优点是经过性能高度优化的库,执行效率高缺点专用于Intel处理器和某些领域,不便利移植进展趋势为广泛的多媒体供应功能,并着眼于持续改进产品的生命周期IntelTBBIntelTBBThreadingBuildingBlocksIntel线程构建模块,是一个为创建牢靠的、可移植的和可扩展的并行程序的C++模板库专用于编写高层抽象的C++程序,和可移植的程序优点可移植、可扩展缺点性能没有IPP高进展趋势扩展TBB到支持java和・netMapReduceMapReducesh是Google的人讨论出来的一个模型,开发的一个针对大规模群组中的海量数据处理的分布式编程模型优点能用于处理大规模数据,能将许多繁琐的细节隐蔽起来,伸缩性特别好缺点不适应实时应用的需求进展趋势用优化云计算下的的编程。