并行计算基本概念优秀PPT.ppt

《并行计算基本概念优秀PPT.ppt》由会员分享，可在线阅读，更多相关《并行计算基本概念优秀PPT.ppt（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2022/11/1并行计算基础学问1/66主要内容w并行计算w并行计算系统基础w并行计算基本概念w几种典型的benchmark2022/11/1并行计算基础学问2/66并行计算基本概念wParallel computing、high performance computing、high-end computingnThe simultaneous use of more than one computer to solve a problem.w多计算机-网络w多进程/线程-通信w并行计算环境w加速比/可扩展性2022/11/1并行计算基础学问3/66并行计算系统基础w并行计算机分类w主流并行

2、计算机系统比较w机群并行计算环境2022/11/1并行计算基础学问4/66并行计算机分类w依据指令流和数据流的不同，通常把计算机系统分为：w单指令流单数据流（SISD）w单指令流多数据流（SIMD）w多指令流单数据流（MISD）w多指令流多数据流（MIMD）w并行计算机系统绝大部分为MIMD系统，包括w并行向量机（PVP，Parallel Vector Processor）；w对称多处理机（SMP,Symmetric Multiprocessor）；w大规模并行处理机（MPP，Massively Parallel Processor）；w机群（Cluster）；w分布式共享存储多处理机（DSM

3、，Distributied Shared Memory）2022/11/1并行计算基础学问5/66Top500中的超级计算机w地球模拟器wASCI QwASCI White2022/11/1并行计算基础学问6/66Earth SimulatorEarth simulator centerNecRmax:35.86Tflops8*8*6402022/11/1并行计算基础学问7/66Earth Simulator2022/11/1并行计算基础学问8/66Earth Simulator2022/11/1并行计算基础学问9/66ASCI Q1024 nodes8cpu/node10240Gflops7

4、727Gflops2022/11/1并行计算基础学问10/66ASCI whiteLLNL IBM SP power3 Rmax 7.22Tflops2022/11/1并行计算基础学问11/66SMP 对称多处理机wSMP系统一般运用商品化微处理器，具有片上或外置高速缓存w经由高速总线（或交叉开关）连向共享存储器。每个处理器可等同地访问共享存储器、I/O设备和操作系统服务。w单一操作系统映像，全系统只有一个操作系统驻留在共享存储器中，它依据各个处理器的负载状况，动态地安排各个进程到各个处理器，并保持负载平衡；w低通信延迟，各个进程通过读/写操作系统供应的共享数据缓存区来完成处理器间的通信，其延

5、迟通常小于网络通信延迟；w共享总线带宽，全部处理器共享总线带宽，完成对内存模块和I/O模块的访问。2022/11/1并行计算基础学问12/66SMP 对称多处理机（续）w问题：欠牢靠，总线、存储器、操作系统失效可能导致系统崩溃；w可扩展性较差，由于全部处理器都共享总线带宽，而总线带宽每3年才增加2倍，赶不上处理器速度和存储容量的增长步伐，因此SMP的处理器个数一般少于64个，且只能供应每秒数百亿次的浮点运算。wSMP的 典 型 代 表 有：SGI POWER Challenge XL系 列、DEC Alphaserver 84005/440、HP9000/T600和IBM RS6000/R40

6、。2022/11/1并行计算基础学问13/66SMP 对称多处理机（续）P/CP/CP/C总 线 或 交 叉 开 关SMSMSM2022/11/1并行计算基础学问14/66DSM 分布式共享存储多处理机wDSM的 典 型 代 表 为 SGI的 Origin2000和Origin3000系列并行机w处理器对物理分布的共享存储器的访问是不对称的，因此远端访问延迟一般是本地访问延迟的3倍以上w单一内存地址空间，全部这些内存模块都由硬件进行了统一编址，并通过互连网络形成了并行机的共享存储器2022/11/1并行计算基础学问15/66DSM（续）w基于Cache的数据一样性wDSM较好地改善了SMP的可

7、扩展性能。一般地，DSM可以扩展到上百个节点，能供应每秒数千亿次的浮点运算功能w单一的系统映像，在DSM中，用户只看到一个操作系统，它可以依据各节点的负载状况，动态地安排进程2022/11/1并行计算基础学问16/66DSM（续）定 制 网 络P/CLMDIRMBNICP/CLMDIRMBNIC2022/11/1并行计算基础学问17/66机群（Cluster）w我国的曙光1000A、曙光2000、曙光3000以及前不久推出的曙光4000L等都是机群架构的并行计算机wCluster的每个系统都是一个完整的工作站，一个节点可以是一台PC或SMPw各个节点一般由商品化的网络互连，节点上的网络接口是松

8、散耦合到I/O总线上的w每个节点一般有本地磁盘，一个完整的操作系统驻留在每个节点上2022/11/1并行计算基础学问18/66机群（Cluster）定 制 网 络P/CMBMBLDNICIOBP/CMBMBLDNICIOB2022/11/1并行计算基础学问19/66可扩展高性能机群服务器技术ExpandabilityCluster CoreCluster CoreCluster CoreNode IndependentNode Failure Isolated&Taken OverSingle Point LoginSingle System File ImageSingle Point of

9、 ManagementNode ExpandableUser ExpandableSystem ExpandableApplication ExpandableSingle System imageShare ResourceShare System ManagementEasy to manageHigh Availability2022/11/1并行计算基础学问20/66单一系统映像w单一系统映像（Single System Image，SSI）并不是指系统中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统。w其基本特征是单一系统、单一限制、对称性、位置透亮。接受SSI的主要

10、目的，是使机群的运用、限制和维护似乎和一台工作站一样。w单一系统映像包括单一入口点、单一文件层次结构、单一I/O空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间。2022/11/1并行计算基础学问21/66三种体系结构比较（一）分 布式 计算 系统机群计算机DSMSMP节点系统复杂度单一系统映像2022/11/1并行计算基础学问22/66三种体系结构比较（二）可扩展性系统可靠性MPPSMPPC机群专用容错系统2022/11/1并行计算基础学问23/66Beowulf与机群wBeowulf：自己攒的“高性能计算机”n买PC、网络设备、装linux、MPI、ATLASw降低了高性能计算

11、门槛，促进了高性能计算普及w迫切的问题：单一系统映像n单一管理点n单一文件系统n单一作业管理n负载自动均衡2022/11/1并行计算基础学问24/66Beowulf：第一台：第一台Hrothgar2022/11/1并行计算基础学问25/66十年来CPU演化（1）2022/11/1并行计算基础学问26/66十年来CPU演化（2）2022/11/1并行计算基础学问27/66十年来CPU演化（3）2022/11/1并行计算基础学问28/66十年来体系结构的演化2022/11/1并行计算基础学问29/66机群：厂家面临的问题w怎样避开同质化？w一样的CPU、一样的网络、一样的操作系统、几乎一样的机群系

12、统w不一样的用户需求，一样的系统能最优满足？wSUMA标准wScalability可扩展性wUsability 易用性wManageability可管理性wAvailability高可用性2022/11/1并行计算基础学问30/66怎样避开同质化w应用分类nCPU密集、MEM密集、DISK密集、NIC密集w针对不同应用需求，提出不同的方案w可重构计算2022/11/1并行计算基础学问31/66Intel与AMDwOpteronn与32位兼容的64位处理器nHyperTransportwXeonn主频持续上升wItanium n？2022/11/1并行计算基础学问32/66华大基因（北京）wDr

13、aft Sequence of Rice Genome2022/11/1并行计算基础学问33/66曙光百万亿数据处理超级服务器2022/11/1并行计算基础学问34/664000L主要指标w40个机柜组成w644个CPUw每秒3万亿次浮点计算峰值速度w644GB内存w百万亿字节（100TB）存储n最大可“在线”扩展到80个机柜n1300个CPUn每秒6.75万亿次峰值速度n4000G内存n600T存储n1200A最大电流，160千瓦最大功耗的海量处理系统2022/11/1并行计算基础学问35/66初步的面对网格的特点wGrid Terminal智能限制台能够实现浩大系统的平安管理wGridVi

14、ew网格监控中心软件则供应了逻辑视角、视角的可伸缩性、历史记录分析三项特色，被称为系统的“千里眼”。2022/11/1并行计算基础学问36/66中国近期的一些新闻w曙光“红色网格”孕育10万亿次超级计算机w中科院网络信息中心托付联想研制高性能计算机系统w高性能计算的“超级”对抗w浪潮高性能计算 生命科学领域显奇功w高性能计算：处于什么样的阶段？2022/11/1并行计算基础学问37/66HPC：处于什么样的阶段w机群高性能计算系统已经成熟，步入量产阶段w国内曙光、联想、浪潮，还有大量小公司w高性能计算应用的快速扩展阶段w从去年起先，机群销量猛增，应用在科学计算和信息服务等全部领域w高性能计算教

15、化相对滞后、人才相对稀缺阶段w北大、清华、科大等有限几所高校设置相应专业课程2022/11/1并行计算基础学问38/66并行计算基本概念w并行算法的定义与分类w并行算法的困难性w数据相关性与可并行化w并行计算模型2022/11/1并行计算基础学问39/66并行算法的定义与分类w算法是解题的精确描述，n是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解w并行算法就是对并行计算过程的精确描述w并行算法可以从不同的角度分类为n数值计算并行算法和非数值计算并行算法n同步并行算法和异步并行算法n共享存储并行算法

16、和分布存储并行算法2022/11/1并行计算基础学问40/66数值算法与非数值算法w数值计算是指基于代数关系运算的计算问题，w如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法（Numerical Algorithm）。w科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。w非数值计算是指基于比较关系运算w诸如排序、选择、搜寻、匹配等符号处理，相应的算法也称为非数值算法（Non-numerical Algorithm）。w非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题、海量数据挖掘等，w近年来广泛关注的生物信息学主要也是非数

17、值计算 2022/11/1并行计算基础学问41/66并行算法的困难性w上界 nf(n)=cg(n)，则 称g(n)是f(n)的 一 个 下 界，记 做f(n)=(g(n)w紧致界 nc1g(n)=f(n)=c2g(n)，则称g(n)是f(n)的一个紧致界，记做f(n)=(g(n)。2022/11/1并行计算基础学问42/66描述并行算法w假如要求输入输出N个数据，则认为该算法的I/O时间界为O(N)w假如问题规模为n，涉及的计算量一般为t(n)，则该算法的计算CPU时间界为O(t(n)w对要求通信和同步的次数为L、通信量为M个数据，则该算法的并行开销为O(L+M)2022/11/1并行计算基础

18、学问43/66问题规模w问题规模有可分为w输入输出规模、计算规模、内存需求、通信（同步）规模，w分别表示问题求解所须要的I/O量、计算量、内存大小和通信量（包括通信次数与通信数据量）。w依据消耗资源程度，又相应分为wCPU密集应用、memory密集应用、disk密集应用和网络密集应用。w不同类型的问题，性能瓶颈也往往不同。并行算法就是要又针对性的消退相应的瓶颈，从而达到缩短计算时间的目的。2022/11/1并行计算基础学问44/66相关性与可并行化伯恩斯坦准则lI1O2，即P1的输入变量集与P2的输出变量集不相交；lI2O1，即P2的输入变量集与P1的输出变量集不相交；lO1O2，即P1和P2

19、的输出变量集不相交w可并行处理2022/11/1并行计算基础学问45/66数据相关wP1：AB+CwP2：DABw其中，变量A是导致P1和P2发生数据相关的缘由。为了保证程序执行的语义正确性，变量A必需是先在P1中写入后方可从P2中读出，即必需先写后读。w明显，P1和P2不能并行执行。2022/11/1并行计算基础学问46/66数据反相关P1：ABCP2：CE+DP1通过变量C数据相关于P2。为保证语义正确性，必需等P1将变量C读出后，P2方可向变量C进行写入操作，即必需先读后写。也不行并行化2022/11/1并行计算基础学问47/66数据输出相关wP1：AB+CwP2：ADEw为保证语义正确

20、性，必需保证P1先写入A，然后允许P2再写入A。w除了上述3种相关外，还存在一种特殊状况，即两个程序段的输入变量互为输出变量。此时，两者必需并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。2022/11/1并行计算基础学问48/66并行计算模型w计算模型是对计算机的抽象w计算模型为设计、分析和评价算法供应基础w冯.偌依曼机就是一个志向的串行计算模型w但现在还没有一个通用的并行计算模型wPRAM模型wLogP模型2022/11/1并行计算基础学问49/66PRAM模型w PRAM（Parallel Random Acces

21、s Machine）模型，即并行随机存取模型，是一种抽象的并行计算模型。w假设存在着一个容量无限大的共享存储器；w每台处理器有简洁的算术运算和逻辑推断功能；w在任何时刻各处理器均可以通过共享存储单元交换数据。2022/11/1并行计算基础学问50/66PRAM模型w可分为SIMD-PRAM和MIMD-PRAM。wSIMD-PRAM模型又可以细分为nPRAM-EREW模型；nPRAM-CREW模型；nPRAM-CRCW模型。lCPRAM-EREW模型；lPPRAM-EREW模型lAPRAM-EREW模型。2022/11/1并行计算基础学问51/66PRAM模型SIMD-PRAM计算模型 MIMD

22、-PRAM计算模型控制单元P1LMP2LMPnLM互连网络全局共享存储器控制器1P1LMP2LMPnLM互连网络全局共享存储器控制器2控制器n2022/11/1并行计算基础学问52/66LogP LogP 模型模型 w充分说明白互连网络的性能特点，而未涉及网络的结构。模型主要由4个参数描述。wL（Latency）源处理机与目的处理机进行消息（一个或几个字）通信所须要的等待或延迟时间的上限。wo（overhead）处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理机不能执行其他操作。wg（gap）一台处理机连续两次发送或连续两次接受消息时的最小时间

23、间隔，其倒数即为处理机的通信带宽。wP（Processor）处理机的个数。2022/11/1并行计算基础学问53/66LogP 模型w揭示了分布存储并行计算机的性能瓶颈，用L、o、g三个参数刻画了通信网络的特性，w但屏蔽了网络拓扑、选路算法和通信协议等具体细微环节w参数g反映了通信带宽w在任何时刻，最多只能有L/g条消息从一个处理器传到另一个处理器，这就是网络容限，当一台处理机发送的消息达到这个容限时，在发送的消息就会被堵塞；w在网络容限范围内，点到点传送一条消息的时间为（2*o+L）。w设想LogP模型中的L、o、g都为0，那么LogP模型就等同于PRAM模型 2022/11/1并行计算基础

24、学问54/66各种计算模型比较 模型属性PRAMAPRAMBSPLogPC3体系结构SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM计算模式同步异步异步异步异步同步方式自动同步路障同步路障同步隐式同步路障同步模型参数单位时间步d,读/写时间B,同步时间p,处理器数g,带宽因子l,同步间隔L,通信延迟o,额外开销g,带宽因子P,处理器数l,信包长度s,发送建立时间h,通信延迟计算粒度细粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式读/写共享变量读/写共享变量发送/接收消息发送/接收消息发送/接收消息地址空间全局地址空间单地址空间单/多地址空间单/多地址

25、空间多地址空间2022/11/1并行计算基础学问55/66性能评价与benchmarkw加速比定律与并行效率w常见benchmark简介2022/11/1并行计算基础学问56/66加速比定律w在给定的并行计算系统上给定的应用，并行算法（并行程序）的执行速度相对于串行算法（串行程序）加快的倍数，就是该并行算法（并行程序）的加速比。wAmdahl定律适用于固定计算规模的加速比性能描述，Gustafson定律适用于可扩展问题 2022/11/1并行计算基础学问57/66Amdahl定律S=(WS+WP)/(WS+WP/p)=1/(1/p+f(1-1/p)明显，当p时，S=1/f即对于固定规模的问题，

26、并行系统所能达到的加速上限为1/f。假定并行计算系统的处理器数为p，W为问题规模，WS为应用程序中的串行重量，WP为可并行化部分；f为串行重量的比例（f=Ws/W），1-f为并行重量的比例；Ts=T1为串行执行时间，Tp为并行计算时间；S为加速比，E为并行效率 2022/11/1并行计算基础学问58/66Gustafson定律S=（WS+pwp）/（WS+WP）=p-f（p-1）=f+p（1-f）w加速比与处理器数成斜率为（1-f）的线性关系w这样串行比例f就不再是程序扩展性的瓶颈，w当然，f越低，斜率会越大，加速性能越好。2022/11/1并行计算基础学问59/66Linpack由J.Don

27、garra编写的Linpack接受主元高斯消去法求解双精度(64bits)稠密线性代数方程组，结果按每秒浮点运算次数（flops）表示。包含三类测试，问题规模与优化选择各不相同：100100测试 在该测试中，不允许对Linpack测试程序进行任何修改（包括注释行）。10001000测试 在该测试中，允许对算法和软件进行修改或替换，并尽量利用系统的硬件特点，以达到尽可能高的性能。但是全部的优化都必需保持和标准算法如高斯消去法相同的相对精度，而且必需运用Linpack的主程序进行调用。2022/11/1并行计算基础学问60/66linpackw HPL测试 w针对大规模并行计算系统的测试，其名称为

28、High Performance Linpack(HPL)，1.0版 于2000年9月发布，是第一个标准的公开版本并行Linpack测试软件包，w一般用于TOP500超级计算机上的并行超级计算机。wHPL与其前辈不同，运用者可以变更问题规模。w要获得Linpack实测峰值，须要运用与内存匹配的最大的问题规模（一般接近内存总容量的80%）。2022/11/1并行计算基础学问61/66HPL测试wRpeak:系统的最大的理论峰值性能，按GFLOPS表示。wNmax:给出达到最高GFLOPS值时的问题规模（矩阵规模）。wRmax:在Nmax问题规模下，达到的最大峰值（GFLOPS）。wNB:矩阵分块

29、大小，与高速缓存大小相关。一般在32到256之间。2022/11/1并行计算基础学问62/662022/11/1并行计算基础学问63/66NAS Parallel BenchmarkwNPB套件由八个程序组成w每个基准测试有五类：A、B、C、D、W(工作站)。A是最小的，D是最大的。wNPB套件以每秒百万次运算为单位输出结果。n整数排序(IS)n快速Fourier变换（FT）n多栅格基准测试（MG）n共轭梯度(CG)基准测试 n稀疏矩阵分解（LU）n五对角方程（SP）和块状三角(BT)求解 n密集并行(EP)2022/11/1并行计算基础学问64/66参考文献w黄铠、徐志伟，可扩展并行计算，机械工业出版社，2000年w陈国良，并行计算，高等教化出版社，1999年wRajkumar Buyya，高性能机群计算，电子工业出版社，2001年w李晓梅、莫则尧等，可扩展并行算法的设计与分析，国防工业出版社，2000年2022/11/1并行计算基础学问65/66谢 谢！