第七章 多处理机

多处理机具有两个以上的处理机，在操作系统控制下，通过共享的主存或输入/输出子系统或高速通信网络进行通信。 多任务处理，协同求解，提高速度； 利用冗余，提高可靠性、适应性、可用性。 分为：同构型、异构型、分布型

目录 多处理机的概念、问题和硬件结构 紧耦合多处理机多Cache的一致性问题 多处理机的并行和性能 多处理机的操作系统 多处理机的发展

多处理机 属于多指令流、多数据流系统 多处理机系统由多个独立的处理机组成，每个处理机都能够独立执行自己的程序。 实现更高一级的作业、任务之间的并行 结构上：要用多个指令部件分别控制，通过机间互联网络实现通信 算法上：不限于向量数组 系统管理上：依靠软件手段解决资源分配和管理，任务分配、处理机调度、进程同步和通讯

多处理机与并行处理机的主要差别 方 面 并行处理机 多处理机 结构灵活性 程序并行性 并行任务派生 进程同步 资源分配和任务调度 方 面 并行处理机 多处理机   结构灵活性 针对向量、数组处理而设计的，有专用性，虽然处理单元数多16384个，但设置有限的、固定的机间互连通路 实现作业、任务、程序段的并行，适应算法，结构灵活多变，实现复杂的机间互连，避免争用共享的硬件资源 程序并行性 实现操作级并行，并行性存在指令内部 并行性还存在于指令外部，表现于多个任务间的并行 并行任务派生 通过指令来反映数据间是否并行计算，并由指令直接启动多个处理单元并行工作 需要专门的指令或语句指明程序中各程序段的并发关系，并控制并发执行 进程同步 实现指令内部对数据操作的并行 实现指令、任务作业级的并行 资源分配和任务调度 处理单元数目固定，利用屏蔽手段，改变数目 处理机数目不固定，复杂

多处理机存在的技术问题 硬件结构上如何解决处理机、存储器模块及I/O子系统之间的互连 如何最大限度地开发系统的并行性，实现多处理机各级的全面并行； 如何分割任务的大小，任务的粒度大小； 如何协调好处理机中各并行执行的任务和进程间的同步问题； 如何将各个人物分配到一个或多个处理机上，解决好处理机调度、任务调度和资源分配问题，防止死锁； 系统发生故障，系统如何重新组织，正常工作

多处理机的硬件结构 紧耦合和松耦合 机间互连形式----性能的重要因素 存储器的组织

紧耦合多处理机 是通过共享主存来实现处理机间通讯，通信速率受限于主存的频率。 减少主存冲突，采用模m多体交叉存取； 是否带专用Cache，有两种 各个处理机为同构型，同一类型、功能相同的多处理机；

处理机之间共享主存储器，通过高速总线或高速开关连接。 主存储器有多个独立的存储模块 每个CPU能够访问任意一个存储器模块 通过映象部件MAP把全局逻辑地址变换成局部物理地址 通过互连网络寻找合适的路径，并分解访问存储器的冲突 多个输入输出处理机IOP也连接在互连网络上，I/O设备与CPU共享主存储器。 处理机个数不能太多，几个到十几个

紧密偶合方式要求有很高通信频带。可以采用如下措施： 采用高速互连网络 增加存储器模块个数，一般n?m，取1～2倍之间。 每个存储器模块再分成多个小模块，并采用流水线方式工作。 每个CPU都有自己的局部存储器LM。 每个CPU设置一个Cache。

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

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

松耦合多处理机 每一台处理都由容量较大的局部存储器，减少访存冲突，不同处理机间或者通过通道互连实现通信，或者通过消息传送系统（MTS）。 可看成分布系统； 松耦合非层次型多处理机 层次型总线形式的多处理机

LM0 IOP0 互连网络 通过多输入输出输出口连接的多处理机 CPU0 ……

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

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

机间互联形式 总线形式 环形互连形式 交叉开关形式 多端口存储器形式 蠕虫穿洞寻径网络 开关枢纽结构形式

总线形式 多个处理机、存储器模块和外围设备通过接口与公用总线相连，采用分时或多路转接技术传送。 结构简单，成本低，增减模块方便，但对总线的失效敏感。 IBM Stretch、UNIVAC Larg 提高总线的系统效率： 采用优质高频同轴电缆，用光纤； 采用多总线方式减少冲突概率；

总线仲裁算法 静态优先级算法：为每一个连到总线的部件分配一固定的优先级 固定时间片算法：把总线按固定大小时间片，轮流提供给部件使用 适合同步总线，时钟同步 动态优先级算法：让总线上各部件优先级可根据情况按一定规则动态地改变 先来先服务算法：按接受到访问总线请求先后顺序来响应

环形互连形式 总线形成环形互连。 令牌（Token） 点点连接，物理参数容易控制 适合于高带宽的光纤；

P6 P7 P5 P4 P0 P1 P3 P2 级间采用环形互连的多处理机

交叉开关形式 包含一组纵横开关阵列。 是总线方式的极端。 总线数=m+I+n,m：存储器模块数，n：处理机数，I：I/o设备数，一般：M>=I+N 交叉开关阵列复杂 例子：美国。C.MMP、S-1

Pn M1 M2 Mm I/O1 I/Oi 交叉开关形式

多端口存储器形式 如果每个存储器模块有多各访问端口，且将分布在交叉开关矩阵中的控制、转换和优先级仲裁逻辑分别移到相应存储器模块的接口中。

I/O1 M1 M4 M3 M2 P1 P2 四端口存储器形式的结构

UNIVAC

CRAY_XMP

开关枢纽结构形式 把互连结构的开关设置在各个处理机或其接口内部，组成分布式结构。 美国加州大学伯克利分校设计的树形多处理机X-TREE

存储器的组织 并行存储器的构成 多Cache的一致性问题

并行存储器的构成 有高位交叉和低位交叉 低位交叉：按物理地址顺序轮流地分布在各个存储模块中。 不连续，步距为m 向量、流水或阵列处理机中采用低位交叉 高位交叉：按物理地址顺序从模块0到模块m-1依次连续分布。 连续 多处理机中采用高位交叉；

(n-1)*m im m (n-1)*m+1 im+1 m+1 1 n*m-1 (i+1)m-1 2m-1 m-1 模块0 模块1 模块m-1 模块内部单元号 模块号 log2n log2m m个模块的低位交叉编址

n-1 i 1 2n-1 n+i n+1 n M*n-1 (m-1)n+i (m-1)*n+1 (m-1)*n 模块0 模块1 模块m-1 模块内部单元号 模块号 log2n log2m m个模块的高位交叉编址

本地存储器（HomeMemory）：处理机常用到的存储器模块；

M0 M1 Mm-1 Pp-1 处理机存储器互连网络PMIN- 本地存储器的概念

§2 紧耦合多处理机多Cache的一致性问题

多Cache的一致性问题 每一个处理机都有自己专用的Cache，但主存中同一个信息块在多个Cache中都有时，会出现信息不一致情况； 写直达法---保证一个； 进程迁移----将一个尚未执行完而被挂起的进程调度到另一个空闲的处理机上去执行； 对于进程迁移的Cache不一致性----禁止进程迁移

写直达法缓存一致性问题的例子 时间 共享内存 高速缓存 C0 C1 C2 C3 说明 b b - - - C0读入块b 1 b b - b b b - - - C0读入块b 1 b b - b C1和C3读入块b 2 b b - b3 处理器P3修改块b的副本。现在系统处于不一致状态 3 b3 处理器P3执行写直达式。因为C0和C1拥有不同的副本，系统处于不一致状态 4 b3 b3 - b3 共享内存控制器更新C0和C1。现在系统处于一致性状态

写回法缓存一致性问题的例子 时间 共享内存 高速缓存 C0 C1 C2 C3 说明 b b - - - C0读入块b 1 b b - b b b - - - C0读入块b 1 b b - b C1和C3读入块b 2 b b - b3 处理器P3修改块b的副本。现在系统处于不一致状态 3 B b0 b1 - b3 处理器P0和P1各自修改块b的副本 4 B1 P1执行写回式到内存 5 b1 ？ b1 b1 ? 哪个副本的值可以更新到内存和缓存中？

多Cache的一致性问题的解决办法 解决进程迁移引起的多Cache不一致性 以硬件为基础实现多Cache的一致性

多Cache的一致性问题 两类方法： 硬件方法------通讯量大，处理机数多时复杂； 硬件为基础----监视Cache协议（Snoopy Protocol）写作废法、写更新法 软件为基础----目录表法，全映像目录表法、有限目录表法、链式目录表法 硬件方法------通讯量大，处理机数多时复杂； 软件方法------减少复杂，降低通讯量，性能价格比高，适合于处理机数多。实验系统