第1章3w200411月15.ppt

1、1,并行处理与体系结构,2,第一章 并行计算机模型,1 计算技术的现状 2 多处理机和多计算机 3 多向量机和SIMD计算机 4 并行计算机的抽象模型 5 可扩展的范围和设计,3,2 多处理机和多计算机,一、共享存储型多处理机 1. UMA模型 UMA -Uniform Memory Access 结构和特点：,4,5,紧耦合系统(tightly coupled system) 多处理机由于高度资源共享 系统的互连采用总线、交叉开关、或多级网络形式 对称(symmetric)多处理机 当所有处理机都能同样访问所有外围设备时。,6,例 Fortran程序可在单处理机上顺序执行，分析CPU的运行时

2、间，假设条件： 所有数组A(I)，B(I)，C(I)都有N个元素； 分析：求和Fortran程序,7,L1: Do 10 I1，N L2: A(I)B(I)+C(I) L3:10 Continue L4: SUM0 L5: Do 20 J1，N L6: SUMSUM+A(J) L7:20 Continue 假定取指令和加载数据的开销可以忽略不计； 所有数组已经装人主存储器，并且短程序段已经装入高速缓冲存储器。 忽略总线争用或存储器存取冲突问题。,8,再假设： 执行代码行L2，L4和L6，每行要用一个机器周期。 执行程序控制语句L1，L3，L5和L7所需的时间可以忽略。 假定经过共享存储器的处理

3、机之间的每次通信操作需要k个周期。 结论：CPU用2N个周期,9,串行程序并行化 在M处理机系统上执行程序 将循环操作划分成M段，每段有LNM个元素。 假设经过共享存储器的处理机之间的每次通信操作需要： k个周期。,10,Doall表示所有M段在M台处理机上并行执行 Doall k1，M Do 10 IL(k-1)+1，kL。 A(I)B(I)+C(I) 10 Continue SUM(k)0 Do 20 J1，L SUM(k) = SUM(k) + A(L(k-1)+ J) 20 Continue ENDall,11,分析： 循环1是L个周期；循环2是L个周期 总时间： 2L+ h(k+1)

4、=2N/M+(k+1) log2M,12,2. NUAM模型,13,3.COMA模型 概念：只使用高速缓存的多处理机,14,实现的机器： 瑞典计算机科学研究所的数据扩散机(DDM，Hagersten等，1990) KendallSquareReserch公司的KSR1机器(Burkhart等，1992)。,15,特点： COMA模型是NUMA机的一种特例，将NUMA 中分布主存储器换成了高速缓存； 全部高速缓冲存储器组成了全局地址空间； 远程高速缓存访问则借助于分布高速缓存目录进行，分级目录往往可用来寻找高速缓存块的副本，这与所用的互连网络有关； 数据的初始位置并不重要，因为它最终将会迁移到要

5、用到它的地方。,16,模型的演变： 例如，高速缓存一致性非均匀存储存取(CCNUMA)模型。 可以用分布共享存储器和高速缓存目录来描述。 CCNUMA模型的实例 斯坦福大学的Dash系统(Lenosh等，1990)和麻省理工学院的Alewife系统(Agarwal等，1990)； 这些将在后面讨论。,17,4.典型的多处理机,18,二、分布存储型多计算机系统 1.概念 由多个计算机结点，通过消息传递网络互相连接而成，每个结点是一台由处理机、本地存储器和有时接有磁盘或I0外围设备组成的自治的计算机。,19,20,2.特点： 消息传递网络提供结点之间的点到点静态连接 传统的多计算机已被称为近地存储

6、访问(NORMA)机 所有本地存储器是私用的，而且只有本地处理机才能访问； 私用存储器逐渐在分布共享存储器的多计算机中将被逐步取消。,21,3. 多计算机的换代 现代多计算机用硬件寻径器来传送信息； 计算机结点与寻径器相连，边界上的寻径器与 IO和外围设备连接； 任何两结点间的消息传递会涉及一连串的寻径器和通道。 在异构多计算机系统中，可以有多种类型的结点，结点间的通信是通过可兼容的数据表示和消息传递协议来实现的。,22,消息传递型多计算机的发展换代 第一代(19831987)是基于处理机板技术，采用了超立方体结构和软件控制的消息交换方法。 加州理工学院的Cosmic和InteliPSC1是这

7、一代研制的代表。 第二代(19881992)是用网格连接的系统结构、硬件消息寻径和中粒度分布计算的软件环境实现的； IntelParagon和ParsysSuperNodel000可作为代表性产品。,23,现在面临的第三代(1993)预期是细粒度计算机 麻省理工学院的J-Machine和加州工学院的Mosaic，VLSI片上实现处理机和通讯工具。,24,示例：,IBM POWER4体系结构特点 PowerPC 64位体系结构 单芯片双处理器，MCM八处理器 集成多处理器互连接口 集成I/O控制器 集成L3Cache控制器 集成存储控制器,25,26,IBM POWER4 (MCM结构),27,

8、IBM POWER4 (32CPU),28,4.典型多计算机 多计算机的可编程性取决于: 高效编译器实用 高效的分布式操作系统实用,29,30,总结： 本节区分了多处理机和多计算机的主要差别和分类。,31,3 多向量机和SIMD计算机,一、向量超级计算机 1.早期的超级计算机可分为： 流水线向量机； SIMD计算机两类。,32,33,执行过程： 当译出的指令为向量操作； 它将被送至向量控制器，控制器将监督主存储器与向量功能流水线之间的向量数据流，向量数据流由控制器协调控制； 向量处理机则装有若干条向量功能流水线。,34,2.寄存器寄存器的系统结构 如1976年推出的Cray 1。,35,36,

9、向量寄存器用来保存向量操作数、中间和最终的向量结果; 向量功能流水线从向量寄存器检索操作数，并将结果放入寄存器。,37,3.存储器存储器结构 这种结构比较早，与寄存器寄存器结构的区别就在于采用向量流水部件代替了向量寄存器。 例如:,38,39,40,二、SIMD超级计算机,41,1. SIMD的操作模型 可用五元组表示 M N为机器的处理单元(PE)数。 例如，illiac IV有64个PE，而连接机(ConnectionMachine)CM2采用65 536个PE。 C为由控制部件(CU)直接执行的指令集； 包括标量和程序流控制指令。,42,I为由CU广播至所有PE进行并行执行的指令集； 它

10、包括算术运算、逻辑运算、数据寻径、屏蔽以及其它由每个活动的PE对它的数据所执行的局部操作。 M为屏蔽方案集 其中每种屏蔽将PE集划分为允许操作和禁止操作两种子集。 R是数据寻径功能集 说明互连网络中PE间通信所需要的各种设置模式。,43,示例： 描述具体的SIMD机器MasParMP1计算机的操作特性-五元组特性： MP1是一种SIMD机器，其PE数N1024至16 384。PE数目与机器配置有关。 CU执行标量指令，将译码后的向量指令播送到PE阵列，并控制PE间的通信。,44,每个PE都是基于寄存器的加载存储RISC处理机，能执行不同数据量的整数运算和标准浮点运算。各PE从CU接受指令。 屏

11、蔽方案设在每个PE中，并由CU连续监控，它能在运行时动态地使每个PE处于置位或复位状态。 例如： MP1有一个XNet网格网络和一个全局多级交叉开关寻径器，以实现CUPE之间、XNet的8个近邻之间和全局寻径器的通信。,45,2.SIMD的实施模型 （1）分布式存储器模型,46,存储器分布的SIMD特点： SIMD计算机开发的是PE之间的空间并行性。 存储器分布的SIMD计算机由同一阵列控制部件控制的PE阵列组成。 程序和数据通过主机装入控制存储器。 指令是送到控制部件进行译码。 标量操作或控制操作，则将直接由与控制部件相连的标量处理机执行。 向量操作，则将它广播到所有PE并行地执行。,47,划分后的数据集合通过向量数据总线广播到所有PE的本地存储器。 PE通过数据寻径网络互连。数据寻径网络执行PE间的通信