第20讲 并行计算

并行计算1并行计算介绍

什么是并行计算基本概念并行计算机的发展我国并行计算机的发展情况当前最快的超级计算机并行计算机体系结构并行算法2并行计算传统的软件是为串行计算机而编写的:在只有一个处理器的单台计算机上运行

把一个问题分解成离散的指令序列

指令被一条条的顺序执行任何时候只有一条指令在执行3并行计算的应用需求

数值天气预报全球气象中期天气预报要求在24

小时内完成48

小时天气预测数值模拟，至少需635

万个网格点，内存需求大于1T，计算性能高达25

万亿次/秒.

核武器数值模拟美国1996年实施的ASCI计划，分四个阶段实现万亿次、十万亿次、30万亿次和100万亿次大规模并行数值模拟，实现全三维、全物理过程、高分辨率的核武器数值模拟.并行计算能力已成为衡量一个国家综合实力的重要标志之一！4并行计算机系统的应用领域数学基因信息气象预报生物物理石油勘探信息服务汽车制造船舶制造5并行计算并行计算（高性能计算、超级计算）大任务分解多个子任务不同处理单元分

给快速求解协同合作基本条件：

硬件（并行机）、并行算法设计、并行编程环境主要目标：提高求解速度，扩大问题规模6串行计算与并行计算78组成并行计算机的各个部分：节点（node）互联网络（interconnectnetwork）内存（memory）内存模块与节点分离内存模块位于节点内部并行计算8并行计算介绍什么是并行计算基本概念并行计算机的发展我国并行计算机的发展情况当前最快的超级计算机弗林经典分类并行计算机体系结构并行算法9弗林根据指令和数据这两个独立维度的情况，对多处理器计算机结构进行了如下分类SISD单指令流单数据流SIMD单指令流多数据流MISD多指令流单数据流MIMD多指令流多数据流基本概念10单指令流单数据流(SISD)一个串行(非并行)计算机

单指令流:在任何一个时钟周期，CPU中只有一个指令流在活动。单数据流:在任何一个时钟周期，只有一个数据流作为输入在被使用。执行结果是确定的。从很早一直到现在，这都是计算机的最主要的形式。基本概念11单指令流多数据流(SIMD)并行计算机的一种

。单指令流:在任何一个时钟周期，CPU中只有一个指令流在活动。多数据流:每个处理单元能在不同的数据元素上进行操作。最适合具有高度规律性的特殊的问题，比如图像处理。同步（步调一致）和确定的执行两种类型:处理器阵列和向量流水线基本概念12多指令流单数据流(MISD)单一的数据流流入多个处理器单元去处理每个处理器单元通过独立的指令流对数据进行处理这种类型的并行计算机很少有存在的例子，有一个实验室的产品是卡内基梅陇大学的C.mmp计算机(1971)。

一些想象中的可能应用：

多种频率的滤波器处理同一个信号流用多个密码算法尝试解开一个编码信息。基本概念13多指令流多数据流(MIMD)目前最常用的并行计算机。大多数现代计算机属于这一类多指令流:每个处理器可以执行不同的指令流多数据流:每个处理器可以工作在不同的数据流上执行可以是同步的或者异步的，确定的或者不确定的举例:很多目前的巨型计算机、网络并行计算机“网格”、多处理器SMP计算机以及多核处理器。基本概念14基本概念15并行计算机存储结构多级存储体系结构为了解决存储墙（memorywall）性能瓶颈问题。在节点内部的cache称为二级cache（L2cache）。在处理器内部更小的cache成为一级cache(L1cache)L1cache连接CPU寄存器和L2cache，负责缓存L2cache中的数据到寄存器中。1616微处理器的多级存储结构

微机机群的一次消息传递延迟相当于

50000次峰值浮点运算17微处理器的多级存储结构

微处理器主频越来越高，内存容量越来越大，

但内存访问速度的增长较慢

缓解内存墙性能瓶颈：Cache高速缓存18并行计算机体系结构并行计算机体系

结构示意图

内存模块与结点分离并行计算机体系

结构示意图

内存模块位于

结点内部19并行计算机存储结构多级存储体系结构Cache的映射策略指的是内存块和cache行之间如何建立相互映射关系。直接映射策略（directmappingstrategy）每个内存块只能被唯一的映射到一条cache行中K－路组相联映射策略（K-waysetassociationmappingstrategy）Cache被分解为V个组，每个组由K个cache行组成，内存块按直接映射策略映射到某个组，但在该组中，内存块可以被映射到任意一个cache行。全相联映射策略（fullassociationmappingstrategy）内存块可以被映射到cache中的任意一个cache行。20并行计算机存储结构分布式存储MEMORYNODEMEMORYNODEMEMORYNODEMEMORYNODEnetworkNODE（节点）=单处理器或多处理器21并行计算机存储结构分布式存储-NORMA(No-RemoteMemoryAccess)节点有它们自己的局部存储器。一个节点内的存储器地址不会映射到其他节点上，所以在全部节点中没有全局地址空间的概念。因为每一个节点有它自己局部存储器它们独立地操作。因此Cache一致性的概念不存在。当一个节点需要存取另一个节点的数据（很少见），通常要程序员明确提供如何以及何时数据被传送的信息。22并行计算机存储结构分布式存储优点增加节点数，就自然成比例地增加了存储容量.每个节点能快速地存取它自己的存储器而无需干涉也没有试图保持Cache一致性的开销。成本效率:可以用商业化的，现成的处理器和网络。缺点

如果数据在两个节点间传送，就要求程序员提供很多有关数据传送的细节。很难将现在基于全局存储的已有数据结构映射到这种存储组织中。非均匀内存访问(NUMA)时间

23并行计算机存储结构共享存储NODEMEMORYNODE（节点）=单处理器或多处理器NODENODENODE24并行计算机存储结构共享存储共享存储的并行计算机千差万别，但都能够使所有的节点以全局地址空间的形式访问全部的存储器空间。多个节点可以独立操作但又可共享相同的存储资源。在一个节点上改变一个存储位置的值对其他节点来说也是可见和可用的。25并行计算机存储结构共享存储均匀存储访问(UMA):存储器和节点分离物理存储器能够通过互联网络被所有节点共享。发生访存竞争时，仲裁策略平等对待每个节点，即每个节点机会均等；外围I/O设备也可以共享，且每个节点有平等的访问权利。最常见的代表是当前的对称多处理器机器(SMP)26并行计算机存储结构共享存储均匀存储访问(UMA):所有节点访问任意存储单元的时间相同；各节点的CPU可带有局部私有高速缓存；互联网络可以是单总线、多总线或者交叉开关。

有时候称为CC-UMA–Cache一致性UMA.Cache一致性意味着如果一个处理器修改了共享存储器中的某个位置的数，其他的所有处理器都知道这个改变。Cache的一致性在硬件一级完成。27network并行计算机存储结构分布式共享存储器(DSM)NODENODEMEMORYNODENODENODENODEMEMORYNODENODENODENODEMEMORYNODENODENODENODEMEMORYNODENODENODE（节点）=单处理器或多处理器28并行计算机存储结构分布式共享存储器(DSM)共享存储器部分通常是一个Cache一致性的SMP机器。在给定的SMP中的处理器，能够以全局方式寻址这个机器的存储器。分布式存储部分是多个SMP联网。SMP只知道它们自己的存储器-不是在其他SMP上的存储器。因此，需要网络通信来将数据从一个SMP移动到另一个。目前的趋势似乎表明这种类型的存储结构将继续盛行，并将在高端计算机上得到增强。29并行计算机存储结构分布式共享存储器(DSM)非均匀存储访问(NUMA)每个节点都有共享存储的一部分（局部存储器）存储器只有一个地址空间任何节点都可以实际地址直接访问任何存储器每个节点都可以有局部Cache不是所有的节点能够以相同的时间访问所有的存储器，访问时间与该存储器到该节点的距离有关。跨链接的存储访问比较慢如果保持Cache一致性，它也可以称为CC-NUMA–Cache一致性NUMA3031并行计算机存储结构分布式共享存储器全高速缓存存储访问(COMA):每个节点拥有共享存储的一部分。然而，这次共享存储器是由Cache组成的。没有层次性存储，地址空间是针对Cache的。有一个Cache目录来帮助远程Cache访问。需要将数据转移到需要它的节点上。3132并行计算机存储结构分布式共享存储器优点全局地址空间提供一个用户友好的访存编程方式。由于节点与内存接近，任务间的数据共享快速统一缺点

增加一些节点会使得存储器到节点的路径的拥挤程度成几何增大。对于cache一致性系统，增加更多的节点会使得与cache/存储器管理相关联的冲突成几何增长。程序员的责任就是能确保全局存储的正确访问的同步结构。32并行计算机系统架构33以动物的食物链为例并行计算机系统架构34并行计算机系统架构35对称多处理机系统(SMP)SMP对称式共享存储:任意处理器可直接访问任意内存地址,且访问延迟、带宽、机率都是等价的;系统是对称的；微处理器:一般少于64个;处理器不能太多,总线和交叉开关的一旦作成难于扩展；例子:IBMR50,SGIPowerChallenge,SUNEnterprise,36分布式共享存储系统(DSM)DSM分布共享存储:内存模块物理上局部于各个处理器内部,但逻辑上(用户)是共享存储的;这种结构也称为基于Cache目录的非一致内存访问(CC-NUMA)结构;局部与远程内存访问的延迟和带宽不一致;与SMP的主要区别：DSM在物理上有分布在各个节点的局部内存从而形成一个共享的存储器；微处理器:16-128个;代表:SGIOrigin2000,CrayT3D;37大规模并行计算机系统(MPP)MPP物理和逻辑上均是分布内存能扩展至成百上千个处理器(微处理器或向量处理器)采用高通信带宽和低延迟的互联网络(专门设计和定制的)一种异步的MIMD机器；程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用；代表:CRAYT3E(2048),ASCIRed(3072),IBMSP238机群系统(Cluster)Cluster每个节点都是一个完整的计算机各个节点通过高性能网络相互连接网络接口和I/O总线松耦合连接每个节点有完整的操作系统曙光2000、3000、4000,ASCIBlueMountain39并行计算机的发展始于70年代

1946年第一台计算机ENIAC

（ElectronicNumericalIntegratorAndComputer）占地170平方重约30吨

5000次加法/秒

或500次乘法/秒

15分钟换一个零件主要用于弹道计算

和氢弹研制40并行计算机的发展始于70年代

1972年第一台并行计算机ILLIACIV（伊利诺依大学）60年代末开始建造

72年建成,74年运行

第一个完整程序,

76年

运行第一个应用程序

64个处理器，是当时

性能最高的CDC7600

机器的2-6倍公认的1981年前最快1982年退役可扩展性好，

但可编程性差41并行计算机的发展始于70年代向量机Cray-1

一般将Cray-1投入

运行的1976年称为

“超级计算元年”编程方便，

但可扩展性差以Cray为代表的

向量机称雄超级

计算机界十几载收藏于DeutschesMuseum德意志

博物馆的Cray-1原型42并行计算机的发展

80年代百家争鸣早期：以MIMD并行计算机的研制为主

DenelcorHEP

（1982年）第一台商用MIMD并行计算机

CrayX-MP

Cray研究公司第一台MIMD并行计算机

IBM309080

年代普遍为银行所采用西摩•克雷SeymourCray(1925-1996)，

电子工程学学士，应用数学硕士，

超级计算机之父，Cray研究公司的创始人，

亲手设计了Cray机型的全部硬件与操作系统，

作业系统由他用机器码编写完成。1984年时，

公司占据了超级计算机市场70%的份额。

1996年Cray研究公司被SGI收购，2000年被

出售给Tera计算机公司，成立Cray公司。43并行计算机的发展

80年代百家争鸣中期：共享存储多处理机Shared-MemoryMultiProcessor

SMP

(SymmetricalMulti-Processing)：在一个计算机上汇集一组处理器，各处理器对称共享内存及计算机的其他资源，由单一操作系统管理，极大提高整个系统的数据处理能力。

扩展性较差可靠性较差内存访问瓶颈44并行计算机的发展

80年代百家争鸣后期：具有强大计算能力的并行机

通过二维Mesh连接的Meiko（Sun）系统

超立方体连接的MIMD并行机：nCUBE-2、iPSC/80共享存储向量多处理机CrayY-MP

······45并行计算机的发展

90年代：体系结构框架趋于统一(DSM、MPP、NOW)

DSM（DistributedSharedMemory）分布式共享存储以结点为单位，每个结点有一个或多个CPU专用的高性能互联网络连接（Myrinet,Infiniband,…）分布式存储：内存模块局部在每个结点中单一的操作系统单一的内存地址空间：所有内存模块都由硬件进行了统一的编址，各个结点既可以直接访问局部内存单元，又可以直接访问其他结点的局部内存单元可扩展到上百个结点支持消息传递、共享存储并行程序设计46并行计算机的发展

90年代：体系结构框架趋于统一

DSM（DistributedSharedMemory）分布式共享存储47并行计算机的发展

90年代：体系结构框架趋于统一

MPP（MassivelyParallelProcessing）大规模并行处理结构

每个结点相对独立，有一个或多个微处理器每个结点均有自己的操作系统各个结点自己独立的内存，避免内存访问瓶颈各个结点只能访问自己的内存模块扩展性较好

DM-MPP分布式存储MPP：每个结点仅包含一个微处理器

SMP-MPP：每个结点是一台SMP并行机

DSM-MPP：每个结点是一台DSM并行机48并行计算机的发展

MPP体系结构示意图

90年代：体系结构框架趋于统一49并行计算机的发展

90年代：体系结构框架趋于统一

NOW（NetworkofWorkstations）工作站机群投资风险小、结构灵活、可扩展性强、通用性好、异构能力强，被大量中小型计算用户和科研院校所采用每个结点安装消息传递并行程序设计软件，实现通信、负载平衡等每个结点都是一个完整的工作站，有独立的硬盘与UNIX系统结点间通过低成本的网络（如千兆以太网）连接也称为COW（ClusterofWorkstations）

NOW（COW）与MPP之间的界线越来越模糊50并行计算机的发展

NOW的典型代表：Beowulfcluster微机机群性能价格比极高

90年代：体系结构框架趋于统一51并行计算机的发展第一台Beowulf机群52并行计算机的发展

2000年至今：前所未有大踏步发展

Cluster机群

Constellation星群每个结点含多个商用处理器，结点内部共享存储

采用商用机群交换机通过前端总线连接结点，结点分布存储各个结点采用Linux操作系统、GNU编译系统和作业管理系统每个结点是一台子并行机采用商用机群交换机通过前端总线连接结点，结点分布存储各个结点运行专用的结点操作系统、编译系统和作业管理系统

MPP专用高性能网络，大多为政府直接支持53并行计算机的发展并行计算机发展趋势由于向量机和MPP

受研制费用高、售价高等因素的影响，其市场受到一定的限制

SMP

由于共享结构的限制，系统的规模不可能很大由于机群系统具有投资风险小、可扩展性好、可继承现有软硬件资源和开发周期短、可编程性好等特点，目前已成为并行处理的热点和主流54并行计算介绍什么是并行计算并行计算机的发展我国并行计算机的发展情况当前最快的超级计算机并行计算机体系结构操作系统与并行计算编程环境并行算法55我国高性能计算机的发展

1958年第一台国产计算机

－－103型计算机运行速度每秒1500次第一台计算机56我国高性能计算机的发展

1983年12月，我国第一台每秒钟运算达1亿次以上的计算机“银河I”问世

1992年“银河-II”问世，每秒运算达10亿次

1997年成功研制百亿次并行机“银河-III”，由130多个处理结点组成超级计算机曙光（曙光信息产业有限公司

）深腾（联想集团）银河神威军事部门57我国高性能计算机的发展

1999年9月，由国家并行计算机工程技术研究中心牵头研制成功的“神威”计算机系统投入运行。2000年，“神威I”面向社会开放使用。“神威I”的峰值速度为每秒3840亿次浮点运算神威

I58我国高性能计算机的发展

1993年10月研制成功“曙光一号”SMP多处理机

2000年推出每秒3000亿次的曙光3000超级服务器

2004年6月，推出11万亿次的曙光4000A超级计算机，落户上海超算中心，进入全球前十名，从而使中国成为继美国和日本之后，第三个能研制10万亿次高性能计算机的国家

2008年6月，曙光5000A发布，实际运算速度超过每秒160万亿次，排名世界第十曙光5000A59我国高性能计算机的发展

2002年，联想发布深腾1800计算机，排名全球第43位，成为首家正式进入排行榜前100的中国企业

2003年，深腾6800计算机发布，列全世界TOP500第14位，其78.5%的整机效率列世界通用高端计算机第一名

2008年12月，联想发布百万亿次超级计算机深腾7000深腾700060并行计算介绍什么是并行计算并行计算机的发展我国并行计算机的发展情况当前最快的超级计算机并行计算机体系结构操作系统与并行计算编程环境并行算法61当前高性能计算机

Top500：2007年11月排名第一的

IBMBlueGene/L由212992

个处理器构成，内存为73728G

理论峰值为596378

GFlops测试峰值478200

GFlops

2008年06月排名第二62当前高性能计算机63当前高性能计算机64当前高性能计算机

并行机类型Architecturesharefor06/200965当前高性能计算机

并行机采用的操作系统OperatingsystemFamilysharefor06/200966当前高性能计算机

并行机采用的网络链接67

并行计算机发展趋势68国内高性能计算机

Top100inChina：http:///曙光公司中国科学院计算技术研究所国家智能计算机研究开发中心国家高性能计算中心

合作伙伴：AMD、上海超级计算中心最新产品：曙光5000A（百万亿次）联想公司合作伙伴：Intel、中科院计算机网络中心（超级计算中心）最新产品：深腾7000（百万亿次）69国内超级计算中心国家高性能计算中心

国家高性能计算中心（北京）

1995年5月成立，第一个高性能计算中心

国家高性能计算中心（合肥）：1995年9月，中科大

国家高性能计算中心（成都）：1997年11月，西南交大

国家高性能计算中心（武汉）：1997年12月，华中科技

国家高性能计算中心（上海）：1998年4月，复旦大学

国家高性能计算中心（杭州）：2001年4月，浙江大学

国家高性能计算中心（西安）：2002年4月，西安交大70并行计算介绍什么是并行计算并行计算机的发展我国并行计算机的发展情况当前的超级计算机并行计算机体系结构操作系统与并行计算编程环境并行算法71操作系统与编程语言并行计算机主流操作系统：UNIX/Linux

AIX（IBM）

HPUX（HP）

Solaris（SUN）

IRIX（SGI）

Linux编程语言

Fortran77/90/95

C/C++72进程与线程进程（process）运行中的程序各个进程拥有独立的执行环境进程间通信同一台处理机或不同处理机的多个进程之间交流信息通信（消息传递）、同步、聚集线程（threads）降低系统管理开销一个进程可以含一个或多个线程73并行编程环境常见的并行编程环境消息传递、共享存储、数据并行特征消息传递共享数据数据并行典型代表

可移植性

存储方式

学习难度

可扩展性MPI，PVM

所有流行并行机

分布式存储

较难

好OpenMP

SMP，DSM

共享存储

容易

较差HPF

SMP，DSM，MPP

共享存储

偏易

一般三种并行编程环境主要特征一览74并行计算介绍什么是并行计算并行计算机的发展我国并行计算机的发展情况当前的超级计算机并行计算机体系结构操作系统与并行计算编程环境并行算法75并行算法适合在并行机上实现的算法

好的并行算法应充分发挥并行机计算机的潜在性能并行算法并行算法分类按运算对象：数值并行算法、非数值并行算法

按并行进程执行顺序：

同步并行算法、异步并行