并行计算基本概念备课讲稿.ppt

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

1、并行计算基本概念2022/11/30并行计算基础知识2/66并行计算系统基础w并行计算机分类w主流并行计算机系统比较w机群并行计算环境2022/11/30并行计算基础知识3/66并行计算机分类w根据指令流和数据流的不同，通常把计算机系统分为：n单指令流单数据流（SISD）n单指令流多数据流（SIMD）n多指令流单数据流（MISD）n多指令流多数据流（MIMD）w并行计算机系统绝大部分为MIMD系统，包括n并行向量机（PVP，Parallel Vector Processor）；n对称多处理机（SMP,Symmetric Multiprocessor）；n大规模并行处理机（MPP，Massive

2、ly Parallel Processor）；n机群（Cluster）；n分布式共享存储多处理机（DSM，Distributied Shared Memory）2022/11/30并行计算基础知识4/66Top500中的超级计算机w地球模拟器wASCI QwASCI White2022/11/30并行计算基础知识5/66Earth SimulatorEarth simulator centerNecRmax:35.86Tflops8*8*6402022/11/30并行计算基础知识6/66Earth Simulator2022/11/30并行计算基础知识7/66Earth Simulator20

3、22/11/30并行计算基础知识8/66ASCI Q1024 nodes8cpu/node10240Gflops7727Gflops2022/11/30并行计算基础知识9/66ASCI whiteLLNL IBM SP power3 Rmax 7.22Tflops2022/11/30并行计算基础知识10/66SMP 对称多处理机wSMP系统一般使用商品化微处理器，具有片上或外置高速缓存w经由高速总线（或交叉开关）连向共享存储器。每个处理器可等同地访问共享存储器、I/O设备和操作系统服务。w单一操作系统映像，全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态地分配各个进程

4、到各个处理器，并保持负载平衡；w低通信延迟，各个进程通过读/写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信延迟；w共享总线带宽，所有处理器共享总线带宽，完成对内存模块和I/O模块的访问。2022/11/30并行计算基础知识11/66SMP 对称多处理机（续）w问题：欠可靠，总线、存储器、操作系统失效可能导致系统崩溃；w可扩展性较差，由于所有处理器都共享总线带宽，而总线带宽每3年才增加2倍，赶不上处理器速度和存储容量的增长步伐，因此SMP的处理器个数一般少于64个，且只能提供每秒数百亿次的浮点运算。wSMP的 典 型 代 表 有：SGI POWER Challenge

5、 XL系 列、DEC Alphaserver 84005/440、HP9000/T600和IBM RS6000/R40。2022/11/30并行计算基础知识12/66SMP 对称多处理机（续）P/CP/CP/C总 线 或 交 叉 开 关SMSMSM2022/11/30并行计算基础知识13/66DSM 分布式共享存储多处理机wDSM的 典 型 代 表 为 SGI的 Origin2000和Origin3000系列并行机w处理器对物理分布的共享存储器的访问是不对称的，因此远端访问延迟一般是本地访问延迟的3倍以上w单一内存地址空间，所有这些内存模块都由硬件进行了统一编址，并通过互连网络形成了并行机的共

6、享存储器2022/11/30并行计算基础知识14/66DSM（续）w基于Cache的数据一致性wDSM较好地改善了SMP的可扩展性能。一般地，DSM可以扩展到上百个节点，能提供每秒数千亿次的浮点运算功能w单一的系统映像，在DSM中，用户只看到一个操作系统，它可以根据各节点的负载情况，动态地分配进程2022/11/30并行计算基础知识15/66DSM（续）定 制 网 络P/CLMDIRMBNICP/CLMDIRMBNIC2022/11/30并行计算基础知识16/66机群（Cluster）w我国的曙光1000A、曙光2000、曙光3000以及前不久推出的曙光4000L等都是机群架构的并行计算机wC

7、luster的每个系统都是一个完整的工作站，一个节点可以是一台PC或SMPw各个节点一般由商品化的网络互连，节点上的网络接口是松散耦合到I/O总线上的w每个节点一般有本地磁盘，一个完整的操作系统驻留在每个节点上2022/11/30并行计算基础知识17/66机群（Cluster）定 制 网 络P/CMBMBLDNICIOBP/CMBMBLDNICIOB2022/11/30并行计算基础知识18/66可扩展高性能机群服务器技术ExpandabilityCluster CoreCluster CoreCluster CoreNode IndependentNode Failure Isolated&T

8、aken OverSingle Point LoginSingle System File ImageSingle Point of ManagementNode ExpandableUser ExpandableSystem ExpandableApplication ExpandableSingle System imageShare ResourceShare System ManagementEasy to manageHigh Availability2022/11/30并行计算基础知识19/66单一系统映像w单一系统映像（Single System Image，SSI）并不是指系统

9、中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统。w其基本特征是单一系统、单一控制、对称性、位置透明。采用SSI的主要目的，是使机群的使用、控制和维护似乎和一台工作站一样。w单一系统映像包括单一入口点、单一文件层次结构、单一I/O空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间。2022/11/30并行计算基础知识20/66三种体系结构比较（一）分 布式 计算 系统机群计算机DSMSMP节点系统复杂度单一系统映像2022/11/30并行计算基础知识21/66三种体系结构比较（二）可扩展性系统可靠性MPPSMPPC机群专用容错系统2022/11/30并行计算基础知识2

10、2/66Beowulf与机群wBeowulf：自己攒的“高性能计算机”n买PC、网络设备、装linux、MPI、ATLASw降低了高性能计算门槛，促进了高性能计算普及w迫切的问题：单一系统映像n单一管理点n单一文件系统n单一作业管理n负载自动均衡2022/11/30并行计算基础知识23/66Beowulf：第一台：第一台Hrothgar2022/11/30并行计算基础知识24/66十年来CPU演变（1）2022/11/30并行计算基础知识25/66十年来CPU演变（2）2022/11/30并行计算基础知识26/66十年来CPU演变（3）2022/11/30并行计算基础知识27/66十年来体系结

11、构的演变2022/11/30并行计算基础知识28/66机群：厂家面临的问题w怎样避免同质化？n一样的CPU、一样的网络、一样的操作系统、几乎一样的机群系统n不一样的用户需求，一样的系统能最优满足？wSUMA标准nScalability可扩展性nUsability易用性nManageability 可管理性nAvailability高可用性2022/11/30并行计算基础知识29/66怎样避免同质化w应用分类nCPU密集、MEM密集、DISK密集、NIC密集w针对不同应用需求，提出不同的方案w可重构计算2022/11/30并行计算基础知识30/66Intel与AMDwOpteronn与32位兼容

12、的64位处理器nHyperTransportwXeonn主频持续上升wItanium n？2022/11/30并行计算基础知识31/66华大基因（北京）wDraft Sequence of Rice Genome2022/11/30并行计算基础知识32/66曙光百万亿数据处理超级服务器2022/11/30并行计算基础知识33/664000L主要指标w40个机柜组成w644个CPUw每秒3万亿次浮点计算峰值速度w644GB内存w百万亿字节（100TB）存储n最大可“在线”扩展到80个机柜n1300个CPUn每秒6.75万亿次峰值速度n4000G内存n600T存储n1200A最大电流，160千瓦最

13、大功耗的海量处理系统2022/11/30并行计算基础知识34/66初步的面向网格的特点wGrid Terminal智能控制台能够实现庞大系统的安全管理wGridView网格监控中心软件则提供了逻辑视角、视角的可伸缩性、历史记录分析三项特色，被称为系统的“千里眼”。2022/11/30并行计算基础知识35/66中国近期的一些新闻w曙光“红色网格”孕育10万亿次超级计算机w中科院网络信息中心委托联想研制高性能计算机系统w高性能计算的“超级”对抗w浪潮高性能计算 生命科学领域显奇功w高性能计算：处于什么样的阶段？2022/11/30并行计算基础知识36/66HPC：处于什么样的阶段w机群高性能计算系

14、统已经成熟，步入量产阶段n国内曙光、联想、浪潮，还有大量小公司w高性能计算应用的快速扩展阶段n从去年开始，机群销量猛增，应用在科学计算和信息服务等所有领域w高性能计算教育相对滞后、人才相对稀缺阶段n北大、清华、科大等有限几所高校设置相应专业课程2022/11/30并行计算基础知识37/66并行计算基本概念w并行算法的定义与分类w并行算法的复杂性w数据相关性与可并行化w并行计算模型2022/11/30并行计算基础知识38/66并行算法的定义与分类w算法是解题的精确描述，n是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并

15、最终获得问题的求解w并行算法就是对并行计算过程的精确描述w并行算法可以从不同的角度分类为n数值计算并行算法和非数值计算并行算法n同步并行算法和异步并行算法n共享存储并行算法和分布存储并行算法2022/11/30并行计算基础知识39/66数值算法与非数值算法w数值计算是指基于代数关系运算的计算问题，n如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法（Numerical Algorithm）。n科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。w非数值计算是指基于比较关系运算n诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算法（

16、Nonnumerical Algorithm）。n非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题、海量数据挖掘等，n近年来广泛关注的生物信息学主要也是非数值计算 2022/11/30并行计算基础知识40/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/30并行计算基础知识41/66描述并行算法w如果要求输入输出N个数据，则认为该算法的I/O时间界为O(N)w如果问题规模为n，涉

17、及的计算量一般为t(n)，则该算法的计算CPU时间界为O(t(n)w对要求通信和同步的次数为L、通信量为M个数据，则该算法的并行开销为O(L+M)2022/11/30并行计算基础知识42/66问题规模w问题规模有可分为n输入输出规模、计算规模、内存需求、通信（同步）规模，n分别表示问题求解所需要的I/O量、计算量、内存大小和通信量（包括通信次数与通信数据量）。w根据消耗资源程度，又相应分为nCPU密集应用、memory密集应用、disk密集应用和网络密集应用。n不同类型的问题，性能瓶颈也往往不同。并行算法就是要又针对性的消除相应的瓶颈，从而达到缩短计算时间的目的。2022/11/30并行计算基

18、础知识43/66相关性与可并行化伯恩斯坦准则lI1O2，即P1的输入变量集与P2的输出变量集不相交；lI2O1，即P2的输入变量集与P1的输出变量集不相交；lO1O2，即P1和P2的输出变量集不相交w可并行处理2022/11/30并行计算基础知识44/66数据相关wP1：AB+CwP2：DABl其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。w显然，P1和P2不能并行执行。2022/11/30并行计算基础知识45/66数据反相关wP1：ABCwP2：CE+DlP1通过变量C数据相关于P2。为保证语义正确

19、性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。w也不可并行化2022/11/30并行计算基础知识46/66数据输出相关wP1：AB+CwP2：ADEl为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。除了上述3种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。2022/11/30并行计算基础知识47/66并行计算模型w计算模型是对计算机的抽象w计算模型为设计、分析和评价算法提供基础w冯.偌依曼机就是一个

20、理想的串行计算模型w但现在还没有一个通用的并行计算模型lPRAM模型lLogP模型2022/11/30并行计算基础知识48/66PRAM模型w PRAM（Parallel Random Access Machine）模型，即并行随机存取模型，是一种抽象的并行计算模型。n假设存在着一个容量无限大的共享存储器；n每台处理器有简单的算术运算和逻辑判断功能；n在任何时刻各处理器均可以通过共享存储单元交换数据。2022/11/30并行计算基础知识49/66PRAM模型w可分为SIMD-PRAM和MIMD-PRAM。wSIMD-PRAM模型又可以细分为nPRAM-EREW模型；nPRAM-CREW模型；n

21、PRAM-CRCW模型。lCPRAM-EREW模型；lPPRAM-EREW模型lAPRAM-EREW模型。2022/11/30并行计算基础知识50/66PRAM模型SIMD-PRAM计算模型 MIMD-PRAM计算模型控制单元P1LMP2LMPnLM互连网络全局共享存储器控制器1P1LMP2LMPnLM互连网络全局共享存储器控制器2控制器n2022/11/30并行计算基础知识51/66LogP LogP 模型模型 w充分说明了互连网络的性能特点，而未涉及网络的结构。模型主要由4个参数描述。lL（Latency）源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限。lo（

22、overhead）处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理机不能执行其他操作。lg（gap）一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即为处理机的通信带宽。lP（Processor）处理机的个数。2022/11/30并行计算基础知识52/66LogP 模型w揭示了分布存储并行计算机的性能瓶颈，用L、o、g三个参数刻画了通信网络的特性，l但屏蔽了网络拓扑、选路算法和通信协议等具体细节l参数g反映了通信带宽l在任何时刻，最多只能有L/g条消息从一个处理器传到另一个处理器，这就是网络容限，当一台处理机发送的消息达到这个容

23、限时，在发送的消息就会被阻塞；l在网络容限范围内，点到点传送一条消息的时间为（2*o+L）。w设想LogP模型中的L、o、g都为0，那么LogP模型就等同于PRAM模型 2022/11/30并行计算基础知识53/66各种计算模型比较 模型属性PRAMAPRAMBSPLogPC3体系结构SIMD-SMMIMD-SMMIMD-DMMIMD-DMMIMD-DM计算模式同步异步异步异步异步同步方式自动同步路障同步路障同步隐式同步路障同步模型参数单位时间步d,读/写时间B,同步时间p,处理器数g,带宽因子l,同步间隔L,通信延迟o,额外开销g,带宽因子P,处理器数l,信包长度s,发送建立时间h,通信延迟

24、计算粒度细粒度/中粒度中粒度/粗粒度中粒度/粗粒度中粒度/粗粒度粗粒度通信方式读/写共享变量读/写共享变量发送/接收消息发送/接收消息发送/接收消息地址空间全局地址空间单地址空间单/多地址空间单/多地址空间多地址空间2022/11/30并行计算基础知识54/66性能评价与benchmarkw加速比定律与并行效率w常见benchmark简介2022/11/30并行计算基础知识55/66加速比定律w在给定的并行计算系统上给定的应用，并行算法（并行程序）的执行速度相对于串行算法（串行程序）加快的倍数，就是该并行算法（并行程序）的加速比。wAmdahl定律适用于固定计算规模的加速比性能描述，Gusta

25、fson定律适用于可扩展问题 2022/11/30并行计算基础知识56/66Amdahl定律S=(WS+WP)/(WS+WP/p)=1/(1/p+f(1-1/p)w显然，当p时，S=1/fw即对于固定规模的问题，并行系统所能达到的加速上限为1/f。l假定并行计算系统的处理器数为p，W为问题规模，WS为应用程序中的串行分量，WP为可并行化部分；f为串行分量的比例（f=Ws/W），1f为并行分量的比例；Ts=T1为串行执行时间，Tp为并行计算时间；S为加速比，E为并行效率 2022/11/30并行计算基础知识57/66Gustafson定律S=（WS+pwp）/（WS+WP）=p-f（p-1）=f

26、+p（1-f）w加速比与处理器数成斜率为（1-f）的线性关系w这样串行比例f就不再是程序扩展性的瓶颈，w当然，f越低，斜率会越大，加速性能越好。2022/11/30并行计算基础知识58/66Linpack由J.Dongarra编写的Linpack采用主元高斯消去法求解双精度(64bits)稠密线性代数方程组，结果按每秒浮点运算次数（flops）表示。包含三类测试，问题规模与优化选择各不相同：n100100测试 w在该测试中，不允许对Linpack测试程序进行任何修改（包括注释行）。n10001000测试 w在该测试中，允许对算法和软件进行修改或替换，w并尽量利用系统的硬件特点，以达到尽可能高的

27、性能。w但是所有的优化都必须保持和标准算法如高斯消去法相同的相对精度，而且必须使用Linpack的主程序进行调用。2022/11/30并行计算基础知识59/66linpackw HPL测试 n针对大规模并行计算系统的测试，其名称为High Performance Linpack(HPL)，1.0版于2000年9月发布，是第一个标准的公开版本并行Linpack测试软件包，n一般用于TOP500超级计算机上的并行超级计算机。nHPL与其前辈不同，使用者可以改变问题规模。n要获得Linpack实测峰值，需要使用与内存匹配的最大的问题规模（一般接近内存总容量的80%）。2022/11/30并行计算基础

28、知识60/66HPL测试wRpeak:系统的最大的理论峰值性能，按GFLOPS表示。wNmax:给出达到最高GFLOPS值时的问题规模（矩阵规模）。wRmax:在Nmax问题规模下，达到的最大峰值（GFLOPS）。wNB:矩阵分块大小，与高速缓存大小相关。一般在32到256之间。2022/11/30并行计算基础知识61/662022/11/30并行计算基础知识62/66NAS Parallel BenchmarkwNPB套件由八个程序组成w每个基准测试有五类：A、B、C、D、W(工作站)。A是最小的，D是最大的。wNPB套件以每秒百万次运算为单位输出结果。n整数排序(IS)n快速Fourier

29、变换（FT）n多栅格基准测试（MG）n共轭梯度(CG)基准测试 n稀疏矩阵分解（LU）n五对角方程（SP）和块状三角(BT)求解 n密集并行(EP)2022/11/30并行计算基础知识63/66参考文献w黄铠、徐志伟，可扩展并行计算，机械工业出版社，2000年w陈国良，并行计算，高等教育出版社，1999年wRajkumar Buyya，高性能机群计算，电子工业出版社，2001年w李晓梅、莫则尧等，可扩展并行算法的设计与分析，国防工业出版社，2000年2022/11/30并行计算基础知识64/66谢 谢！此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢