第1讲并行计算概述1

2019/12/20并行计算概述1并行计算概述安俊秀[e-mail]软件工程学院并行计算实验室6412云计算云搜索中心（成都）并行计算的产生人类对计算及性能的需求是无止境的从系统的角度：集成系统资源，以满足不断增长的对性能和功能的要求从应用的角度：适当分解应用，以实现更大规模或更细致的计算2如何满足不断增长的计算力需求？用速度更快的硬件，也就是减少每一条指令所需时间优化算法（或者优化编译）用多个处理机(器)同时解决一个问题并行计算3并行计算概述并行计算的概念4...处理器可分解的计算任务串行计算并行计算任务队列并行计算概述5并行计算是相对于串行计算来说的并行计算所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。计算换通信并行计算基础知识6/66并行计算机的分类并行计算科学中主要研究的是空间上的并行问题。空间上的并行导致了两类并行机的产生，按照Flynn的说法分为：单指令流多数据流（SIMD）和多指令流多数据流（MIMD）。我们常用的串行机也叫做单指令流单数据流（SISD）。SISDSIMDMIMD并行计算--高性能计算并行计算(ParallelComputing）高端计算(High-endParallelComputing)高性能计算(HighPerformanceComputing)超级计算(SuperComputing)任何高性能计算和超级计算都离不开使用并行技术Thesimultaneoususeofmorethanonecomputertosolveaproblem.由由运行在多个部件上的小任务合作来求解一个规模很大的计算问题的一种方法89并行计算并行计算（高性能计算、超级计算）大任务分解多个子任务不同处理单元分给快速求解协同合作基本条件：硬件（并行机）、并行算法设计、并行编程环境主要目标：提高求解速度，扩大问题规模并行计算的应用需求1011全球气候变化图1-1系统速度天气预报72小时油藏建模机翼设计物体特性分析年后19951991198019881993存储器容量48结构生物学药物设计化学动力学1000GB100GB10GB1GB100MB10MB小时天气预报100Mflops1Gflops10Gflops100Gflops1Tflops人类基因湍流飞行动力学海洋环流粘滞流体动力学超导建模半导体建模视觉量子染色动力学3维等离子体建模12计算科学与传统的两种科学，即理论科学和实验科学，并列被认为是人类认识自然的三大支柱，他们彼此相辅相成地推动科学发展与社会进步。在许多情况下，或者是理论模型复杂甚至理论尚未建立，或者实验费用昂贵甚至无法进行时，计算就成了求解问题的唯一或主要的手段。并行计算的应用需求13并行的层次程序级并行子程序级并行语句级并行操作级并行微操作级并行并行粒度粗细后三层大都由硬件和编译器负责处理，程序员通常处理前两层的并行15并行计算机的发展始于70年代1972年第一台并行计算机ILLIACIV（伊利诺依大学）60年代末开始建造72年建成,74年运行第一个完整程序,76年运行第一个应用程序64个处理器，是当时性能最高的CDC7600机器的2-6倍公认的1981年前最快1982年退役可扩展性好，但可编程性差16并行计算机的发展始于70年代向量机Cray-1一般将Cray-1投入运行的1976年称为“超级计算元年”编程方便，但可扩展性差以Cray为代表的向量机称雄超级计算机界十几载收藏于DeutschesMuseum德意志博物馆的Cray-1原型17并行计算机的发展80年代百家争鸣早期：以MIMD并行计算机的研制为主DenelcorHEP（1982年）第一台商用MIMD并行计算机CrayX-MPCray研究公司第一台MIMD并行计算机IBM309080年代普遍为银行所采用西摩•克雷SeymourCray(1925-1996)，电子工程学学士，应用数学硕士，超级计算机之父，Cray研究公司的创始人，亲手设计了Cray机型的全部硬件与操作系统，作业系统由他用机器码编写完成。1984年时，公司占据了超级计算机市场70%的份额。1996年Cray研究公司被SGI收购，2000年被出售给Tera计算机公司，成立Cray公司。18并行计算机的发展80年代百家争鸣中期：共享存储多处理机Shared-MemoryMultiProcessorSMP(SymmetricalMulti-Processing)：在一个计算机上汇集一组处理器，各处理器对称共享内存及计算机的其他资源，由单一操作系统管理，极大提高整个系统的数据处理能力。扩展性较差可靠性较差内存访问瓶颈19并行计算机的发展80年代百家争鸣后期：具有强大计算能力的并行机通过二维Mesh连接的Meiko（Sun）系统超立方体连接的MIMD并行机：nCUBE-2、iPSC/80共享存储向量多处理机CrayY-MP······20并行计算机的发展90年代：体系结构框架趋于统一(DSM、MPP、NOW)DSM（DistributedSharedMemory）分布式共享存储以结点为单位，每个结点有一个或多个CPU专用的高性能互联网络连接（Myrinet,Infiniband,…）分布式存储：内存模块局部在每个结点中单一的操作系统单一的内存地址空间：所有内存模块都由硬件进行了统一的编址，各个结点既可以直接访问局部内存单元，又可以直接访问其他结点的局部内存单元可扩展到上百个结点支持消息传递、共享存储并行程序设计21并行计算机的发展90年代：体系结构框架趋于统一DSM（DistributedSharedMemory）分布式共享存储22并行计算机的发展90年代：体系结构框架趋于统一MPP（MassivelyParallelProcessing）大规模并行处理结构每个结点相对独立，有一个或多个微处理器每个结点均有自己的操作系统各个结点自己独立的内存，避免内存访问瓶颈各个结点只能访问自己的内存模块扩展性较好DM-MPP分布式存储MPP：每个结点仅包含一个微处理器SMP-MPP：每个结点是一台SMP并行机DSM-MPP：每个结点是一台DSM并行机23并行计算机的发展MPP体系结构示意图90年代：体系结构框架趋于统一24并行计算机的发展90年代：体系结构框架趋于统一NOW（NetworkofWorkstations）工作站机群投资风险小、结构灵活、可扩展性强、通用性好、异构能力强，被大量中小型计算用户和科研院校所采用每个结点安装消息传递并行程序设计软件，实现通信、负载平衡等每个结点都是一个完整的工作站，有独立的硬盘与UNIX系统结点间通过低成本的网络（如千兆以太网）连接也称为COW（ClusterofWorkstations）NOW（COW）与MPP之间的界线越来越模糊25并行计算机的发展NOW的典型代表：Beowulfcluster微机机群性能价格比极高90年代：体系结构框架趋于统一26并行计算机的发展第一台Beowulf机群27并行计算机的发展2000年至今：前所未有大踏步发展Cluster机群Constellation星群每个结点含多个商用处理器，结点内部共享存储采用商用机群交换机通过前端总线连接结点，结点分布存储各个结点采用Linux操作系统、GNU编译系统和作业管理系统每个结点是一台子并行机采用商用机群交换机通过前端总线连接结点，结点分布存储各个结点运行专用的结点操作系统、编译系统和作业管理系统MPP专用高性能网络，大多为政府直接支持28并行计算机的发展并行计算机发展趋势由于向量机和MPP受研制费用高、售价高等因素的影响，其市场受到一定的限制SMP由于共享结构的限制，系统的规模不可能很大由于机群系统具有投资风险小、可扩展性好、可继承现有软硬件资源和开发周期短、可编程性好等特点，目前已成为并行处理的热点和主流2011年4月动物食物链29/192011年4月1984年的计算机食物链MainframeVectorSupercomputerMiniComputerWorkstationPC30/192011年4月1994年的计算机食物链MainframeVectorSupercomputerMPPWorkstationPCMiniComputer(hittingwallsoon)(futureisbleak)31/192011年4月现在和未来的计算机食物链32/19并行计算的研究现状并行计算的硬件平台(即并行计算机)并行计算的软件支撑(即并行程序设计)并行计算的理论基础(即并行算法)以及并行计算的具体应用并行计算的研究现状并行计算的结构部分包含了高端的高性能计算机和低端的普及型计算机；并行计算的算法部分包含了并行算法的设计与分析以及算法库和测试库；并行计算的编程部分包含了并行编程模型以及并行编程的环境工具；并行计算的应用部分包含了科学工程应用和各种新型的应用.并行计算的研究现状并行计算研究内容研究内容并行计算机的体系结构并行算法设计与分析并行实现技术：编程实现，优化性能并行应用：开发并行应用软件并行计算需要解决的关键问题近年来并行算法本身的研究呈现低调的局面。大部分的并行应用的效率依然较低，无法高效的使用并行计算机的资源。并行编程语言对于一般的编程人员还不够简单易行，也缺乏高效的并行编程环境工具。并行计算机本身的构建也存在着能耗过大、管理困难、可扩展性差等方面的问题。并行计算的性能分析1、加速比（speedup)是同一个任务在单处理器系统和并行处理器系统中运行消耗的时间的比率，用来衡量并行系统或程序并行化的性能和效果。speedup是加速比，T1是单处理器下的运行时间，Tn是在有n个处理器并行系统中的运行时间。1/(1)1/(/)PPNS1Nspeedup=T/T并行计算的性能分析2、并行效率云计算云计算就是通过网络将庞大的计算处理程序自动分拆成无数个较小的子程序，再交由多部服务器所组成的庞大系统经搜寻、计算分析之后将处理结果回传给用户。计算换通信并行计算基础知识40/66云计算是互联网赐予的礼物云的维度云的规模（目录服务、搜索服务、机器学习）云强化人的社交与专业互动云需要更智能的设备云推动服务器的进步反之亦然计算换通信并行计算基础知识41/66云计算时代的来临Google的云计算由分布式文件系统GoogleFileSystem(GFS)、大规模分布式数据库BigTable、程序设计模式MapReduce、分布式锁机制Chubby等几个相互独立又紧密结合的系统组成，如图所示Google云计算架构。43/20Google的云计算基础设施44/20Google的云计算基础设施计算换通信并行计算基础知识45/66MapReduce处理流程47/202019/12/20Datastore1Datastorenmap(key1,values...)(key2,values...)(key3,values...)map(key1,values...)(key2,values...)(key3,values...)Inputkey*valuepairsInputkey*valuepairs==Barrier==:Aggregatesintermediatevaluesbyoutputkey