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