并行计算基础知识讲座PPT讲稿.ppt

并行计算基础知识讲座第1页，共50页，编辑于2022年，星期六主要内容n并行计算环境n并行算法基础n什么问题可以并行化n串行程序如何改为并行程序第2页，共50页，编辑于2022年，星期六为什么需要并行计算机问题:科学和工程问题的数值模拟与仿真计算密集数据密集网络密集三种混合要求:在合理的时限内完成计算任务秒级制造业分钟级短时天气预报(当天)小时级中期天气预报(310日)尽可能快长期天气预报(气候)可计算湍流模拟第3页，共50页，编辑于2022年，星期六什么任务适合在超级计算环境内运行？n一般来说，计算量极大而使PC不能满足要求或者根本不能计算的任务是适合在超级计算环境中运行的。比如，（1）需要分布式并行处理的科学计算任务，包括：由于对计算资源要求过大而使现在的硬件条件无法满足要求的计算任务，通过将串行源代码改编为并行源代码来进行计算，或者有通行的并行计算程序（商业或非商业）；（2）虽然可以计算但是时间过长的问题等。第4页，共50页，编辑于2022年，星期六并行计算机的分类并行计算机的分类n并行向量机（PVP）n对称多处理共享存储多处理机（SMP）n大规模并行处理机（MPP）n工作站（微机）机群（COW）n分布式共享存储多处理机（DSM）第5页，共50页，编辑于2022年，星期六COW(Cluster of Workstation)n一个节点可以是一台PC或SMP；n各节点一般由商品化的网络互连；机群节点通过使用标准网络协议（TCP/IP）来通信。使用的是千兆网。n每个节点一般有本地磁盘；n节点上的网络接口是松散耦合到I/O总线上；n每个节点有一个完整的操作系统,但是通过中间层实现了单一系统映像（SSI）。第6页，共50页，编辑于2022年，星期六单一系统映像n单一系统映像（Single System Image，SSI）并不是指系统中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统。n其基本特征是单一系统、单一控制、对称性、位置透明。采用SSI的主要目的，是使机群的使用、控制和维护似乎和一台工作站一样。n单一系统映像包括单一入口点、单一文件层次结构、单一I/O空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间。第7页，共50页，编辑于2022年，星期六定制网络P/CMBMBLDNICIOBP/CMBMBLDNICIOB第8页，共50页，编辑于2022年，星期六第9页，共50页，编辑于2022年，星期六并行机软件环境n操作系统方面：RatHat9.0n程序设计语言：Fortran 77、Fortran 90、C/C+等第10页，共50页，编辑于2022年，星期六什么是并行算法n算法是解题的精确描述，是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解n并行算法就是对并行计算过程的精确描述第11页，共50页，编辑于2022年，星期六并行算法的分类n非数值计算并行算法n数值计算并行算法，基于矩阵运算、多项式求解、线性方程组求解等代数关系运算的计算问题。第12页，共50页，编辑于2022年，星期六进程进程 1 发送信息发送信息进程进程 2 接收信息接收信息传统的串行计算串行计算，分为“指令”和“数据”两个部分，并在程序执行时“独立地申请和占有”内存空间，且所有计算均局限于该内存空间。并行计算并行计算将进程相对独立的分配于不同的节点上，由各自独立的操作系统调度，享有独立的CPU和内存资源（内存可以共享）；进程间相互信息交换通过消息传递；进程进程 1 进程进程 2 第13页，共50页，编辑于2022年，星期六进程间通信n现代操作系统提供基本的系统调用函数，允许位于同一台处理机或不同处理机的多个进程之间相互交流信息，操作具体表现为三种形式：通信、同步和聚集。n以上的三种形式统称为进程间通信，操作的具体数据对象为消息，具体的操作为消息传递。第14页，共50页，编辑于2022年，星期六通信n进程间的数据传递称为进程间通信。n在同一台处理机中，通信可以读/写操作系统提供的共享数据缓存区来实现。n不同处理机中，通信可以通过网络来实现。第15页，共50页，编辑于2022年，星期六同步n同步是使位于相同或不同处理机中的多个进程之间的相互等待的操作，它要求进程的所有操作均必须等待到达某一控制状态之后才并行。第16页，共50页，编辑于2022年，星期六聚集n聚集将位于相同后不同处理机中的多个进程的局部结果综合起来，通过某种操作，例如最大值、最小值、累加和，产生一个新的结果，存储在某个指定的或者所有的进程变量中。第17页，共50页，编辑于2022年，星期六共享存储共享存储共享存储共享存储的模型和语言(适于PVP,SMP,DSM)X3H5,PthreadOpenMP消息传递消息传递消息传递消息传递的模型和语言的模型和语言的模型和语言的模型和语言(适于适于适于适于MPP,Cluster,COW)MPP,Cluster,COW)MPI(MPI(Fortran,C,Gamess,VaspFortran,C,Gamess,Vasp)PVM(PVM(Fortran,CFortran,C)数据并行数据并行数据并行数据并行的模型和语言的模型和语言的模型和语言的模型和语言(适于在适于在适于在适于在MPP/ClusterMPP/Cluster上实现上实现上实现上实现SPMDSPMD应用应用应用应用)Fortran 90Fortran 90HPF(High Performance Fortran)HPF(High Performance Fortran)并行编程环境第18页，共50页，编辑于2022年，星期六MPI(Message Passing Interface)在当前所有的消息传递软件中,最重要最流行的是MPI,它能运行在所有的并行平台上。程序设计语言支持C,Fortran等。第19页，共50页，编辑于2022年，星期六 MPI已经成为一种标准，它以与语言独立的形式来定义这个接口库,这个定义不包含任何专用于某个特别的制造商、操作系统或硬件的特性.由于这个原因,MPI在并行计算界被广泛地接受.第20页，共50页，编辑于2022年，星期六nMPI标准的实现包括MPICH、LAM、IBM MPL等多个版本，最常用和稳定的是MPICH。它提供了与C、Fortran语言的绑定。第21页，共50页，编辑于2022年，星期六n我们可以将MPI看成一个“库”，目前使用的消息传递库是MPICH 1.2，共有上百个接口，在FORTRAN 77和C语言中可以直接对这些函数进行调用。多个进程通过调用这些函数（类似调用子程序），进行通信；第22页，共50页，编辑于2022年，星期六Include文件nC语言应用程序应有#include“mpi.h”nFortran语言应用程序应有#include mpif.h第23页，共50页，编辑于2022年，星期六MPI并行编程模式n单程序多数据流模式（SPMD）n多程序多数据流模式（MPMD）为了降低使用和维护并行应用软件的复杂度，一般采用SPMD模式第24页，共50页，编辑于2022年，星期六MPI程序的SPMD执行模式n一个程序同时启动多份,形成多个独立的进程，在不同的处理机上运行，拥有独立的内存空间，进程间通信通过调用MPI函数来实现；第25页，共50页，编辑于2022年，星期六SPMD模式：单程序多数据流模式：单程序多数据流 第26页，共50页，编辑于2022年，星期六例一n进程0发送一个整数给进程1；进程1将该数加1，传递给进程2；进程2再将该数加1，再传递给进程3；依次类推，最后，进程N-1将该数传递给进程0，由进程1负责广播该数给所有进程，并打印输出。第27页，共50页，编辑于2022年，星期六进程1传递信息进程3传递信息进程2传递信息进程0传递信息第28页，共50页，编辑于2022年，星期六编译运行命令nmpif77 o exam exam.fnmpirun np 4 exam n其中，exam.f指需要编译的源文件，o表示生成输出文件，exam指输出文件名，np表示进程数。n使用mpicc和mpif77省略了有关MPI的路径设置第29页，共50页，编辑于2022年，星期六第30页，共50页，编辑于2022年，星期六什么可以并行n能否将顺序执行的程序转换成语义等价的、可并行执行的程序，主要取决于程序的结构形式，特别是其中的数据相关性。第31页，共50页，编辑于2022年，星期六nP1：AB+CnP2：DAB 其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。n显然，P1和P2不能并行执行。数据相关第32页，共50页，编辑于2022年，星期六数据反相关nP1：ABCnP2：CE+D P1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。n也不可并行化第33页，共50页，编辑于2022年，星期六数据输出相关nP1：AB+CnP2：ADE 为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。除了上述3种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。第34页，共50页，编辑于2022年，星期六相关性与可并行化伯恩斯坦准则 I1O2，即P1的输入变量集与P2的输出变量集不相交；I2O1，即P2的输入变量集与P1的输出变量集不相交；O1O2，即P1和P2的输出变量集不相交n可并行处理第35页，共50页，编辑于2022年，星期六如何将串行程序改为并行n为理解创建一个并行程序中的步骤，为理解创建一个并行程序中的步骤，让让我们首先定义三个重要的概念我们首先定义三个重要的概念:任务，任务，进程和处理器。进程和处理器。第36页，共50页，编辑于2022年，星期六任务n任务是程序要完成的一个工作，任务是程序要完成的一个工作，其内容其内容和大小是随意的，和大小是随意的，它是并行程序所能处它是并行程序所能处理的并发性最小的单元理的并发性最小的单元;即一个任务只能即一个任务只能由一个处理器执行，由一个处理器执行，处理器之间的并发处理器之间的并发性只能在性只能在任务之间开发。第37页，共50页，编辑于2022年，星期六进程n进程(我们也称为线程)是一个完成任务的实体。一个并行程序由许多合作的进程构成，每个完成程序中任务的一个子集。通过某种分配机制，任务被分配给进程。n进程完成其任务的方式是通过在机器的物理处理器上执行 第38页，共50页，编辑于2022年，星期六进程与处理器的区别n并行化的观点，并行化的观点，：处理器是物理资源，处理器是物理资源，进程是抽象，进程是抽象，或者虚拟化多处理器的一或者虚拟化多处理器的一种方便的方式种方便的方式:我们通过进程，我们通过进程，而不是而不是处理器来写并行程序处理器来写并行程序;将进程映射到处理将进程映射到处理器是下一步。器是下一步。在一次程序的执行中，在一次程序的执行中，进进程数不一定要等于处理器数。程数不一定要等于处理器数。如果进程如果进程多，多，一个处理器有可能要执行多个进程一个处理器有可能要执行多个进程;如果进程少，如果进程少，某些处理器则要闲置某些处理器则要闲置第39页，共50页，编辑于2022年，星期六串行程序并行化的几个步骤n 从一个串行程序得到一个并行程序的工作由四个步骤构成：1.将计算的问题分解成任务 2.将任务分配给进程 3.在 进 程 之 间 组 织 必 要 的 数 据 访 问，通信，和同步。4.将进程映射或绑定到处理器第40页，共50页，编辑于2022年，星期六n在以上的几个步骤中，并没有考虑并行的效率问题。n考虑到消息传递的开销是计算开销的10倍以上，一般来说，如果在应用的一部分中，计算的时间是分钟级的而数据传输的时间是秒级的，那么这一部分可以并行执行。估计并行的效率第41页，共50页，编辑于2022年，星期六例二：矩阵相乘C=A B其中A 和B 分别是m k 和k n 矩阵,C 是m n 矩阵.不失一般性,假设m=m p,k=k p和n=n p。第42页，共50页，编辑于2022年，星期六串行程序doubleaNN,bNN,cNN;for(i=0;iN;i+)for(j=0;jN;j+)for(k=0;kN;k+)cij+=aik*bkj;第43页，共50页，编辑于2022年，星期六并行实现n先将矩阵分块 第44页，共50页，编辑于2022年，星期六n将 存放在 中，使数据在处理机中不重复。n矩阵A在各自进程中保持不变，B在处理机中每次循环向前移动一个处理机。第45页，共50页，编辑于2022年，星期六第46页，共50页，编辑于2022年，星期六n对应于前面所提到的四个步骤，矩阵乘法并行算法可做如下表述：n1、将问题（矩阵乘法）分成p个任务，即将C的求解分成p块。n2、每个进程对应一个C块的求解。第47页，共50页，编辑于2022年，星期六n组织进程间的通讯。即将B的各个子块send()到各个进程。n通过mpirun运行,将进程映射到处理器上。第48页，共50页，编辑于2022年，星期六并行描述for i=0 to p 1 dol i+myid mod pCl=A*B,mp1 myid+1 mod p,mm1 myid-1 mod pif i！=p 1,send(B,mm1),recv(B,mp1)Endfor第49页，共50页，编辑于2022年，星期六 谢谢！第50页，共50页，编辑于2022年，星期六