并行计算简介 高性能事业部：曹振南 caozn@dawning.com.cn czn@ncic.ac.cn 2004.4 2004年4月.

Presentation on theme: "并行计算简介 高性能事业部：曹振南 caozn@dawning.com.cn czn@ncic.ac.cn 2004.4 2004年4月."— Presentation transcript:

1 并行计算简介 高性能事业部：曹振南 2004.4 2004年4月

2 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI 、PVM、OpenMP
2004年4月

3 并行计算--高性能计算 并行计算(Parallel Computing） 高端计算(High-end Parallel Computing)
高性能计算(High Performance Computing) 超级计算(Super Computing) 任何高性能计算和超级计算都离不开使用并行技术 计算科学与传统的两种科学，即理论科学和实验科学，并立被认为是人类认识自然的三大支柱，他们彼此相辅相成地推动科学发展与社会进步。在许多情况下，或者是理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至无法进行时，计算就成了求解问题的唯一或主要的手段。 2004年4月

4 并行:古老的思想! “...并行计算并不是什么新的思想,只是将它扩展应用于计算机而已”. 作者也不认为这种扩展应用会存在什么无法克服的困难. 但也不要期待有效的并行编程方法与技术能够在一夜之间诞生. 期间还需要有许多的工作和实验要做. 毕竟, 今天的编程技术(串行)是若干年来艰苦的探索才取得的. 现在编程工作似乎成了一种令人单调乏味的工作,事实上,并行编程的出现将会使重新恢复编程工作者们的探索精神 ...” (Gill, S. (1958), “Parallel Programming” The Computer Journal, vol. 1, April, pp ) Parallel Programming with MPI by Peter Pacheco(2000) 2004年4月

5 什么是并行计算? 并行计算: 由运行在多个部件上的小任务合作来求解一个规模很大的计算问题的一种方法
例: 在曙光2000上用8个节点计算的Mandelbrot集结果(Mandelbrot为分形理论创始人) 2004年4月

6 现代计算机的共同特点： 并行性 2004年4月

7 现代计算机的共同特点： 并行性 2004年4月

8 为什么要做并行计算？ －－应用需求 2004年4月

9 为什么要做并行计算？ 人类对计算及性能的要求是无止境的 从系统的角度：集成系统资源，以满足不断增长的对性能和功能的要求
从应用的角度：适当分解应用，以实现更大规模或更细致的计算 2004年4月

10 为什么要做并行计算？ 问题: 科学和工程问题的数值模拟与仿真 计算密集 数据密集 网络密集 三种混合 要求:在合理的时限内完成计算任务
秒级 制造业 分钟级 短时天气预报(当天) 小时级 中期天气预报(3~10日) 尽可能快 长期天气预报(气候) 可计算 湍流模拟 2004年4月

11 2004年4月

12 并行计算的功能 降低单个问题求解的时间 增加问题求解规模、提高问题求解精度 (多机同时执行多个串行程序)容错、更高的可用性、提高吞吐率
2004年4月

13 如何实现并行计算? 分而治之! 2004年4月

14 分而治之 并行化的主要方法:分而治之 根据问题的求解过程，把任务分成若干子任务(任务级并行或功能并行)
根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理(数据并行) 2004年4月

15 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI 、PVM、OpenMP
常用编译器 编译优化 如何编译 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI 、PVM、OpenMP 2004年4月

16 GNU Compiler GNU Compiler 自由软件，一般操作系统都自带
支持C/C++、Fortran77、Java、COBAL等等许多语言 支持大部分硬件平台 高性能计算中常用的： C/C++：GCC (GNU C/C++ Compiler) Fortran 77：G77 不支持Fortran 90/ 95 不支持OpenMP 是最常用的编译器，性能一般(相对于一些针对特定平台优化的编译器) 由于缺少对Fortran 90/ 95，限制了其在高性能计算中的使用 2004年4月

17 PGI Compiler PGI Compiler 由Portland公司开发的编译器
支持AMD Opteron/Althon处理器、Intel Xeon处理器等，在Opteron上同时支持32-bit和64-bit() 支持Linux、Windows 支持C/C++（pgcc）、Fortran77(pgf77)、Fortran90/95（pgf90)、HPF（High Performance Fortran） 支持多线程和OpenMP 最新版本：5.1 需要购买，但可以从网上得到15天试用版本 2004年4月

18 Intel Compiler Intel Compiler 由Intel公司针对Intel处理器开发（Xeon、Pentium）
支持Linux、Windows 支持C/C++（icc：Intel C/C++ Compiler）、Fortran77/90/95（ifc： Intel Fortran Compiler) 支持多线程和OpenMP 最新版本：8.0 需要购买，但可以从网上得到30天试用版本 2004年4月

19 编译优化 编译优化对于计算密集型程序的性能提高非常帮助 优化消耗CPU资源最多的那部分，即计算密集部分 一般采用-O2、-O3
可以采用SIMD指令集，eg: Intel和AMD处理器的MMX、SSE1、SSE2 具体编译优化的选项和编译器以及CPU相关，参见编译器手册 对于有些应用程序，过分的优化会导致计算结果错误 2004年4月

20 编译优化 在双路Intel Xeon平台上，采用SSE2优化和不采用SSE2优化，所获得的HPL性能。
2004年4月

21 编译简介 在Linux系统中，可执行文件没有统一的后缀，系统从文件的属性来区分可执行文件和不可执行文件
大部分编译器通过后缀来区别输入文件的类别，下面来介绍常用的一些后缀 .c：C语言源代码文件 .f：Fortran 77语言源代码文件 .o：编译后的目标文件 .a：由目标文件构成的档案库文件 .C、.cc、.cxx：C++源代码文件 .f90：Fortran 90语言源代码文件 .h：程序所包含的头文件 2004年4月

22 基本的用法 cc/f77/f90 [options] [filenames] 编译器名 编译参数 编译文件
编译器名 编译参数 编译文件 其中options就是编译器所需要的参数，filenames给出相关的文件名称 2004年4月

23 常用编译参数 -c：只编译，不连接成为可执行文件，编译器只是由输入的.c/.f等源代码文件生成.o为后缀的目标文件，通常用于编译不包含主程序的子程序文件。 -o output_filename：确定输出文件的名称为output_filename，同时这个名称不能和源文件同名。如果不给出这个选项，就给出预设的可执行文件a.out -g：产生符号调试工具所必要的符号资讯，要想对源代码进行调试，我们就必须加入这个选项。 -O：对程序进行优化编译、连接，采用这个选项，整个源代码会在编译、连接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、连接的速度就相应地要慢一些。 -O2、-O3、-O4：比-O更好的优化编译、连接，当然整个编译、连接过程会更慢。（具体和编译器相关） 2004年4月

24 常用编译参数 -Idirname：将dirname所指出的目录加入到程序头文件目录列表中，是在预编译过程中使用的参数。C程序中的头文件包含两种情况： A)#include <stdio.h> B)#include “myinc.h” 其中，A类使用尖括号(< >)，B类使用双引号(“ ”)。对于A类，预处理程序cpp在系统预设包含文件目录(如/usr/include)中搜寻相应的文件，而对于B类，cpp在当前目录中搜寻头文件，这个选项的作用是告诉cpp，如果在当前目录中没有找到需要的文件，就到指定的dirname目录中去寻找。在程序设计中，如果我们需要的这种包含文件分别分布在不同的目录中，就需要逐个使用-I选项给出搜索路径。 2004年4月

25 常用编译参数 -Ldirname：将dirname所指出的目录加入到程序函数档案库文件的目录列表中，是在连接过程中使用的参数。在预设状态下，连接程序ld在系统的预设路径中(如/usr/lib)寻找所需要的档案库文件，这个选项告诉连接程序，首先到-L指定的目录中去寻找，然后到系统预设路径中寻找，如果函数库存放在多个目录下，就需要依次使用这个选项，给出相应的存放目录。 -lname：在连接时，装载名字为“libname.a”的函数库，该函数库位于系统预设的目录或者由-L选项确定的目录下。例如，-lm表示连接名为“libm.a”的数学函数库。 上面我们简要介绍了编译器最常用的功能和主要参数选项，更为详尽的资料可以参看Linux系统的联机帮助。 2004年4月

26 GCC应用举例 1.gcc hello.c 生成a.out 2. gcc –o hello helo.c 生成hello
3. gcc –O –o hello hello.c 生成hello 4. gcc –O2 –o hello hello.c 生成hello 5. gcc –c hello.c 生成hello.o gcc –o hello hello.o 生成hello 6. gcc –c hello1.c 生成hello1.o gcc –c hello2.c 生成hello2.o gcc –o hello hello1.o hello2.o 生成hello 7. gcc –o test test1.o –lm –I/home/czn/include 2004年4月

27 Make简介 在开发大系统时，经常要将程序划分为许多模块。各个模块之间存在着各种各样的依赖关系，在Linux中通常使用 Makefile来管理 由于各个模块间不可避免存在关联，所以当一个模块改动后，其他模块也许会有所更新，当然对小系统来说，手工编译连接是没问题，但是如果是一个大系统，存在很多个模块，那么手工编译的方法就不适用了。 为此，在Linux系统中，专门提供了一个make命令来自动维护目标文件。 与手工编译和连接相比，make命令的优点在于他只更新修改过的文件，而对没修改的文件则置之不理，并且make命令不会漏掉一个需要更新的文件 2004年4月

28 一个简单的例子 先举一个例子: a.c b.c两个程序
a.c extern void p(char *); main() { p("hello world"); } b.c void p(char *str) { printf("%sn",str); } Makefile hello: a.c b.c gcc a.c b.c -o hello 注意这里是一个Tab 执行make gcc a.c b.c -o hello 产生一个叫hello的可执行程序 2004年4月

29 书写makefile文件 Makefile时由规则来组成的,每一条规则都有三部分组成:目标(object),依赖(dependency)和命令(command).在上面的例子中, Makefile只有一条规则,其目标为hello,期依赖为a.c b.c,其命令为gcc a.c b.c -o hello 依赖可以是另一条规则的目标,也可以是文件.每一条规则被这样处理.如目标是一个文件是:当它的依赖是文件时,如果依赖的时间比目标要新, 则运行规则所包含的命令来更新目标; 如果依赖是另一个目标则用同样的方法先来处理这个目标.如目标不是一个存在的文件时,则一定执行. 2004年4月

30 一个简单的makefile文件 例如: Makefile hello: a.o b.o gcc a.o b.o -o hello a.o: a.c gcc –c a.c b.o: b.c gcc –c b.c 当运行make时，可以接一目标名(eg:make hello)作为参数，表示要处理改目标。如没有参数，则处理第一个目标。 对上述例子执行make，则是处理hello这个目标。 hello依赖于文件目标a.o和b.o，则先去处理a.o,调用gcc –c a.c来更新a.o，之后更新b.o，最后调用gcc a.c b.o -o hello 来更新hello 2004年4月

31 Make中的宏(macro) 在make中是用宏，要先定义，然后在makefile中引用。宏的定义格式为：
宏名 = 宏的值 (宏名一般习惯用大写字母) 例： CC = gcc hello: a.o b.o $(CC) a.o b.o -o hello a.o: a.c $(CC) –c a.c b.o: b.c $(CC) –c b.c 2004年4月

32 系统定义的宏 还有一些设定好的内部变量，它们根据每一个规则内容定义。 $@ 当前规则的目的文件名 $< 依靠列表中的第一个依靠文件
当前规则的目的文件名 $< 依靠列表中的第一个依靠文件 $^ 整个依靠的列表（除掉了里面所有重复的文件名）。 $? 依赖中所有新于目标的 以用变量做许多其它的事情，特别是当你把它们和函数混合 使用的时候。如果需要更进一步的了解，请参考 GNU Make 手册。 ('man make', 'man makefile') 2004年4月

33 修改原先的makefile CC = gcc CFLAGS = -O2 OBJS = a.o b.o hello: $(OBJS)
$(CC) $^ -o a.o: a.c $(CC) $(CFLAGS) -c $< b.o: b.c clean: rm –f *.o hello 2004年4月

34 隐含规则 请注意在上面的例子里，几个产生.o文件的命令都是一样的，都是从.c文件和相关文件里产生.o文件，这是一个标准的步骤。
其实make已经知道怎么做—它有一些叫做隐含规则的内置的规则，这些规则告诉它当你没有给出某些命令的时候，应该怎么办。 如果你把生成a.o和b.o的命令从它们的规则中删除，make将会查找它的隐含规则，然后会找到一个适当的命令。 它的命令会使用一些变量，因此你可以按照你的想法来设定它：它使用变量CC做为编译器，并且传递变量CFLAGS,CPPFLAGS,TARGET_ARCH，然后它加入 ‘-c’ ，后面跟变量$<，然后是 $(CC) $(CFLAGS) $(CPPFLAGS) $(TARGET_ARCH) -c $< -o 当然你可以按照你自己的需要来定义这些变量。 2004年4月

35 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI BLAS 其它
2004年4月

36 BLAS BLAS 基本线性代数库(Basic Linear Algebra Subroutines） 提供最基本的线性代数函数接口
分为三级 BLAS 1（Level 1）：向量与向量操作 BLAS 2（Level 2）：矩阵与向量操作 BLAS 3（Level 3）：矩阵与矩阵操作 2004年4月

37 LAPACK LAPACK：线性代数计算子程序包（Linear Algebra Package）
LAPACK是建立在BLAS 1、BLAS 2和BLAS 3基础之上 使用Fortran 77语言开发 使用了线性代数中最新、最精确的算法，同时采用了将大型矩阵分解成小块矩阵的方法从而可以有效的使用存储空间 开放源码， 2004年4月

38 ScaLAPACK ScaLAPACK：可扩展线性代数库(Scalable LAPACK)，是LAPACK的增强版本
是美国能源部ODE2000支持开发的20多个ACTS工具箱之一，由Oak Ridge国家实验室、加州大学Berkeley分校和Illinois大学等联合开发 分布式存储环境运行的线性代数库，主要为可扩放的、分布存储的并行计算机而设计的 支持稠密和带状矩阵的各类操作，如：乘法、转置、分解等等 开发源码， 2004年4月

39 常用BLAS库 Linux自带Blas库 由Linux操作系统提供，在安装Linux时可以选择安装 性能相对较差 /usr/lib目录下
2004年4月

40 常用BLAS库 －ATLAS ATLAS 开放源代码(免费)，用户可以下载源代码，在自己的平台上编译 在编译中调整性能，达到性能最优
包括全部BLAS函数和一部分LAPACK函数 提供C和Fortran 77接口 最新版本：3.7 (下载源代码) (下载针对一些常用平台已编译完成的ATLAS库) 2004年4月

41 常用BLAS库 －GOTO GOTO 免费提供各种平台二进制代码的下载
支持Opteron、Xeon、Itanium、Power、Alpha等平台 支持Windows平台（Xeon、Opteron） 支持多线程 性能最优 最新版本：0.9 下载网址： 2004年4月

42 常用BLAS库 －ACML ACML ACML：AMD Core Math Library，基于Opteron处理器
AMD公司公司与英国Numerical Algorithms Group（NAG）共同开发 支持32bit和64bit的Windows平台、 32bit和64bit的Linux平台 提供一级、二级、三级BLAS以及LAPACK、FFT 通过PGI编译器同时支持面向Linux开发的OpenMP和非OpenMP 免费下载，下载网址： 最新版本：4月5日发布2.0版 2004年4月

43 常用BLAS库 －MKL MKL Intel® Math Kernel Library
Intel公司开发，针对Intel处理器，Pentium、Xeon、Itanium 包括诸如BLAS和LAPACK等线性代数功能，离散傅利叶变换（DFT）以及向量超越函数（向量数学库/VML），以及向量统计函数（VSL ） Linux版本和Windows版本 需要购买，但可以从网上得到30天试用版本 最新版本：7.0 2004年4月

44 常用BLAS库 －ESSL ESSL ESSL库(Engineering and Scientific Subroutine Library)是IBM提供的工程与科学计算优化库，针对IBM Power系列处理器 包括：线性代数子程序，矩阵运算，线性代数方程、本征系统分析，傅立叶变换、卷积与对射变换及其它信号处理相关计算，排序与搜索，插值，数值积分，微分方程，随机数生成 2004年4月

45 PETSc PETSc：并行可扩展科学计算工具箱（Parallel Extensible Toolkits for Scientific Computing） 核心人员：美国数学与计算机部、Argonne国家重点实验室等等 基于MPI、BLAS库、LAPACK库 使用Fortran、C/C++开发 PETSc软件包含一个功能强大的工具集以在高性能计算机上数值求解偏微分方程及其相关问题 可移植性：CRAY T3D，T3E，Origin 2000, IBM SP, HP UX, ASCI Red, Blue Mountain, NOWs，LINUX，ALPHA等 公开源代码，免费下载 2004年4月

46 PETSc 2004年4月

47 PETSc PETSc 的一些模块处理： 索引集，包括用于向量索引的置换，重新计数等 向量 矩阵（一般是稀疏的）
分布阵列（对正规的基于网格问题的并行化有用） Krylov 子空间方法 预条件子，包括多重网格和稀疏直接解法器 非线性解法器 解时间相关（非线性）PDEs 的时间步进解法器 2004年4月

48 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI 、PVM、OpenMP
2004年4月

49 并行计算机系统结构 Flynn分类： 结构模型： 访存模型： SISD, SIMD, MIMD, MISD
PVP, SMP, MPP, DSM, COW 访存模型： UMA, NUMA, COMA, CC-NUMA, NORMA 2004年4月

50 Flynn分类 Flynn(1972)提出指令流、数据流和多倍性概念，把不同的计算机分为四大类：
SISD（Single-Instruction Single-Data） SIMD（Single-Instruction Multi-Data） MISD（Multi-Instruction Single-Data） MIMD（Multi-Instruction Multi-Data） 2004年4月

51 结构模型 2004年4月

52 共享存储对称多处理机系统(SMP) SMP:
对称式共享存储：任意处理器可直接访问任意内存地址,且访问延迟、带宽、几率都是等价的; 系统是对称的； 微处理器: 一般少于64个; 处理器不能太多, 总线和交叉开关的一旦作成难于扩展； 例子: IBM R50, SGI Power Challenge, SUN Enterprise, 曙光一号 2004年4月

53 分布共享存储多处理机系统(DSM) DSM:
分布共享存储: 内存模块物理上局部于各个处理器内部,但逻辑上(用户)是共享存储的; 这种结构也称为基于Cache目录的非一致内存访问(CC-NUMA)结构;局部与远程内存访问的延迟和带宽不一致,3-10倍高性能并行程序设计注意; 与SMP的主要区别：DSM在物理上有分布在各个节点的局部内存从而形成一个共享的存储器； 微处理器: 个,几百到千亿次; 代表: SGI Origin 2000, Cray T3D; 2004年4月

54 大规模并行计算机系统(MPP) MPP: 物理和逻辑上均是分布内存 能扩展至成百上千个处理器(微处理器或向量处理器)
采用高通信带宽和低延迟的互联网络 (专门设计和定制的) 一种异步的MIMD机器；程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用； 代表:CRAY T3E(2048), ASCI Red(3072), IBM SP2, 曙光1000； 2004年4月

55 机群系统(Cluster) Cluster: 每个节点都是一个完整的计算机 各个节点通过高性能网络相互连接 网络接口和I/O总线松耦合连接
每个节点有完整的操作系统 曙光2000, 3000, ASCI Blue Mountain (48台128-way DSM Origin 2000,6144个处理器) 2004年4月

56 访存模型 多处理机（单地址空间共享存储器） UMA: Uniform Memory Access
NORMA: UMA: NUMA: 多处理机（单地址空间共享存储器） UMA: Uniform Memory Access NUMA: Nonuniform Memory Access 多计算机（多地址空间非共享存储器） NORMA:No-Remote Memory Access 2004年4月

57 均匀存储器存取 (UMA) 均匀存储器存取（UMA－Uniform Memory Access）
所有处理器均匀共享物理存储器，这里所谓均匀是指所有处理器对所有存储字具有相同的存取时间 每台处理器可带私有高速缓存 外围设备也可以一定形式共享 各处理机之间的通信是通过共享存储器的共享变量来实现的 这一类多处理机由于对资源的高度共享,常称紧耦合系统(tightly coupled system) UMA: 2004年4月

58 均匀存储器存取 (UMA) 对称多处理机系统(symmetric multi-processor)
所有处理机都能同样访问所有外围设备；所有处理机都能同样运行执行程序，如操作系统的内核、I/O服务程序 不对称处理机系统(asymmtric multi-processor) 只有一台或一组处理机（MP主处理机）执行操作系统并操纵I/O，其余处理机（AP附属处理机）没有I/O能力 2004年4月

59 非均匀存储访问(NUMA) 非均匀存储访问(NUMA—Nonuniform Memory Access)
被共享的存储器在物理上是分布在所有的处理其中的，其所有本地存储器的集合就组成了全局地址空间 处理器访问存储器的时间是不一样的：访问本地存储器(LM)较快，而访问外地的存储器较慢（此即是非均匀存储访问名称的由来） 每台处理器可带私有高速缓存，且外设也可以某种形式共享 NUMA: 2004年4月

60 非远程存储访问(NORMA) 非远程存储访问(NORMA — No-Remote Memory Access)
所有存储器都是私有的，仅能由其处理器所访问 绝大都数都不支持远程存储器的访问 NORMA: 2004年4月

61 结构模型 ---- 访存模型 NUMA: UMA: NORMA: 2004年4月

62 多处理机 ＆ 多计算机 多处理机 （共享存储） 多计算机 （分布式存储） UMA: NORMA: NUMA: 2004年4月

63 几种体系结构特征比较 2004年4月

64 曙光系列 曙光一号 SMP (1993) 曙光1000 MPP (1995) 曙光2000I Cluster (1998)
曙光2000II Cluster (1999) 曙光 Cluster (2000) 曙光4000l Cluster (2002) 曙光4000A Cluster (2004) 2004年4月

65 动物食物链 2004年4月

66 1984年的计算机食物链 Mainframe PC Workstation Mini Computer
Vector Supercomputer Mini Computer Workstation PC 2004年4月

67 1994年的计算机食物链 (hitting wall soon) Mini Computer PC Workstation
Mainframe Vector Supercomputer MPP Workstation PC Mini Computer (hitting wall soon) (future is bleak) 2004年4月

68 现在和未来的计算机食物链 2004年4月

69 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI 2004年4月

70 并行计算软件环境及现状 操作系统：UNIX、LINUX、Windows NT
在SMP,DSM并行机上编译系统通常具有一定的对用户程序(C/Fortran) 进程自动并行化的能力,但经常需要人工干预 (通过编译制导,命令行选项等) 以达到理想的并行效率.且并行主要针对循环进行 (属于细粒度并行); 在分布式内存并行机上尚无通过高效的自动并行工具,主要依靠人工编写并行程序; 并行算法的设计及并行程序的编制已成为目前特约大规模并行计算机应用的主要障碍. 并行编程现状 : 并行软件开发远远落后于并行系统体系结构的发展。缺少合适的并行软件是阻碍主流用户社会接纳并行计算的原因。 : 与串行软件相比，并行软件数量少，功能原始。 2004年4月

71 ?? 编程环境 3算法 J人 落后的并行编译器、调试器 vs. 通用先进的串行编程环境. 自动并行编译器远远满足不了程序并行化的要求.
问题的并行求解的困难在于问题的多样性和求解过程中所需的创造性劳动，使得这一过程难以进行自动化 对串行机而言, 解法 = 唯一串行算法+计算程序(通用) 对并行机而言, 解法 = 某种并行算法+有针对性的计算程序(很难通用) J人 稀少而初级的并行编程人员 vs. 成熟而经验丰富的串行程序员 2004年4月

72 一些途径 充分利用顺序程序开发的经验、方法和工具，特别是顺序领域中的问题求解、算法设计方法，这是简化并行程序开发的重要手段。
并行程序开发的困难主要在于问题的并行求解，而不是并行程序设计语言。“从事并行程序设计实践的人往往把精力耗费在为变量分配内存、为循环体寻求并行上，却忽略对问题本身的分析。其实能否并行的决定因素是应用问题本身。” 在并行算法的设计阶段最大限度地开发出问题本身固有的并行性才是提高计算效率的根本手段。只有粗粒度的并行，才能具有高的计算通信比，而粗粒度的并行只能在算法设计阶段开发出来 2004年4月

73 并行软件程序员的工作 前两层大都由硬件和编译器负责处理，程序员通常处理后两层的并行 指令层，非常细的粒度 数据层，细粒度 控制层，中粒度
任务层，大粒度 前两层大都由硬件和编译器负责处理，程序员通常处理后两层的并行 2004年4月

74 并行程序设计方法 隐式并行程序设计： 显式并行程序设计： 常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行
程序的自动并行化是一个理想目标，存在难以克服的困难 语言容易，编译器难 显式并行程序设计： 在用户程序中出现“并行”的调度语句 显式的并行程序开发则是解决并行程序开发困难的切实可行的 语言难，编译器容易 2004年4月

75 并行程序设计模型 隐式并行（Implicit Parallel） 数据并行（Data Parallel）
共享变量（Shared Variable） 消息传递（Message Passing） 2004年4月

76 隐式并行(Implicit Parallel)
概况： 程序员用熟悉的串行语言编程(未作明确的制定并行性) 编译器和运行支持系统自动转化为并行代码 特点： 语义简单 可移植性好 单线程，易于调试和验证正确性 细粒度并行 效率很低 2004年4月

77 数据并行（Data Parallel） 概况： 特点： 优点:编程相对简单,串并行程序一致.
SIMD的自然模型 局部计算和数据选路操作 特点： 单线程 并行操作于聚合数据结构（数组） 松散同步 单一地址空间 隐式交互作用 显式数据分布 优点:编程相对简单,串并行程序一致. 缺点:程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解. 并行粒度局限于数据级并行,粒度较小. 2004年4月

78 共享变量(Shared Variable)
概况： PVP, SMP, DSM的自然模型 特点： 多线程：SPMD, MPMD 异步 单一地址空间 显式同步 隐式数据分布 隐式通信 典型代表： OpenMP 2004年4月

79 消息传递(Message Passing)
概况： MPP、COW的自然模型 特点： 多线程 异步 多地址空间 显式同步 显式数据映射和负载分配 显式通信 典型代表 MPI、PVM 2004年4月

80 并行编程标准 数据并行语言标准 Fortran90, HPF(1992), Fortran95/2001:显式数据分布描述,并行DO循环.
线程库标准(Thread Library) – Win32 API. – POSIX threads线程模型. 编译制导(Compiler Directives) – OpenMP : portable shared memory parallelism 消息传递库标准(Message Passing Libraries) – MPI : Message Passing Interface – PVM : Parallel Virtual Machine 数据并行编程 共享变量编程 消息传递编程 2004年4月

81 并行编程标准归类 所有并行编程标准可分为以下三类: 三者可混合使用: 数据并行 共享编程 消息传递
HPF, Fortran90 用于SMP, DSM 共享编程 OpenMP 消息传递 MPI, PVM 用于所有并行计算机 三者可混合使用: 如对以SMP为节点的Cluster来说, 可以在节点间进行消息传递,在节点内进行共享变量编程. 2004年4月

82 基本并行化方法 相并行（Phase Parallel） 流水线并行（Pipeline Parallel）
主从并行（Master-Slave Parallel） 分治并行（Divide and Conquer Parallel） 工作池并行（Work Pool Parallel） 2004年4月

83 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI 、PVM、OpenMP
2004年4月

84 并行计算性能评测 Benchmark LINPACK www.top500.org 机器的理论峰值速度 用户能得到的实际速度 加速比、效率
S＝并行算法(程序)性能 / 串行算法(程序)性能 可扩展性：体系结构、软件、算法 随着计算负载的增加和机器规模的扩大，计算系统的性能是否随着处理器的数目的增加而按比例的增加 性能依赖因素： 算法设计：并行性、计算量 程序设计：体系结构特点的利用(通信、存储、Cache)、负载平衡、并行粒度 2004年4月

85 机器的理论峰值速度 理论峰值速度=CPU主频 ×每个时钟周期执行浮点运算的次数 × CPU数目
每个时钟周期执行浮点运算的次数是由处理器中浮点运算单元的个数及每个浮点运算单元在每个时钟周期能处理几条浮点运算来决定的 IBM Power4 PA-RISC Alpha Ultra Sparc SGI MIPS Itanium Xeon Pentium Opteron Flops/ cycle 4 2 1 2004年4月

86 基准测试程序(Benchmark) 基本测试程序 科学与工程计算性能
SPEC：原主要是测试CPU性能，现在强调开发能反映真实应用的基准测试程序，并以推广至客户/服务器计算、商业应用、I/O子系统等等 科学与工程计算性能 Linpack：高斯消元法求解线性代数方程组 NPB(NAS Parallel Benchmark)：美国NAS项目开发，包含8个空气动力学计算类应用，测试范围从整数排序到复杂的数值计算 LAPACK、ScalLAPACK：稠密、带状矩阵上的各类操作 Perfect、SPLASH、ParkBench 2004年4月

87 2004年4月

88 Linpack Linpack是国际上流行的用于测试高性能计算机系统浮点性能的benchmark
通过对高性能计算机采用LU分解求解线性代数方程组能力的测试，评价高性能计算机的浮点处理性能 2004年4月

89 Linpack 由J. Dongarra编写的Linpack采用主元高斯消去法求解双精度(64bits)稠密线性代数方程组 结果按每秒浮点运算次数（flops）表示 包含三类测试（问题规模与优化选择各不相同） 100×100测试 不允许对Linpack测试程序进行任何修改（包括注释行）。所有的优化只能在编译器里完成 1000×1000测试 允许对算法和软件进行修改或替换 并尽量利用系统的硬件特点，以达到尽可能高的性能 但是所有的优化都必须保持和标准算法如高斯消去法相同的相对精度，而且必须使用Linpack的主程序进行调用 2004年4月

90 HPL 高性能Linpack：HPL(High Performance Linpack)
针对大规模的并行计算机系统的测试， 2000年9月发布1.0版 是TOP500超级计算机排名的主要依据 采用MPI实现，基于BLAS库或VSIPL库 用户可以选择矩阵的大小(问题规模)、使用各种优化方法来执行测试程序，寻求最佳的测试结果 浮点峰值＝总计算量 / 计算时间 总计算量＝2/3 * N^3 – 2*N^2 计算时间：可通过系统时钟获得 2004年4月

91 如何做HPL测试 所必须的软件包 安装编译器、MPI、BLAS库，编译HPL 运行xhpl 查看结果文件 HPL
BLAS库：GOTO、ATLAS、ACML、MKL、Linux自带的BLAS库 等等 编译器：需要C语言和Fortran 77编译器。eg：gcc/g77、icc/ifc、pgcc/pgf77等等 并行环境：MPI 安装编译器、MPI、BLAS库，编译HPL 运行xhpl eg: mpirun –np 4 xhpl 查看结果文件 2004年4月

92 如何做HPL测试 HPL.out文件或在HPL.dat中设定 得到Linpack性能 eg: 3.975 Gflops
================================================= T/V N NB P Q Time Gflops WC03C2C e+00 ||Ax-b||_oo / ( eps * ||A||_1 * N ) = PASSED ||Ax-b||_oo / ( eps * ||A||_1 * ||x||_1 ) = PASSED ||Ax-b||_oo / ( eps * ||A||_oo * ||x||_oo ) = PASSED 得到Linpack性能 eg: Gflops 效率： Linpack性能 / 理论浮点性能 2004年4月

93 HPL性能调优 性能调优是一个很复杂的工作，涉及的因数众多，且和具体平台密切相关（CPU、内存、网络、OS、节点数及分布、体系结构、BLAS、编译器、内存和访存、IO等等）。主要包括： HPL参数的调整 编译优化 网络拓扑、通讯模式 负载平衡 数据局部性（Cache、Memory、TLB等） 内存使用：80％为宜 任务加载 OS、网络的调整 ….. ….. 2004年4月

94 NPB NAS并行基准测试程序（NPB Parallel Benchmark，NPB）是由美国国家航空和宇宙航行局（National Aeronautics and Space Administration，NASA）的NAS（Numerical Aerodynamic Simulation）研究组开发的一套代表流体动力学计算的应用程序集，它已经成为公认的用于评测大规模并行机和超级计算机的标准测试程序 NPB 2是一个并行版本，主要采用FORTRAN 77/90、C语言和MPI库编写 2004年4月

95 NPB NPB由八个程序组成，包括五个核心程序和三个伪应用，从不同的方面反映了流体动力学计算的特点
NPB 2中每个基准测试程序有6类问题规模，A、B、C、D和S、W。 从A类到D类，A类的规模最小，D类则是规模最大的 W（Workstation）类通常用于工作站 S（Sample）类是样例程序，倾向于测试 NPB中每类应用都有其各自的特点，其中IS基准程序由C语言编写，大部分计算是整数算术运算；FT为FORTRAN 90编写，其它6个基准程序均由FORTRAN 77编写，为浮点密集型计算 2004年4月

96 NPB 整数排序（IS）基准测试检测整数计算速度和通信能力，它检测并行排序操作，不包含浮点运算；但使用了显著的通信数据。整数排序对通信潜伏期敏感，因此低潜伏期的互相连接和高带宽在大量通信的应用中，尤如在IS中，倾向于有较好的性能。 繁杂并行（EP）检测按照特殊的方案产生一对高斯无序偏差。主要执行浮点数计算，EP显著的特点是不执行任何处理器间的通信，因此用不同的互相连接得到的结果显示同样的执行特点。 快速Fourier转换（FT）检测长距离的通信，利用快速傅立叶变换来解一个求解3维的偏微分方程，有大量计算的FT执行多种谱分析方法的实质性任务。 多栅格基准测试（MG）检测短距和长距的高度结构化的通信。MG是一个简化的多栅格核心，它有不变的系数而不是类似于许多滞弹性应用的可变系数问题。 2004年4月

97 NPB 共轭梯度方程求解（CG）基准测试检测不规则的长距离通信。CG基准测试使用共轭梯度方法计算较大的稀疏对称有限矩阵的最小特征值。CG是典型的非结构栅格计算，因为它是使用非规则的长距离通信和稀疏矩阵矢量乘法。 上下对角线（LU）检测细小块通信。此基准测试采用对称的连续松弛数字方案求解规则的稀疏方块5×5的下面和上面的三角矩阵系统。在LU中大多数的MPI通信使用“方块化”MPI发送和MPI接收。此外其大都是较小片段的通信，而且信息尺寸跨越一个数量级。由于算法实现上没有高度并行化，大多数MPI操作处于阻塞模式。其性能瓶颈主要发生在网络互连方面。 标量五角（SP）和块状三角（BT）倾向于检测计算和通信之间的平衡。与其它程序的不同的是，SP和BT需要处理器的平方数。在此两个基准测试中，对非对角性的SP和BT方程的多个独立系统分别求解。虽然SP和BT是相似的，但在通信与计算的比率上有基本的差别，SP比BT有更高的通信强度。 2004年4月

98 PMB PMB（Pallas MPI Benchmark）是由德国Pallas公司开发的、用于评测高性能计算机系统MPI层通信性能的一组基准测试程序 采用C语言编写的MPI并行程序 根据MPI应用程序中各种通信方式不同的特点，PMB中包括PingPong、PingPing、Sendrecv、Exchange、Bcast、Allgather、Allgatherv、Alltoall、Reduce、Reduce_scatter、Allreduce和Barrier12个测试程序来模拟实际应用程序中不同的通信方式。 2004年4月

99 STREAM STREAM测试可持续的存储带宽及其相应的计算速度
其开发的动机是，处理器比存储器越来越快，所以程序的瓶颈是存储器的带宽，而不是处理器的速度 STREAM迭代地执行四种向量操作，a(i)=b(i)、a(i)=q×b(i)、a(i)=b(i)＋c(i)和a(i)=b(i)+q×c(i)，其中向量a、b、c都是两百万元素的数组，每个元素是一个8字节的字。存储器的读和写操作都包含着计算带宽。 2004年4月

100 加速比性能定律 并行系统的加速比简单的说就是指对于一个给定的应用，并行算法或并行程序的执行速度相对于串行算法或串行程序的执行速度加快了多少倍
线性加速：对于通信很少的应用 eg: 矩阵相加、求内积 分治类问题：类似于二叉树，可望达到p/log p的加速 通信密集型应用：加速经验公式S＝1/C(P) 超线性加速：eg: 存储层次的影响 三种加速比性能定律： Amdahl定律：适用于固定计算负载 Gustafson定律：适用于可扩放问题 Sun和Ni定律：受限于存储器 P ： 处理器数 W ：问题规模 Ws：问题中的串行分量 Wp：并行分量 W＝Ws＋Wp S ：加速比 f ：串行分量的比率 f＝Ws/W 2004年4月

101 三种加速比性能定律 Amdahl定律：适用于固定计算负载 Gustafson定律：适用于可扩放问题 Sun和Ni定律：受限于存储器
很多科学计算实时性要求较高，时间是关键因数，而计算负载固定不变 计算负载固定载不变，增加处理器数来提高速度、减少时间 s=(Ws+Wp)/(Ws+Wp/p)=(f+(1-f))/(f+(1-f)/p) s--->1/f 实际上并行加速不仅受限于程序串行分量，还受并行程序运行时的额外开销影响 s＝1/(f+Wo/W) Gustafson定律：适用于可扩放问题 很多大型计算，精度要求很高，而计算时间固定不变 为提高精度，必须加大计算量，相应的必须增加处理器数 S=(Ws+pWp)/(Ws＋Wp)=f+p(1-f)=p+f(1-p)=p-f(p-1) Sun和Ni定律：受限于存储器 只要存储空间许可，应尽量增大问题规模以产生更好、更精确的解 S=(f+(1-f)G(p))/(f+(1-f)G(p)/p) G(p)=1 :Amdahl; G(p)=p,Gustafson 2004年4月

102 可扩放性 可扩放性(Scalability): 确定的应用背景下，计算系统(或算法或编程等)的性能随着处理器的数目的增加而按比例的提高的能力
可扩放性时算法和结构的组合，研究可扩放性时，总是将并行算法和体系结构一并考虑 算法的可扩放性: 该算法针对某一特定机器的可扩放性 体系结构的可扩放性: 该体系结构的机器的某一并行算法的可扩放性 一般情况下，增加处理器数，会增加额外开销和降低处理器利用率；所以对于一个特定的并行系统、并行算法或并行程序，它们能否有效的利用不断增加的处理器的能力应是受限的 研究可扩放性的目的 确定某类问题用哪种并行算法与哪种并行体系结构结合，可以有效地利用大量处理器 运行于某种体系结构的并行机上的某种算法，根据在小规模机器上的运行性能，预测在大规模机器上的性能 对固定的问题规模，确定最有的处理机数和加速比 指导改进算法、体系结构，以利用可扩充的大量处理器 2004年4月

103 可扩放性评测标准 等效率度量标准: 若问题规模w不变，随着处理器数P的增加会导致开销To随之增加，效率E下降。为了保持E不变，则在增加p的同时相应的增加问题规模W，以抵消由于p增加而导致的To的增加，从而保持效率不变 随着系统规模的增加(处理器数目的增加) ，测量增加多少运算量会保持效率不变 增加越少表明可扩放性越好 E＝1/(1+To/W) To: 额外开销时间之和 曲线1表示的算法具有很好的可扩放性，曲线2次之，曲线3最差 2004年4月

104 可扩放性评测标准 等速度度量标准 等计算时间/通信开销比率度量标准 计算时间/通信开销比率
系统规模增加时，若保持平均速度(每个处理器的速度)不变，每个处理器增加浮点操作的量 速度常以每秒多少次浮点运算(Flops)来表示 等计算时间/通信开销比率度量标准 系统规模增加时，保持计/通比不变所需要增加的问题规模 计算时间/通信开销比率 并行计算时间与系统开销之比 2004年4月

105 讲座主要内容提示 并行计算简介 编译环境 数学库 并行计算机体系结构 并行软件环境 并行计算机性能评测 MPI、PVM、OpenMP
2004年4月

106 消息传递并行程序设计 消息传递并行程序设计 并行计算粒度大，特别适合于大规模可扩展并行算法
指用户必须通过显式地发送和接收消息来实现处理机间的数据交换。 在这种并行编程中，每个并行进程均有自己独立的地址空间，相互之间访问不能直接进行，必须通过显式的消息传递来实现。 这种编程方式是大规模并行处理机（MPP）和机群（Cluster）采用的主要编程方式。 并行计算粒度大，特别适合于大规模可扩展并行算法 由于消息传递程序设计要求用户很好地分解问题,组织不同进程间的数据交换,并行计算粒度大,特别适合于大规模可扩展并行算法. 消息传递是当前并行计算领域的一个非常重要的并行程序设计方式 2004年4月

107 什么是MPI? Massage Passing Interface:是消息传递函数库的标准规范，由MPI论坛开发，支持Fortran和C
2004年4月

108 MPI的发展过程 发展的两个阶段 MPI 1.1: 1995 MPICH:是MPI最流行的非专利实现,由Argonne国家实验室和密西西比州立大学联合开发,具有更好的可移植性. MPI 1.2~2.0:动态进程, 并行 I/O, 支持F90和C++(1997). 2004年4月

109 为什么要用MPI? 高可移植性 MPI已在IBM PC机上、MS Windows上、所有主要的Unix工作站上和所有主流的并行机上得到实现。使用MPI作消息传递的C或Fortran并行程序可不加改变地运行在IBM PC、MS Windows、Unix工作站、以及各种并行机上。 2004年4月

110 从简单入手! 下面我们首先分别以C语言和Fortran语言的形式给出一个最简单的MPI并行程序Hello (下页).
该程序在终端打印出Hello World!字样. “Hello World”:一声来自新生儿的问候. 2004年4月

111 Hello world(C) #include <stdio.h> #include "mpi.h“ main(
int argc, char *argv[] ) { MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize(); } 2004年4月

112 Hello world(Fortran) program main include ‘mpif.h’ integer ierr
call MPI_INIT( ierr ) print *, 'Hello, world!' call MPI_FINALIZE( ierr ) end 2004年4月

113 C和Fortran中MPI函数约定 C Fortran MPI函数的参数被标志为以下三种类型： 必须包含mpi.h.
MPI 函数返回出错代码或 MPI_SUCCESS成功标志. MPI-前缀，且只有MPI以及MPI_标志后的第一个字母大写，其余小写. Fortran 必须包含mpif.h. 通过子函数形式调用MPI，函数最后一个参数为返回值. MPI-前缀，且函数名全部为大写. MPI函数的参数被标志为以下三种类型： IN：参数在例程的调用中不会被修正. OUT：参数在例程的调用中可能会被修正. INOUT：参数在一些例程中为IN，而在另一些例程中为OUT. 2004年4月

114 MPI初始化--MPI_INIT int MPI_Init(int *argc, char **argv) MPI_INIT(IERROR)
MPI_INIT是MPI程序的第一个调用，它完成MPI程序的所有初始化工作。所有的MPI程序的第一条可执行语句都是这条语句。 启动MPI环境,标志并行代码的开始. 并行代码之前,第一个mpi函数(除MPI_Initialize()外). 要求main必须带参数运行,否则出错. 2004年4月

115 MPI结束-MPI_FINALIZE int MPI_Finalize(void) MPI_FINALIZE(IERROR)
MPI_FINALIZE是MPI程序的最后一个调用，它结束MPI程序的运行，它是MPI程序的最后一条可执行语句，否则程序的运行结果是不可预知的。 标志并行代码的结束,结束除主进程外其它进程. 之后串行代码仍可在主进程(rank = 0)上运行(如果必须) 2004年4月

116 %小写o MPI程序的的编译与运行 mpif77 hello.f 或 mpicc hello.c
默认生成a.out的可执行代码. mpif77 –o hello hello.f 或 mpicc –o hello hello.c 生成hello的可执行代码. mpirun –np 4 a.out mpirun –np 4 hello 4 指定np的实参,表示进程数,由用户指定. a.out / hello 要运行的MPI并行程序. %小写o np: The number of process. 2004年4月

117 :运行我们的MPI程序! server0{czn}17: mpicc -o hello hello.c
server0{czn}18: ./hello () [0] Aborting program ! Could not create p4 procgroup. Possible missing fileor program started without mpirun. server0{czn}19: mpirun -np 4 hello () Hello World! server0{czn}20: 计算机打印字符 我们输入的命令 2004年4月

118 :Hello是如何被执行的? SPMD: Single Program Multiple Data(MIMD) ::::
#include "mpi.h" #include <stdio.h> main( int argc, char *argv[] ) { MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize(); } #include "mpi.h" #include <stdio.h> main( int argc, char *argv[] ) { MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize(); } #include "mpi.h" #include <stdio.h> main( int argc, char *argv[] ) { MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize(); } #include "mpi.h" #include <stdio.h> main( int argc, char *argv[] ) { MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize(); } #include "mpi.h" #include <stdio.h> main( int argc, char *argv[] ) { MPI_Init( &argc, &argv ); printf( "Hello, world!\n" ); MPI_Finalize(); } Hello World! 2004年4月

119 :开始写MPI并行程序 在写MPI程序时，我们常需要知道以下两个问题的答案： 任务由多少个进程来进行并行计算？ 我是哪一个进程?
2004年4月

120 :开始写MPI并行程序 MPI 提供了下列函数来回答这些问题： 用MPI_Comm_size 获得进程个数 p
int MPI_Comm_size(MPI_Comm comm, int *size); 用MPI_Comm_rank 获得进程的一个叫rank的值，该 rank值为0到p-1间的整数,相当于进程的ID int MPI_Comm_rank(MPI_Comm comm, int *rank); 2004年4月

121 更新的Hello World(c) #include <stdio.h> #include "mpi.h"
main( int argc, char *argv[] ) { int myid, numprocs; MPI_Init( &argc, &argv ); MPI_Comm_rank( MPI_COMM_WORLD, &myid ); MPI_Comm_size( MPI_COMM_WORLD, &numprocs ); printf(“I am %d of %d\n", myid, numprocs ); MPI_Finalize(); } 2004年4月

122 更新的Hello World(Fortran)
program main include ‘mpif.h’ integer ierr, myid, numprocs call MPI_INIT( ierr ) call MPI_COMM_RANK( MPI_COMM_WORLD, myid, ierr ) call MPI_COMM_SIZE( MPI_COMM_WORLD, numprocs, ierr ) print *, ‘I am', myid, ‘of', numprocs call MPI_FINALIZE( ierr ) end 2004年4月

123 :运行结果 server0{czn}22: mpicc –o hello1 hello1.c
server0{czn}23: mpirun -np 4 hello1 I am 0 of 4 I am 1 of 4 I am 2 of 4 I am 3 of 4 server0{czn}24: 计算机打印字符 我们输入的命令 2004年4月

124 有消息传递 greetings(c) #include <stdio.h> #include "mpi.h"
main(int argc, char* argv[]) { int numprocs, myid, source; MPI_Status status; char message[100]; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myid); MPI_Comm_size(MPI_COMM_WORLD, &numprocs); 2004年4月

125 有消息传递 greetings(c) if (myid != 0) { strcpy(message, "Hello World!");
MPI_Send(message,strlen(message)+1, MPI_CHAR, 0,99, MPI_COMM_WORLD); } else {/* myid == 0 */ for (source = 1; source < numprocs; source++) { MPI_Recv(message, 100, MPI_CHAR, source, 99, MPI_COMM_WORLD, &status); printf("%s\n", message); } MPI_Finalize(); } /* end main */ 2004年4月

126 Greeting执行过程 2004年4月

127 解剖greetings程序 头文件: mpi.h/mpif.h. int MPI_Init(int *argc, char ***argv)
并行代码之前,第一个mpi函数(除MPI_Initialize()外). 要求main必须带能运行,否则出错. 通信子(通信空间): MPI_COMM_WORLD： 一个通信空间是一个进程组和一个上下文的组合.上下文可看作为组的超级标签,用于区分不同的通信子. 在执行函数MPI_Init之后,一个MPI程序的所有进程形成一个缺省的组,这个组的通信子即被写作MPI_COMM_WORLD. 该参数是MPI通信操作函数中必不可少的参数,用于限定参加通信的进程的范围. 2004年4月

128 解剖greetings程序 int MPI_Comm_size ( MPI_Comm comm, int *size )
指定一个communicator,也指定了一组共享该空间的进程, 这些进程组成该communicator的group. int MPI_Comm_rank ( MPI_Comm comm, int *rank ) 得到本进程在通信空间中的rank值,即在组中的逻辑编号(从0开始). int MPI_Finalize() 标志并行代码的结束,结束除主进程外其它进程. 之后串行代码仍可在主进程(rank = 0)上运行(如果必须). 2004年4月

129 消息传送(先可不关心参数含义) 数据传送 + 同步操作 需要发送方与接收方合作完成.
MPI_Send(A, 10, MPI_DOUBLE, 1,99, MPI_COMM_WORLD); MPI_Recv(B, 20, MPI_DOBULE, 0, 99, MPI_COMM_WORLD, &status); 数据传送 + 同步操作 Data Process 0 Process 1 发送请求 Yes Time 需要发送方与接收方合作完成. 2004年4月

130 MPI程序的编译 mpicc编译并连接用C语言编写的MPI程序 mpiCC编译并连接用C++编写的MPI程序
mpif77编译并连接用FORTRAN 77编写的MPI程序 mpif90编译并连接用Fortran 90编写的MPI程序 这些命令可以自动提供MPI需要的库，并提供特定的开关选项（用-help查看） 2004年4月

131 MPI程序的编译 用mpicc编译时，就像用一般的C编译器一样。还可以使用一般的C的编译选项，含义和原来的编译器相同 例如：
./mpicc -c foo.c ./mpicc -o foo foo.o 2004年4月

132 MPI程序的运行 MPI程序的执行步骤一般为： 将可执行程序拷贝到各个节点机上 通过mpirun命令并行执行MPI程序
2004年4月

133 最简单的MPI运行命令 mpirun –np N <program> 其中： 例如： N： 同时运行的进程数
<program>: 可执行MPI程序名 例如： mpirun –np 6 cpi mpirun –np 4 hello 2004年4月

134 一种灵活的执行方式 mpirun –p4pg <pgfile> <program>
<机器名> <进程数> <程序名> 例如： (注：第一行的0并不表示在node0上没有进程，这里的0特指在node0上启动MPI程序) node0 0 /public0/czn/mpi/cpi node1 1 /public0/czn/mpi/cpi node2 1 /public0/czn/mpi/cpi 这种方式允许可执行程序由不同的名字和不同的路径 2004年4月

135 完整的MPI运行方式 MPI程序的一般启动方式： 完整的MPI运行方式：
mpirun –np <number of processor> <program name and argument> 完整的MPI运行方式： mpirun [mpirun_options] <program> [options…] 详细参数信息执行mpirun -help 2004年4月

136 各种不同的底层通信库的不同接口的统一标准(相当于某一种底层通信库)
曙光4000L: MPI-BCL MPI-BCL:为曙光4000l优化的MPI通信库，和基于TCP/IP的网络版MPICH1.2 (三层结构) 各种不同的底层通信库的不同接口的统一标准(相当于某一种底层通信库) Point to point Collective API ADI:Abstract Device Interface 具体的底层通信库 MPI-BCL:MPI-Basic Communication Library 移植:根据不同的device(即平台或底层通信)实现不同的ADI接口 2004年4月

137 曙光4000L: run 常用形式：run –np 4 a.out
run -h|help|-? -sz <size>|-sz <hXw> -pn <pnode list> -np <nprocs> -pl <poolname> -cpu program <parameters> -h|help|-? 得到run的帮助信息,需要帮助时用 -sz <size> 指定物理节点数,默认与np数相等,可忽略, run –sz 4 –np 8 a.out 表示在4个物理节点上运行a.out的8个进程 -sz <hXw> 指定物理节点的长和宽,选定mesh结构, run –sz 4X4 a.out表示在一个4*4的mesh结构上组织通信 -np <nprocs> 指定进程数 -on <pnode list> 指定物理节点列表 run –on node0..3 a.out 表示在节点0,1,2,3上运行a.out -pl <plname> 指定节点池名p1,p2,默认为p1/(0-15) -cpu 载入要执行程序的cpu模式 –ep独占通讯端口,-en独占节点 program <parameters> 要执行程序名以及其参数 常用形式：run –np 4 a.out 2004年4月

138 PVM(Parallel Virtual Machine)
开发时间: 始于1989年 开发单位: 美国橡树岭(Oak Ridge)国家实验室、美国Tennessee大学和Emory大学联合研制 特点: 具有较好的适应性、可扩展性、可移植性和易使用性等特点, 源代码可以免费获取, 现已被用户广泛采纳。 现状: 目前对它的研究和开发工作仍在各大学和研究机构进行. 随着它的不断流行, 已经被移植到PVP、SMP、MPP、工作站和机群系统。 PVM出现的时间较MPI早，且是一个自包含系统(MPI不是自包含的)，同时PVM不是一个标准(MPI是个标准)。目前，PVM和MPI正在互相靠拢。 2004年4月

139 PVM概貌 PVM系统的组成(两部分)： PVM监控进程(Daemon Process), 称为pvmd, 它常驻在虚拟机的每一台节点机上。
PVM可调用的库, 称为libpvm3.a, 它与用户的应用程序链接, 用于进程管理, 消息传递和虚拟机管理。 在PVM中, 节点(a node)称为主机(a host). 进程(a process)称为任务(a task). 并行虚拟机的组成 1~多台主机(硬件) 唯一1个master pvmd, 运行在称为控制台的主机上 0~多个slave pvmd 2004年4月

140 共享存储并行机模型 体系结构特点: 多台处理机通过互联网络共享一个统一的内存空间,通过单一内存地址来实现处理机间的协调.
内存空间也可由多个存储器模块构成. 每台处理机可以执行相同或不同的指令流,每台处理机可以直接访问到所有数据. 处理机间通信是借助于共享主存来实现的. 可扩展性差,当处理机需要同时访问共享全局变量时,产生内存竞争现象而严重影响效率,比较适合中小规模应用问题的计算和事务处理. 2004年4月

141 共享存储编程标准与特点 共享存储器编程标准 共享存储器编程特点 语言 Pthreads(线程标准) X3H5(线程标准)
OpenMP(最常用的共享存储并行编程方式,是我们讨论的重点.) 共享存储器编程特点 显式多线程库调用.(Pthreads). 编译制导语句,OpenMP等. 语言 C,Fortran77,Fortran90/95,C++… 2004年4月

142 与X3H5的关系 X3H5是ANSI/X3授权的小组委员会,主要目的是在PCF(the Parallel Computing Forum)工作的基础上,发展并行计算的一个ANSI标准. PCF是一非正式的工业组织,虽在DO循环的并行化方法的标准化方面做一些工作,但在起草拟了一个标准后就草草收场 OpenMP专门针对这类并行化问题,并完成了这项工作,同时得到工业界的广泛支持 2004年4月

143 ANSI X3H5共享编程标准 概念性的编程模型(ANSI标准(1993)) X3H5支持C,Fortran77以及Fortran90语言.
没有任何商品化的共享存储器系统依附于X3H5,但X3H5的基本概念影响以后共享存储器系统的并行编程.(一些基本概念在OpenMP均出现!) X3H5支持C,Fortran77以及Fortran90语言. X3H5规定的基本的并行结构用于并行性表述: 并行块(分散任务Work Sharing) 并行循环 单进程 parallel { … } end parallel psections { … } end psections pdo { … } end pdo psingle { … } end psingle 2004年4月

144 X3H5编程实例 program main !程序以顺序模式执行 end A !A只由基本线程执行 parallel !转换成并行模式
B !B为每个组员所复制 psections !并行块开始 section C !一个组员执行C D !另一个组员执行D end psections !等待C和D都结束 psingle 暂时转换成顺序模式 E !E只能被一个组员执行 end psingle !转回并行模式 pdo I=1,6 !并行do循环开始 F(i) !各线程分担循环任务 end pdo no wait !无隐式路障同步 G !更多的复制代码 end parallel !结束并行模式 H !根进程执行H … !更多的并行构造 end 线程 P Q R 隐式barrier B B B C D 隐式barrier E 隐式barrier F(1:2) F(3:4) F(5:6) 无隐式barrier G G G 隐式barrier H 各线程以负载平衡方式分担任务 可能为:F(1:1),F(2:2),F(3:6)… 2004年4月

145 X3H5例程执行过程描述 程序以顺序方式启动,此时只有一个初始化线程,称为基本线程或主线程.当程序遇到parallel时,通过派生多个子线程转换为并行执行模式(线程数隐式决定).基本线程与它的子线程形成一个组.所有组员并行处理后继并行代码,直至end parallel.然后程序转为顺序模式,只有基本线程继续执行. 子线程遇到内部并行或任务分担构造时,可以继续派生其子线程,从而成为一个新组的基本线程. 线程间同步,通信与交互 隐式路障:parallel, end parallel, end pdo或end psingle处隐式barrier.如果不需,则加no wait; 各处理机通过全局变量通信,通过私有变量封装数据 顺序执行 fork …... 并行执行 barrier 顺序执行 … 2004年4月

146 OpenMP: 并行模型 Fork-Join 并行模式: 主线程根据需要创建一组子线程进行工作分担. 可对串行程序进行逐步并行化. 主线程
并行执行区域 2004年4月

147 如何应用OpenMP? OpenMP常用于循环并行化: – 找出最耗时的循环 – 将循环由多线程完成
void main() { double Res[1000]; for(int i=0;i<1000;i++) { do_huge_comp(Res[i]); } void main() { double Res[1000]; #pragma omp parallel for for(int i=0;i<1000;i++) { do_huge_comp(Res[i]); } 串行程序 并行程序 2004年4月

148 OpenMP并行程序编译 支持编译OpenMP的编译器会提供编译器命令选项,以解释OpenMP编译制导语句.
IBM AIX xlc编译器,编译器命令选项为-qsmp xlc file.c –qsmp xlf_r file.f -qsmp (xlf_r为IBM AIX4.3为支持多线程编程的编译器) 曙光3000：OS: AIX4.3 -qsmp AIX4.3支持 OpenMP编译选项 Intel C/C++编译器icc, Intel Fortran编译器选项为-openmp icc file.c –openmp ifc file.c –openmp 曙光4000L：OS:Redhat Linux 7.3 2004年4月

149 谢谢！ 2004年4月