[理学]并行计算基础知识课件(PPT 55页)

1、第一章 并行计算基础知识第1页，共55页。第一章 并行计算基础知识1.1 并行计算的主要研究目标和内容 1.1.1 并行计算的定义 1.1.2 并行计算的研究内容 1.1.3 并行计算的应用范围 1.1.4 并行计算的应用分类1.2 并行计算机发展历史 1.2.1 并行计算机发展简述 1.3 并行计算机体系结构 1.3.1 并行计算机体系结构的要素 1.3.2 并行计算机的类型2第2页，共55页。1.1 并行计算的主要研究目标 和内容第3页，共55页。1.1.1并行计算的定义并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统，它是将多个处理

2、器（可以几个、几十个、几千个、几万个等）通过网络连接以一定的方式有序地组织起来（一定的连接方式涉及网络的互联拓扑、通信协议等，而有序的组织则涉及操作系统、中间件软件等）。并行计算的主要目的：一是为了提供比传统计算机快的计算速度；二是解决传统计算机无法解决的问题。 4第4页，共55页。1.1.2并行计算的研究内容 并行计算的研究内容广泛，包括并行计算机系统结构、并行算法设计、并行编程环境等，具体表现在下面几个方面：(1)并行计算机的设计包括本并行计算机的结构设计、互联拓扑、网络通信等。设计并行计算机重要的一点要考虑处理机数目的按比例增长（即可扩展性）及支持快速通信及处理机间的数据共享等。5第5页

3、，共55页。1.1.2并行计算的研究内容 (2)有效算法的设计如果没有有效的并行算法，并行计算机无法使用，而并行算法的设计完全不同于串行算法的设计，不同的并行计算机的算法设计不同，只有将不同的并行计算机与不同的实际问题相结合，才能设计出有效的并行算法。主要研究内容包括并行计算模型、并行算法的一般设计方法、基本设计技术和一般设计过程，并讨论一些数值并行算法与非数值并行算法的设计。 6第6页，共55页。1.1.2并行计算的研究内容 (3)评价并行算法的方法对于给定的并行计算机及运行在上面的并行算法，需要评价运行性能。性能分析需解决的问题：如何利用基于并行计算机及其相适应的并行算法去快速地解决问题，

4、及如何有效地利用各个处理器。研究内容包括结合机器与算法，提出相应的性能评测指标，为设计高效的并行算法提供依据。7第7页，共55页。1.1.2并行计算的研究内容 (4)并行计算机语言与传统的机器语言不同，并行计算机语言依赖于并行计算机，并行计算机语言必须简洁，编程容易，可以有效地实现，目前的语言有：PVM、MPI、HPF等，而且新的编程语言和编程模式正在不断地出现。 8第8页，共55页。1.1.2并行计算的研究内容 (5)并行编程环境与工具为了使编程容易，必须开发综合的编程环境与工具，且能达到两个目的：并行计算机的底层机构对用户透明；为用户提供设计与开发程序所需要的调试器与模拟器等工具。9第9页

5、，共55页。1.1.2并行计算的研究内容 (6)并行程序的可移植性 可移植性为并行程序设计的主要问题，要求在一台并行机上开发的程序不加修改或进行少量修改即可在另一台计算机上运行。这一点为目前受到了广泛关注的重要课题。(7) 并行计算机的自动编程可否设计一个并行化编译器，使用户的串行程序通过并行化编译器编译，直接可在并行机上运行。到目前为此，这种编译器还不存在，而仅有一些半自动并行化编译器。10第10页，共55页。1.1.3 并行计算的应用范围 并行计算在许多计算机应用领域都产生了巨大的影响，使原来无法解决的应用问题成为可能。 天气预报、卫星数据处理、石油数据处理（连续优化问题），调度问题、平面

6、性问题及VLSI设计（离散优化问题）、生物工程、医药研究、飞机制造、汽车设计、环境保护等领域。11第11页，共55页。1.1.4并行计算的应用分类 科学与工程计算对并行计算的需求是十分广泛的，但所有的应用可概括为三个方面：（1）计算密集型（Compute-Intensive）这一类型的应用问题主要集中在大型科学工程计算与数值模拟（气象预报、地球物理勘探等） 12第12页，共55页。1.1.4并行计算的应用分类 （2）数据密集型 (Data-Intensive)Internet的发展，为我们提供了大量的数据资源，但有效地利用这些资源，需要进行大量地处理，且对计算机的要求也相当高，这些应用包括数字

7、图书馆、数据仓库、数据挖掘、计算可视化。（3）网络密集型 (Network-Intensive)通过网络进行远距离信息交互，来完成用传统方法不同的一些应用问题。如协同工作、遥控与远程医疗诊断等。13第13页，共55页。1.2 并行计算机发展历史第14页，共55页。1.2.1 并行计算机发展简述 40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。创建和使用并行计算机的主要原因是因为并行计算机是解决单处理器速度瓶颈的最好方法之一。 15

8、第15页，共55页。1.2.1 并行计算机发展简述并行计算机是由一组处理单元组成的，这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。 16第16页，共55页。1.2.1 并行计算机发展简述 60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现，这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机（Mainfr

9、ame）。IBM 360是这一时期的典型代表。 17第17页，共55页。1.2.1 并行计算机发展简述 到了60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。 18第18页，共55页。1.2.1 并行计算机发展简述1972年，诞生了第一台并行计算机ILLIAC (Illinois Integrator and Automatic Computer) 伊利诺斯(理工学院)积分仪和自动计算机。它由Illinois 大学和Burrouphs公司合作研制成功的。运算速度为1.5亿次/秒 (

10、1.5*108次/秒)由64台处理器组成的阵列机(Array Computer)可对数组进行并行计算它是当时性能最高的 CDC 7600 机器速度的26倍。19第19页，共55页。1.2.1 并行计算机发展简述从80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP 方式的总线协议，而伯克利加州大学则对总线协议进行了扩展，提出了Cache一致性问题的处理方案。从此，共享存储多处理器之路越走越宽；现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。 同一时期，基于消息传递机制的并行计算机也开始不断涌现。80年代中期，加州理工成功地将64个i8086/i8087处理器通过超立

11、方体互连结构连结起来。此后，便先后出现了Intel iPSC系列、INMOS Transputer 系列、Intel Paragon 以及IBM SP 的前身Vulcan等基于消息传递机制的并行计算机。 20第20页，共55页。1.2.1 并行计算机发展简述 80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM 将大量早期RISC微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性（Scalability）。90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布

12、式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。 21第21页，共55页。1.2.1 并行计算机发展简述 90年代以来，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息；CRAY T3D是一台NUMA结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。 22第22页，共55页。1.3 并行计算机体系结构第23页，共55页。结点（node）：包含一个或多个CPU，这些CPU通过HUB或全互联交叉开关相互联接，并共享内存，也可以直接与外部

13、进行I/O操作。 互联网络（interconnect network）：所有结点通过互联网络相互连接相互通信。内存（memory）：内存由多个存储模块组成，这些模块可以与结点对称地分布在互联网络的两侧，或者位于各个结点的内部。1.3.1 并行计算机体系结构的要素24第24页，共55页。结点是构成并行机的最基本单位。一个结点包含2 个或2 个以上微处理器（CPU），并行程序执行时，程序分派的各个进程将并行地运行在结点的各个微处理器上。每个微处理器拥有局部的二级高速缓存（L2 cache）。L2 cache 是现代高性能微处理器用于弥补日益增长的CPU 执行速度和内存访问速度差距（访存墙）而采取的

14、关键部件。它按cache 映射策略缓存内存访问的数据，同时为CPU 内部的一级cache 提供计算数据。CPU 内部的一级cache为寄存器提供数据，寄存器为逻辑运算部件提供数据。1.3.1 并行计算机体系结构的要素25第25页，共55页。随着处理器速度的日益增长，结点内配置的内存容量也在增长。传统地，1 个单位的浮点运算速度配1 个字节的内存单元，是比较合理的。但是，考虑到日益增长的内存墙的影响，这个比例可以适当缩小。例如，1 个单位的浮点运算速度配0.4 个字节的内存单元。如果以单个微处理器速度为每秒60 亿次计算，包含4 个处理器的单结点的峰值运算速度可达240 亿次，内存空间需要8GB

15、 以上。于是，在当前并行机的结点内，一般需要采用64 位的微处理器，才能操作如此大的内存空间。1.3.1 并行计算机体系结构的要素26第26页，共55页。互联网络是连接所有结点成并行机的高速网络。对于一般的并行机使用者，无须知道互联网络底层复杂的通信原理，而只需从拓扑结构的角度了解互联网络。互联网络的拓扑结构可用无向图表示。其中，图中的结点唯一地代表并行机的各个结点，图中的边表示在两个端点代表的并行机结点之间，存在直接连接的物理通信通道。1.3.1 并行计算机体系结构的要素27第27页，共55页。拓扑结构的几个重要定义： 并行机规模：并行机包含的结点总数，或者包含的CPU总数； 结点度：互联网

16、络拓扑结构中联入或联出的一个结点的边的条数，称为该结点的度； 结点距离：两个结点之间跨越的图的边的条数； 网络直径：网络中任意两个结点之间的最长距离； 点对点带宽：图中边对应的物理联接的物理带宽； 点对点延迟：图中任意两个结点之间的一次零长度消息传递必须花费的时间。延迟与结点间距离相关，其中所有结点之间的最小延迟称为网络的最小延迟，所有结点之间的最大延迟称为网络的最大延迟； 折半宽度：对分网络成两个部分（它们的结点个数至多相差1）所必须去掉的边的网络带宽的总和； 总通信带宽：所有边的带宽之和； 1.3.1 并行计算机体系结构的要素28第28页，共55页。互联网络评价： 大：结点度、点对点带宽、

17、折半宽度、总通信带宽； 小：网络直径、点对点延迟； 1.3.1 并行计算机体系结构的要素29第29页，共55页。按结点间连接的性质，拓扑结构可分为静态拓扑结构、动态拓扑结构和宽带互联网络三类。静态拓扑结构：结点之间存在固定的物理联接方式，程序执行过程中，结点间的点对点联接关系不变。动态拓扑结构：结点之间无固定的物理联接关系，而是在联接路径的交叉点处用电子开关、路由器或仲裁器等提供动态联接的特性，主要包含单一总线、多层总线、交叉开关、多级互联网络。宽带互联网络：当前，除了专用MPP 系统采用静态的拓扑结构外，微机机群均采用宽带互联网络连接各个计算结点。1.3.1 并行计算机体系结构的要素30第3

18、0页，共55页。Flynn(1966年)分类法是根据系统的指令流和数据流对计算机系统进行分类的一种方法。指令流：机器所执行的指令序列数据流：指令流调用的数据序列（包括输入数据和中间结果）SISD (Single Instruction stream Single Data stream)SIMD (Single Instruction stream Multiple Data stream)MISD (Multiple Instruction stream Single Data stream)MIMD (Multiple Instruction stream Multiple Data st

19、ream)1.3.2 并行计算机的类型31第31页，共55页。SISD：传统的单处理机系统。由程序生成的一个单指令流，在任意时刻处理单独的数据项。SIMD：如：阵列处理机系统(Processor Arrays)。由一个控制器负责从存储器中取出指令并将这些指令发送给各个处理器，每个处理器同步执行相同的指令，但操作不同的数据。MISD：相当于在指令一级并行，而在被操作的数据级串行的情况，实际上这种模型是不能实现的。1.3.2 并行计算机的类型32第32页，共55页。MIMD：当今绝大多数并行计算机都属于这一类。每个处理器拥有一个单独的程序，每个程序为每一个处理器生成一个指令流，每条指令对不同的数据

20、进行操作。Flynn分类法实际上并不能对所有计算机进行分类，如流水线向量处理机就难于按Flynn分类法简单地归为上述四类之一。并行计算机系统除少量专用的SIMD系统外，绝大部分为MIMD系统。1.3.2 并行计算机的类型33第33页，共55页。进程：具有一定功能的一段程序的一次运行活动。进程的并行执行方式分为以下几种：MPMD (Multiple Programs & Multiple Data) 控制并行结构：在这种并行结构中各进程执行的程序不同，操作的数据也不同。各进程既可以是异步执行的，也可以以同步方式执行。SPMD (Single Program & Multiple Data) 数据

21、域并行结构：在分布存储并行计算机系统上执行的程序，每个进程执行相同的程序，但处理不同的数据。1.3.2 并行计算机的类型34第34页，共55页。在SPMD 程序设计中，所有节点机得到相同的程序副本，但程序中可以含有条件语句来决定哪个节点机执行某段程序与否。SPMD并行结构常用于主从结构并行机中从节点机中。1.3.2 并行计算机的类型35第35页，共55页。1.3.2 并行计算机的类型（1）并行向量处理机 (Parallel Vector Processors PVP)1976年，出现了具有实用价值的向量处理机Cray-1单处理机，多向量寄存器模式运算速度： 3160M flops平均速度： 2

22、080M flops向量点积速度： 22M flops利用大量的向量寄存器快速地实现向量运算1985年，Cray Inc.推出Cray-2 超级计算机，该机的向量处理速度是Cray-1的12倍 (1G flops)36第36页，共55页。PVP结构模型VPVPVP交叉开关SMSMSMVP: Vector Processor SM: Shared Memory37第37页，共55页。1.3.2 并行计算机的类型典型的PVP机型80年代中、后期是PVP的时代，有很多PVP相继问世，如：Convex公司的C3800系列DEC公司的 VAX 9000IBM公司的IBM 390/VFFujitsu公司的

23、VP 2000Cray公司的 YMP-9038第38页，共55页。1.3.2 并行计算机的类型（2）对称多处理机 (Symmetric Multiprocessor SMP)将各处理器经由高速总线（或交叉开关）与共享存储器相连每个处理器对共享存储器具有同等的访问权利每个处理器对I/O设备和其它系统资源享有同等的访问权利在SMP系统中一般要求每个处理机是相同的 因此称之为对称多处理机39第39页，共55页。对称多处理机结构模型P/C总线或交叉开关SMSMSMP/CP/CP/C: Processor/Cache SM: Shared Memory40第40页，共55页。1.3.2 并行计算机的类型

24、典型SMP机型SGI公司的SGI Onyx系统和SGI Power ChallengeSequent Computer System, Inc.的Sequent Symmetry S-81系统IBM公司的ES/9000系统和R50Sun公司的SparcCenter 2000我国的曙光1号41第41页，共55页。1.3.2 并行计算机的类型（3）大规模并行处理机 (Massively Parallel Processors MPP)采用松耦合体系结构连接各种不同的处理器 即各处理器以使用自己的局部内存为主，处理器之间进行同步通信实现数据交换42第42页，共55页。大规模并行处理机结构模型LM1L

25、M2LMnP/C1P/C2P/Cn专用互连网络P/C: Processor/Cache LM: Local Memory43第43页，共55页。1.3.2 并行计算机的类型MPP的优点：突破了只看到一个统一的存储空间的方式具有良好的可扩展性MPP的缺点：分布存储要求用户必须将被操作的数据分配到各局部存储器中运算过程中用户要考虑数据在各节点间的传送和同步44第44页，共55页。1.3.2 并行计算机的类型典型的MPP机型：Intel公司的Paragon XP/SMasPar公司的MP-2Thinking Machine公司的CM-5IBM公司的SP 2Cray公司的Cray T3D我国的曙光 1

26、00045第45页，共55页。1.3.2 并行计算机的类型（4）分布式共享存储多处理机系统 (Distributed Shared Memory DSM)DSM系统具有以下特点：存储器在物理上分布于各处理器附近，但在逻辑上可由多个处理器共享整个内存DSM系统实际上是SMP和MPP结构的折中46第46页，共55页。分布式共享存储多处理机系统LM1LM2LMnP/C1P/C2P/Cn专用互连网络47第47页，共55页。1.3.2 并行计算机的类型DSM的优点：避免了集中式存储结构中处理器和存储器的复杂连接有良好的可扩展性相对MPP来说，更容易编程DSM系统需着重考虑的问题：系统应具有维持存储器访问一致性的硬件支持相对SMP系统来说，其访问非物理局部存储器的时间要更长。48第48页，共55页。1.3.2 并行计算机的类型典型的DSM机型：Cray公司的Cray T3ESGI/Cray公司的Origon 2000BBN公司的TC