计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机

第九章 多处理机 9.1 多处理机结构 9.2 多处理机性能模型 9.3 多处理机的Cache一致性 9.4 多处理机实例

第九章 多处理机 多处理机系统 两个或两个以上处理机(包括PE和CU) 高速互连网络连接 统一的操作系统管理 指令以上级(任务级、作业级)并行 按照Flynn分类法，多处理机系统属于MIMD计算机 多处理机系统由多个独立的处理机组成 每个处理机都能独立执行自己的程序

9.1 多处理机结构 流水线机器 流水线机器通过几级流水的同时操作来获得高性能 连续计算机器 连续计算的机器由多台处理机组成，每台处理机执行相同的程序 前几章讨论了如何加快单指令流执行速度的方法 开发单条指令流内部的指令并行性 本章讨论多处理机--由若干台独立的处理机组成的系统 器件本身的物理条件限制了任何单处理机(单指令流, 时钟周期)的速度最高不能超过某个上界值 欲达到超过这个上界值的速度就必须采用其它的方法 通过多处理机----多指令流系统来实现这个目的 Intel, 10GHz---->多核 本章的中心议题--多处理机的结构和性能 介绍如何把多台处理机组成高并行度的系统 深入分析这类系统的瓶颈和改进性能的方法

9.1.1a 松散偶合多处理机 处理机之间的连接频带比较低 通过输入输出接口连接,处理机间互为外围设备进行连接 IBM公司的机器，可通过通道到通道的连接器CTC连接两个不同计算机系统的IOP 通过并口或串口连接多台计算机 用串行口加一个MODEL拨号上网 直接连接 多台计算机之间的连接需要有多个接口 通过Ethernet网络接口连接多台计算机 速度达10Mb、100Mb、1Gb Mynet已经达到1.28Gb和2.56Gb 当通信速度要求更高时，可通过一个通道和仲裁开关CAS(Channel and Arbiter Switch)直接在存储器总线之间建立连接 在CAS中有一个高速的通信缓冲存储器

通过多输入输出输出口连接的多处理机 LM0 IOP0 互连网络 CPU0 LM1 IOP1 CPU1 …… LMn-1 IOPn-1 CPUn-1 LM0 互连网络 …… PE0 CU LM1 PE1 LMn-1 PEn-1 IOP

通过消息传送系统连接的松散耦合多处理机 LM IOP 互连网络 CPU CAS 模块０ 模块n-1

9.1.1b 紧密偶合多处理机 处理机之间共享主存储器，通过高速总线或高速开关连接 主存储器有多个独立的存储模块 每个CPU能够访问任意一个存储器模块 通过映象部件MAP把全局逻辑地址变换成局部物理地址 通过互连网络寻找合适的路径，并分解访问存储器的冲突 多个输入输出处理机IOP连接在互连网络，I/O设备与CPU共享主存储器 处理机个数不能太多，几个到十几个 紧密偶合方式要求有很高通信频带 (1) 采用高速互连网络 (2) 增加存储器模块个数，一般n<m，取1～2倍之间 (3) 每个存储器模块再分成多个小模块，以流水线方式工作 (4) 每个CPU都有自己的局部存储器LM (5) 每个CPU设置一个Cache

紧密耦合多处理机模型 MAP MM CPU-MM-IOP 互连网络 CPU … IOP

带二维共享存储器、局部Cache及存储器的多处理机 IOP … CPU MAP Cache LM CPU-IOP互联网络 CPU-MM互联网络 MM

多处理机在结构原理上区别于并行处理机的主要特点 (1)多处理机有多个控制器 有多个指令部件，对各个PE实现单独的控制，而又相互协调配合 (2)多处理机的外围设备要能被多个PE分别调用 通过互连网络转接 并行处理机的外围设备统一访问主存储器进行程序和数组的有规则的传送

多处理机在结构原理上区别于并行处理机的主要特点 (3)并行处理机主要完成数组向量运算，PE和MM间数据交往比较规则，存储器访问的地址变换功能要求不高，互连网络的作用主要在数据对准，可比较简单 多处理机的互连网络须满足各个PE随机访问主存储器的要求 连接模式、频带和路径选择等问题都要复杂得多 存储映射部件对每一个PE也是必需的 多处理机系统中存储器的数据和存储空间都要被多个处理机共享 不允许每一个PE运行自己的程序段时直接产生物理地址 利用存储映射部件来满足存储器动态分配和处理机共享数据块的需要

9.1.2 多处理机系统的特点 1、结构灵活 并行处理机：专用，PE数很多(几千个)，固定有限的通信 多处理机：通用，几十个，高速灵活的通信 2、程序并行性 并行处理机的并行性存在于指令内部，识别比较容易 多处理机的并行性存在于指令外部，在多个任务之间，识别难度较大 一个简单的例子 Y = A+B*C*D/E+F 用两个处理机 CPU1 CPU2 B*C D/E A+F B*C*D/E A+B*C*D/E+F

9.1.2 多处理机系统的特点 3、并行任务派生 并行处理机把同种操作集中在一起，由指令直接启动各PE同时工作 多处理机用专门的指令来表示并发关系，一个任务开始执行时能够派生出与它并行执行的另一些任务 如果任务数多于处理机数，多余的任务进入排队器等待 4、进程同步 并行处理机仅一个CU，自然是同步的 多处理机执行不同的指令，工作进度不会也不必保持相同, 先做完的要停下来等待 有数据相关和控制相关也要停下来等待 要采取特殊的同步措施来保持程序所要求的正确顺序

9.1.2 多处理机系统的特点 5、资源分配和进程调度 并行处理机的PE是固定的，采用屏蔽手段改变实际参加操作的PE数目 多处理机执行并发任务，需用处理机的数目不固定，各个处理机进入或退出任务的时刻不相同，所需共享资源的品种、数量又随时变化 提出资源分配和进程调度问题，对整个系统的效率有很大的影响

9.2 多处理机性能模型 引起峰值性能下降的原因 (1)因处理机间通信而产生的延迟 (2)一台处理机与其它处理机同步所需的开销 (3)没有足够多任务时，一台或多台处理机处于空闲状态 (4)由于一台或多台处理机执行无用的工作 (5)系统控制和操作调度所需开销 研究多处理机的目的 提前5年得到速度高10倍的机器----跨越设计、生产工艺的台阶 或用1/10的价格获得一台高性能的机器----低成本的组合 设计得好，某些适合进行并行处理的应用领域，可达到 提前10年得到速度高100倍的机器 或用1/100的价格获得一台高性能的机器

R/C比值 并行性在很大程度上依赖于R/C比值 其中：R代表程序执行时间，C代表通信开销 通常：R/C比值小，并行性低。R/C比值大，并行性高 如果把作业分解成较大的块，就能得到较大的R/C值，但是所得到的并行性比最大可能的并行性要小得多 R/C比值是衡量任务粒度(Granularity)大小的尺度 粗粒度(Coarsegrain)并行时，R/C比值比较大，通信开销小 细粒度(Finegrain)并行时，R/C比值比较小，通信开销大 细粒度并行性需要的处理机多，粗粒度并行性需要的处理机少 细粒度并行性的基本原理是把一个程序尽可能地分解成能并行执行的小任务 在极端情况下，一个小任务只完成一个操作

9.2.1 基本模型 假设有一个包含M个任务的应用程序，希望在一个由N台处理机组成的系统上以最快的速度执行这个程序 考虑一个仅有两台处理机的系统，再逐步增加处理机数目 为了模拟性能，用公式表示执行时间和额外开销 先承认下面两个假设是成立的，以获得初步结论，然后放宽假设，观察性能如何变化 (1)每个任务的执行时间为R个单位时间 (2)两个任务不在同一台处理机时，其通信所需的额外开销为C个单位时间。两个任务在同一台处理机时，通信所需的额外开销为0

一个应用程序在两台处理机系统上运行有多种分配方法 可全部任务都分配给一台处理机而另一台空闲 通信开销最小，但没有利用并行性 也可按不同比例将任务分配给两台处理机 总处理时间是执行时间和额外开销时间之和 CPU1 CPU2 M 0 M-1 1 M-2 2 ... 0 M

其它额外开销 用C表示用于通信的时间，它还包括系统所有其它额外开销 某些情况下，系统的额外开销的操作可与计算过程重叠进行 如处理机在执行指令的同时能通过I/O接口进行通信 并不是所有的额外开销都可以被屏蔽掉 如处理机在访问共享数据或通信通路时可能会发生竞争，处理机在等待同步信号期间处于空闲状态等 假设一部分额外开销的操作会增加总处理时间

程序的总处理时间 一个程序的总处理时间 总处理时间=Rmax(M-K，K)+C(M-K)K (9.1) M个任务的应用程序，在由N台处理机组成的系统执行 C表示用于通信的时间 每个任务的执行时间为R个单位 总处理时间是两个时间的和 一个是执行时间 另一个是用于通信和其它额外开销的时间 两台处理机系统，执行时间取两台处理机较大的一个 K个任务分配给一台处理机，剩下的(M-K)个任务分配给另一台处理机时，执行时间取R(M-K)和RK中较大的一个 K为任务分配参数 第二项表示额外开销时间与通信次数成正比例关系 通信次数与任务分配方法有关 第一项是K的线性函数，第二项是K的二次函数

程序的总处理时间 总处理时间是K的函数，其最小值是多少呢？即任务如何分配才能获得最小的总处理时间 用图解法来求最小处理时间 R/C代入式(9.1)，令C=1

图9.2 两种不同R/C比值的并行执行时间 对于该模型的结论 R/C＜M/2时，所有任务分配给同一台处理机能使总处理时间最小 R/C＞M/2时，任务平均地分配给两台处理机能使总处理时间最小

9.2.2 N台处理机系统的基本模型 M个任务分配给N台处理机，求总处理时间的最小值 实际的最小值发生在极端分配情况下，或者将所有的任务集中在一台处理机上，或者将任务平均分配给所有处理机 平均分配方法 4个任务平均分给3台处理机(P) 方案 P1 P2 P3 执行时间 通信时间 总处理时间 一 2 1 2R 5C 2R+5C 二 4C 2R+4C 1 2

11个任务平均分给5台处理机(P) 方案 P1 P2 P3 P4 P5 执行时间 通信时间 总处理时间 一 3 2 3R 48C 3R+48C 二 1 47C 3R+47C 三 45C 3R+45C 每个P最大任务数3 完全均分，每个P为2个任务，多出的一个分给其中任一个 不超出最大任务数3，往前推，若干个3，一个2，其余为0 最大任务数尽量小---->R 尽量往前推，不足最大任务数的余数分给一个P---->C 2 3 6 3*(2+2+2+2)=24 4

M个任务平均分配给N台处理机的最佳分配方法 最大任务数每台分 个任务 分得最大任务数的有 台处理机 如果M/N ≠ 0 则另有1台处理机分得剩下的 个任务 剩下的 台处理机不分配任何任务 处理机任务数有3个取值： 、 、0 如101个任务平均分给50台处理机 每台分给 =3个任务,有 = 33台处理机 另有1台处理机分给 101 mod 3 =2个任务 剩下的 50-33-1=16 台处理机不分配任务

M个任务平均分配给N台处理机的最佳分配方法 假设Ki个任务分给了第i台处理机 第一项求出N台处理机中最大执行时间 第二项计算出Ki与(M-Ki)任务之间两两通信的开销时间,第二项是关于Ki的二次函数 其中，Ki最多有3个取值： 、 、0 当M是N的倍数时，有 R/C＞M/2时采用平均分配方法 R/C＜M/2时采用集中分配方法

多处理机系统的加速比 一个计算问题在一台处理机上运行时间与在多处理机系统上运行时间的比值称为多处理机系统的加速比 M 是N 的倍数时，有 如果M 和N 较小，R /C 较大，即分母中的第一项远大于第二项，则加速比与处理机台数N 成正比 当处理机台数N很大，加速比≈ 即加速比趋近于一个常数 这时再增加处理机，性能的提高很小，与所增加的成本相比不值得

9.2.3 随机模型 略

9.2.4 通信开销为线性的模型 略

9.2.5 完全重叠通信的理想模型 略

9.2.6 具有多条通信链的模型 略

几个模型的总结 (1)多处理机系统结构所需的额外开销，包括调度，对共享资源的竞争，同步，处理机之间通信等 串行机和向量机(或别的单指令流机)系统结构中不存在 (2)运行某个程序的处理机数目增加时，用于计算的那部分时间将减少，额外开销时间增加 实际上，额外开销的增加可能比处理机数目的线性增加更快

几个模型的总结 (3)R/C比值表示当一个程序在某一特定系统结构上执行时，程序执行时间(运行时间)与额外开销时间(通信时间)的比值 该比值越大，越有利于计算过程 因为随着R/C比值的增加属于额外开销的时间相对减少了 如果将整个计算分成几大部分而不是很多小部分从而获得较大的R/C值，那么，并行程度将大为降低，也就限制了在多处理机上能够获得的加速比 一方面，R/C要足够小使能并行执行的任务数目较多 另一方面，R/C要足够大以免额外开销太大 由于这个矛盾，不能期望简单地通过增加处理机数目制造出高速的多处理机系统 处理机数目究竟多少才能使价格和性能都比较合理 存在一个极大值，这个值很大程度上依赖于机器的系统结构，基本技术(尤其是通信技术)和每一个具体应用问题的性质

9.2.7 多处理机模型 略

9.3 多处理机的Cache一致性 在并行处理机和多处理机系统中，采用局部Cache会引起Cache与共享存储器之间的一致性问题 9.3.1 问题由来 9.3.2 监听协议 9.3.3 基于目录的协议

9.3.1 问题由来 出现不一致性问题的原因有三个 共享可写的数据 进程迁移 I/O传输

1、写共享数据引起的不一致性 使用多个局部Cache时，可能发生Cache不一致性问题 共享可写数据引起的Cache不一致性 P1把X的值写为X'之后，如果P1采用写通过策略，内存中的内容也变为X'，但P2处理机Cache中的内容还是X 如果P1采用写回策略，内存中的内容还是X，P2处理机要读X时，读到的是X而不是X'

2、进程迁移引起的数据不一致性 P1和P2中都有共享数据X的拷贝 P2修改了X，采用写通过方式，所以内存中的X修改成了X'。 如果该进程迁移到P1上，这时，P1的Cache中仍然是X P1中有共享数据X的拷贝，而P2中没有该共享数据 P1进程对X进行了修改，如果采用了写回方式，暂时没有对内存中的数据进行修改 如果该进程迁移到了P2上，P2运行时从内存中读到是X

3、I/O造成数据不一致性 如果P1和P2在各自的局部Cache中都有X的拷贝，I/O将一个新数据X'写入存储器就导致存储器和Cache间的数据不一致性 如果两个局部Cache中都有X的拷贝，并采用写回方式，当P1把X修改成X'之后，输出部件读X，存储器就把X传给输出部件

把I/O处理机分别连接到各自的局部Cache上 一种解决I/O操作引起数据不一致性的方法是把I/O处理机分别连接到各自的局部Cache I/O处理机就能和CPU共享Cache 只要能保证各Cache之间以及Cache和内存之间的数据一致性，就能保证I/O操作的一致性

9.3.2 监听协议 两类解决Cache不一致性问题的协议 监听协议 基于目录的协议 总线互连的多处理机系统，通常采用监听协议 其他多处理机系统，通常采用基于目录协议

1、两种监听协议 使用监听协议，有两种方法 方法一：写无效(Write Invalidate)策略，在本地Cache的数据块修改时使远程数据块都无效 方法二：写更新(Write Update)策略，在本地Cache数据块修改时通过总线把新的数据块广播给含该数据块的所有其他Cache 采用写无效或写更新策略与Cache采用写回方式(Write Back)还是写通过方式(Write Through)无关 如果Cache采用的写通过方式，在使远程数据块无效或更新其他Cache的同时，还要同时修改共享存储器中的内容

Cache采用写通过方式时的写无效策略和写更新策略 由于写更新策略在本地Cache修改时需通过总线把修改过的数据块广播给所有含该数据块的其他Cache，增加了总线的负担 大部分多处理机系统使用写无效策略

2、采用写通过方式的Cache 数据块有两种状态: 有效和无效 有效表示该数据块内容正确，两种状态的转换如图 RL、WL表示本地处理机对Cache的读操作和写操作 RR、WR表示远程处理机对Cache中相同内容数据的读操作和写操作

3、采用写回方式的Cache 只读状态表示整个系统中有多个数据块拷贝是正确的 读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，即在整个系统中只有一个数据块拷贝正确 对于只读的数据块 本地的和远程的读操作都是安全的 本地的写操作将使状态转移为读写 远程的写操作将使之变为无效 对于读写状态的数据块 本地的读、写操作都是安全的 而远程的读操作将数据块传递给远程处理机的Cache，使两个Cache都转移至只读状态 远程写操作使远程处理机Cache转移至读写状态，而本地Cache转移至无效状态 对于无效状态 本地读操作，使状态转移至只读 本地写操作，使状态转移至读写，同时使其他Cache中相应数据块的状态转移为无效状态 其他操作不会引起从无效状态向其他状态的转移

采用写回方式的Cache状态图

4、写一次(Write-Once)协议 1983年James Goodman提出写一次Cache一致性协议 第一次写Cache采用写通过方式，以后采用写回方式 整个系统中只有一份正确的拷贝 为了区分第一次写，把“读写”状态分为：“保留(Reserved)”和“重写(Dirty)” 共有4种状态 (1)有效(Valid, 相当于写回方式中的只读) 从存储器读入的并与存储器一致的Cache数据块 (2)无效(Invalid) 在Cache中找不到或Cache中的数据块已作废 (3)保留(Reserved) 数据从存储器读入Cache后只被写过一次 Cache和存储器中的拷贝都是正确 (4)重写(Dirty) Cache中的数据块被写过多次，且是唯一正确的数据块 此时存储器中的数据块不正确

写一次协议的状态图 Rl、Rr、Wl、Wr分别表示本地读、远程读、本地写、远程写

CPU读Cache,有两种可能性 (1)数据块在Cache中存在(包括有效、保留或重写) CPU直接读取数据，Cache状态不变 (2)Cache中的数据块处于无效状态 触发读缺失事件 如果存在处于有效、保留或重写状态的相应数据块 将其调入本地Cache 相应数据块处于重写状态时，还要同时禁止存储器操作 如果不存在处于有效、保留或重写状态的相应数据块 只有存储器中是唯一正确的拷贝 直接从存储器中读入 把读入Cache中的相应数据块置为“有效”状态

CPU写Cache,也有两种可能 (1)写命中 当Cache处于“有效”状态时 采用写通过方式，把写入Cache的内容同时写入存储器 将Cache的状态转移为“保留” 将其他Cache的相应数据块状态置为“无效” 当Cache处于“保留”或“重写”态时 使用写回方式 Cache的状态转移至“重写” 其他的存有相同内容的Cache处于“无效”态 (2)写不命中 将数据块调入Cache 采用写通过方式, 同时写存储器 将本地Cache的状态置为“保留” 同时将其他Cache的状态置为“无效”

写一次协议 写一次协议的优点 减少大量的无效操作，提高了总线效率 缺点 当主存储器的内容无效时,读缺失引起的总线读操作必须禁止访问主存储器 大多数总线不支持这种操作 IEEE Futurebus+总线支持该操作

9.3.3 基于目录的协议 非总线结构的多处理机系统，采用基于目录的Cache一致性协议

1、Cache目录结构 Cache目录存放的内容是大量的指针，用以指明块拷贝的地址 每个目录项还有一个重写位，指明是否有一个Cache允许写入数据 根据Cache目录的存放形式，有集中式和分布式两种 根据目录的结构，目录协议分成三类 全映射(Full-Map)目录：存放全局存储器中每个块的数据 有限(Limited)目录：每个目录项的指针数固定 链式(Chained)目录：把目录分布到所有Cache 目录的使用规则 当一个CPU对Cache进行写操作时，根据Cache目录的内容将所有其他存有相同内容的Cache拷贝无效，并置重写位 在CPU对Cache进行读操作时 如果读命中，直接读Cache 如果重写位为“0”，则从主存或其他Cache中读入该块，并修改目录

2、全映射目录 目录项中有N个处理机位和一个重写位 处理机位表示相应处理机对应的Cache块的状态 重写位为“1”，且只有一个处理机位为“1”，则该处理机可以对该块进行写操作 Cache的每个数据块有两个状态位: 一位表示数据块是否有效，另一位表示有效块是否允许写 图(a)表示全系统中所有Cache中都没有X的拷贝 图(b)表示三个处理机都对X有过读请求 图(c)表示P3处理机获得对X的写权限之后的状态

2、全映射目录 从第二种状态转移至第三种状态的过程 (1) Cache3发现包含X单元的块是有效的，但是不允许写 (2) Cache3向包含X单元的存储器模块发写请求，并暂停P3的工作 (3) 该存储器模块发无效请求至Cache1和Cache2 (4) Cache1和Cache2接到无效请求后，将对应块置为无效态，并发回答信号给存储器模块 (5) 存储器模块接到Cache1和Cache2的回答信号后，置重写位为“1”，清除指向Cache1和Cache2的指针，发允许写信号到Cache3 (6) Cache3接到允许写信号，更新Cache状态，并激活P3 全映射目录协议的效率比较高 但开销与处理机数目的平方成正比，不具有扩展性

3、有限目录 处理机数目为N，限制目录大小为O(Nlog2N) 目录指针需要对N进行二进制编码，每个指针占log2N位，目录所占的总存储空间与(O(Nlog2N))成正比 目录项数为2，当Cache1和Cache2中都有X的拷贝时，若P3请求X，则必须在Cache1和Cache2中选择一个使之无效，这种替换过程称为驱逐 有限目录的驱逐需要一种驱逐策略 驱逐策略的好坏对系统的性能具有很大的影响 驱逐策略与Cache替换策略在很多方面是相同的

4 链式目录 通过维护一个目录指针链来跟踪共享数据拷贝 当P1读X时，存储器送X到Cache1，同时写Cache1的一个链结束指针CT，在存储器中也保存一个指向Cache1的指针 当P2读X时，存储器送X给Cache2，同时给Cache2一个指向Cache1的指针，存储器则保存一个指向Cache2的指针

4 链式目录 当某一个处理机需要写X时，它必须沿整个目录链发送一个数据无效信息。在收到所有相关处理机的回答信号之后，存储器才给该处理机写允许权 Cache中的数据块需要替换时，把该Cache从目录链中删除 (1) 把Cachei+1的指针指向Cachei-1。在Cachei中可以存放别的数据块 (2) 使Cachei及链中位于其后的所有Cache中的单元X无效 (3) 使用双向链。在替换时不再需要遍历整个链。但指针增加了一倍，一致性协议也更加复杂 优点：不限制共享数据块的拷贝数目，又保持了可扩展性。 指针的长度以处理机数目的对数关系增长，Cache的每个数据块的指针数目与处理机数目无关 缺点：链式目录的复杂程度超过了前两种目录

9.4 多处理机实例 多处理机系统主要有四大类 (1) 多向量处理机系统 如Cray YMP-90, NEC SX-3和FUJITSU VP-2000 (2) SMP (Symmetry MultiProcessors)对称多处理机 SMP(Shared Memory MulptiProcessors)共享存储多处理机 如SGI Challenge，Sun SparcCenter 2000 (3)MPP (massively parallel processing)大规模并行处理机 如Intel Paragon, CM-5, Cray T3D (4) Cluster 机群系统(NOW或COM) Cluster(集群)、NOW(工作站网络, Network Of Workstations)、COW(工作站集群,Cluster Of Workstations) 9.4.1 大规模并行处理机(MPP) 9.4.2 对称多处理机(SMP) 9.4.3 机群系统(Cluster)

9.4.1 大规模并行处理机(MPP) 科学计算中的重大课题要求提供3T性能 (1) 1 Teraflops计算能力 (2) 1 Terabyte主存储器 (3) 1 Terabyte/s 输入输出频带宽度 目前，速度还慢1000倍左右，存储容量和I/O带宽差距更大 科学计算中的重大课题 全球气候预报, 基因工程 ,飞行动力学 ,海洋环流, 流体动力学, 超导建模, 半导体建模, 量子染色动力学, 视觉 采用的关键技术 VLSI 可扩展技术 共享虚拟存储技术

虚拟共享存储器(Shared Virtual Memory) 也称共享分布存储器(Distributed Shared Memory) 物理上分布存储器，逻辑上共享存储器 虚拟共享存储器的优点 编程容易, 系统结构灵活 可扩充性好, 有较好的软件移植性 与消息传递方式相比，程序运行效率高，主要原因 (1) 数据块缓存在本地 (内存或Cache中), 可以多次使用 (2) 通信时间分散，提高了并行性 (3) 扩大存储空间，减少换页操作 虚拟共享存储器实现途径 (1) 硬件实现, 利用Cache技术。需要增加专用硬件 (2) 操作系统和库实现，通过虚拟存储机制取得共享和一致性 在松耦合的分布存储多处理机上，不需要增加任何硬件 (3) 编译实现，自动将共享访问转换成同步和一致原语 大多数系统采用途径(1)和(2)，或这两种途径结合实现

1、同步的MIMD机器 SIMD与MIMD的优点结合在一起 CM-5的同步MIMD结构能够同时支持SIMD与MIMD两种并行计算方式 数据并行可采用SIMD模式、多SIMD模式或同步MIMD模式

CM-5 32到16384个处理器结点 每个结点有一个SPARC处理机，32MB存储器，64位浮点和整数操作，速度为128Mflops的向量处理部件 控制处理机1到几十台 根据需要配置存储器和磁盘 输入输出接口与图形设备、海量辅助存储器以及高性能网络相连 占地面积为30米×30米，峰值速度超过1Tflops 三个网络：数据网络、控制网络和诊断网络 数据网络提供点对点通信 控制网络提供广播、同步、扫描和系统管理功能 诊断网络从后台访问所有系统硬件，测试系统完整性，检测和隔离错误 数据网络和控制网络有很好的可扩展性，与处理机类型无关 可划分成一个或多个分区供用户使用 每个分区一台控制处理机，一组处理结点，数据和控制网络的专用部分 允许任何分区中的进程访问任何I/O设备

2、CM-5网络结构 数据网络采用胖树型网 数据处理结点、控制处理机和I/O通道都位于胖树的叶子上 利用胖树的层次结构特性，可以划分一棵子树给一个用户

2、CM-5网络结构 采用4元胖树实现，每个内部开关结点由n个寻径器芯片组成。每个寻径器与4个子芯片和2个或4个父芯片相连 可分配不同的子树处理不同的作业，子树的大小任意 为把消息从一台处理机传送到另一台处理机，首先沿树将消息向上传送到离两台处理机最近的公共祖先，然后向下传送到目的处理机 每台处理机与数据网络有两条连接通路，每个叶子结点的输入和输出的频宽为40兆字节/秒 当一个消息沿树向上传送时，使用哪条父连接通路则有几种选择

3、控制处理机 控制处理机由CPU、存储器、本地磁盘、网络接口、以太网组成。它相当于一台标准工作站 网络接口通过控制网络和数据网络使处理机与系统的其它部分相连 控制处理机专门执行管理功能，不需要高性能的运算部件 每台控制处理机运行操作系统，负责并行处理资源的管理 一部分控制处理机管理用户区的计算资源，其它管理I/O资源

4、处理结点 采用SPARC处理器，利用重叠寄存器窗技术，实现快速的进程切换，使不同时间不同用户分区能够动态地使用处理结点 网络接口通过控制网络和数据网络将结点与系统的其它部分相连 向量部件执行由标量处理机发出的向量指令，每个向量部件有一个流水ALU和64个64位的寄存器 每条向量指令可能传送给一个指定的向量部件、或一对向量部件、或同时广播给所有4个向量部件 标量处理机负责地址转换和循环控制，与向量部件的操作并行执行 每个结点的峰值速度为128Mflops 16384个处理结点的总峰值速度为214×27=221 Mflops =2Tflops 网络的系统结构设计，做到与所选择的处理器无关

处理结点基本结构 处理结点基本结构 带向量部件的处理结点

9.4.2 对称多处理机 (SMP) SMP称为共享存储多处理机(Shared Memory mulptiProcessors) 也称对称多处理机(Symmetry MultiProcessors) 1 三种模型 (1) UMA多处理机 均匀存储器存取模型(Uniform Memory Access) 存储器被所有处理机均匀共享 所有处理机对所有存储单元具有相同的存取时间 每台处理机有局部Cache 外围设备可以共享 (2) NUMA多处理机 非均匀存储器存取(Nonuniform Memory Access)模型 存储器访问时间随存储单元的位置不同而变化 共享存储器物理上是分布在所有处理机中的本地存储器 所有局部存储器地址空间的集合就组成了全局地址空间 处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢，因为通过互连网络会产生附加的时间延迟

多处理机 系统互连网络 (总线、交叉开关、多级网络) UMA多处理机模型 P1 …… P2 Pn SM1 SM2 I/O 系统互连网络 NUMA多处理机模型 P1 LM1 …… P2 LM2 Pn LMn

(3) COMA多处理机 只有Cache的存储器结构(Cache-Only Memory Architecture)模型 COMA是一种只用Cache的多处理机系统 COMA模型是NUMA模型的一种特例，后者分布存储器换成了Cache 在每个处理机结点上没有主存储器，全部Cache组成了全局虚拟地址空间 远程Cache访问通过分布Cache目录D进行 共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输

COMA多处理机模型 互连网络 COMA多处理机模型 D1 Cache1 …… P1 D2 Cache2 P2 Dn Cachen Pn

2、S2MP结构 1996年SGI Origin 2000服务器采用S2MP并行计算机体系结构 可扩展共享存储器多处理(Scalable Shared-memory MultiProcessing) S2MP实际上是NUMA多处理机系统，采用分布存储器，通过Cache对系统的共享和私有数据都进行缓存，以达到高性能 从用户编程角度看，S2MP是一种共享存储的多处理机系统 S2MP的主要特点：易编程、可扩展 (1) 编程简单，使用方便 (2) 可扩展性好，增加处理器数目不受总线带宽的限制 (3) 通信开销小，可以开发程序中的细粒度并行性 S2MP的关键技术 (1) 高速无阻塞互连网络，增加系统的通信带宽 (2) 采用分布式存储器，随处理器数目的增加自动增加存储器带宽 (3) 引入Cache，降低访存时延 (4) 所有存储器统一编址，提供单一的地址空间 (5) 在每个处理器结点上增加一个目录存储器，维护Cache一致性

S2MP结构

3. SGI Origin 2000系列服务器 Origin 2000结合SMP、MPP、NOW的优点 SMP易编程，MPP可扩展性，NOW可用性 有4种机型 Origin 2000，塔式系统，最多4个处理器 Origin 2000 Deskside，桌边服务器，最多8个处理器 Origin 2000 Rack，机柜服务器，处理器数目最多为16个 Cray Origin 2000，支持128个处理器 S2MP结构的典型实现，地址空间成指数增长，连续可扩展最多可以扩展至1024个处理器，具有高带宽和低时延 关键技术 CrayLink，多重交叉开关互连技术，用于连接处理器、存储器、I/O设备 Cellular IRIX，蜂窝式操作系统，实现从小系统到大系统的连续扩展

Origin 2000系列服务器结构： (1) 结点板 每个结点板(Origin 2000的主板)有一到两个R10000处理器、二级Cache、主存储器、目录存储器、HUB、I/O接口、互连网络路由器接口

HUB结构 HUB有四个双向的端口 每个端口的单向速率800MB/s，双工带宽1.6GB/s 四个端口分别连接到处理器、主存储器、XIO和互连网络 四个端口在内部以交叉开关互连

HUB ASIC结构

(3) 互连网络 互连网络是一组开关组成，称为路由器 允许多个传输同时发生；速度极高，每条链路带宽达1.6GB/s 互连网络不需要仲裁，也不存在竞争 路由器的核心是6路全交叉开关 峰值通信带宽9.6GB/s

路由器Router ASIC结构

(4) 存储系统 有一个统一的共享地址空间，存储系统共分为四个层次 第一层：寄存器堆，访问延迟时间最短 第二层：Cache，主Cache在R10000芯片上，二级Cache在结点板上 第三层：本地存储器，在结点板上，包括主存储器和目录存储器 第四层：远程Cache，用于减少访问共享存储空间所需的时间

(8) 扩展连接方式 可构成4、16、32、64、128个处理器的互连拓扑结构 图中：P是处理器、N是结点板、H表示HUB、R表示路由器

(8) 扩展连接方式 两个结点板通过HUB直接连接得到4个处理器的机器 由于路由器提供了两条连接结点板的链路，由一个路由器和两个结点板构成一个模块，利用路由器的其他4个接口可以扩展到不同的规模 使用其中的2条链路，可连接16个处理器 使用其中的3条链路，形成一个立方体，可连接32个处理器 使用4条链路，构成一个4维超立方体，可连接64个处理器 采用Cray Router，最大配置可以达到128个处理器

9.4.3 机群系统 (Cluster) 1、机群系统的组成 机群系统 利用高速网络连接一组高性能工作站或高档PC机 并行程序设计以及可视化人机交互集成开发环境支持 统一调度，协调处理，实现高效并行处理的系统 Cluster(集群)、NOW(工作站网络, Network Of Workstations)、COW(工作站集群,Cluster Of Workstations) 从结构和结点间的通信方式来看，属于分布存储系统 机群系统中的主机和网络可以是同构的，也可以是异构的 微处理机技术、网络技术和并行编程环境的发展使得机群系统这一新的并行处理系统形式正成为当前研究的热点 (1)微处理器的性能不断提高 (2)网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解 (3)并行编程环境的开发使得新编并行程序或改写串行程序更为容易

2、机群系统的特点 (1)系统开发周期短 (2)用户投资风险小 (3)系统价格低 (4)节约系统资源 UC Berkeley计算机系100多台工作站的使用情况表明，一般单机系统的使用率不到10%，而机群系统中的资源利用率可达到80%左右 (5)系统扩展性好 (6)用户编程方便

3、机群系统的关键技术 (1)高效的通信系统 在用户空间实现通信协议 精简通信协议 Active Message通信机制

(2) 并行程序设计环境 PVM(Parallel Virtual Machine) 开始于1989年夏天,美国橡树岭国家实验室(ORNL) 一套并行计算工具软件，支持多用户及多任务运行 支持多种结构的计算机，工作站、并行机以及向量机等 支持C、C++和Fortran语言 自由软件，使用非常广泛 编程模型可以是SPMD或MPMD 具有容错功能，发现一个结点出故障时，自动将之删除

(2) 并行程序设计环境 MPI(Message Passing Interface) 在1992年11月至1994年元月产生 能用于大多数并行计算机、计算机机群和异构网络环境 支持C和Fortran两种语言,编程模型采用SPMD Express 美国Parasoft公司推出；能在不同的硬件环境上运行；支持C和Fortran两种程序设计语言 Linda 美国Yale大学与科学计算协会共同研制；通过函数扩充现并行程序的设计；支持C-Linda、Fortran-Linda等

(3) 并行程序设计语言 多处理机系统中，须用并行程序设计语言编写程序。或者把已经用串行语言编写的程序转换成并行语言程序后，才能在多处理机系统上运行 传统串行语言程序转换成并行语言程序的过程称为并行编译 两种并行编译方式 全自动并行编译与半自动并行编译 全自动并行编译是方向，但实现起来很困难 半自动并行编译又称为交互式并行编译。程序员通过多次与机器对话，找到串行程序中可以并行执行的部分 并行编译器生成代码的形式 并行高级语言程序、并行中间语言程序、并行目标语言程序

(4) 负载平衡技术 一个大任务可分解为多个子任务，把多个子任务分配到各个处理结点上并行执行的技术称为负载平衡技术 对于由异构处理结点构成的并行系统，相同的负载在各结点上的运行时间可能不同。因此，准确的负载定义应是负载量与结点处理能力的比值 负载平衡技术的核心就是调度算法，即将各个任务比较均衡地分布到不同的处理结点上并行计算，从而使各结点的利用率达到最大 负载平衡技术分为静态和动态两大类 静态方法 是在编译时针对用户程序的各种信息(任务的计算量和通信关系等)及并行系统本身的状况(网络结构、各结点计算能力等)对用户程序中的并行任务作出静态分配决策 动态方法 是在程序运行过程中实现负载平衡的。它通过分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整，以消除系统中负载分布的不均匀性。动态负载平衡的算法简单，实时控制，但增加了系统的额外开销

(5)并行程序调试技术 用并行程序设计语言编写程序，比用串行程序设计语言更容易出错 在多处理机系统中，用并行程序设计语言编写程序更加依赖于并行调试工具 并行程序调试的主要困难：并行程序的执行过程不能重现

(6)可靠性技术 多处理机上运行的程序通常比较大，程序执行时间很长(几十个小时或几十天)。如果在程序执行过程中出现偶然故障(如电源掉电、磁盘满、某一台处理机故障等)，则整个运算过程要从头开始 定时设置检查点，保存现场信息。当出现故障时，只要回复到上一个检查点，不必从头开始执行