<计算机系统结构>CA7 多处理机 MIMD

CA7 多处理机 MIMD

多处理机：多台处理机共享 I/O 系统，经共享主存或高速通信网络通信，在统一操作系统控制下，协同处理复杂问题的计算机系统。为 作业/任务级并行。

多处理机要解决以下问题：

• 硬件结构上，处理机、存储器、I/O 系统 间的互连方式
• 最大限度开发系统并行性，以实现多处理机各级的全面并行
• 如何选择分割任务和子任务大小，使并行度高，辅助开销小
• 如何协调多处理机中并行任务/进程间的同步问题
• 如何将各任务分配到多个处理机上，进行处理机调度、任务调度、资源调度，避免死锁
• 单个处理机故障时，如何对系统进行重新组织而使其不瘫痪

由于应用目的和结构不同，多处理机分为 同构型、异构型、分布型 三种。

CA7.1 多处理机的硬件结构

处理器间的连接分为 紧耦合 与 松耦合 两种：

• 紧耦合多处理机：通过 共享主存 实现处理机间通信。其通信速率受限于主存频宽。

  由于各处理机与主存经互连网络连接，系统中的 处理机数量 会受限于 互连网络带宽 及 多处理机访问主存发生冲突的概率。

  就处理机而言，有 同构对称型（处理机结构相同）和 异构非对称型（处理机结构不同）。并行任务时，常用同构对称型的紧耦合多处理机。

  紧耦合多处理机采用 非对称 I/O 互连，即连到一台处理机的设备不能被另一处理机直接访问。为避免单一处理机若故障引起的 I/O 失连，可以采用 冗余连接（使 I/O 设备连接到多个处理机）

  紧耦合多处理机共享主存，可能出现 Cache 一致性问题。解决方法有：

  • 限制功能：禁止进程迁移（禁止可能造成问题的功能）、写直流
  • 硬件方法：监听法（写更新、写作废）、目录法（全映像目录法、有限目录法、链式目录表法）
  • 软件方法：（没有。因为 Cache 对于软件是透明的）

• 松耦合多处理机：每台处理机有一个较大的局部存储器，存储常用指令和数据，以减少耦合系统中的主存冲突。

  不同处理机通过 通道互连/消息传递系统 通信。粗粒度并行。

  松耦合多处理机的构形有 非层次型 和 层次型。

机器间的链接方式有以下几种：

• 总线形式：多个处理机、存储器模块、外围设备间通过接口与公用总线连接，采用分时或多路转接技术传递。

  单总线方式结构简单、成本低，但效率较差，对总线失效敏感。可以考虑的优化方式：使用光纤、多总线

• 环形互连：总线形成闭环。信息传递时要引入令牌概念。

• 交叉开关：总线数等于全部相连的模块数，每个处理机与 I/O 设备都能分到总线与存储器连通并行通信。互连网络不争用开关，可以大大展宽互连传输频带，提高系统效率。

• 多端口存储器模式：存储器具有多个端口，使得原本分布于交叉开关矩阵中的控制、转移、优先级仲裁逻辑移到存储器相应模块接口中。

• 蠕虫穿洞寻径网络：机间采用小容量缓冲存储器，用于消息分组寻经存储转发。将消息分割成一系列更小的小组，小组以异步流水方式不间断地按序传送。利用虚拟通道思想，使得存在于发送和接收节点间的物理通道能被多个虚拟通道共享

• 开关枢纽结构形式：按照 多端口存储器模式 的思想，将互联结构开关设置在各处理机或接口内部，组成分布式结构。

多处理机的主存通常采用多个模块构成的并行存储器，以尽量减少多处理机访问同一模块的冲突。其组织方式有：

• m 个模块低位交叉编址：能更多地让多个存储模块服务同一处理机

• m 个模块高位交叉编址：能更多地让单个存储模块服务同一处理机

• 二维并行存储

  每个处理机拥有一个模块作为 本地存储，访问各自本地存储的速度比访问其他模块更快。

  不同模块间采用 高位交叉。各模块内部（本地存储内部）使用 低位交叉。

CA7.2 多处理机的操作系统

多处理机操作系统设计时要注意以下问题：

• 处理机的分配、进程调度
• 进程间的同步和通信
• 存储系统的管理、文件系统的管理
• 某处理机或设备故障时系统的重组

多处理机操作系统的分类：

• 主从型（集中控制、专门控制）：管理程序仅在指定处理机（称为主处理机）上运行。从处理机通过陷入指令请求主处理机服务。
• 各自独立型：每台处理机有独立的管理程序运行。管理程序必须是可再入的。
• 浮动型：在较长时间内随机指定一台处理机为控制处理机。

CA7.3 多处理机的并行性

多处理机的并行性既存在于指令内部，也存在于指令外部。要利用 算法、程序设计语言、编译、操作系统、指令、硬件 等多种途径来开拓指令外部的并行性。

并行算法的分类方法：

• 按运算基本对象分为：数值型、非数值型
• 按并行进程间的操作顺序分为：同步型（任务中数据相关）、异步型（任务中无相关，任务起止有控制相关）、独立型
• 按计算任务大小分为：细粒度、中粒度、粗粒度
• 按并行进程是否相同分为：同构型（SIMD）、异构型（MIMD）

并行算法的划分方式有：

• 程序划分：将程序从逻辑上分段

  将大的程序分解为多个过程（进程、任务、程序段），每个过程作为一个节点，用树形结构描述过程的关系。

• 数据划分：将数据分组

分析并行算法使用的参数：

• $P$：可并行处理的处理机个数
• $T_P$：处理机运算级数（树的高度）
• $S_P$：单处理机顺序运算级数，与 $P$ 台处理机并行运算的 $T_P$ 之比
• $E_P$：$P$ 台处理机的设备利用率，有 $E_P=\dfrac{S_P}{P}$

程序并行时，可能发生相关：

• 数据相关：即 先写后读相关。

  如 $P_i:A=B+D\qquad P_j:C=A+E$。此时 $P_i$ 与 $P_j$ 不能并行。

• 数据反相关：即 先读后写相关。

  如 $P_i:C=A+E\qquad P_j:A=B+D$。必须保证 $P_i$ 对 $A$ 先进行读出才能并行

• 数据输出相关：即 先写后写相关。

  如 $P_i:A=B+D\qquad P_j:A=C+E$。必须保证 $P_i$ 先进行写入才能并行。

• 互为输出变量：同时具有 先写后读 和 先读后写 相关。

  如 $P_i:A=B\qquad P_j:B=A$。$P_i$ 与 $P_j$ 必须同时执行。

• 若两个程序不存在任何数据相关（无共同变量，或共同变量只出现在右侧的源操作数），则可以无条件并行、串行或交换串行。

并行任务的派生 是使一个任务执行的同时，派生出与其并行执行的其他任务，分配给不同处理机完成。待其全部完成后，再汇合起来继续执行后续任务。

CA7.4 多处理机的发展

下面是按照访存模型的多处理机的分类：

$$\operatorname{MIMD}\begin{cases} {多处理器(单地址空间共享存储器)}\begin{cases} 中央存储器\ \operatorname{UMA}\begin{cases} \operatorname{PVP\ (Cray\ T-90\ 等)} \\\operatorname{SMP\ (Intel\ SHV\ 等)} \end{cases} \\分布处理器\ \operatorname{NUMA}\begin{cases} \operatorname{COMA\ (KSR-1,\ DDM\ 等)} \\\operatorname{CC-NUMA\ (SGI\ Origin\ 2000\ 等)} \\\operatorname{NCC-NUMA\ (Cray\ T3E\ 等)} \end{cases} \end{cases} \\{\operatorname{NORMA}(多地址空间非共享存储器)}\begin{cases} \operatorname{松散耦合\ Cluster\ (IBM\ SP2\ 等)} \\\operatorname{紧耦合\ MMP\ (Intel\ TFLOPS\ 等)} \end{cases} \end{cases}$$

• 分布式共享存储器多处理机：共享虚拟存储器。物理上分散存储，逻辑上统一编址，从而统一虚拟地址空间。

  graph TB
  LM1[LM]---PC1[P/C]---N[定制网络]
  LM2[LM]---PC2[P/C]---N
  LM3[LM]---PC3[P/C]---N
  subgraph 虚拟分布共享存储 DSM
  LM1
  LM2
  LM3
  end

• 集中共享存储多处理机：任意处理器可直接访问内存地址，其访问延迟、带宽、几率等价，系统是对称的。

  graph TB
  PC1[P/C]---N[总线或交叉开关]---SM[SM]
  PC2[P/C]---N
  PC3[P/C]---N
  subgraph 共享主存
  SM
  end

• 多向量多处理机：多台处理机、多个向量流水部件和标量部件，共享主存的松耦合结构。

• 并行向量处理机：若干数目不等的强功能的专用向量处理器，共享若干存储器模块，以高带宽的纵横交叉开关互连。

  一般不用 Cache，而是采用大量向量寄存器和指令缓冲寄存器。

• 大规模并行处理机 MPP：物理与逻辑上都是分布内存，采用高通信带宽低延迟的互连网络。

  是一种异步的 MIMD 机器，扩展性强。各进程有私有地址空间，进程间采用传递消息相互作用。

• 集群系统 Cluster（机群系统）：每个节点都是完整的计算机，每个节点都有完整的操作系统。

  节点间通过高性能网络相互连接，网络接口和 I/O 总线松耦合连接。

  机群系统有许多优势：性价比高、系统开发周期短、可扩展性好、资源利用率高、投资风险小、编程方便

CA7.5 数据流计算机和归约机

为了提高计算机并行处理的能力，有必要突破 冯·诺依曼 结构，寻求更有利于开发高度并行功能的计算机模型

计算模型中不仅要考虑数据控制类型，还要考虑驱动模式（控制机制）。驱动模式有：

• 控制驱动：冯·诺依曼结构中的驱动方式。指令执行次序受指令计数器控制。特点是 共享数据，串行执行。

• 数据驱动：只要程序中任意指令所需的操作数齐备，就能立即启动执行。不需要指令计数器控制。数据驱动是一种提前求值的策略

  数据流计算机 就是一种数据驱动计算机。根据对数据令牌的处理方式不同，数据流计算机又分为 静态数据流计算机 和 动态数据流计算机

• 需求驱动：一个操作仅在需要用到其结果时才开始执行。操作数不齐备时，再递归启动给出操作数的操作。需求驱动是一种滞后求值的策略

  归约机 就是一种需求驱动计算机。归约又分为 串规约 和 图规约。

• 模式匹配驱动：计算的进行是由谓词模式匹配加以驱动的。程序的执行受控于寻找谓词的匹配和度量的归一操作，其中的谓词是代表客体间关系的一种字符串模式。