并行计算机模型课件

并行计算机模型

1计算技术的现状

2多处理机和多计算机

3多向量机和SIMD计算机

4并行计算机的抽象模型

5可扩展的范围和设计

1计算技术的现状一、并行技术的出现二、现代并行计算机的组成涉及6个问题：1.计算问题

现实生活中对问题要求快速而精确地求解推动了计算机的广泛使用。科学技术中的数值计算问题人工智能(AI)问题2.算法和数据结构并行计算问题中的运算和通信，需要各种专门的算法和数据结构。符号处理：存在的问题

：3.硬件资源处理机、存储器和外围设备组成了计算机系统的硬件核心外围设备可以直接或通过局域网和广域网与主机相连4.操作系统管理用户程序执行过程中的资源分配和再分配。映射是一种算法结构与硬件结构相匹配的双向过程。并行操作系统的映射算法和数据结构到机器结构的映射包括处理机调度、存储器映象、处理器间的通信等。这些问题通常都与系统结构有关。5.系统软件支持

存在的问题：不能以通用和可移植方式进行并行程序设计开发并行编程环境：一种与系统结构无关的语言、编译器和软件工具。两个方向：对于开发并行语言，我们将着眼点放在语言执行的效率、对不同机器的可移植性、与现有的顺序语言的兼容性、并行性的表达和编程的简便性等上面。可以设计一种新的语言，逐步扩展现有的顺序语言。新语言有用显式高级结构描述并行性的优点，但是新语言往往与现有语言不兼容，而需要新的编译器或者通过新的步骤才能利用现有的编译器。大部分系统选用的是语言扩展方式。6.编译器支持

改进编译器有三种途径：预处理程序;预编译器;并行化编译器。预处理程序采用顺序编译器和目标计算机的低层程序库实现高级并行结构。预编译器需要程序流分析、相关性检查和有限的优化来检测并行性。联接过程的效果取决于预处理程序、预编译器、并行化编译器、加载程序和操作系统支持的功效。由于程序行为的不可预测，现有的编译器在检测所有类型的并行性时都不是完全自动或完全智能进行的。有效的方法：将编译器命令插入源代码，帮编译器做出较好的结果。这样，用户可与编译器进行交互重构程序，这已被证明对提高并行计算机性能是十分有用的。7.并行程序的设计环境

隐式并行性伊利诺依大学的DavidKuck和Rice大学的KenKennedy以及他们的合作者都已采用这种隐式并行性方法。显式并行性加州理工学院的CharlesSeitz和麻省理工学院的WilliamDaily在开发多计算机时采用了这种显式方法。总结：要使一个环境对用户更加友好，必须要有专用软件工具。一些工具是传统高级语言的并行扩展；一些则是集成环境其中包括提供不同级别的程序抽象、验证、测试、查错和调试等各种工具；性能预测和监控；辅助程序开发的可视化支持、性能测量以及计算结果的图形显示及动画表示三、计算机系统结构向高性能发展历程主要探讨顺序到并行的过程1.先行、并行性和流水线技术用先行技术预取指令可使I／E(指令读取／译码和执行)支持功能并行性的方法有两种：一种是同时使用多个功能部件；另一种是在不同处理级分别实施流水线技术。流水线指令执行、流水线算术计算和存储器存取操作。2.Flynn分类法MkhealFlynn(1972)根据指令和数据流概念提出了不同计算机系统结构的分类法。传统的顺序机被称为SISD(单指令流单数据流)计算机。向量计算机--标量和向量硬件装备，或以SIMD(单指令流多数据流)机的形式出现。并行计算机则属MIMD(多指令流多数据流)机MISD(多指令流单数据流)机在执行不同的指令流时，同一数据流通过处理机线性阵列。这种系统结构也就是所谓流水线执行特定算法的脉动阵列(Systolicarrays)。由卡内基—梅隆大学的美籍华人学者H．T．Kung于1978年提出的。这一结构是随着VLSI技术的发展和各种大运算量的信号/图象处理及科学计算的运算要求而建立起来的。例1：用脉动阵列(Systolicarray)结构计算矩阵乘脉动阵列的特点：处理单元简单流水算法专业例2：数据流计算机数据流的计算模型--试图使并行计算的基本方面在机器层显式化，而不利用有可能限制程序并行性的人为约束。它的想法是程序由一个基本数据依赖图来表示；一个指令可能在获得了它的操作数后的任意时刻被执行，不是显式控制线性程序列的固定组合。3.并行／向量计算机

真正的并行计算机是那些以MIMD模式执行程序的计算机。并行计算机有两大类，即共享存储型多处理机和消息传递型多计算机。多处理机和多计算机之间的主要差别就在于存储器共享和处理机间通信机制的不同。多处理机系统中的处理机通过公用存储器的共享变量实现互相通信。多计算机系统的每个计算机结点有一个与其它结点不共享的本地存储器。处理机之间的通信通过结点间的消息传递来实现。显式向量计算机指令是随向量处理机的问世而出现的。一台向量处理机可以装备有用硬件或固件并发控制的多条向量流水线。4.开发层次

LionelNi的最新分类法(1990)，并行计算机的分层开发可表示于下图四、性能的系统属性1

.时钟频率和CPI

主频当前数字计算机的CPU(或简称处理机)是由一个恒定周期(τ，以ns表示)的时钟驱动的。周期的倒数是时钟频率(ｆ＝1/

τ）（以MHz表示）。程序的规模是由其指令数(Ic)，也就是程序串要执行的机器指令数来决定的。执行不同的机器指令所需要的时钟周期数也是不一样的。一条指令的周期数(CPl)就成为衡量执行每条指令所需时间的重要参数。2.性能因子执行程序所需的CPU时间：设Ic为已知程序的指令条数。执行程序所需的CPU时间(T，以秒/程序表示)可用三个主要因素的乘积来计算：

T＝Ic

×CPI×τ可将上式重写成如下形式：

T＝Ic

×(p+m×k)×τ

一种指令类型的CPI可分为完成指令所需的处理机周期数和存储器周期数两部分。完整的指令执行过程可能包含一至四次存储器访问(一次用于取指令，两次用于取操作数，一次用于存储结果)，这与指令的类型有关。式中的细化：p为指令译码和执行所需的处理机周期数;m为所需的存储器访问次数;k为存储周期与处理机周期之比;Ic为指令条数，为处理机周期。3.系统属性计算机系统属性可以由五元组表示：(Ic，p，m，k，τ),五个量可以称为性能因子。与四种系统属性有关：指令系统结构、编译技术、CPU实现和控制技术、高速缓存与存储器层次结构。4.Mips速率5.吞吐率系统的吞吐率:系统在单位时间内能执行多少个程序，这称为系统的吞吐率(单位为程序数／秒)Ws

。在多道程序系统中，系统吞吐率常低于CPU吞吐率Wp。Wp可用下式表示：

或：Wp=(MIPS)×106／Ic

Wp的单位是程序数／秒。CPU吞吐率是根据MIPS速率和程序的平均长度(Ic)来衡量机器每秒钟能执行多少个程序的尺度。Ws<Wp，用多道程序或分时操作在CPU上交叉执行多个程序时，I／O、编译器和操作系统产生的额外系统开销所造成的。总结：并行的产生并行背景下的计算问题串行向并行的演化并行的性能与系统的关系并行处理与体系结构第一章并行计算机模型

1计算技术的现状

2多处理机和多计算机

3多向量机和SIMD计算机

4并行计算机的抽象模型

5可扩展的范围和设计

2多处理机和多计算机一、共享存储型多处理机1.UMA模型UMA

--UniformMemoryAccess

结构和特点：紧耦合系统(tightlycoupledsystem)多处理机由于高度资源共享系统的互连采用总线、交叉开关、或多级网络形式对称(symmetric)多处理机当所有处理机都能同样访问所有外围设备时。例Fortran程序可在单处理机上顺序执行，分析CPU的运行时间，假设条件：所有数组A(I)，B(I)，C(I)都有N个元素；分析：求和Fortran程序L1:Do10I＝1，NL2:A(I)＝B(I)+C(I)L3:10ContinueL4:SUM＝0L5:Do20J＝1，NL6:SUM＝SUM+A(J)L7:20Continue假定取指令和加载数据的开销可以忽略不计；所有数组已经装人主存储器，并且短程序段已经装入高速缓冲存储器。忽略总线争用或存储器存取冲突问题。再假设：

执行代码行L2，L4和L6，每行要用一个机器周期。执行程序控制语句L1，L3，L5和L7所需的时间可以忽略。假定经过共享存储器的处理机之间的每次通信操作需要k个周期。结论：CPU用2N个周期串行程序并行化在M—处理机系统上执行程序将循环操作划分成M段，每段有L＝N／M个元素。假设经过共享存储器的处理机之间的每次通信操作需要：k个周期。

Doall表示所有M段在M台处理机上并行执行Doallk＝1，MDo10I＝L(k-1)+1，kL。

A(I)＝B(I)+C(I)10Continue

SUM(k)＝0Do20J＝1，L

SUM(k)=SUM(k)+A(L(k-1)+J)20ContinueENDall分析：循环1是L个周期；循环2是L个周期总时间：2L+h(k+1)=2N/M+(k+1)log2M2.NUAM模型3.COMA模型概念：只使用高速缓存的多处理机实现的机器：瑞典计算机科学研究所的数据扩散机(DDM，Hagersten等，1990)KendallSquareReserch公司的KSR—1机器(Burkhart等，1992)。特点：COMA模型是NUMA机的一种特例，将NUMA中分布主存储器换成了高速缓存；全部高速缓冲存储器组成了全局地址空间；远程高速缓存访问则借助于分布高速缓存目录进行，分级目录往往可用来寻找高速缓存块的副本，这与所用的互连网络有关；数据的初始位置并不重要，因为它最终将会迁移到要用到它的地方。模型的演变：例如，高速缓存一致性非均匀存储存取(CC—NUMA)模型。可以用分布共享存储器和高速缓存目录来描述。CC—NUMA模型的实例斯坦福大学的Dash系统(Lenosh等，1990)和麻省理工学院的Alewife系统(Agarwal等，1990)；这些将在后面讨论。4.典型的多处理机二、分布存储型多计算机系统1.概念由多个计算机结点，通过消息传递网络互相连接而成，每个结点是一台由处理机、本地存储器和有时接有磁盘或I／0外围设备组成的自治的计算机。2.特点：消息传递网络提供结点之间的点到点静态连接传统的多计算机已被称为近地存储访问(NORMA)机所有本地存储器是私用的，而且只有本地处理机才能访问；私用存储器逐渐在分布共享存储器的多计算机中将被逐步取消。3.多计算机的换代现代多计算机用硬件寻径器来传送信息；计算机结点与寻径器相连，边界上的寻径器与I／O和外围设备连接；任何两结点间的消息传递会涉及一连串的寻径器和通道。在异构多计算机系统中，可以有多种类型的结点，结点间的通信是通过可兼容的数据表示和消息传递协议来实现的。消息传递型多计算机的发展换代

第一代(1983—1987)是基于处理机板技术，采用了超立方体结构和软件控制的消息交换方法。加州理工学院的Cosmic和InteliPSC／1是这一代研制的代表。第二代(1988—1992)是用网格连接的系统结构、硬件消息寻径和中粒度分布计算的软件环境实现的；IntelParagon和ParsysSuperNodel000可作为代表性产品。现在面临的第三代(1993—)预期是细粒度计算机麻省理工学院的J-Machine和加州工学院的Mosaic，VLSI片上实现处理机和通讯工具。

示例：IBMPOWER4体系结构特点PowerPC64位体系结构单芯片双处理器，MCM八处理器集成多处理器互连接口集成I/O控制器集成L3Cache控制器集成存储控制器IBMPOWER4(MCM结构)IBMPOWER4(32CPU)4.典型多计算机多计算机的可编程性取决于:高效编译器实用高效的分布式操作系统实用总结：本节区分了多处理机和多计算机的主要差别和分类。

3多向量机和SIMD计算机一、向量超级计算机1.早期的超级计算机可分为：流水线向量机；SIMD计算机两类。执行过程：当译出的指令为向量操作；它将被送至向量控制器，控制器将监督主存储器与向量功能流水线之间的向量数据流，向量数据流由控制器协调控制；向量处理机则装有若干条向量功能流水线。2.寄存器—寄存器的系统结构如1976年推出的Cray1。向量寄存器用来保存向量操作数、中间和最终的向量结果;向量功能流水线从向量寄存器检索操作数，并将结果放入寄存器。

3.存储器—存储器结构这种结构比较早，与寄存器—寄存器结构的区别就在于采用向量流水部件代替了向量寄存器。例如:二、SIMD超级计算机1.SIMD的操作模型可用五元组表示M＝<N，C，I，M，R>N为机器的处理单元(PE)数。例如，illiacIV有64个PE，而连接机(ConnectionMachine)CM—2采用65536个PE。C为由控制部件(CU)直接执行的指令集；包括标量和程序流控制指令。I为由CU广播至所有PE进行并行执行的指令集；它包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。M为屏蔽方案集其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集。R是数据寻径功能集说明互连网络中PE间通信所需要的各种设置模式。示例：描述具体的SIMD机器MasParMP—1计算机的操作特性--五元组特性：MP—1是一种SIMD机器，其PE数N＝1024