单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,2004,年,4,月,*,/149,2004,年,4,月,1,/149,讲座主要内容提示,并行计算简介,编译环境,数学库,并行计算机体系结构,并行软件环境,并行计算机性能评测,MPI,、,PVM,、,OpenMP,,2004年4月1/149讲座主要内容提示并行计算简介,2004,年,4,月,2,/149,并行计算,--,高性能计算,并行计算,(Parallel Computing,）,,高端计算,(High-end Parallel Computing),,高性能计算,(High Performance Computing),,超级计算,(Super Computing),,任何高性能计算和超级计算都离不开使用并行技术,,计算科学,与传统的两种科学，即,理论科学,和,实验科学,，并立被认为是人类认识自然的三大支柱，他们彼此相辅相成地推动科学发展与社会进步在许多情况下，或者是理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至无法进行时，计算就成了求解问题的唯一或主要的手段2004年4月2/149并行计算--高性能计算并行计算(Pa,2004,年,4,月,3,/149,并行,:,古老的思想,!,“...,并行计算并不是什么新的思想,,,只是将它扩展应用于计算机而已”,.,作者也不认为这种扩展应用会存在什么无法克服的困难,.,但也不要期待有效的并行编程方法与技术能够在一夜之间诞生,.,期间还需要有许多的工作和实验要做,.,毕竟,,,今天的编程技术,(,串行,),是若干年来艰苦的探索才取得的,.,现在编程工作似乎成了一种令人单调乏味的工作,,,事实上,,,并行编程的出现将会使重新恢复编程工作者们的探索精神,...”,(,Gill, S. (1958),,“Parallel Programming”,,The Computer Journal, vol. 1, April, pp. 2-10.),Parallel Programming with MPI,by Peter Pacheco(2000),2004年4月3/149并行:古老的思想!“...并行计算并,2004,年,4,月,4,/149,什么是并行计算,?,并行计算,:,,由运行在多个部件上的小任务合作来求解一个规模很大的计算问题的一种方法,,例,:,在曙光,2000,上用,8,个节点计算的,Mandelbrot,集结果,(Mandelbrot,为分形理论创始人,),,2004年4月4/149什么是并行计算?并行计算: 由运行在,2004,年,4,月,5,/149,现代计算机的共同特点： 并行性,2004年4月5/149现代计算机的共同特点：,2004,年,4,月,6,/149,现代计算机的共同特点： 并行性,2004年4月6/149现代计算机的共同特点：,2004,年,4,月,7,/149,为什么要做并行计算？ －－应用需求,2004年4月7/149为什么要做并行计算？,2004,年,4,月,8,/149,为什么要做并行计算？,人类对计算及性能的要求是无止境的,从系统的角度,：集成系统资源，以满足不断增长的对性能和功能的要求,从应用的角度,：适当分解应用，以实现,更大规模,或,更细致,的计算,2004年4月8/149为什么要做并行计算？人类对计算及性能,2004,年,4,月,9,/149,为什么要做并行计算？,问题,:,科学和工程问题的数值模拟与仿真,计算密集,数据密集,网络密集,三种混合,,要求,:,在合理的时限内完成计算任务,秒级 制造业,分钟级 短时天气预报,(,当天,),小时级 中期天气预报,(3~10,日,),尽可能快 长期天气预报,(,气候,),可计算 湍流模拟,2004年4月9/149为什么要做并行计算？问题: 科学和工,2004,年,4,月,10,/149,2004年4月10/149,2004,年,4,月,11,/149,并行计算的功能,降低单个问题求解的时间,,增加问题求解规模、提高问题求解精度,,(,多机同时执行多个串行程序,),容错、更高的可用性、提高吞吐率,2004年4月11/149并行计算的功能降低单个问题求解的时,2004,年,4,月,12,/149,如何实现并行计算,?,,分而治之,!,2004年4月12/149如何实现并行计算?分而治之!,2004,年,4,月,13,/149,分而治之,并行化的主要方法,:,分而治之,根据问题的求解过程，把任务分成若干子任务,(,任务级并行或功能并行,),根据处理数据的方式，形成多个相对独立的数据区，由不同的处理器分别处理,(,数据并行,),2004年4月13/149分而治之并行化的主要方法:分而治之,2004,年,4,月,14,/149,讲座主要内容提示,并行计算简介,编译环境,常用编译器,编译优化,如何编译,数学库,并行计算机体系结构,并行软件环境,并行计算机性能评测,MPI,、,PVM,、,OpenMP,,2004年4月14/149讲座主要内容提示并行计算简介,2004,年,4,月,15,/149,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月15/149GNU CompilerGNU C,2004,年,4,月,16,/149,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月16/149PGI CompilerPGI C,2004,年,4,月,17,/149,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,天试用版本, CompilerInt,2004,年,4,月,18,/149,编译优化,编译优化对于计算密集型程序的性能提高非常帮助,优化消耗,CPU,资源最多的那部分，即计算密集部分,一般采用,-O2,、,-O3,可以采用,SIMD,指令集，,eg: Intel,和,AMD,处理器的,MMX,、,SSE1,、,SSE2,具体编译优化的选项和编译器以及,CPU,相关，参见编译器手册,对于有些应用程序，过分的优化会导致计算结果错误,2004年4月18/149编译优化编译优化对于计算密集型程序,2004,年,4,月,19,/149,编译优化,在双路,Intel Xeon,平台上，采用,SSE2,优化和不采用,SSE2,优化，所获得的,HPL,性能。
在这种情况下，,采用,SSE2,技术得到的性能高出近,90,％,,,2004年4月19/149编译优化在双路Intel Xeon,2004,年,4,月,20,/149,编译简介,在,Linux,系统中，可执行文件没有统一的后缀，系统从文件的属性来区分可执行文件和不可执行文件,大部分编译器通过后缀来区别输入文件的类别，下面来介绍常用的一些后缀,.c,：,C,语言源代码文件,.f,：,Fortran 77,语言源代码文件,.o,：编译后的目标文件,.a,：由目标文件构成的档案库文件,.C,、,.cc,、,.cxx,：,C++,源代码文件,.f90,：,Fortran 90,语言源代码文件,.h,：程序所包含的头文件,2004年4月20/149编译简介在Linux系统中，可执行,2004,年,4,月,21,/149,基本的用法,,cc/f77/f90 [options] [filenames],,编译器名 编译参数 编译文件,,其中,options,就是编译器所需要的参数，,filenames,给出相关的文件名称,,2004年4月21/149基本的用法,2004,年,4,月,22,/149,常用编译参数,-c,：只编译，不连接成为可执行文件，编译器只是由输入的,.c/.f,等源代码文件生成,.o,为后缀的目标文件，通常用于编译不包含主程序的子程序文件。
o output_filename,：确定输出文件的名称为,output_filename,，同时这个名称不能和源文件同名如果不给出这个选项，就给出预设的可执行文件,a.out,-g,：产生符号调试工具所必要的符号资讯，要想对源代码进行调试，我们就必须加入这个选项O,：对程序进行优化编译、连接，采用这个选项，整个源代码会在编译、连接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、连接的速度就相应地要慢一些O2,、,-O3,、,-O4,：比,-O,更好的优化编译、连接，当然整个编译、连接过程会更慢具体和编译器相关）,2004年4月22/149常用编译参数-c：只编译，不连接成,2004,年,4,月,23,/149,常用编译参数,-Idirname,：将,dirname,所指出的目录加入到程序头文件目录列表中，是在预编译过程中使用的参数C,程序中的头文件包含两种情况：,A)#include ,B)#include “myinc.h”,,其中，,A,类使用尖括号,(),，,B,类使用双引号,(“ ”),对于,A,类，预处理程序,cpp,在系统预设包含文件目录,(,如,/usr/include),中搜寻相应的文件，而对于,B,类，,cpp,在当前目录中搜寻头文件，这个选项的作用是告诉,cpp,，如果在当前目录中没有找到需要的文件，就到指定的,dirname,目录中去寻找。
在程序设计中，如果我们需要的这种包含文件分别分布在不同的目录中，就需要逐个使用,-I,选项给出搜索路径2004年4月23/149常用编译参数-Idirname：将,2004,年,4,月,24,/149,常用编译参数,-Ldirname,：将,dirname,所指出的目录加入到程序函数档案库文件的目录列表中，是在连接过程中使用的参数在预设状态下，连接程序,ld,在系统的预设路径中,(,如,/usr/lib),寻找所需要的档案库文件，这个选项告诉连接程序，首先到,-L,指定的目录中去寻找，然后到系统预设路径中寻找，如果函数库存放在多个目录下，就需要依次使用这个选项，给出相应的存放目录lname,：在连接时，装载名字为“,libname.a”,的函数库，该函数库位于系统预设的目录或者由,-L,选项确定的目录下例如，,-lm,表示连接名为“,libm.a”,的数学函数库上面我们简要介绍了编译器最常用的功能和主要参数选项，更为详尽的资料可以参看,Linux,系统的联机帮助2004年4月24/149常用编译参数-Ldirname：将,2004,年,4,月,25,/149,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月25/149GCC应用举例1.gcc hel,2004,年,4,月,26,/149,Make,简介,在开发大系统时，经常要将程序划分为许多模块。
各个模块之间存在着各种各样的依赖关系，在,Linux,中通常使用,Makefile,来管理,由于各个模块间不可避免存在关联，所以当一个模块改动后，其他模块也许会有所更新，当然对小系统来说，手工编译连接是没问题，但是如果是一个大系统，存在很多个模块，那么手工编译的方法就不适用了为此，在,Linux,系统中，专门提供了一个,make,命令来自动维护目标文件,与手工编译和连接相比，,make,命令的优点在于他只更新修改过的文件,，,而对没修改的文件则置之不理，并且,make,命令不会漏掉一个需要更新的文件,2004年4月26/149Make简介在开发大系统时，经常要,2004,年,4,月,27,/149,一个简单的例子,先举一个例子,: 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月27/149一个简单的例子先举一个例子: a.,2004,年,4,月,28,/149,书写,makefile,文件,Makefile,时由规则来组成的,,,每一条规则都有三部分组成,:,目标,(object),,依赖,(dependency),和命令,(command).,在上面的例子中,, Makefile,只有一条规则,,,其目标为,hello,,期依赖为,a.c b.c,,其命令为,gcc a.c b.c -o hello,,依赖可以是另一条规则的目标,,,也可以是文件,.,每一条规则被这样处理,.,如目标是一个文件是,:,当它的依赖是文件时,,,如果依赖的时间比目标要新,,,则运行规则所包含的命令来更新目标,;,如果依赖是另一个目标则用同样的方法先来处理这个目标,.,如目标不是一个存在的文件时,,,则一定执行,.,2004年4月28/149书写makefile文件Makef,2004,年,4,月,29,/149,一个简单的,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月29/149一个简单的makefile文件例如,2004,年,4,月,30,/149,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月30/149Make中的宏(macro)在ma,2004,年,4,月,31,/149,系统定义的宏,还有一些设定好的内部变量，它们根据每一个规则内容定义@,当前规则的目的文件名,$<,依靠列表中的第一个依靠文件,$^,整个依靠的列表（除掉了里面所有重复的文件名）。
依赖中所有新于目标的,以用变量做许多其它的事情，特别是当你把它们和函数混合 使用的时候如果需要更进一步的了解，请参考,GNU Make,手册'man make', 'man makefile'),2004年4月31/149系统定义的宏还有一些设定好的内部变,2004,年,4,月,32,/149,修改原先的,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,$(CC) $(CFLAGS) -c $<,clean:,rm –f *.o hello,2004年4月32/149修改原先的makefile CC,2004,年,4,月,33,/149,隐含规则,请注意在上面的例子里，几个产生,.o,文件的命令都是一样的，都是从,.c,文件和相关文件里产生,.o,文件，这是一个标准的步骤其实,make,已经知道怎么做,—,它有一些叫做隐含规则的内置的规则，这些规则告诉它当你没有给出某些命令的时候，应该怎么办。
如果你把生成,a.o,和,b.o,的命令从它们的规则中删除，,make,将会查找它的隐含规则，然后会找到一个适当的命令它的命令会使用一些变量，因此你可以按照你的想法来设定它：它使用变量,CC,做为编译器，并且传递变量,CFLAGS,CPPFLAGS,TARGET_ARCH,，然后它加入 ‘,-c’,，后面跟变量,$<,，然后是 ‘,-o’,跟变量,$@,一个Ｃ编译的具体命令将会是：,,$(CC) $(CFLAGS) $(CPPFLAGS) $(TARGET_ARCH) -c $< -o $@,当然你可以按照你自己的需要来定义这些变量2004年4月33/149隐含规则请注意在上面的例子里，几个,2004,年,4,月,34,/149,讲座主要内容提示,并行计算简介,编译环境,数学库,BLAS,其它,并行计算机体系结构,并行软件环境,并行计算机性能评测,MPI,,2004年4月34/149讲座主要内容提示并行计算简介,2004,年,4,月,35,/149,BLAS,BLAS,基本线性代数库,(,Basic Linear Algebra Subroutines,）,提供最基本的线性代数函数接口,分为三级,BLAS 1,（,Level 1,）：向量与向量操作,BLAS 2,（,Level 2,）：矩阵与向量操作,BLAS 3,（,Level 3,）：矩阵与矩阵操作,,2004年4月35/149BLASBLAS,2004,年,4,月,36,/149,LAPACK,LAPACK,：线性代数计算子程序包（,Linear Algebra Package,）,LAPACK,是建立在,BLAS 1,、,BLAS 2,和,BLAS 3,基础之上,使用,Fortran 77,语言开发,使用了线性代数中最新、最精确的算法，同时采用了将大型矩阵分解成小块矩阵的方法从而可以有效的使用存储空间,开放源码，,lib.org/lapack/,,2004年4月36/149LAPACKLAPACK：线性代数,2004,年,4,月,37,/149,ScaLAPACK,ScaLAPACK,：可扩展线性代数库,(Scalable LAPACK),，是,LAPACK,的增强版本,是美国能源部,ODE2000,支持开发的,20,多个,ACTS,工具箱之一，由,Oak Ridge,国家实验室、加州大学,Berkeley,分校和,Illinois,大学等联合开发,分布式存储环境运行的线性代数库，主要为可扩放的、分布存储的并行计算机而设计的,支持稠密和带状矩阵的各类操作，如：乘法、转置、分解等等,开发源码，,lib.org/scalapack,,,2004年4月37/149ScaLAPACKScaLAPAC,2004,年,4,月,38,/149,常用,BLAS,库,Linux,自带,Blas,库,由,Linux,操作系统提供，在安装,Linux,时可以选择安装,性能相对较差,/usr/lib,目录下,,,2004年4月38/149常用BLAS库 Linux自带Bl,2004,年,4,月,39,/149,常用,BLAS,库 －,ATLAS,ATLAS,开放源代码,(,免费,),，用户可以下载源代码，在自己的平台上编译,在编译中调整性能，达到性能最优,包括全部,BLAS,函数和一部分,LAPACK,函数,提供,C,和,Fortran 77,接口,最新版本：,3.7,http://math- －ATLASATL,2004,年,4,月,40,/149,常用,BLAS,库 －,GOTO,GOTO,免费提供各种平台二进制代码的下载,支持,Opteron,、,Xeon,、,Itanium,、,Power,、,Alpha,等平台,支持,Windows,平台（,Xeon,、,Opteron,）,支持多线程,性能最优,最新版本：,0.9,下载网址：,http://www.cs.utexas.edu/users/kgoto/,,2004年4月40/149常用BLAS库 －GOTOGOTO,2004,年,4,月,41,/149,常用,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,免费下载，下载网址：, －ACMLACML,2004,年,4,月,42,/149,常用,BLAS,库 －,MKL,MKL,Intel,®,Math Kernel Library,Intel,公司开发，针对,Intel,处理器，,Pentium,、,Xeon,、,Itanium,包括诸如,BLAS,和,LAPACK,等线性代数功能，离散傅利叶变换（,DFT,）以及向量超越函数（向量数学库,/VML,），以及向量统计函数（,VSL,）,Linux,版本和,Windows,版本,需要购买，但可以从网上得到,30,天试用版本, －MKLMKL,2004,年,4,月,43,/149,常用,BLAS,库 －,ESSL,ESSL,ESSL,库,(Engineering and Scientific Subroutine Library),是,IBM,提供的工程与科学计算优化库，针对,IBM Power,系列处理器,包括：,线性代数子程序,，,矩阵运算,，,线性代数方程,、,本征系统分析,，,傅立叶变换、卷积与对射变换及其它信号处理相关计算,，,排序与搜索,，,插值,，,数值积分,，,微分方程,，,随机数生成,2004年4月43/149常用BLAS库 －ESSLESSL,2004,年,4,月,44,/149,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,等,公开源代码，免费下载,http://www.mcs.anl.gov/petsc,,2004年4月44/149PETScPETSc：并行可扩展科,2004,年,4,月,45,/149,PETSc,2004年4月45/149PETSc,2004,年,4,月,46,/149,PETSc,PETSc,的一些模块处理：,索引集，包括用于向量索引的置换，重新计数等,向量,矩阵（一般是,稀疏,的）,分布阵列（对正规的基于网格问题的并行化有用）,Krylov,子空间方法,预条件子，包括多重网格和稀疏直接解法器,非线性解法器,解时间相关（非线性）,PDEs,的时间步进解法器,,2004年4月46/149PETScPETSc 的一些模块处,2004,年,4,月,47,/149,讲座主要内容提示,并行计算简介,编译环境,数学库,并行计算机体系结构,并行软件环境,并行计算机性能评测,MPI,、,PVM,、,OpenMP,,2004年4月47/149讲座主要内容提示并行计算简介,2004,年,4,月,48,/149,并行计算机系统结构,Flynn,分类：,SISD, SIMD, MIMD, MISD,,结构模型：,PVP, SMP, MPP, DSM, COW,,访存模型：,UMA, NUMA, COMA, CC-NUMA, NORMA,2004年4月48/149并行计算机系统结构Flynn分类：,2004,年,4,月,49,/149,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月49/149Flynn分类Flynn(1972,2004,年,4,月,50,/149,结构模型,2004年4月50/149结构模型,2004,年,4,月,51,/149,共享存储对称多处理机系统,(SMP),SMP,:,对称式共享存储：任意处理器可直接访问任意内存地址,,,且访问延迟、带宽、几率都是等价的,;,系统是对称的；,微处理器,:,一般少于,64,个,;,处理器不能太多,,,总线和交叉开关的一旦作成难于扩展；,例子,: IBM R50, SGI Power Challenge, SUN Enterprise,,曙光一号,2004年4月51/149共享存储对称多处理机系统(SMP),2004,年,4,月,52,/149,分布共享存储多处理机系统,(DSM),DSM:,分布共享存储,:,内存模块物理上局部于各个处理器内部,,,但逻辑上,(,用户,),是共享存储的,;,这种结构也称为基于,Cache,目录的非一致内存访问,(CC-NUMA),结构,;,局部与远程内存访问的延迟和带宽不一致,,3-10,倍,,高性能并行程序设计注意,;,与,SMP,的主要区别：,DSM,在物理上有分布在各个节点的局部内存从而形成一个共享的存储器；,微处理器,: 16-128,个,,,几百到千亿次,;,代表,: SGI Origin 2000, Cray T3D;,2004年4月52/149分布共享存储多处理机系统(DSM),2004,年,4,月,53,/149,大规模并行计算机系统,(MPP),MPP:,物理和逻辑上均是分布内存,能扩展至成百上千个处理器,(,微处理器或向量处理器,),采用高通信带宽和低延迟的互联网络,(,专门设计和定制的,),一种异步的,MIMD,机器；程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用；,代表,:CRAY T3E(2048), ASCI Red(3072), IBM SP2,,曙光,1000,；,2004年4月53/149大规模并行计算机系统(MPP)MP,2004,年,4,月,54,/149,机群系统,(Cluster),Cluster:,每个节点都是一个完整的计算机,各个节点通过高性能网络相互连接,网络接口和,I/O,总线松耦合连接,每个节点有完整的操作系统,曙光,2000, 3000, ASCI Blue Mountain (48,台,128-way DSM Origin 2000,6144,个处理器,),2004年4月54/149机群系统(Cluster)Clus,2004,年,4,月,55,/149,访存模型,UMA:,NORMA:,NUMA:,多处理机（单地址空间共享存储器）,,UMA: Uniform Memory Access,NUMA: Nonuniform Memory Access,多计算机（多地址空间非共享存储器）,,NORMA:No-Remote Memory Access,2004年4月55/149访存模型UMA:NORMA:NUM,2004,年,4,月,56,/149,均匀存储器存取,(UMA),均匀存储器存取（,UMA,－,Uniform Memory Access,）,所有处理器,均匀共享,物理存储器，这里所谓均匀是指所有处理器对所有存储字具有相同的存取时间,每台处理器可带私有高速缓存,外围设备也可以一定形式共享,各处理机之间的通信是通过共享存储器的共享变量来实现的,这一类多处理机由于对资源的高度共享,,,常称,紧耦合,系统,(tightly coupled system),UMA:,2004年4月56/149均匀存储器存取 (UMA)均匀存储,2004,年,4,月,57,/149,均匀存储器存取,(UMA),对称多处理机系统,(symmetric multi-processor),所有处理机都能同样访问所有外围设备；所有处理机都能同样运行执行程序，如操作系统的内核、,I/O,服务程序,,不对称处理机系统,(asymmtric multi-processor),只有一台或一组处理机（,MP,主处理机）执行操作系统并操纵,I/O,，其余处理机（,AP,附属处理机）没有,I/O,能力,2004年4月57/149均匀存储器存取 (UMA)对称多处,2004,年,4,月,58,/149,非均匀存储访问,(NUMA),非均匀存储访问,(NUMA,—,Nonuniform Memory Access),被共享的存储器在物理上是分布在所有的处理其中的，其所有本地存储器的集合就组成了全局地址空间,处理器访问存储器的时间是不一样的：访问本地存储器,(LM),较快，而访问外地的存储器较慢（此即是非均匀存储访问名称的由来）,每台处理器可带私有高速缓存，且外设也可以某种形式共享,NUMA:,2004年4月58/149非均匀存储访问(NUMA)非均匀存,2004,年,4,月,59,/149,非远程存储访问,(NORMA),非远程存储访问,(NORMA,—,No-Remote Memory Access),所有存储器都是私有的，仅能由其处理器所访问,绝大都数都不支持远程存储器的访问,NORMA:,2004年4月59/149非远程存储访问(NORMA)非远程,2004,年,4,月,60,/149,结构模型,----,访存模型,UMA:,NUMA:,NORMA:,2004年4月60/149结构模型 ---- 访存模型UMA,2004,年,4,月,61,/149,多处理机 ＆ 多计算机,UMA:,NUMA:,NORMA:,,多处理机,（,共享存储,）,,多计算机,（,分布式存储,）,2004年4月61/149多处理机 ＆ 多计算机UMA:NU,2004,年,4,月,62,/149,几种体系结构特征比较,2004年4月62/149几种体系结构特征比较,2004,年,4,月,63,/149,曙光系列,曙光一号,SMP (1993),曙光,1000 MPP (1995),曙光,2000I Cluster (1998),曙光,2000II Cluster (1999),曙光,3000 Cluster (2000),曙光,4000l Cluster (2002),曙光,4000A Cluster (2004),2004年4月63/149曙光系列曙光一号 SMP (199,2004,年,4,月,64,/149,动物食物链,2004年4月64/149动物食物链,2004,年,4,月,65,/149,1984,年的计算机食物链,Mainframe,Vector Supercomputer,Mini Computer,Workstation,PC,2004年4月65/1491984年的计算机食物链Mainf,2004,年,4,月,66,/149,1994,年的计算机食物链,Mainframe,Vector Supercomputer,MPP,Workstation,PC,Mini Computer,(hitting wall soon),(future is bleak),2004年4月66/1491994年的计算机食物链Mainf,2004,年,4,月,67,/149,现在和未来的计算机食物链,2004年4月67/149现在和未来的计算机食物链,2004,年,4,月,68,/149,讲座主要内容提示,并行计算简介,编译环境,数学库,并行计算机体系结构,并行软件环境,并行计算机性能评测,MPI,,2004年4月68/149讲座主要内容提示并行计算简介,2004,年,4,月,69,/149,并行计算软件环境及现状,操作系统：,UNIX,、,LINUX,、,Windows NT,在,SMP,DSM,并行机上编译系统通常具有一定的对用户程序,(C/Fortran),进程自动并行化的能力,,,但经常需要人工干预,(,通过编译制导,,,命令行选项等,),以达到理想的并行效率,.,且并行主要针对循环进行,(,属于细粒度并行,);,在分布式内存并行机上尚无通过高效的自动并行工具,,,主要依靠人工编写并行程序,;,并行算法的设计及并行程序的编制已成为目前特约大规模并行计算机应用的主要障碍,.,,并行编程现状,,:,并行软件开发远远落后于并行系统体系结构的发展。
缺少合适的并行软件是阻碍主流用户社会接纳并行计算的原因,:,与串行软件相比，并行软件数量少，功能原始2004年4月69/149并行计算软件环境及现状操作系统：U,2004,年,4,月,70,/149,??,编程环境,落后的并行编译器、调试器,vs.,通用先进的串行编程环境,.,自动并行编译器远远满足不了程序并行化的要求,.,,3,算法,并行模型的多样化,(,并行计算机系统结构的多样性,) vs.,串行编程中的唯一模型,:,冯,.,诺依曼模型,问题的并行求解的困难在于问题的多样性和求解过程中所需的创造性劳动，使得这一过程难以进行自动化,对串行机而言,,,解法,=,唯一串行算法,+,计算程序,(,通用,),对并行机而言,,,解法,=,某种并行算法,+,有针对性的计算程序,(,很难通用,),,J,人,稀少而初级的并行编程人员,vs.,成熟而经验丰富的串行程序员,2004年4月70/149??编程环境,2004,年,4,月,71,/149,一些途径,充分,利用顺序程序开发的经验、方法和工具,，特别是顺序领域中的问题求解、算法设计方法，这是简化并行程序开发的重要手段并行程序开发的困难主要在于,问题的并行求解,，而不是并行程序设计语言。
从事并行程序设计实践的人往往把精力耗费在为变量分配内存、为循环体寻求并行上，却忽略对问题本身的分析其实能否并行的决定因素是应用问题本身在并行算法的设计阶段,最大限度地开发出问题本身固有的并行性,才是提高计算效率的根本手段只有,粗粒度的并行,，才能具有高的计算通信比，而粗粒度的并行只能在算法设计阶段开发出来,2004年4月71/149一些途径充分利用顺序程序开发的经验,2004,年,4,月,72,/149,并行软件程序员的工作,,,,,,,,指令层，非常细的粒度,数据层，细粒度,控制层，中粒度,任务层，大粒度,,前两层大都由硬件和编译器负责处理，程序员通常处理后两层的并行,,,2004年4月72/149并行软件程序员的工作 指令层，非常,2004,年,4,月,73,/149,并行程序设计方法,隐式并行程序设计：,常用传统的语言编程成顺序源编码，把“并行”交给编译器实现自动并行,程序的自动并行化是一个理想目标，存在难以克服的困难,语言容易，编译器难,,显式并行程序设计：,在用户程序中出现“并行”的调度语句,显式的并行程序开发则是解决并行程序开发困难的切实可行的,语言难，编译器容易,2004年4月73/149并行程序设计方法隐式并行程序设计：,2004,年,4,月,74,/149,并行程序设计模型,隐式并行（,Implicit Parallel,）,数据并行（,Data Parallel,）,共享变量（,Shared Variable,）,消息传递（,Message Passing,）,2004年4月74/149并行程序设计模型隐式并行（Impl,2004,年,4,月,75,/149,隐式并行,(Implicit Parallel),概况：,程序员用熟悉的,串行语言,编程,(,未作明确的制定并行性,),编译器,和,运行支持系统,自动转化为并行代码,特点：,语义简单,可移植性好,单线程，易于调试和验证正确性,细粒度并行,效率很低,2004年4月75/149隐式并行(Implicit Par,2004,年,4,月,76,/149,数据并行（,Data Parallel,）,概况：,SIMD,的自然模型,局部计算和数据选路操作,特点：,单线程,并行操作于聚合数据结构（数组）,松散同步,单一地址空间,隐式交互作用,显式数据分布,优点,:,编程相对简单,,,串并行程序一致,.,缺点,:,程序的性能在很大程度上依赖于所用的编译系统及用户对编译系统的了解,.,并行粒度局限于,数据级并行,,,粒度较小,.,2004年4月76/149数据并行（Data Paralle,2004,年,4,月,77,/149,共享变量,(Shared Variable),概况：,PVP, SMP, DSM,的自然模型,特点：,多线程：,SPMD, MPMD,异步,单一地址空间,显式同步,隐式数据分布,隐式通信,典型代表：,OpenMP,2004年4月77/149共享变量(Shared Varia,2004,年,4,月,78,/149,消息传递,(Message Passing),概况：,MPP,、,COW,的自然模型,特点：,多线程,异步,多地址空间,显式同步,显式数据映射和负载分配,显式通信,典型代表,MPI,、,PVM,2004年4月78/149消息传递(Message Pass,2004,年,4,月,79,/149,并行编程标准,数据并行语言标准,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月79/149并行编程标准数据并行语言标准共享变,2004,年,4,月,80,/149,并行编程标准归类,所有并行编程标准可分为以下三类,:,数据并行,HPF, Fortran90,用于,SMP, DSM,共享编程,OpenMP,用于,SMP, DSM,消息传递,MPI, PVM,用于所有并行计算机,三者可混合使用,:,如对以,SMP,为节点的,Cluster,来说,,,可以在节点间进行消息传递,,,在节点内进行共享变量编程,.,2004年4月80/149并行编程标准归类所有并行编程标准可,2004,年,4,月,81,/149,基本并行化方法,相并行（,Phase Parallel,）,流水线并行（,Pipeline Parallel,）,主从并行（,Master-Slave Parallel,）,分治并行（,Divide and Conquer Parallel,）,工作池并行（,Work Pool Parallel,）,2004年4月81/149基本并行化方法相并行（Phase,2004,年,4,月,82,/149,讲座主要内容提示,并行计算简介,编译环境,数学库,并行计算机体系结构,并行软件环境,并行计算机性能评测,MPI,、,PVM,、,OpenMP,,2004年4月82/149讲座主要内容提示并行计算简介,2004,年,4,月,83,/149,并行计算性能评测,机器的理论峰值速度,用户能得到的实际速度,,Benchmark LINPACK,www.top500.org,加速比、效率,S,＝并行算法,(,程序,),性能,/,串行算法,(,程序,),性能,可扩展性：体系结构、软件、算法,随着计算负载的增加和机器规模的扩大，计算系统的性能是否随着处理器的数目的增加而按比例的增加,性能依赖因素：,算法设计：并行性、计算量,程序设计：体系结构特点的利用,(,通信、存储、,Cache),、负载平衡、并行粒度,2004年4月83/149并行计算性能评测机器的理论峰值速度,2004,年,4,月,84,/149,机器的理论峰值速度,理论峰值速度,=,CPU,主频,,×,每个时钟周期执行浮点运算的次数,×,CPU,数目,每个时钟周期执行浮点运算的次数,是由处理器中浮点运算单元的个数及每个浮点运算单元在每个时钟周期能处理几条浮点运算来决定的,2004年4月84/149机器的理论峰值速度理论峰值速度=C,2004,年,4,月,85,/149,基准测试程序,(Benchmark),基本测试程序,SPEC,：原主要是测试,CPU,性能，现在强调开发能反映真实应用的基准测试程序，并以推广至客户,/,服务器计算、商业应用、,I/O,子系统等等,,科学与工程计算性能,Linpack,：高斯消元法求解线性代数方程组,NPB(NAS Parallel Benchmark),：美国,NAS,项目开发，包含,8,个空气动力学计算类应用，测试范围从整数排序到复杂的数值计算,LAPACK,、,ScalLAPACK,：稠密、带状矩阵上的各类操作,Perfect,、,SPLASH,、,ParkBench,2004年4月85/149基准测试程序(Benchmark),2004,年,4,月,86,/149,www.top500.org,2004年4月86/149www.top500.org,2004,年,4,月,87,/149,Linpack,Linpack,是,国际上流行的用于测试高性能计算机系统浮点性能的,benchmark,,通过对高性能计算机采用,LU,分解求解线性代数方程组能力的测试，评价高性能计算机的浮点处理性能,2004年4月87/149LinpackLinpack是国际,2004,年,4,月,88,/149,Linpack,由,J. Dongarra,编写的,Linpack,采用主元高斯消去法求解双精度,(64bits),稠密线性代数方程组,结果按每秒浮点运算次数（,flops,）表示,包含三类测试（问题规模与优化选择各不相同）,100×100,测试,不允许对,Linpack,测试程序进行任何修改（包括注释行）。
所有的优化只能在编译器里完成,,1000×1000,测试,允许对算法和软件进行修改或替换,并尽量利用系统的硬件特点，以达到尽可能高的性能,但是所有的优化都必须保持和标准算法如高斯消去法相同的相对精度，而且必须使用,Linpack,的主程序进行调用,2004年4月88/149Linpack由J. Dongar,2004,年,4,月,89,/149,HPL,高性能,Linpack,：,HPL,(High Performance Linpack),针对大规模的并行计算机系统的测试，,2000,年,9,月发布,1.0,版,是,TOP500,超级计算机排名的主要依据,采用,MPI,实现，基于,BLAS,库或,VSIPL,库,用户可以选择矩阵的大小,(,问题规模,),、使用各种优化方法来执行测试程序，寻求最佳的测试结果,浮点峰值,＝,总计算量,,/,计算时间,总计算量＝,2/3 * N^3 – 2*N^2,计算时间：可通过系统时钟获得,2004年4月89/149HPL高性能Linpack：HPL,2004,年,4,月,90,/149,如何做,HPL,测试,所必须的软件包,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月90/149如何做HPL测试所必须的软件包,2004,年,4,月,91,/149,如何做,HPL,测试,HPL.out,文件或在。
