《并行程序设计基础》由会员分享，可在线阅读，更多相关《并行程序设计基础（50页珍藏版）》请在金锄头文库上搜索。
1、并行程序设计基础联想高性能服务器事业部联想高性能服务器事业部3并行计算系统基础并行计算系统基础?并行计算机分类?主流并行计算机系统比较?机群并行计算环境4并行计算机分类并行计算机分类?根据指令流和数据流的不同，通常把计算机系统分为： 单指令流单数据流（SISD） 单指令流多数据流（SIMD） 多指令流单数据流（MISD） 多指令流多数据流（MIMD）?并行计算机系统绝大部分为MIMD系统，包括 并行向量机（PVP，Parallel Vector Processor）； 对称多处理机（SMP,Symmetric Multiprocessor）； 大规模并行处理机（MPP，Massively Pa
2、rallel Processor）； 机群（Cluster）； 分布式共享存储多处理机（DSM，Distributied Shared Memory）5Earth SimulatorEarth simulator centerNecRmax:35.86Tflops8*8*6407Earth Simulator8SMP 对称多处理机对称多处理机?SMP系统一般使用商品化微处理器，具有片上或外置高速缓存?经由高速总线（或交叉开关）连向共享存储器。每个处理器可等同地访问共享存储器、I/O设备和操作系统服务。?单一操作系统映像，全系统只有一个操作系统驻留在共享存储器中，它根据各个处理器的负载情况，动态
3、地分配各个进程到各个处理器，并保持负载平衡；?低通信延迟，各个进程通过读/写操作系统提供的共享数据缓存区来完成处理器间的通信，其延迟通常小于网络通信延迟；?共享总线带宽，所有处理器共享总线带宽，完成对内存模块和I/O模块的访问。9SMP 对称多处理机（续）对称多处理机（续）?问题：欠可靠，总线、存储器、操作系统失效可能导致系统崩溃；?可扩展性较差，由于所有处理器都共享总线带宽，而总线带宽每3年才增加2倍，赶不上处理器速度和存储容量的增长步伐，因此SMP的处理器个数一般少于64个，且只能提供每秒数百亿次的浮点运算。?SMP的典型代表有：SGI POWER Challenge XL系列、DEC A
4、lphaserver 84005/440、HP9000/T600和IBM RS6000/R40。11DSM 分布式共享存储多处理机分布式共享存储多处理机?DSM的典型代表为SGI的Origin2000和Origin3000系列并行机?处理器对物理分布的共享存储器的访问是不对称的，因此远端访问延迟一般是本地访问延迟的3倍以上?单一内存地址空间，所有这些内存模块都由硬件进行了统一编址，并通过互连网络形成了并行机的共享存储器12DSM （续）（续）?基于Cache的数据一致性?DSM较好地改善了SMP的可扩展性能。一般地，DSM可以扩展到上百个节点，能提供每秒数千亿次的浮点运算功能?单一的系统映像，
5、在DSM中，用户只看到一个操作系统，它可以根据各节点的负载情况，动态地分配进程13机群（机群（Cluster）?我国的曙光1000A、曙光2000、曙光3000；联想深腾1800以及前不久推出的曙光4000L和联想深腾6800等都是机群架构的并行计算机?Cluster的每个系统都是一个完整的工作站，一个节点可以是一台PC或SMP?各个节点一般由商品化的网络互连，节点上的网络接口是松散耦合到I/O总线上的?每个节点一般有本地磁盘，一个完整的操作系统驻留在每个节点上14可扩展高性能机群服务器技术可扩展高性能机群服务器技术ExpandabilityCluster CoreCluster CoreCl
6、uster CoreNode Independent Node Failure Isolated & Taken OverSingle Point Login Single System File Image Single Point of ManagementNode Expandable User Expandable System Expandable Application ExpandableSingle System imageShare Resource Share System ManagementEasy to manageHigh Availability15单一系统映像单
7、一系统映像?单一系统映像（Single System Image，SSI）并不是指系统中仅有唯一的操作系统映像驻留在内存，而只是感觉上，像一个单一系统。?其基本特征是单一系统、单一控制、对称性、位置透明。采用SSI的主要目的，是使机群的使用、控制和维护似乎和一台工作站一样。?单一系统映像包括单一入口点、单一文件层次结构、单一I/O空间、单一网络、单一作业管理系统、单一存储空间和单一进程空间。16三种体系结构比较（一）三种体系结构比较（一）分 布 式 计 算 系 统机群计算机DSMSMP节点系统复杂度单一系统映像17三种体系结构比较（二）三种体系结构比较（二）可扩展性系统可靠性MPPSMPPC机
8、群专用容错系统18Beowulf与机群与机群?Beowulf：自己攒的“高性能计算机” 买PC、网络设备、装linux、MPI、ATLAS?降低了高性能计算门槛，促进了高性能计算普及?迫切的问题：单一系统映像 单一管理点 单一文件系统 单一作业管理 负载自动均衡19Beowulf：第一台Hrothgar20机群：厂家面临的问题机群：厂家面临的问题?怎样避免同质化？ 一样的CPU、一样的网络、一样的操作系统、几乎一样的机群系统 不一样的用户需求，一样的系统能最优满足？21怎样避免同质化怎样避免同质化?应用分类 CPU密集、MEM密集、DISK密集、NIC密集?针对不同应用需求，提出不同的方案22
9、Intel与与AMD?Xeon 主频持续上升?Itanium Madison 1.5G，目前最快的处理器?Opteron 与32位兼容的64位处理器 HyperTransport23HPC：处于什么样的阶段：处于什么样的阶段?机群高性能计算系统已经成熟，步入量产阶段 国内联想、曙光、浪潮，还有大量小公司?高性能计算应用的快速扩展阶段 从去年开始，机群销量猛增，应用在科学计算和信息服务等所有领域?高性能计算教育相对滞后、人才相对稀缺阶段 北大、清华、科大等有限几所高校设置相应专业课程24并行计算基本概念并行计算基本概念?并行算法的定义与分类?并行算法的复杂性?数据相关性与可并行化?并行计算模型?
10、并行计算的评估与调试25并行算法的定义与分类并行算法的定义与分类?算法是解题的精确描述， 是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。并行计算时可同时求解的诸进程的集合，这些进程相互作用和协调动作，并最终获得问题的求解?并行算法就是对并行计算过程的精确描述?并行算法可以从不同的角度分类为 数值计算并行算法和非数值计算并行算法 同步并行算法和异步并行算法 共享存储并行算法和分布存储并行算法26数值算法与非数值算法数值算法与非数值算法?数值计算是指基于代数关系运算的计算问题， 如矩阵运算、多项式求值、线性代数方程组求解等。求解数值计算问题的算法称为数值算法（Numerical Al
11、gorithm）。 科学与工程中的计算问题如计算力学、计算物理、计算化学等一般是数值计算问题。?非数值计算是指基于比较关系运算 诸如排序、选择、搜索、匹配等符号处理，相应的算法也称为非数值算法（Non-numerical Algorithm）。 非数值计算在符号类信息处理中获得广泛应用，如数据库领域的计算问题、海量数据挖掘等， 近年来广泛关注的生物信息学主要也是非数值计算27并行算法的复杂性并行算法的复杂性?上界 f(n)=cg(n)，则称g(n)是f(n)的一个下界，记做f(n)=(g(n)?紧致界 c1g(n)=f(n)=c2g(n)，则称g(n)是f(n)的一个紧致界，记做f(n)=(g
12、(n)。28描述并行算法描述并行算法?如果要求输入输出N个数据，则认为该算法的I/O时间界为O(N)?如果问题规模为n，涉及的计算量一般为t(n)，则该算法的计算CPU时间界为O(t(n)?对要求通信和同步的次数为L、通信量为M个数据，则该算法的并行开销为O(L+M)29问题规模问题规模?问题规模有可分为 输入输出规模、计算规模、内存需求、通信（同步）规模， 分别表示问题求解所需要的I/O量、计算量、内存大小和通信量（包括通信次数与通信数据量）。?根据消耗资源程度，又相应分为 CPU密集应用、memory密集应用、disk密集应用和网络密集应用。 不同类型的问题，性能瓶颈也往往不同。并行算法就
13、是要有针对性的消除相应的瓶颈，从而达到缩短计算时间的目的。30相关性与可并行化相关性与可并行化伯恩斯坦准则 I1O2，即P1的输入变量集与P2的输出变量集不相交； I2O1，即P2的输入变量集与P1的输出变量集不相交； O1O2，即P1和P2的输出变量集不相交?可并行处理31数据相关数据相关?P1： AB+C?P2： DAB 其中，变量A是导致P1和P2发生数据相关的原因。为了保证程序执行的语义正确性，变量A必须是先在P1中写入后方可从P2中读出，即必须先写后读。?显然，P1和P2不能并行执行。32数据反相关数据反相关?P1： ABC?P2： CE+D P1通过变量C数据相关于P2。为保证语义
14、正确性，必须等P1将变量C读出后，P2方可向变量C进行写入操作，即必须先读后写。?也不可并行化33数据输出相关数据输出相关?P1： AB+C?P2： AD E 为保证语义正确性，必须保证P1先写入A，然后允许P2再写入A。 除了上述3种相关外，还存在一种特殊情况，即两个程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性。这就要求硬件机构能保证两者进行同步读写。但若两个处理机各带有局部存储器，则可降低同步要求。34并行计算模型并行计算模型?计算模型是对计算机的抽象?计算模型为设计、分析和评价算法提供基础?冯.偌依曼就是一个理想的串行计算模型?但现在还没有一个通用的并行计算
15、模型 PRAM模型 LogP模型35PRAM模型模型?PRAM（Parallel Random Access Machine）模型，即并行随机存取模型，是一种抽象的并行计算模型。 假设存在着一个容量无限大的共享存储器； 每台处理器有简单的算术运算和逻辑判断功能； 在任何时刻各处理器均可以通过共享存储单元交换数据。36PRAM模型模型控制器1P1 LMP2 LMPn LM互连网络全局共享存储器控制器2控制器n控制单元P1 LMP2 LMPn LM互连网络全局共享存储器SIMD-PRAM计算模型MIMD-PRAM计算模型37LogP模型?充分说明了互连网络的性能特点，而未涉及网络的结构。模型主要由
16、4个参数描述。 L（Latency） 源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限。 o（overhead） 处理机准备发送或准备接受每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理机不能执行其他操作。 g（gap） 一台处理机连续两次发送或连续两次接受消息时的最小时间间隔，其倒数即为处理机的通信带宽。 P（Processor） 处理机的个数。38LogP 模型模型?揭示了分布存储并行计算机的性能瓶颈，用L、o、g三个参数刻画了通信网络的特性， 但屏蔽了网络拓扑、选路算法和通信协议等具体细节 参数g反映了通信带宽 在任何时刻，最多只能有L/g条消息从一个处理器传到另一个处理器，这就是网络容限，当一台处理机发送的消息达到这个容限时，在发送的消息就会被阻塞； 在网络容限范围内，点到点传送一条消息的时间为（2*o+L）。?设想LogP模型中的L、o、g都为0
