1、2018/10/9,并行计算基础知识,1,并行计算基础知识,冯圣中 中国科学院计算技术研究所国家智能计算机研究开发中心国家高性能计算中心（北京）,2018/10/9,并行计算基础知识,2/66,主要内容,并行计算并行计算系统基础并行计算基本概念几种典型的benchmark,2018/10/9,并行计算基础知识,3/66,并行计算基本概念,Parallel computing、high performance computing、 high-end computingThe simultaneous use of more than one computer to solve a problem
2、.多计算机-网络多进程/线程-通信并行计算环境加速比/可扩展性,2018/10/9,并行计算基础知识,4/66,并行计算系统基础,并行计算机分类主流并行计算机系统比较机群并行计算环境,2018/10/9,并行计算基础知识,5/66,并行计算机分类,根据指令流和数据流的不同，通常把计算机系统分为：单指令流单数据流（SISD）单指令流多数据流（SIMD）多指令流单数据流（MISD）多指令流多数据流（MIMD）并行计算机系统绝大部分为MIMD系统，包括并行向量机（PVP，Parallel Vector Processor）；对称多处理机（SMP,Symmetric Multiprocessor）；大
3、规模并行处理机（MPP，Massively Parallel Processor）；机群（Cluster）；分布式共享存储多处理机（DSM，Distributied Shared Memory）,2018/10/9,并行计算基础知识,6/66,Top500中的超级计算机,地球模拟器ASCI QASCI White,2018/10/9,并行计算基础知识,7/66,Earth Simulator,Earth simulator centerNecRmax:35.86Tflops8*8*640,2018/10/9,并行计算基础知识,8/66,Earth Simulator,2018/10/9,并行计
4、算基础知识,9/66,Earth Simulator,2018/10/9,并行计算基础知识,10/66,ASCI Q,1024 nodes8cpu/node10240Gflops7727Gflops,2018/10/9,并行计算基础知识,11/66,ASCI white,LLNL IBM SP power3 Rmax 7.22Tflops,2018/10/9,并行计算基础知识,12/66,SMP 对称多处理机,SMP系统一般使用商品化微处理器，具有片上或外置高速缓存经由高速总线（或交叉开关）连向共享存储器。每个处理器可等同地访问共享存储器、I/O设备和操作系统服务。单一操作系统映像，全系统只有
5、一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程到各个处理器，并保持负载平衡；低通信延迟，各个进程通过读/写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信延迟；共享总线带宽，所有处理器共享总线带宽，完成对内存模块和I/O模块的访问。,2018/10/9,并行计算基础知识,13/66,SMP 对称多处理机（续）,问题：欠可靠，总线、存储器、操作系统失效可能导致系统崩溃；可扩展性较差，由于所有处理器都共享总线带宽，而总线带宽每3年才增加2倍，赶不上处理器速度和存储容量的增长步伐，因此SMP的处理器个数一般少于64个，且只能提供每秒数百亿次的浮
6、点运算。SMP的典型代表有：SGI POWER Challenge XL系列、DEC Alphaserver 84005/440、HP9000/T600和IBM RS6000/R40。,2018/10/9,并行计算基础知识,14/66,SMP 对称多处理机（续）,2018/10/9,并行计算基础知识,15/66,DSM 分布式共享存储多处理机,DSM的典型代表为SGI的Origin2000和Origin3000系列并行机处理器对物理分布的共享存储器的访问是不对称的，因此远端访问延迟一般是本地访问延迟的3倍以上单一内存地址空间，所有这些内存模块都由硬件进行了统一编址，并通过互连网络形成了并行机的
7、共享存储器,2018/10/9,并行计算基础知识,16/66,DSM （续）,基于Cache的数据一致性DSM较好地改善了SMP的可扩展性能。一般地，DSM可以扩展到上百个节点，能提供每秒数千亿次的浮点运算功能单一的系统映像，在DSM中，用户只看到一个操作系统，它可以根据各节点的负载情况，动态地分配进程,2018/10/9,并行计算基础知识,17/66,DSM （续）,2018/10/9,并行计算基础知识,18/66,机群（Cluster）,我国的曙光1000A、曙光2000、曙光3000以及前不久推出的曙光4000L等都是机群架构的并行计算机Cluster的每个系统都是一个完整的工作站，一个
8、节点可以是一台PC或SMP各个节点一般由商品化的网络互连，节点上的网络接口是松散耦合到I/O总线上的每个节点一般有本地磁盘，一个完整的操作系统驻留在每个节点上,2018/10/9,并行计算基础知识,19/66,机群（Cluster）,2018/10/9,并行计算基础知识,20/66,可扩展高性能机群服务器技术,2018/10/9,并行计算基础知识,21/66,单一系统映像,单一系统映像（Single System Image，SSI）并不是指系统中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统。其基本特征是单一系统、单一控制、对称性、位置透明。采用SSI的主要目的，是使机群的使
9、用、控制和维护似乎和一台工作站一样。单一系统映像包括单一入口点、单一文件层次结构、单一I/O空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间。,2018/10/9,并行计算基础知识,22/66,三种体系结构比较（一）,2018/10/9,并行计算基础知识,23/66,三种体系结构比较（二）,2018/10/9,并行计算基础知识,24/66,Beowulf与机群,Beowulf：自己攒的“高性能计算机”买PC、网络设备、装linux、MPI、ATLAS降低了高性能计算门槛，促进了高性能计算普及迫切的问题：单一系统映像单一管理点单一文件系统单一作业管理负载自动均衡,2018/10/9,
10、并行计算基础知识,25/66,Beowulf：第一台Hrothgar,2018/10/9,并行计算基础知识,26/66,十年来CPU演变（1）,2018/10/9,并行计算基础知识,27/66,十年来CPU演变（2）,2018/10/9,并行计算基础知识,28/66,十年来CPU演变（3）,2018/10/9,并行计算基础知识,29/66,十年来体系结构的演变,2018/10/9,并行计算基础知识,30/66,机群：厂家面临的问题,怎样避免同质化？一样的CPU、一样的网络、一样的操作系统、几乎一样的机群系统不一样的用户需求，一样的系统能最优满足？SUMA标准Scalability可扩展性Usa
11、bility易用性Manageability可管理性Availability高可用性,2018/10/9,并行计算基础知识,31/66,怎样避免同质化,应用分类CPU密集、MEM密集、DISK密集、NIC密集针对不同应用需求，提出不同的方案可重构计算,2018/10/9,并行计算基础知识,32/66,Intel与AMD,Opteron与32位兼容的64位处理器HyperTransportXeon主频持续上升Itanium ？,2018/10/9,并行计算基础知识,33/66,华大基因（北京）,Draft Sequence of Rice Genome,2018/10/9,并行计算基础知识,34
12、/66,曙光百万亿数据处理超级服务器,2018/10/9,并行计算基础知识,35/66,4000L主要指标,40个机柜组成644个CPU每秒3万亿次浮点计算峰值速度644GB内存百万亿字节（100TB）存储最大可“在线”扩展到80个机柜1300个CPU每秒6.75万亿次峰值速度4000G内存600T存储1200A最大电流，160千瓦最大功耗的海量处理系统,2018/10/9,并行计算基础知识,36/66,初步的面向网格的特点,Grid Terminal智能控制台能够实现庞大系统的安全管理GridView网格监控中心软件则提供了逻辑视角、视角的可伸缩性、历史记录分析三项特色，被称为系统的“千里眼
13、”。,2018/10/9,并行计算基础知识,37/66,中国近期的一些新闻,曙光“红色网格”孕育10万亿次超级计算机中科院网络信息中心委托联想研制高性能计算机系统高性能计算的“超级”对抗浪潮高性能计算 生命科学领域显奇功高性能计算：处于什么样的阶段？,2018/10/9,并行计算基础知识,38/66,HPC：处于什么样的阶段,机群高性能计算系统已经成熟，步入量产阶段国内曙光、联想、浪潮，还有大量小公司高性能计算应用的快速扩展阶段从去年开始，机群销量猛增，应用在科学计算和信息服务等所有领域高性能计算教育相对滞后、人才相对稀缺阶段北大、清华、科大等有限几所高校设置相应专业课程,2018/10/9,
14、并行计算基础知识,39/66,并行计算基本概念,并行算法的定义与分类并行算法的复杂性数据相关性与可并行化并行计算模型,2018/10/9,并行计算基础知识,40/66,并行算法的定义与分类,算法是解题的精确描述，是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解并行算法就是对并行计算过程的精确描述并行算法可以从不同的角度分类为数值计算并行算法和非数值计算并行算法同步并行算法和异步并行算法共享存储并行算法和分布存储并行算法,2018/10/9,并行计算基础知识,41/66,数值算法与非数值算法,数值计算
15、是指基于代数关系运算的计算问题，如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法（Numerical Algorithm）。科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。非数值计算是指基于比较关系运算诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算法（Non-numerical Algorithm）。非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题、海量数据挖掘等，近年来广泛关注的生物信息学主要也是非数值计算,2018/10/9,并行计算基础知识,42/66,并行算法的复杂性,上界 f(n)=cg(n)，
16、则称g(n)是f(n)的一个下界，记做f(n)=(g(n)紧致界 c1g(n)=f(n)=c2g(n)，则称g(n)是f(n)的一个紧致界，记做f(n)=(g(n)。,2018/10/9,并行计算基础知识,43/66,描述并行算法,如果要求输入输出N个数据，则认为该算法的I/O时间界为O(N)如果问题规模为n，涉及的计算量一般为t(n)，则该算法的计算CPU时间界为O(t(n)对要求通信和同步的次数为L、通信量为M个数据，则该算法的并行开销为O(L+M),2018/10/9,并行计算基础知识,44/66,问题规模,问题规模有可分为输入输出规模、计算规模、内存需求、通信（同步）规模，分别表示问题
17、求解所需要的I/O量、计算量、内存大小和通信量（包括通信次数与通信数据量）。根据消耗资源程度，又相应分为CPU密集应用、memory密集应用、disk密集应用和网络密集应用。不同类型的问题，性能瓶颈也往往不同。并行算法就是要又针对性的消除相应的瓶颈，从而达到缩短计算时间的目的。,2018/10/9,并行计算基础知识,45/66,相关性与可并行化,伯恩斯坦准则I1O2，即P1的输入变量集与P2的输出变量集不相交；I2O1，即P2的输入变量集与P1的输出变量集不相交；O1O2，即P1和P2的输出变量集不相交可并行处理,2018/10/9,并行计算基础知识,46/66,数据相关,P1： AB+CP2
18、： DAB其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。显然，P1和P2不能并行执行。,2018/10/9,并行计算基础知识,47/66,数据反相关,P1： ABCP2： CE+DP1通过变量C数据相关于P2。为保证语义正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。也不可并行化,2018/10/9,并行计算基础知识,48/66,数据输出相关,P1： AB+CP2： ADE为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。除了上述3种相关外，还存在一种特殊情
19、况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。,2018/10/9,并行计算基础知识,49/66,并行计算模型,计算模型是对计算机的抽象计算模型为设计、分析和评价算法提供基础冯.偌依曼机就是一个理想的串行计算模型但现在还没有一个通用的并行计算模型PRAM模型LogP模型,2018/10/9,并行计算基础知识,50/66,PRAM模型,PRAM（Parallel Random Access Machine）模型，即并行随机存取模型，是一种抽象的并行计算模型。假设存在着
20、一个容量无限大的共享存储器；每台处理器有简单的算术运算和逻辑判断功能；在任何时刻各处理器均可以通过共享存储单元交换数据。,2018/10/9,并行计算基础知识,51/66,PRAM模型,可分为SIMD-PRAM和MIMD-PRAM。SIMD-PRAM模型又可以细分为PRAM-EREW模型；PRAM-CREW模型；PRAM-CRCW模型。CPRAM-EREW模型；PPRAM-EREW模型APRAM-EREW模型。,2018/10/9,并行计算基础知识,52/66,PRAM模型,SIMD-PRAM计算模型 MIMD-PRAM计算模型,2018/10/9,并行计算基础知识,53/66,LogP 模型
21、,充分说明了互连网络的性能特点，而未涉及网络的结构。模型主要由4个参数描述。L（Latency） 源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限。o（overhead） 处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理机不能执行其他操作。g（gap） 一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即为处理机的通信带宽。P（Processor） 处理机的个数。,2018/10/9,并行计算基础知识,54/66,LogP 模型,揭示了分布存储并行计算机的性能瓶颈，用L、o、g三个参数刻画了通信网络的特
22、性，但屏蔽了网络拓扑、选路算法和通信协议等具体细节参数g反映了通信带宽在任何时刻，最多只能有L/g条消息从一个处理器传到另一个处理器，这就是网络容限，当一台处理机发送的消息达到这个容限时，在发送的消息就会被阻塞；在网络容限范围内，点到点传送一条消息的时间为（2*o+L）。设想LogP模型中的L、o、g都为0，那么LogP模型就等同于PRAM模型,2018/10/9,并行计算基础知识,55/66,各种计算模型比较,2018/10/9,并行计算基础知识,56/66,性能评价与benchmark,加速比定律与并行效率常见benchmark简介,2018/10/9,并行计算基础知识,57/66,加速比
23、定律,在给定的并行计算系统上给定的应用，并行算法（并行程序）的执行速度相对于串行算法（串行程序）加快的倍数，就是该并行算法（并行程序）的加速比。Amdahl定律适用于固定计算规模的加速比性能描述，Gustafson定律适用于可扩展问题,2018/10/9,并行计算基础知识,58/66,Amdahl定律,S=(WS+WP)/(WS+WP/p) =1/(1/p+f(1-1/p)显然，当p时，S=1/f即对于固定规模的问题，并行系统所能达到的加速上限为1/f。假定并行计算系统的处理器数为p，W为问题规模，WS为应用程序中的串行分量，WP为可并行化部分；f为串行分量的比例（f=Ws/W），1-f为并行
24、分量的比例；Ts=T1为串行执行时间，Tp为并行计算时间；S为加速比，E为并行效率,2018/10/9,并行计算基础知识,59/66,Gustafson定律,S=（WS+pwp）/（WS+WP） =p-f（p-1）=f+p（1-f）加速比与处理器数成斜率为（1-f）的线性关系这样串行比例f就不再是程序扩展性的瓶颈，当然，f越低，斜率会越大，加速性能越好。,2018/10/9,并行计算基础知识,60/66,Linpack,由J. Dongarra编写的Linpack采用主元高斯消去法求解双精度(64bits)稠密线性代数方程组，结果按每秒浮点运算次数（flops）表示。包含三类测试，问题规模与优
25、化选择各不相同： 100100测试 在该测试中，不允许对Linpack测试程序进行任何修改（包括注释行）。 10001000测试 在该测试中，允许对算法和软件进行修改或替换，并尽量利用系统的硬件特点，以达到尽可能高的性能。但是所有的优化都必须保持和标准算法如高斯消去法相同的相对精度，而且必须使用Linpack的主程序进行调用。,2018/10/9,并行计算基础知识,61/66,linpack,HPL测试 针对大规模并行计算系统的测试，其名称为High Performance Linpack (HPL)，1.0版于2000年9月发布，是第一个标准的公开版本并行Linpack测试软件包，一般用于T
26、OP500超级计算机上的并行超级计算机。HPL与其前辈不同，使用者可以改变问题规模。要获得Linpack实测峰值，需要使用与内存匹配的最大的问题规模（一般接近内存总容量的80%）。,2018/10/9,并行计算基础知识,62/66,HPL测试,Rpeak:系统的最大的理论峰值性能，按GFLOPS表示。Nmax: 给出达到最高GFLOPS值时的问题规模（矩阵规模）。Rmax: 在Nmax问题规模下，达到的最大峰值（GFLOPS）。 NB: 矩阵分块大小，与高速缓存大小相关。一般在32到256之间。,2018/10/9,并行计算基础知识,63/66,2018/10/9,并行计算基础知识,64/66
27、,NAS Parallel Benchmark,NPB套件由八个程序组成每个基准测试有五类：A、B、C、D、W (工作站)。A是最小的，D是最大的。NPB套件以每秒百万次运算为单位输出结果。整数排序(IS)快速Fourier变换（FT）多栅格基准测试（MG） 共轭梯度(CG) 基准测试 稀疏矩阵分解（LU） 五对角方程（SP）和块状三角(BT)求解 密集并行(EP),2018/10/9,并行计算基础知识,65/66,参考文献,黄铠、徐志伟，可扩展并行计算，机械工业出版社，2000年陈国良，并行计算，高等教育出版社，1999年Rajkumar Buyya，高性能机群计算，电子工业出版社，2001年李晓梅、莫则尧等，可扩展并行算法的设计与分析，国防工业出版社，2000年,2018/10/9,并行计算基础知识,66/66,谢 谢！,
