《并行计算概念》由会员分享，可在线阅读，更多相关《并行计算概念（66页珍藏版）》请在金锄头文库上搜索。
1、*并行计算基础知识1并行计算基础知识冯圣中 中国科学院计算技术研究所 国家智能计算机研究开发中心 国家高性能计算中心（北京）*并行计算基础知识2/66主要内容w 并行计算 w 并行计算系统基础 w 并行计算基本概念 w 几种典型的benchmark*并行计算基础知识3/66并行计算基本概念w Parallel computing、high performance computing 、 highend computingnThe simultaneous use of more than one computer to solve a problem. w 多计算机网络 w 多进程/线程通信w
2、 并行计算环境 w 加速比/可扩展性*并行计算基础知识4/66并行计算系统基础w 并行计算机分类 w 主流并行计算机系统比较 w 机群并行计算环境*并行计算基础知识5/66并行计算机分类w 根据指令流和数据流的不同，通常把计算机系统分为 ：n单指令流单数据流（SISD）n单指令流多数据流（SIMD）n多指令流单数据流（MISD）n多指令流多数据流（MIMD） w 并行计算机系统绝大部分为MIMD系统，包括n并行向量机（PVP，Parallel Vector Processor）；n对称多处理机（SMP,Symmetric Multiprocessor）；n大规模并行处理机（MPP，Massiv
3、ely Parallel Processor）；n机群（Cluster）；n分布式共享存储多处理机（DSM，Distributied Shared Memory） *并行计算基础知识6/66Top500中的超级计算机w 地球模拟器 w ASCI Q w ASCI White*并行计算基础知识7/66Earth SimulatorEarth simulator centerNecRmax:35.86Tflops8*8*640*并行计算基础知识8/66Earth Simulator*并行计算基础知识9/66Earth Simulator*并行计算基础知识10/66ASCI Q1024 nodes8
4、cpu/node10240Gflops7727Gflops*并行计算基础知识11/66ASCI whiteLLNL IBM SP power3 Rmax 7.22Tflops*并行计算基础知识12/66SMP 对称多处理机w SMP系统一般使用商品化微处理器，具有片上或外置高速缓存w 经由高速总线（或交叉开关）连向共享存储器。每个处理器可等同 地访问共享存储器、I/O设备和操作系统服务。w 单一操作系统映像，全系统只有一个操作系统驻留在共享存储器中 ，它根据各个处理器的负载情况，动态地分配各个进程到各个处理 器，并保持负载平衡； w 低通信延迟，各个进程通过读/写操作系统提供的共享数据缓存区
5、来完成处理器间的通信，其延迟通常小于网络通信延迟； w 共享总线带宽，所有处理器共享总线带宽，完成对内存模块和I/O 模块的访问。*并行计算基础知识13/66SMP 对称多处理机（续）w 问题：欠可靠，总线、存储器、操作系统失效可能导致系统崩溃； w 可扩展性较差，由于所有处理器都共享总线带宽，而总线带宽每3 年才增加2倍，赶不上处理器速度和存储容量的增长步伐，因此 SMP的处理器个数一般少于64个，且只能提供每秒数百亿次的浮点 运算。 w SMP的典型代表有：SGI POWER Challenge XL系列、DEC Alphaserver 84005/440、HP9000/T600和IBM
6、RS6000/R40。*并行计算基础知识14/66SMP 对称多处理机（续）P/CP/CP/C总 线 或 交 叉 开 关SMSMSM*并行计算基础知识15/66DSM 分布式共享存储多处理机w DSM的典型代表为SGI的Origin2000和 Origin3000系列并行机 w 处理器对物理分布的共享存储器的访问是不对 称的，因此远端访问延迟一般是本地访问延迟 的3倍以上 w 单一内存地址空间，所有这些内存模块都由硬 件进行了统一编址，并通过互连网络形成了并 行机的共享存储器*并行计算基础知识16/66DSM （续）w 基于Cache的数据一致性 w DSM较好地改善了SMP的可扩展性能。一般
7、地 ，DSM可以扩展到上百个节点，能提供每秒数 千亿次的浮点运算功能 w 单一的系统映像，在DSM中，用户只看到一个 操作系统，它可以根据各节点的负载情况，动 态地分配进程*并行计算基础知识17/66DSM （续）定 制 网 络P/CLMDIRMBNICP/CLMDIRMBNIC*并行计算基础知识18/66机群（Cluster）w 我国的曙光1000A、曙光2000、曙光3000以及 前不久推出的曙光4000L等都是机群架构的并行 计算机 w Cluster的每个系统都是一个完整的工作站，一 个节点可以是一台PC或SMP w 各个节点一般由商品化的网络互连，节点上的 网络接口是松散耦合到I/O
8、总线上的 w 每个节点一般有本地磁盘，一个完整的操作系 统驻留在每个节点上*并行计算基础知识19/66机群（Cluster）定 制 网 络P/CMBMBLD NICIOBP/CMBMBLD NICIOB*并行计算基础知识20/66可扩展高性能机群服务器技术ExpandabilityCluster CoreCluster CoreNode Independent Node Failure Isolated & Taken OverSingle Point Login Single System File Image Single Point of ManagementNode Expandabl
9、e User Expandable System Expandable Application ExpandableSingle System imageShare Resource Share System ManagementEasy to manageHigh Availability*并行计算基础知识21/66单一系统映像w 单一系统映像（Single System Image，SSI） 并不是指系统中仅有唯一的操作系统映像驻留 在内存，而只是感觉上，像一个单一系统。 w 其基本特征是单一系统、单一控制、对称性、 位置透明。采用SSI的主要目的，是使机群的使 用、控制和维护似乎和一台工
10、作站一样。 w 单一系统映像包括单一入口点、单一文件层次 结构、单一I/O空间、单一网络、单一作业管理 系统、单一存储空间和单一进程空间。 *并行计算基础知识22/66三种体系结构比较（一）分布 式计 算系 统机群计算机DSMSMP节点系统复杂度单一系统映像*并行计算基础知识23/66三种体系结构比较（二）可扩展性系统可靠性MPPSMPPC机群专用容错系统*并行计算基础知识24/66Beowulf与机群w Beowulf：自己攒的“高性能计算机”n买PC、网络设备、装linux、MPI、ATLAS w 降低了高性能计算门槛，促进了高性能计算普及 w 迫切的问题：单一系统映像n单一管理点n单一文
11、件系统n单一作业管理n负载自动均衡*并行计算基础知识25/66Beowulf：第一台Hrothgar*并行计算基础知识26/66十年来CPU演变（1）*并行计算基础知识27/66十年来CPU演变（2）*并行计算基础知识28/66十年来CPU演变（3）*并行计算基础知识29/66十年来体系结构的演变*并行计算基础知识30/66机群：厂家面临的问题w 怎样避免同质化？n一样的CPU、一样的网络、一样的操作系统、几乎一 样的机群系统n不一样的用户需求，一样的系统能最优满足？ w SUMA标准nScalability可扩展性nUsability易用性nManageability 可管理性nAvaila
12、bility高可用性*并行计算基础知识31/66怎样避免同质化w 应用分类nCPU密集、MEM密集、DISK密集、NIC密集 w 针对不同应用需求，提出不同的方案 w 可重构计算*并行计算基础知识32/66Intel与AMDw Opteronn与32位兼容的64位处理器nHyperTransport w Xeonn主频持续上升 w Itanium n？*并行计算基础知识33/66华大基因（北京）w Draft Sequence of Rice Genome*并行计算基础知识34/66曙光百万亿数据处理超级服务器*并行计算基础知识35/664000L主要指标w 40个机柜组成 w 644个CPU
13、 w 每秒3万亿次浮点计算峰值速度 w 644GB内存 w 百万亿字节（100TB）存储n最大可“在线”扩展到80个机柜n1300个CPUn每秒6.75万亿次峰值速度n4000G内存n600T存储n1200A最大电流，160千瓦最大功耗的海量处理系统*并行计算基础知识36/66初步的面向网格的特点w Grid Terminal智能控制台能够实现庞大系 统的安全管理 w GridView网格监控中心软件则提供了逻辑 视角、视角的可伸缩性、历史记录分析三 项特色，被称为系统的“千里眼”。*并行计算基础知识37/66中国近期的一些新闻w 曙光“红色网格”孕育10万亿次超级计算机 w 中科院网络信息中
14、心委托联想研制高性能 计算机系统 w 高性能计算的“超级”对抗w 浪潮高性能计算 生命科学领域显奇功w 高性能计算：处于什么样的阶段？*并行计算基础知识38/66HPC：处于什么样的阶段w 机群高性能计算系统已经成熟，步入量产阶段n国内曙光、联想、浪潮，还有大量小公司 w 高性能计算应用的快速扩展阶段n从去年开始，机群销量猛增，应用在科学计算和信息 服务等所有领域 w 高性能计算教育相对滞后、人才相对稀缺阶段n北大、清华、科大等有限几所高校设置相应专业课程*并行计算基础知识39/66并行计算基本概念w 并行算法的定义与分类 w 并行算法的复杂性 w 数据相关性与可并行化 w 并行计算模型*并行
15、计算基础知识40/66并行算法的定义与分类w 算法是解题的精确描述，n是一组有穷的规则，它规定了解决某一特定类型问题 的一系列运算。并行计算时可同时求解的诸进程的集 合，这些进程相互作用和协调动作，并最终获得问题 的求解 w 并行算法就是对并行计算过程的精确描述 w 并行算法可以从不同的角度分类为n数值计算并行算法和非数值计算并行算法n同步并行算法和异步并行算法n共享存储并行算法和分布存储并行算法*并行计算基础知识41/66数值算法与非数值算法w 数值计算是指基于代数关系运算的计算问题，n如矩阵运算、多项式求值、线性代数方程组求解等。 求解数值计算问题的算法称为数值算法（Numerical A
16、lgorithm）。n科学与工程中的计算问题如计算力学、计算物理、计 算化学等一般是数值计算问题。 w 非数值计算是指基于比较关系运算n诸如排序、选择、搜索、匹配等符号处理，相应的算 法也称为非数值算法（Nonnumerical Algorithm）。n非数值计算在符号类信息处理中获得广泛应用，如数 据库领域的计算问题、海量数据挖掘等，n近年来广泛关注的生物信息学主要也是非数值计算 *并行计算基础知识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)。*并行计算基础知识43/66描述并行算法w 如果要求输入输出N个数据，则认为该算 法的I/O时间界为O(N) w 如果问题规模为n，涉及的计算量一般为 t(n)，则该算法的计算CPU时间界为O(t(n) w 对要求通信和同步的次数为L、通信量为 M个数据，则该算法的并行开销为O(L+M)*并行计算
