【计算机组成原理】计算机系统结构笔记（9）：多处理机

200803本篇是郑纬民《计算机系统结构》的读书笔记，欢迎各位路过指正！今天是第九章也就是最后一章：多处理机。

文章目录

• 9. 多处理机
• 9.1 多处理机结构
• 9.2 多处理机性能模型
• 9.3 多处理机的Cache一致性
• 9.4 大规模并行处理机
• 9.5 对称多处理机
• 9.6 机群系统

9. 多处理机

• 多处理机：两个或两个以上处理机通过高速互连网络连接起来，在统一的操作系统管理下，实现指令以上级（任务级、作业级）并行。

9.1 多处理机结构

• 分类：

  • 按照处理机之间的连接程度：紧密偶合和松散偶合多处理机；
  • 按照是否共享主存储器：共享存储器和分布存储器多处理机；
  • 按照处理机类型：同构型和异构型多处理机；
  • 按照处理机的个数：大规模并行处理机MPP和对称多处理机SMP。
  • 按照PE与IOP之间互连方式：对称型（每个IOP能够连接到所有PE上）、非对称型（每个IOP只与一个PE连接）、冗余对称型（一个PE与多个IOP连接）
  • 按照存储器的访问方式：均均存储器，UMA模型；非均均存储器，NUMA模型；只有Cache，COMA模型。

• 松散耦合多处理机：处理机之间的连接频带比较低，通过并行口或串行口把多台计算机连接起来。通过Ethernet网络接口连接多台计算机。

• 紧密耦合多处理机：处理机之间共享主存储器，通过高速总线或高速开关连接。处理机个数不能太多，一般几个到几十个。要求有很高通信频带

• 多处理机系统的特点：结构灵活、程序并行性、并行任务派生、进程同步。

9.2 多处理机性能模型

• 引起峰值性能下降的原因：通信延迟、同步开销、空闲状态、无用工作、系统调度。

• 并行性在很大程度上依赖于R/C比值，其中R为程序执行时间，C为通信开销。R/C是衡量任务粒度的尺度。粗粒度并行：R/C大，通信开销小；细粒度并行：R/C小，通信开销大

• 2台处理机总处理时间$T=R\max \{M-K,K\}+C(M-K)K$T=Rmax{M−K,K}+C(M−K)K。K为任务分配参数。当通信时间很小时，把M个任务平均分给两台处理机当通信时间很大时，把M个任务分配给一台处理机。

• N台处理机：M个任务，N台处理机。当R/C＞M/2时采用平均分配方法，当R/C＜M/2时采用集中分配方法。

  • 通信开销为线性函数的模型。总处理时间$T=R\frac{M}{N}+CN$T=RNM​+CN，极小值$N = \frac{\sqrt{RMC}}{C}$N=CRMC​​。最大加速比$S=\frac{\sqrt{RMC}}{2C}$S=2CRMC​​。
  • 通信与计算完全重叠的模型：能够采用重叠或流水线方式并行进行。总处理时间$T=\max \{R\lceil\frac{M}{N}\rceil,\frac{C}{2}(M^2-\sum_{i=1}^Nk_i^2)\}$T=max{R⌈NM​⌉,2C​(M2−∑i=1N​ki2​)}。当R/C＝M/2，即把任务平均分配给两台处理机时，加速比最大。
  • 具有多条通信链的模型，总处理时间$T=\frac{RM}{N}+\frac{CM^2}{2N}(1-\frac{1}{N})$T=NRM​+2NCM2​(1−N1​)。当Ｎ≥2时，随着处理机台Ｎ增加，总处理时间肯定减小。

• 结论：多处理机系统结构需要额外开销；当处理机台数增加时，额外开销时间也增加；R/C比值越大，越有利于计算过程；为了使价格和性能都比较合理，处理机数目存在一个极大值。

9.3 多处理机的Cache一致性

• 在并行处理机和多处理机系统中，采用局部Cache会引起Cache与共享存储器之间的Cache一致性问题。

• 原因：共享可写的数据、进程迁移、I/O传输。

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

• 监听协议：

  • 写无效：在本地Cache的数据块修改时使远程数据块都无效。

  • 写更新：在本地Cache数据块修改时通过总线把新的数据块广播给含该块的所有其他Cache。

  • 采用写通过方式的Cache：数据块有两种状态，有效和无效。
    

  • 采用写回方式的Cache：只读状态表示整个系统中有多个数据块拷贝是正确的，读写状态表示数据块至少被修改过一次，存储器中相应数据块还没有修改，在整个系统中只有一个数据块拷贝是正确的。
    

  • 写一次协议：第一次写Cache采用写通过方式，以后采用写回方式。

• 目录协议：Cache目录结构。全映射目录：存放全局存储器每个块的有关数据。有限目录：每个目录项的指针数固定。链式目录：把目录分布到所有Cache中。 当一个CPU对Cache进行写操作时，要根据Cache目录中的内容将所有其他存有相同内容的所有Cache拷贝无效，并置重写位。
  • 全映射目录：目录项中有N个处理机位和一个重写位。每个数据块有两个状态位。一位表示数据块是否有效，另一位表示有效块是否允许写。
  • 有限目录：当处理机数目为N时，限制目录大小为$\mathcal{O}(N \log N)$O(NlogN)。当Cache1和Cache2中都有X的拷贝时，若P3请求访问X，则必须在在Cache1和Cache2中选择一个使之无效，这种替换过程称为驱逐。
  • 链式目录：通过维护一个目录指针链来跟踪共享数据拷贝。在收到所有处理机的回答信号之后，存储器才给该处理机写允许权。

9.4 大规模并行处理机

• 四类多处理机系统：多向量处理机系统、SMP对称多处理机、MPP大规模并行处理机、Cluster 机群系统。

• 采用的关键技术：VLSI可扩展技术、共享虚拟存储技术、虚拟共享存储器。

• 虚拟共享存储器的优点：编程容易、系统结构灵活、可扩充性好, 有较好的软件移植性。

• 虚拟共享存储器实现途径：硬件实现、操作系统和库实现、编译实现。

• 同步MIMD机器： 数据并行可以采用SIMD、多SIMD或同步MIMD模式。
  

• 三个网络：数据网络提供点对点通信。控制网络提供广播、同步、扫描和系统管理功
  能。诊断网络从后台访问所有系统硬件，测试系统完整性，检测和隔离错误。

• 控制处理机：由CPU、存储器、本地磁盘、网络接口、以太网组成。相当于一台标准工作站。

• 处理结点：通过控制网络和数据网络将结点与系统的其它部分相连。

9.5 对称多处理机

• UMA多处理机：均匀存储器存取模型 ，存储器被所有处理机均匀共享。所有处理机对所有存储单元具有相同的存取时间，每台处理机有局部Cache，外围设备可以共享。

• NUMA多处理机：非均匀存储器存取，存储器访问时间随存储单元的位置不同而变化。共享存储器在物理上是分布在所有处理机中的本地存储器。处理机访问本地存储器比较快，访问属于另一台处理机的远程存储器则比较慢。

• COMA多处理机：只有Cache的存储器结构；COMA是一种只用Cache的多处理机系统。远程Cache访问通过分布Cache目录进行共享存储系统拥有统一的寻址空间，程序员不必参与数据分配和传输。

• S2MP结构：实际上是NUMA多处理机系统，采用分布存储器，并通过cache对系统的共享和局部数据都进行缓存。特点：编程容易、可扩展、通信开销小。关键技术：高速无阻塞互连网络、分布式存储器、引入Cache、存储器统一编址、每个处理器结点上有一个目录存储器。

9.6 机群系统

• 机群系统：利用高速网络将一组高性能工作站或高档PC机连接起来，在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实现高效并行处理的计算机系统。属于分布存储系统。

• 特点：系统开发周期短、用户投资风险小、系统价格低、节约系统资源、扩展性好、编程方便。

• 机群系统的关键技术：高效通信系统、并行程序设计环境、并行程序设计语言、负载平衡技术、并行程序调试技术、可靠性技术。

• 并行编译：把传统串行语言程序转换成并行语言程序的过程。

  • 全自动并行编译是方向，但实现起来很困难。
  • 半自动并行编译，程序员通过多次与机器对话，找到串行程序中可以并行执行的部分。

• 负载均衡技术：

  • 静态方法是在编译时针对用户程序的各种信息及并行系统本身的状况对用户程序中的并行任务作出静态分配决策。
  • 动态方法是在程序运行过程中实现负载平衡的。分析并行系统的实时负载信息，动态地将任务在各处理机之间进行分配和调整。