并行课件2008-2

1、并行算法与编程并行算法与编程 何兵寿何兵寿133708617591337086175966782297(O)66782297(O)思考题思考题 (4) (4) 如何解决更大规模的问题？如何解决更大规模的问题？(1) (1) 回忆你所接触和了解的计算机，它们之间有哪些不同？回忆你所接触和了解的计算机，它们之间有哪些不同？微机、小型机、巨型机微机、小型机、巨型机体积的大小，速度，容量，求解问题的规模体积的大小，速度，容量，求解问题的规模(2) (2) 就你所了解的程度，想一下计算机是如何解决问题的？就你所了解的程度，想一下计算机是如何解决问题的？问题分析、模型，算法，程序，指令，存储问题分析、模型

2、，算法，程序，指令，存储 (3) (3) 你认为如何才能够使计算的速度变得更快？你认为如何才能够使计算的速度变得更快？提高时钟频率提高时钟频率( (一个时钟周期执行的指令条数一个时钟周期执行的指令条数),),更快的存储器更快的存储器不同级别的并行不同级别的并行更大的存储，更快的速度，更多的计算单元或计算机更大的存储，更快的速度，更多的计算单元或计算机地球物理技术发展的需要！地球物理技术发展的需要！地球物理学的特点：地球物理学的特点：1 1、地质、物理、数学、计算机、地质、物理、数学、计算机2 2、计算量庞大、计算量庞大3 3、软件技术举足轻重、软件技术举足轻重地信专业培养计划的规定地信专业培养

3、计划的规定 培养具有大型地学软件开发的专业人才培养具有大型地学软件开发的专业人才为什么要开设这门课程？为什么要开设这门课程？课程内容课程内容 并行计算机与并行算法的基础知识并行计算机与并行算法的基础知识 几种基本的并行算法几种基本的并行算法 MPIMPI程序设计程序设计目的：目的： 了解和掌握大型科学与工程问题中的基本并行了解和掌握大型科学与工程问题中的基本并行编程技术。编程技术。课程基础课程基础C C语言语言FORTRANFORTRAN语言语言UNIXUNIX系统知识系统知识高等数学高等数学高等工程数学高等工程数学参考资料参考资料高性能计算并行编程技术高性能计算并行编程技术MPIMPI并行程

4、序设计并行程序设计 都志辉都志辉 清华大学出版社清华大学出版社并行算法实践并行算法实践 阵国良等阵国良等 高等教育出版社高等教育出版社并行计算并行计算-结构、算法、编程结构、算法、编程 阵国良等阵国良等 高等教育出版社高等教育出版社 /mpi/mpich/mpi/mpichftp:/ftp.epcc.ed.ac.uk/pub/packages/chimp/release/ftp:/ftp.epcc.ed.ac.uk/pub/packages/chimp/release/http:/www.m

5、第一章第一章 并行程序设计基础并行程序设计基础 什么叫并行计算？什么叫并行计算？ 什么叫并行计算机？什么叫并行计算机？ 为什么要建造并行计算机？为什么要建造并行计算机？ 并行计算机的发展历史及趋势并行计算机的发展历史及趋势 并行计算的应用范围并行计算的应用范围 并行计算机的分类并行计算机的分类 并行算法及分类并行算法及分类 并行计算在地球物理领域的应用。并行计算在地球物理领域的应用。一、什么叫并行计算？一、什么叫并行计算？考虑下述问题：考虑下述问题： 图书馆将一些书上架（书按类上架，书架按类分图书馆将一些书上架（书按类上架，

6、书架按类分布）布）任务划分：任务划分：将图书分配给各个工人将图书分配给各个工人通信：通信：工人之间传递图书工人之间传递图书方案一：方案一：由一个工人上架由一个工人上架方案二：方案二：由多个工人上架，图书不分类由多个工人上架，图书不分类方案三：方案三：由多个工人上架，每个工人负责一类或几类图书由多个工人上架，每个工人负责一类或几类图书并行计算的定义并行计算的定义并行计算并行计算指同时对多外任务或多条指令或多个数据项指同时对多外任务或多条指令或多个数据项进程处理的一种方法进程处理的一种方法同意词：同意词：高性能计算，超级计算高性能计算，超级计算并行计算的目的并行计算的目的 提供比传统计算机更快的计

7、算速度提供比传统计算机更快的计算速度 解决传统计算机无法解决的问题解决传统计算机无法解决的问题二、什么叫并行计算机？二、什么叫并行计算机？ 完成并行处理的计算机系统称为完成并行处理的计算机系统称为并行计算机并行计算机，它是，它是将多个（几个、几十个，几千个，上万个）处理器通过将多个（几个、几十个，几千个，上万个）处理器通过网网络络连结以一定的方式连结以一定的方式有序有序地组织起来形成的一种特殊的计地组织起来形成的一种特殊的计算机算机。 连接方式连接方式涉及网络之间的互联拓扑、通信协议等涉及网络之间的互联拓扑、通信协议等 有序组织有序组织涉及操作系统、中间软件等涉及操作系统、中间软件等并行计算机

8、示例并行计算机示例并行计算机示例并行计算机示例并行计算机示例并行计算机示例Berkeley于于1994年开发的集群式系统年开发的集群式系统并行计算机示例并行计算机示例国内独立研制的第一套大规国内独立研制的第一套大规模并行机系统模并行机系统曙光曙光1000并行计算机示例并行计算机示例IBM 建造的并行计算中心，建造的并行计算中心，用于美国能源部的核试验用于美国能源部的核试验并行计算机示例并行计算机示例目前地球物理资料处理目前地球物理资料处理中广泛采用的中广泛采用的PC cluster三、为什么要建造并行计算机？三、为什么要建造并行计算机？一、许多问题串行计算机难以解决一、许多问题串行计算机难以解

9、决核试验，地球物理资料处理，天气预报等核试验，地球物理资料处理，天气预报等二、计算速度的要求二、计算速度的要求串行速度提升缓慢；串行速度提升缓慢；需要在更短的时间内解决相同的问题；需要在更短的时间内解决相同的问题；三、问题的规模不断扩大三、问题的规模不断扩大 物理现象的仿真模拟（一维物理现象的仿真模拟（一维 二维二维 三维）三维） 长期天气预报长期天气预报 更为复杂的科学研究更为复杂的科学研究四、对计算结果的精确性的要求不断提高四、对计算结果的精确性的要求不断提高动物的食物链动物的食物链并行计算机主要解决两类问题并行计算机主要解决两类问题一、常规串行机不能解决的问题一、常规串行机不能解决的问题

10、二、常规机器能够解决，但速度很慢的问题二、常规机器能够解决，但速度很慢的问题四、并行计算机的发展历史及趋势四、并行计算机的发展历史及趋势 20世纪世纪70年代末，向量机的出现标志着超级计算机的开始年代末，向量机的出现标志着超级计算机的开始计算速度：提高了一个数量级计算速度：提高了一个数量级提高计算速度的途径：改进芯片技术，提供共享存储多处理器系统提高计算速度的途径：改进芯片技术，提供共享存储多处理器系统 20世纪世纪80年代后期，共享存储方式的大规模并行计算机蓬年代后期，共享存储方式的大规模并行计算机蓬勃发展，超大规模并行机出现勃发展，超大规模并行机出现 贵族计算机贵族计算机 近年来，集群式系

11、统由于具有以下优点而得到了快速发展近年来，集群式系统由于具有以下优点而得到了快速发展 低成本、高性能、短周期，大规模并行，分布式共享内存低成本、高性能、短周期，大规模并行，分布式共享内存 平民的超级计算机平民的超级计算机发展历史发展历史 向量机向量机（芯片级的并行计算机）（芯片级的并行计算机） MPP（Massively Parallel Processors）（主板级的并行计算机）（主板级的并行计算机） Cluster研制难度逐研制难度逐渐降底渐降底发展趋势：发展趋势： 集群式系统将成为并行机的发展主流集群式系统将成为并行机的发展主流 原因：原因：1、传统向量机与共享内存计算机的计算速度很难

12、突破物理极限、传统向量机与共享内存计算机的计算速度很难突破物理极限2、大型计算机价格昂贵，削弱了其市场竞争力、大型计算机价格昂贵，削弱了其市场竞争力3、操作困难，缺乏一个统一的标准、操作困难，缺乏一个统一的标准4、其它诸多原因、其它诸多原因国内的超级计算中心国内的超级计算中心 国家高性能计算中心国家高性能计算中心（北京，合肥，成都，武汉，（北京，合肥，成都，武汉，上海，杭州，西安）上海，杭州，西安） 山东大学高性能计算中心山东大学高性能计算中心 天津高性能计算中心天津高性能计算中心 北京应用物理与计算数学研究所北京应用物理与计算数学研究所- 高性能计算中心高性能计算中心 上海超级计算中心上海超

13、级计算中心 中国科学院的超级计算中心中国科学院的超级计算中心五、并行计算五、并行计算（机）（机）的应用的应用1 1、理论科学、理论科学2 2、实验科学、实验科学3 3、计算科学、计算科学计算流体力学、计算力学、计算分子动力学、计算流体力学、计算力学、计算分子动力学、计算生物学、计算化学、计算气象学、计算材料计算生物学、计算化学、计算气象学、计算材料学、计算物理学、计算电子学、学、计算物理学、计算电子学、计算量子力计算量子力学、学、 中长期天气预报。每增加一天，要求计算速度增加一中长期天气预报。每增加一天，要求计算速度增加一个数量级。个数量级。 信息战。关键是对信息的处理速度，如雷达信息的处信息

14、战。关键是对信息的处理速度，如雷达信息的处理理 地震预报预测地震预报预测 石油勘测石油勘测 生物信息处理生物信息处理 .六、并行计算机的分类六、并行计算机的分类指令与数据：指令与数据：SIMD(Single-Instruction Multiple-Data)，同时用相同的指令对，同时用相同的指令对不同的数据进行操作不同的数据进行操作MIMD(Multiple-Instruction Multiple-Data)，同时有多条指令，同时有多条指令对不同的数据进行操作对不同的数据进行操作SPMD(Single-Program Multuple-Data)，同时执行相同的程序，同时执行相同的程序对不

15、同数据操作对不同数据操作MPMD(Multiple-Program Multuple-Data)，同时有多个程序对，同时有多个程序对不同的数据进行操作不同的数据进行操作存储方式：存储方式： 共享内存共享内存 处理单元通过对共享内存的访问来交换信息协调各处理处理单元通过对共享内存的访问来交换信息协调各处理器对并行任务的处理。器对并行任务的处理。 分布式内存分布式内存 各个处理单元拥有独立的局部存储器，处理器之间通过各个处理单元拥有独立的局部存储器，处理器之间通过消息传递来交换信息，协调和控制各个处理器的执行。消息传递来交换信息，协调和控制各个处理器的执行。 分布式共享内存分布式共享内存 结合前两

16、者特点，提高了整个系统的计算能力而且可以结合前两者特点，提高了整个系统的计算能力而且可以提高系统的模块性和扩展性，有利于快速构造超大型的计提高系统的模块性和扩展性，有利于快速构造超大型的计算系统算系统七、并行算法及分类七、并行算法及分类 算法是解题的精确描述算法是解题的精确描述 -是一组有穷的规则，它规定了解决某一特定类型问是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算是可同时求解的诸进程的集题的一系列运算。并行计算是可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的合，这些进程相互作用和协调动作，并最终获得问题的求解。求解。 并行算法就是对并行计算过

17、程的精确描述并行算法就是对并行计算过程的精确描述 并行算法可以从不同的角度分类为：并行算法可以从不同的角度分类为： -数值计算并行算法和非数值计算并行算法数值计算并行算法和非数值计算并行算法 -同步并行算法和异步并行算法同步并行算法和异步并行算法 -共享存储并行算法和分布存储并行算法共享存储并行算法和分布存储并行算法数值计算并行算法和非数值计算并行算法数值计算并行算法和非数值计算并行算法数值计算数值计算是指基于代数关系运算的计算问题是指基于代数关系运算的计算问题 -如矩阵运算，多项式求根，线性代数方程组的求如矩阵运算，多项式求根，线性代数方程组的求解等解等 -科学与工程中的计算问题如计算力学，

18、计算物理，科学与工程中的计算问题如计算力学，计算物理，计算化学等一般为数值计算问题计算化学等一般为数值计算问题非数值计算非数值计算是指基于比较关系的运算问题是指基于比较关系的运算问题 -诸如排序、选择、搜索、匹配等符号处理诸如排序、选择、搜索、匹配等符号处理 -在符号类的信息处理中获得广泛应用，如数据库在符号类的信息处理中获得广泛应用，如数据库领域的计算问题，海量数据挖掘，生物信息学等领域的计算问题，海量数据挖掘，生物信息学等同步并行计算和异步并行计算同步并行计算和异步并行计算同步并行计算：同步并行计算：参与并行计算的各个进程必须在相同的参与并行计算的各个进程必须在相同的时刻执行至某一位置，此

19、时较先到达该点的进程必须等时刻执行至某一位置，此时较先到达该点的进程必须等待其它进程均已到达该位置才向下执行待其它进程均已到达该位置才向下执行 大多数工程计算所采用并行计算方式大多数工程计算所采用并行计算方式 并行化程度较低并行化程度较低异步并行计算：异步并行计算：各进程独立运行，互不干涉各进程独立运行，互不干涉 并行化程度较高并行化程度较高同步并行计算同步并行计算异步并行计算异步并行计算共享存储并行算法和分布存储并行算法共享存储并行算法和分布存储并行算法适用于不同的机器适用于不同的机器 划分划分(Partitioning)(Partitioning) 划分计算与数据，开拓并行机会划分计算与数

20、据，开拓并行机会 通信通信(Commutication)(Commutication) 计算之间数据共享，任务协调计算之间数据共享，任务协调 组合组合(Agglomeration)(Agglomeration) 合理组织各任务来提高性能合理组织各任务来提高性能 映射映射(Mapping)(Mapping)分配任务（分布式、共享）分配任务（分布式、共享）分配给不同处理器的任务量应当均衡，分配给不同处理器的任务量应当均衡，不同处理器交互应当最少不同处理器交互应当最少八、八、PCAMPCAM并行算法设计过程并行算法设计过程九、并行计算在地球物理领域的应用九、并行计算在地球物理领域的应用采集采集处理处

21、理解释解释反演反演所有流程所有流程1、地震波场正演、地震波场正演222222222( , , , )( , , , )( , , , )1( , , , )u x y z tu x y z tu x y z tu x y z txyzvt已知模型求响应已知模型求响应v11v12v13v1nv21v2nvijvm1vmn已知模型求响应已知模型求响应三维情况下所需的内存空间三维情况下所需的内存空间2000*2000*2000*4*3=89G弹性波更多弹性波更多2、地震资料叠前偏移、地震资料叠前偏移已知响应求模型已知响应求模型3、地震数据可视化与解释、地震数据可视化与解释4、其它应用、其它应用多波多

22、分量资料多波多分量资料三维连片处理三维连片处理属性提取属性提取.第二章第二章 MPIMPI简介简介 并行语言的产生方式并行语言的产生方式 PVM并行编程并行编程 MPI并行编程并行编程串行语言串行语言并行语言并行语言一、一、 并行语言的产生方式并行语言的产生方式设计全新的并行语言设计全新的并行语言改变串行语言的语法，使其支持并行编程改变串行语言的语法，使其支持并行编程不改变串行语言的语法，仅为串行语言提供并行库不改变串行语言的语法，仅为串行语言提供并行库目前较常用的并行编程语言：目前较常用的并行编程语言： PVM DPF OpenMP MPI共同特点：共同特点： 公用软件公用软件, 易于得到易

23、于得到 多数厂家支持多数厂家支持消息传递的特点消息传递的特点: : 在消息传递模型中在消息传递模型中, , 一个并行应用由一组进程组成一个并行应用由一组进程组成, , 每个进每个进程的代码是本地的程的代码是本地的, , 只能访问私有数据只能访问私有数据, , 进程之间通过传递消进程之间通过传递消息实现数据共享和进程同步息实现数据共享和进程同步. . 优点优点: : 用户可以对并行性的开发、数据分布和通信实现完全控制用户可以对并行性的开发、数据分布和通信实现完全控制. . 缺点缺点: : 要求程序员显式地处理通信问题要求程序员显式地处理通信问题, , 如如, , 消息传递调用的位置消息传递调用的

24、位置, , 数据移动数据移动, , 数据复制数据复制, , 数据操作数据操作, , 数据的一致性等等数据的一致性等等. . 对大多数科学计算程序来说对大多数科学计算程序来说, , 消息传递模型的真正困难还在于消息传递模型的真正困难还在于显式的域分解显式的域分解, , 也就是说也就是说, , 将对相应数据的操作限定在指定的将对相应数据的操作限定在指定的处理器上进行处理器上进行, , 在每个处理器上只能看见整个分布数据的一部在每个处理器上只能看见整个分布数据的一部分分. . (1)(1)无法以渐进的方式、通过逐步将串行代码转换成并行代码而开无法以渐进的方式、通过逐步将串行代码转换成并行代码而开发出

25、来发出来. . 大量的散布在程序各处的域分解要求整个程序由串行大量的散布在程序各处的域分解要求整个程序由串行到并行的转换一次性实现到并行的转换一次性实现, , 而共享存储方法允许在现有的串行而共享存储方法允许在现有的串行代码中插入并行说明从而实现逐步转换代码中插入并行说明从而实现逐步转换. .与之相比与之相比, , 这是消息传这是消息传递的一个明显的缺点递的一个明显的缺点. . PVM(Parallel Virtual Machine)并行虚拟机并行虚拟机 是一种常用的基于消息传递的并行编程环境，它把工是一种常用的基于消息传递的并行编程环境，它把工作站网络构成一个虚拟的并行机系统，为并行应用提

26、供运作站网络构成一个虚拟的并行机系统，为并行应用提供运行平台，使得大型计算在花费较少的情况下得以实现。行平台，使得大型计算在花费较少的情况下得以实现。 PVM的设计初衷是为了将由异种机构成的由低带宽、的设计初衷是为了将由异种机构成的由低带宽、低传输速率相连的网络作为大规模的消息传递并行计算环低传输速率相连的网络作为大规模的消息传递并行计算环境，使之较好地支持粗粒度和混合编程任务的执行。境，使之较好地支持粗粒度和混合编程任务的执行。 PVM是一个自包含、通用的纯软件系统。是一个自包含、通用的纯软件系统。 使用使用PVM时，用户可构造一个虚拟机，该虚拟机由时，用户可构造一个虚拟机，该虚拟机由一组全

27、相联的结点组成，每个结点可以为任何一台计算机。一组全相联的结点组成，每个结点可以为任何一台计算机。二、二、 PVMPVM并行编程并行编程1 1、 PVMPVM的开发历史的开发历史 最早可追溯到最早可追溯到1989年，由美国的年，由美国的Tennessee（田纳西（田纳西州）大学，州）大学，Oak Ridge(奥克里季奥克里季)国家实验室和国家实验室和Emory大学联合研制的一个基于大学联合研制的一个基于UNIX环境的实验性环境的实验性网络计算环境。网络计算环境。 PVM推出后被众多用户广泛采纳，成为并行处理领推出后被众多用户广泛采纳，成为并行处理领域非常流行的软件。域非常流行的软件。 PVM已

28、经在已经在Windows NT和和Windows 95等非等非NUIX平台上实现，程序设计语言支持平台上实现，程序设计语言支持C、FORTRAN、JAVA目前它的研究与开发仍在各大学和研究机构进行。目前它的研究与开发仍在各大学和研究机构进行。 2 2、 PVMPVM的特点的特点 支持多用户及多任务，多个用户可以将系统配置成相互支持多用户及多任务，多个用户可以将系统配置成相互重叠的虚拟机，每个用户可同时执行多个应用程序；重叠的虚拟机，每个用户可同时执行多个应用程序； 支持多种并支持多种并 行计算模型，易于编程；行计算模型，易于编程； 系统提供了一组便于使用的通信原语，具有较高的消息系统提供了一组

29、便于使用的通信原语，具有较高的消息传递能力，同时还提供了消息缓冲区的动态管理机制。传递能力，同时还提供了消息缓冲区的动态管理机制。 提出了任务组的概念，并且在程序运行过程中可动态地提出了任务组的概念，并且在程序运行过程中可动态地改变这些任务组。改变这些任务组。 支持异构计算机联网构成的并行虚拟计算机系统，且易支持异构计算机联网构成的并行虚拟计算机系统，且易于安装、配置。于安装、配置。 具有容错功能，当发现一个节点出故障时，会自动将其具有容错功能，当发现一个节点出故障时，会自动将其从虚拟机中删除。从虚拟机中删除。 3 3、 PVMPVM的通信功能的通信功能 消息缓冲区管理消息缓冲区管理 创建、释

30、放、初始化、获取消息缓冲区创建、释放、初始化、获取消息缓冲区 消息打包、解包消息打包、解包 点对点通信点对点通信 阻塞方式阻塞方式 非阻塞方式非阻塞方式 组通信组通信 多任务发送、广播、同步、规约多任务发送、广播、同步、规约 4 4、 PVMPVM虚拟机的结构虚拟机的结构 PVM守护进程（守护进程（PVMD） PVM的核心，驻留在构成虚拟机的每台实际计算机上的核心，驻留在构成虚拟机的每台实际计算机上 完成虚拟机的维护、任务的控制、消息传递等工作完成虚拟机的维护、任务的控制、消息传递等工作 PVM接口库接口库 包含了用户可调用的包含了用户可调用的PVM库函数（消息传递、任务创库函数（消息传递、任

31、务创建、任务间的协作同步及虚拟机的动态配置等）建、任务间的协作同步及虚拟机的动态配置等） 所有的所有的PVM程序必须和该库链接程序必须和该库链接 PVM控制台控制台 为用户提供用于虚拟机管理、任务管理等功能的交互为用户提供用于虚拟机管理、任务管理等功能的交互式界面式界面 三、三、 MPIMPI并行编程并行编程MPI：Message Passing Interface当前应用最为广泛的并行编程工具当前应用最为广泛的并行编程工具是一个库而不是一门语言是一个库而不是一门语言是一种标准或规范的代表而不特指某一个对它的具体是一种标准或规范的代表而不特指某一个对它的具体实现实现是一种消息传递编程模型是一种

32、消息传递编程模型,并成为这种编程模型的代表并成为这种编程模型的代表和事实上的标准和事实上的标准1 1、什么是什么是MPI？2 2、MPI的三个主要目的的三个主要目的 1 较高的通信性能；较高的通信性能； 2 较好的程序可移植性；较好的程序可移植性； 3 强大的功能。强大的功能。 提供应用程序编程接口。提供应用程序编程接口。 提高通信效率。措施包括避免存储器到存储器的多次提高通信效率。措施包括避免存储器到存储器的多次重复拷贝，允许计算和通信的重叠等。重复拷贝，允许计算和通信的重叠等。 可在异构环境下提供实现。可在异构环境下提供实现。 提供的接口可以方便提供的接口可以方便 C 语言和语言和 For

33、tran 77的调用。的调用。 提供可靠的通信接口。即用户不必处理通信失败。提供可靠的通信接口。即用户不必处理通信失败。 定义的接口和现在已有接口（如定义的接口和现在已有接口（如PVM）差别不能太大）差别不能太大，但是允许扩展以提供更大的灵活性。，但是允许扩展以提供更大的灵活性。 定义的接口能在基本的通信和系统软件无重大改变时定义的接口能在基本的通信和系统软件无重大改变时，在许多并行计算机生产商的平台上实现。接口的语义，在许多并行计算机生产商的平台上实现。接口的语义是独立于语言的。是独立于语言的。 接口设计应是线程安全的。接口设计应是线程安全的。1992年4月 组建了一个制定消息传递接口标准的

34、工作组 1992年10月 初稿形成，主要定义了点对点通信接口 1993年1月 第一届MPI会议在Dallas举行 1993年2月 公布了MPI-1修定版本 1993年11月 MPI的草稿和概述发表在Supercomputing93的会议论文集中 1994年5月 MPI标准正式发布 1994年7月 发布了MPI标准的勘误表 1997年 MPI论坛发布了一个修订的标准, 叫做MPI-2, 同时, 原来的MPI更名为MPI-1 3 3、MPI的产生与发展的产生与发展4 4、MPI的语言绑定的语言绑定 MPI不是一门语言，而是一个库，必须和特定的语不是一门语言，而是一个库，必须和特定的语言绑定才能进行

35、言绑定才能进行MPI_I：C、FORTRAN77MPI_II：C+、FORTRAN905 5、目前、目前MPI的主要实现的主要实现 MPICH： 美国的美国的Argonne国家实验室国家实验室 /mpi/mpich CHIMP： 爱丁堡大学的并行计算中心爱丁堡大学的并行计算中心 ftp:/ftp.epcc.ed.ac.uk/pub/packages/chimp LAM(Local Area Multicomputer): 俄亥俄州立大学俄亥俄州立大学 /lam/download 较强的通信功能较强的通信

36、功能 较高的可移置性较高的可移置性 与最常用的编译器实现了绑定与最常用的编译器实现了绑定 免费，源代码开放免费，源代码开放6 6、MPI的特点的特点第三章第三章 第一个第一个MPIMPI程序程序 MPI程序的框架结构程序的框架结构 第一个第一个MPI程序程序 并行程序的运行方式并行程序的运行方式 MP程序的惯例程序的惯例一、一、MPI程序的框架结构程序的框架结构头文件头文件包含包含MPI库库相关变量的声明相关变量的声明定义与通信有关的变量定义与通信有关的变量程序开始程序开始调用调用MPI初始化函数初始化函数程序结束程序结束调用调用MPI结束函数结束函数 程序体程序体计算与通信计算与通信调用调用

37、MPI其它函数其它函数二、第一个二、第一个MPI程序程序#include void main(int argc, char *argv) printf(“hello world!n”);用串行的用串行的C语言实现语言实现“hello world”第三部分第三部分第五部分第五部分第一部分第一部分用用C+MPI实现实现hello world!#include mpi.h#include #include void main(int argc,char* argv) int myid, numprocs namelen; char processor_nameMPI_MAX_PROCESSOR_NA

38、ME; MPI_Init(&argc,&argv);/*程序初始化程序初始化*/ MPI_Comm_rank(MPI_COMM_WORLD,&myid); /*得到当前进程号得到当前进程号*/MPI_Comm_size(MPI_COMM_WORLD,&numprocs); /*得到总的进程数得到总的进程数*/MPI_Get_processor_name(processor_name,&namelen); /*得到机器名得到机器名*/printf(“hello world! Process %d of %d on %sn, myid, numprocs, processor_name);MPI_

39、Finalize(); /*结束结束*/ 第二部分第二部分第四部分第四部分执行结果执行结果三、并行程序的运行方式三、并行程序的运行方式进程进程进程进程是一个程序，同时包含它的执行环境（内存、寄是一个程序，同时包含它的执行环境（内存、寄存器、程序计数器等），是操作系统中独立存在的可存器、程序计数器等），是操作系统中独立存在的可执行的基本程序单位。执行的基本程序单位。通俗理解通俗理解：串行应用程序编译形成的可执行代码，分：串行应用程序编译形成的可执行代码，分为为“指令指令”和和“数据数据”两个部分，并在程序执行时两个部分，并在程序执行时“独立地申请和占有独立地申请和占有”内存空间，且所有计算均局限

40、于内存空间，且所有计算均局限于该内存空间。该内存空间。正在微机上运行的进程正在微机上运行的进程单机内的多个进程单机内的多个进程多个进程可以多个进程可以同时存在于单机内同一操作系统同时存在于单机内同一操作系统：由操作：由操作系统负责调度分时共享处理机资源（系统负责调度分时共享处理机资源（CPU、内存、存储、内存、存储、外设等）。外设等）。进程间相互独立进程间相互独立（内存空间不相交）：在操作系统调度（内存空间不相交）：在操作系统调度下各自独立地运行，例如多个串行应用程序在同一台计算下各自独立地运行，例如多个串行应用程序在同一台计算机中运行机中运行。进程进程1内存进程进程2最基本的消息传递操作：最

41、基本的消息传递操作：发送消息（发送消息（send）、接受消息）、接受消息（receive）、进程同步（）、进程同步（barrier）、规约（）、规约（reduction）。）。消息传递的实现：消息传递的实现：共享内存或信号量，用户不必关心。共享内存或信号量，用户不必关心。进程间可以相互交换信息进程间可以相互交换信息：例如数据交换、同步等待，：例如数据交换、同步等待，消息消息是这些交换信息的基本单位，是这些交换信息的基本单位，消息传递消息传递是指这些信息是指这些信息在进程间的相互交换，是实现进程间通信的唯一方式在进程间的相互交换，是实现进程间通信的唯一方式。同时运行于单机上的多个进程同时运行于单

42、机上的多个进程进程进程1内存内存进程进程2并行程序的单机运行方式并行程序的单机运行方式进程进程3进程进程4Hello_world程序在单机上的运行方式程序在单机上的运行方式启动程序，开始执行启动程序，开始执行进程进程0进程进程1进程进程2进程进程3MPI_InitMPI_InitMPI_InitMPI_Initmyid=0myid=1myid=2myid=3numproces=4numproces=4numproces=4numproces=4获取机器获取机器名并打印名并打印获取机器获取机器名并打印名并打印获取机器获取机器名并打印名并打印获取机器获取机器名并打印名并打印MPI_Finalize

43、MPI_FinalizeMPI_FinalizeMPI_Finalize程序结束程序结束包含于通过网络联接的不同包含于通过网络联接的不同计算机的多个进程计算机的多个进程 进程独立存在：进程独立存在：进程位于不同的计算机，由各自独立的进程位于不同的计算机，由各自独立的操作系统调度，享有独立的操作系统调度，享有独立的CPU和内存资源。和内存资源。 进程间相互信息交换：进程间相互信息交换：消息传递。消息传递。 消息传递的实现：消息传递的实现：基于网络基于网络socket机制机制,用户不必关心。用户不必关心。进程进程0进程进程1进程进程2进程进程3通过网络进行消息传递通过网络进行消息传递基于消息传递的

44、并行程序执行模式基于消息传递的并行程序执行模式 共享存储与分布式存储共享存储与分布式存储 属于并行机体系结构的范畴，与消息传递并行程序设属于并行机体系结构的范畴，与消息传递并行程序设计平台无关计平台无关。消息传递是相对于消息传递是相对于进程间通信方式进程间通信方式而言的，与具体而言的，与具体并行机存储模式无关，任何支持进程间通信的并行并行机存储模式无关，任何支持进程间通信的并行机，均可支持消息传递并行程序设计。机，均可支持消息传递并行程序设计。几乎所有共享和分布存储并行计算环境均支持进程几乎所有共享和分布存储并行计算环境均支持进程间的消息传递通信间的消息传递通信。共享存储与分布式存储（续）共享

45、存储与分布式存储（续） MPI MPI并行程序设计平台由并行程序设计平台由标准消息传递函数及相标准消息传递函数及相关辅助函数关辅助函数构成，多个进程通过调用这些函数（类构成，多个进程通过调用这些函数（类似调用子程序），进行通信。似调用子程序），进行通信。 SPMDSPMD执行模式：执行模式：一个程序同时启动多份，形成多一个程序同时启动多份，形成多个独立的进程，在不同的处理机上运行，拥有独立个独立的进程，在不同的处理机上运行，拥有独立的内存空间，进程间通信通过调用的内存空间，进程间通信通过调用MPIMPI函数来实现。函数来实现。 每个进程开始执行时，将获得一个唯一的序号每个进程开始执行时，将获得

46、一个唯一的序号（rankrank）。例如启动）。例如启动P P个进程，序号依次为个进程，序号依次为0 0，1 1，P-1P-1。MPI程序在并行机上的执行模式程序在并行机上的执行模式 用用Fortran+MPI实现实现hello world include mpif.hcharacter * (MPI_MAX_PROCESSOR_NAME) processor_nameinteger myid, numprocs, namelen, rc,ierr call MPI_INIT( ierr ) 程序初始化程序初始化call MPI_COMM_RANK( MPI_COMM_WORLD, myid,

47、 ierr ) 得到当前进程号得到当前进程号call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr ) 得到总的进程数得到总的进程数call MPI_GET_PROCESSOR_NAME(processor_name, namelen, ierr) 得到处理器名字得到处理器名字write(10,*) myid,numprocs,processor_name10 format(Hello World! Process,I2,of ,I1, on, 20A)call MPI_FINALIZE(rc) 结束结束endMPI程序的惯例程序的惯例 （1） 所

48、有所有MPI的调用都有前缀的调用都有前缀“MPI_”（ 常量、变常量、变量、过程、函数）。在自己编写的程序中不准说明量、过程、函数）。在自己编写的程序中不准说明以前缀以前缀“MPI_”开始的任何变量和函数开始的任何变量和函数 目的：目的：避免与避免与MPI可能的名字混淆。可能的名字混淆。MPI程序的惯例程序的惯例 （2） FORTRAN形式的形式的MPI调用，一般全为大写（虽然调用，一般全为大写（虽然FORTRAN不区分大小写），不区分大小写）， C形式的形式的MPI调用，则为调用，则为MPI_Aaaa_aaa的形式。的形式。MPI_Comm_rank(MPI_COMM_WORLD,&myid

49、)CALL MPI_COMM_RANK ( MPI_COMM_WORLD , myid , ierr )MPI程序的惯例程序的惯例 （3） 所有所有MPI的的FORTRAN子程序在最后参数中都有一个返子程序在最后参数中都有一个返回代码，对于成功的返回代码值是回代码，对于成功的返回代码值是MPI_SUCCESS，其他，其他的错误代码是依赖于实现的。的错误代码是依赖于实现的。MPI_Comm_rank(MPI_COMM_WORLD,&myid)CALL MPI_COMM_RANK ( MPI_COMM_WORLD , myid , ierr )MPI程序的惯例程序的惯例 （4） FORTRAN中的

50、句柄以整型表示，二值变量是逻辑类中的句柄以整型表示，二值变量是逻辑类型。型。FORTRAN的数组下标是以的数组下标是以1开始，但在开始，但在C中是以中是以0开始。开始。MPI程序的惯例程序的惯例 （5） 除非明显说明，除非明显说明，FORTRAN 77的的MPI程序与程序与ANSI FORTRAN 77标准一致。但有些地方不同于标准一致。但有些地方不同于 ANSI FORTRAN 77 标准，比如：标准，比如：1、MPI标识符限于三十个有效符号标识符限于三十个有效符号, 而不是六个。而不是六个。2、MPI标识符可在第一个字符后包含下划线。标识符可在第一个字符后包含下划线。3、具有一个选择参数的

51、、具有一个选择参数的MPI子程序可以用不同的参数类型子程序可以用不同的参数类型来调用。来调用。4、在一个包含文件、在一个包含文件mpif.h中提供所命名的常量。中提供所命名的常量。5、在支持用户定义类型的系统中、在支持用户定义类型的系统中, 鼓励生产商在鼓励生产商在mpif.h文文件中提供类型说明。件中提供类型说明。 回顾：回顾：MPI程序的基本结构程序的基本结构#include mpi.h#include #include void main(int argc,char* argv) int myid, numprocs namelen; char processor_nameMPI_MAX

52、_PROCESSOR_NAME; MPI_Init(&argc,&argv);/*程序初始化程序初始化*/ MPI_Comm_rank(MPI_COMM_WORLD,&myid); /*得到当前进程号得到当前进程号*/ MPI_Comm_size(MPI_COMM_WORLD,&numprocs); /*得到总的进程数得到总的进程数*/ MPI_Get_processor_name(processor_name,&namelen); /*得到机器名得到机器名*/ printf(“hello world! Process %d of %d on %sn, myid, numprocs, proc

53、essor_name); MPI_Finalize(); /*结束结束*/ C+MPI与与FORTRAN+MPI的比较的比较include mpif.hcharacter * (MPI_MAX_PROCESSOR_NAME) processor_nameinteger myid, numprocs, namelen, rc,ierr call MPI_INIT( ierr ) 程序初始化程序初始化call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr ) 得到当前进程号得到当前进程号call MPI_COMM_SIZE( MPI_COMM_WORLD, n

54、umprocs, ierr ) 得到总的进程数得到总的进程数call MPI_GET_PROCESSOR_NAME(processor_name, namelen, ierr) 得到处理器名字得到处理器名字write(10,*) myid,numprocs,processor_name10 format(Hello World! Process,I2,of ,I1, on, 20A)call MPI_FINALIZE(rc) 结束结束endC+MPI与与FORTRAN+MPI的区别（的区别（1）头文件不同：头文件不同： C： mpi.h FORTRAN : mpif.hC+MPI与与FORTR

55、AN+MPI的区别（的区别（2）接口类型不同：接口类型不同： C：函数：函数 FORTRAN : 过程过程MPI_Comm_rank(MPI_COMM_WORLD,&myid)CALL MPI_COMM_RANK ( MPI_COMM_WORLD , myid , ierr )C+MPI与与FORTRAN+MPI的区别（的区别（3）输出型参数不同：输出型参数不同： C：函数：函数（引用，加取址符（引用，加取址符&） FORTRAN :MPI_Comm_rank(MPI_COMM_WORLD,&myid)CALL MPI_COMM_RANK ( MPI_COMM_WORLD , myid , i

56、err )C+MPI与与FORTRAN+MPI的区别（的区别（4）接口的书写方式不同：接口的书写方式不同： C：MPI_Aaaaaa（第一个字母大写，其余小写）（第一个字母大写，其余小写） FORTRAN : MPI_AAAAA(都为大写都为大写)MPI_Comm_rank(MPI_COMM_WORLD,&myid)CALL MPI_COMM_RANK ( MPI_COMM_WORLD , myid , ierr )C+MPI与与FORTRAN+MPI的区别（的区别（5）参数个数不同：参数个数不同： C： FORTRAN :一般比一般比C语言调用多一个返回状态参数语言调用多一个返回状态参数MP

57、I_Comm_rank(MPI_COMM_WORLD,&myid)CALL MPI_COMM_RANK ( MPI_COMM_WORLD , myid , ierr )C+MPI与与FORTRAN+MPI的区别（的区别（6）数组的存放方式不同数组的存放方式不同 C： 数组的下标从数组的下标从0开始开始 按行存放按行存放 FORTRAN : 数组的下标从数组的下标从1开始开始 按列存放按列存放第四章第四章 六个接口构成的六个接口构成的MPIMPI子集子集 内容：内容： 子集介绍子集介绍 MPI预定义的数据类型预定义的数据类型 数据类型匹配与数据转换数据类型匹配与数据转换 MPI消息消息一、一、

58、子集介绍子集介绍1、MPI调用的说明方式调用的说明方式独立于具体语言的说明独立于具体语言的说明C形式的原型说明形式的原型说明FORTAN形式的原型说明形式的原型说明 MPI_INIT() 独立于语言的说明独立于语言的说明int MPI_Init(int *argc, char *argv) C语言的说明语言的说明MPI_INIT(IERROR)INTEGER IERROR FORTRAN77说明部分说明部分举例举例独立于具体语言的说明独立于具体语言的说明MPI_COMM_RANK(comm,rank)IN comm 该进程所在的通信域（句柄）该进程所在的通信域（句柄）OUT rank 调用进程

59、在调用进程在comm中的标识号中的标识号C形式的原型说明形式的原型说明int MPI_Comm_rank(MPI_Comm comm, int *rank)FORTRAN形式的原型说明形式的原型说明MPI_COMM_RANK(COMM,RANK,IERROR) INTEGER COMM , RANK , IERROR1 1、MPIMPI调用的说明方式（续）调用的说明方式（续）参数说明方式：参数说明方式： IN（输入）：（输入）：调用部分传递给调用部分传递给MPI的参数，的参数，MPI除了除了使用该参数外不允许对这一参数做任何修改使用该参数外不允许对这一参数做任何修改 OUT（输出）（输出）：M

60、PI返回给调用部分的结果参数，该返回给调用部分的结果参数，该参数的初始值对参数的初始值对MPI没有任何意义没有任何意义 INOUT（输入输出）：（输入输出）：调用部分首先将该参数传递给调用部分首先将该参数传递给MPI，MPI对这一参数引用、修改后，将结果返回给外对这一参数引用、修改后，将结果返回给外部调用，该参数的初始值和返回结果都有意义部调用，该参数的初始值和返回结果都有意义 如果某一个参数在调用前后没有改变，比如某个隐含对象如果某一个参数在调用前后没有改变，比如某个隐含对象的句柄但是该句柄指向的对象被修改了，这一参数仍然被的句柄但是该句柄指向的对象被修改了，这一参数仍然被说明为说明为OUT