《并行计算工作原理》PPT课件.ppt

2004年4月,1/149,并行计算-高性能计算,并行计算(Parallel Computing） 高端计算(High-end Parallel Computing) 高性能计算(High Performance Computing) 超级计算(Super Computing) 任何高性能计算和超级计算都离不开使用并行技术,2004年4月,2/149,什么是并行计算?,并行计算: 由运行在多个部件上的小任务合作来求解一个规模很大的计算问题的一种方法 例: 在曙光2000上用8个节点计算的Mandelbrot集结果(Mandelbrot为分形理论创始人),2004年4月,3/149,现代计算机的共同特点： 并行性,2004年4月,4/149,现代计算机的共同特点： 并行性,2004年4月,5/149,如何实现并行计算?,分而治之!,2004年4月,6/149,分而治之,并行化的主要方法:分而治之 根据问题的求解过程，把任务分成若干子任务(任务级并行或功能并行) 根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理(数据并行),并行计算的特点,为利用并行计算，通常计算问题表现为以下特征： （1）将工作分离成离散部分，有助于同时解决； （2）随时并及时地执行多个程序指令； （3）多计算资源下解决问题的耗时要少于单个计算资源下的耗时。 并行计算是相对于串行计算来说的，并行计算分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。,并行计算机的分类,并行计算科学中主要研究的是空间上的并行问题。 空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD Multiple Instruction Stream Multiple Data Stream ）。我们常用的串行机也叫做单指令流单数据流（SISD）。,SISD,SIMD,MIMD,9,并行计算机体系结构,10,并行计算机体系结构,并行计算机体系 结构示意图 内存模块与结点分离,并行计算机体系 结构示意图 内存模块位于 结点内部,11,操作系统与编程语言,并行计算机主流操作系统：UNIX / Linux,AIX（IBM） HPUX（HP） Solaris（SUN） IRIX（SGI） Linux,编程语言,Fortran 77/90/95 C/C+,2004年4月,12/149,并行计算软件环境及现状,操作系统：UNIX、LINUX、Windows NT 在SMP,DSM并行机上编译系统通常具有一定的对用户程序(C/Fortran) 进程自动并行化的能力,但经常需要人工干预 (通过编译制导,命令行选项等) 以达到理想的并行效率.且并行主要针对循环进行 (属于细粒度并行); 在分布式内存并行机上尚无通过高效的自动并行工具,主要依靠人工编写并行程序; 并行算法的设计及并行程序的编制已成为目前特约大规模并行计算机应用的主要障碍. 并行编程现状 : 并行软件开发远远落后于并行系统体系结构的发展。缺少合适的并行软件是阻碍主流用户社会接纳并行计算的原因。 : 与串行软件相比，并行软件数量少，功能原始。,2004年4月,13/149,?,编程环境 落后的并行编译器、调试器 vs. 通用先进的串行编程环境. 自动并行编译器远远满足不了程序并行化的要求. 3算法 并行模型的多样化(并行计算机系统结构的多样性) vs. 串行编程中的唯一模型: 冯.诺依曼模型 问题的并行求解的困难在于问题的多样性和求解过程中所需的创造性劳动，使得这一过程难以进行自动化 对串行机而言, 解法 = 唯一串行算法+计算程序(通用) 对并行机而言, 解法 = 某种并行算法+有针对性的计算程序(很难通用) J人 稀少而初级的并行编程人员 vs. 成熟而经验丰富的串行程序员,2004年4月,14/149,一些途径,充分利用顺序程序开发的经验、方法和工具，特别是顺序领域中的问题求解、算法设计方法，这是简化并行程序开发的重要手段。 并行程序开发的困难主要在于问题的并行求解，而不是并行程序设计语言。“从事并行程序设计实践的人往往把精力耗费在为变量分配内存、为循环体寻求并行上，却忽略对问题本身的分析。其实能否并行的决定因素是应用问题本身。” 在并行算法的设计阶段最大限度地开发出问题本身固有的并行性才是提高计算效率的根本手段。只有粗粒度的并行，才能具有高的计算通信比，而粗粒度的并行只能在算法设计阶段开发出来,15,并行编程环境,常见的并行编程环境,消息传递、共享存储、数据并行,三种并行编程环境主要特征一览,实现并行编程常见方法,1.线程模型（OpenMP,POSIX) 2.消息传递模型（PVM，MPI） PVM:Parallel Virtual Machine Computing MPI:Message Passing Interface 3.数据并行模型（HPF）,三者可混合使用: 如对以SMP为节点的Cluster来说, 可以在节点间进行消息传递,在节点内进行共享变量编程.,18,并行算法,适合在并行机上实现的算法 好的并行算法应充分发挥并行机计算机的潜在性能,并行算法,并行算法分类,按运算对象：数值并行算法、非数值并行算法 按并行进程执行顺序： 同步并行算法、异步并行算法、独立并行算法 按计算任务： 细粒度并行算法（基于向量和循环级并行） 中粒度并行算法（基于较大的循环级并行） 大粒度并行算法（基于子任务级并行）,并行的层次,程序级并行 子程序级并行 语句级并行 操作级并行 微操作级并行,并行粒度,粗,细,后三层大都由硬件和编译器负责处理，程序员通常处理前两层的并行,并行计算机的存储结构,共享内存、分布式内存、混合型分布式共享内存,接点间的连接,按连接方式分类： Completely-connected, Star, Tree, Linear Array and Ring, Hypercube 集群计算机： 通过高速网络LAN将PC机或工作站连结而成。,接点间的连接,按连接方式分类： Completely-connected, Star, Tree, Linear Array and Ring, Hypercube 集群计算机： 通过高速网络LAN将PC机或工作站连结而成。,问题分解,1.作用域分解：与问题相关的数据将会被分解。每个并行的任务只能使用部分数据 。 2.功能分解：关注要被完成的计算而不是操作数据的计算。问题是根据当前一定要完成的任务划分的。每个任务完成全部工作的一部分 。,关注的问题,1、通信 2、同步 3、数据依赖 4、负载平衡 5、I/O,并行计算的性能分析,1、加速比（speedup) 2、并行效率,并行计算的术语（1）,Task：可计算工作在逻辑上不连续的分区。一个任务通常是一个程序或者类似程序一样的可以被处理器执行的指令集。 Parallel Task：一个任务可以被多个处理器安全的并行的执行，产生正确的结果。 Serial Execution：程序相继的执行，每次一个状态。在最简单的情况下，单核处理器就是这样运行的。可是，实际上所有并行的任务有一些并行程序的区域一定要串行的执行。 Parallel Execution：一个或多个任务同时执行的程序，每个任务同时能够执行相同的或不同的代码语句。 Pipelining：不同的处理器单元把一个任务根据输入流来分解成一系列步骤来执行，相当于一条流水线；并行计算的一种。,并行计算的术语（2),Shared Memory（共享内存）：完全从硬件的视角来描述计算机体系结构，所有的处理器直接存取通用的物理内存（基于总线结构）。在编程的角度上来看，他指出从并行任务看内存是同样的视图，并且能够直接定位存取相同的逻辑内存位置上的内容，不管物理内存是否真的存在。 Symmetric Multi-Processor（对称多处理器）：这种硬件体系结构是多处理器共享一个地址空间访问所有资源的模型；共享内存计算。 Distributed Memory（分布式存储）：从硬件的角度来看，基于网络存储的物理内存访问是不常见的。在程序模型中，任务只能看到本地机器的内存，当任务执行时一定要用通信才能访问其他机器上的内存空间。 Communication：并行任务都需要交换数据。有几种方法可以完成，例如：共享内存总线、网络传输，然而不管用什么方法，真实的数据交换事件通常与通信相关。 Synchronization：实时并行任务的调度通常与通信相关。总是通过建立一个程序内的同步点来完成，一个任务在这个程序点上等待，直到另一个任务到达相同的逻辑设备点是才能继续执行。同步至少要等待一个任务，致使并行程序的执行时间增加。,并行计算的术语(3),Observed Speedup：测量代码并行化之后的加速比。这是最简单也最广泛使用的测量并行程序性能的方法。 Parallel Overhead（并行开销）：对并行任务调度花费的时间没有做有用的工作。并行开销可以包含如下因素：任务启动时间、同步、数据通信、并行编译器、库、工具、操作系统等花费的软件开销，任务终止的时间等。 Scalability：指的是并行系统通过增加更多的处理器的个数按比例提高并行性能的能力。促进可扩展性的因素有：硬件特