多处理机

郑振宁2024年4月12日大约 18 分钟

多处理机

真题

简答题

简述多处理机的概念并根据硬件构形不同写出多处理的两种类型 2010

简述多处理机主从型操作系统的优缺点、适用场合。1804 1007。

简述多处理机操作系统中各自独立型操作系统的优缺点 1204

简述设计多处理机的目的 2008 0607 0704 0607

简述多处理机要解决的主要技术问题 0804

简述机群系统与传统的并行处理系统相比较所具有的优点。1804 1610 1604 1104 0404

简述紧耦合多处理机中解决多Cache一致性的办法 1910

简述任务粒度的大小对多处理机性能和效率的影响。1504

简述多处理机机间互连的形式。1304

简述多处理机与阵列机在并行等级、硬件、算法和系统管理、指令流上的区别。1704 2104 ** **

简述紧耦合多处理机以软件为基础实现多cache一致性的优缺点及应用场合 2210

问题

多理机（MIMD）

应试要求

本章讲述多处理机结构、构形、机间互连、紧赮合多处理机多 Cache 的一致性、并行算法、程序并行性、并行语言、操作系统、多处理机的发展。

本章总的要求是：了解多处理机的特点、主要技术问题；理解紧耦合和松耦合的构形和各种机间互连：了解紧耦合多处理机多 Cache 的一致性问题与解决办法：掌握并行算法研究思路，程序并行性分析，并行任务的派生和汇合；理解任务粒度、通信开销对性能的影响;了解操作系统类型、特点、应用场合，以及多处理机的发展。

本章的重点是：多处理机的结构特点，程序并行性，并行任务的派生与汇合，大规模并行处理机 MPP 和机群系统的特点。难点是：并行算法的研究，程序中并行任务的派生和汇合。

1、多处理的概念【*^】

简述设计多处理机的目的 2008 0607 0704 0607
简述多处理机的概念并根据硬件构形不同写出多处理的两种类型 2010

从概念、目的、类别阐明多处理机

多处理机是指具有两台以上的处理机，共享I/O子系统；机间经共享主存或高速通讯网络通信；在操作系统控制下协同求解大而复杂问题的计算机系统。多处理机属 MIMD 系统。

使用多处理机的目的有2个：

提高系统的解题速度。通过多台处理机对多个作业、任务进行并行执行来提高解题速度。
提高系统的可靠性、适应性和可用性。通过多台处理机的重新组织来保障系统的可靠性、可用心和适应性。

多处理机从不同角度看分类不同：

从结构和应用目的的不同，多处理机分为：同构型、异构型、分布型。

从硬件构型的角度，多处理机分为：

紧耦合多处理机
松耦合多处理机 * ：又分 非层次型 和 层次型 。

2、与并行处理机的区别

【图】多处理机与并行处理机的差别

3、与阵列处理机的区别

简述多处理机与阵列机在并行等级、硬件、算法和系统管理上的区别。1704
简述多处理机与阵列处理机在指令流和并行等级的区别。 2104

从**“并硬算系指”**5个方面谈：

并行等级不同：

阵列处理机主要针对向量数组、实现向量指令操作级的并行，是开发并行性中的同时性；
多处理机实现的是作业或任务间的并行，是开发并行性中的并发性。

硬件结构不同：

阵列处理机用简单规整的互连网络连接各部件；
多处理机要用多个指令部件控制，通过共享主存或机间互连网络实现异步通信。

算法支持不同：

阵列处理机仅限于对向量数组的支持；
多处理机不仅限于向量、数组、还要挖掘和实现更多通用算法中隐含的并行性。

系统管理不同：

阵列处理机；
多处理机依靠操作系统等软件手段，解决资源的调度和分配问题。

指令流不同

阵列处理机是单指令流。
多处理机是多指令流。

3、多处理的技术问题 ^

简述多处理机要解决的主要技术问题 0804

多处理面临着一系列技术问题：

【互连问题】如何解决处理机、存储器模块、IO系统之间的互连问题？
【分配问题】如何解决资源的调度和分配问题，以防止死锁与负荷过重 ?
【分割问题】如何处理任务大小、任务粒度的分割问题 ?
【故障问题】如何处理系统故障，使之重新正常工作 ?
【同步问题】如何处理并行执行任务和进程间的同步问题 ?
【并行问题】如何实现各级的全并行，以最大限度开发系统的并行性 ?

4、多处理的硬件构形

多处理机的硬件构形有紧耦合和松耦合两种。

紧耦合多处理机 *

紧耦合多处理是通过共享主存来实现处理机间通讯，通信速率受限于主存的频率。处理机数受限于互连网络带宽和各处理机访主存冲突的概率，可通过采用模m多体交叉存取来减少主存冲突。

【图】紧耦合多处理的结构
image-20230227212437399
image-20230227212713213

紧耦合多处理机多Cache一致性问题【***^】

在并行处理机和多处理机系统中，采用局部 Cache 会引起 Cache 与共享存储器之间的一致性问题。出现不一致性问题的原因有3个：

可写数据的共享
进程的迁移
I/O 的传输

那么，如何解决紧耦合多处理机的多Cache一致性问题？ 紧耦合多处理机解决多Cache一致性的办法：紧耦合多处理机之所以会出现多cache一致性问题，是因为这些处理机之间是通过共享主存进行通信导致的。

进程迁移引起的：
- 未迁移的，禁止进程迁移；
- 已迁移的，在进程挂起时，将改写过的数据强制写回主存相应位置。
以硬件为基础的：
- 监视cache协议法（cache控制器相互监视），有2种：
  - 写更新法；
  - 写作废。
- 目录表法（记录数据块使用情况），有3种：
  - 全映像目录表、
  - 有限目录表、
  - 链式目录表
以软件为基础的：
- 可写的数据不存入cache。
- 在某段时间内，可写的数据不可改写。
以软件为基础解决 cache 一致性的做法，主要优点是可以降低硬件的复杂性，降低对互连网络通信量的要求，因而性能价格比较高，适用于处理机数多的多处理机。

⚠️ 目前用得最多的是用硬件的方式处理多cache一致性问题，原因：禁止进程迁移的方式限制了进程迁移的应用；软件方式的实现极为复杂且不可控。

松耦合多处理机

【*^】松耦合多处理机中，每一台处理机都有一个容量较大的局部存储器，用于存储经常用的指令和数据，以减少访存冲突；不同处理机间的通信方式可以采用通道互连或消息传送系统实现通信；松耦合多处理适用于粗粒度的并行计算；其一般分为 ^：

层次型松耦合多处理机
非层次型松耦合多处理机

两图说明详见《计算机系统结构（2012版）》/李学干/p240-241
【图】通过消息传送系统实现通信的松散耦合非层次型多处理机
image-20230227214156753
【图】层次型总线形式的多处理机
image-20230227214249286

5、机间互连形式【^】

机间的互连形式是决定多处理机性能的重要因素。为实现“高通信速率，低成本”，多处理机一般采用以下几种互连形式：

总线形式，适用于机数较少的多处理机系统。
环形互连形式，适用于高带宽光纤的多处理机系统。
交叉开关形式，适用于机数较多的多处理机系统。
多端口存储器形式，适用于机数较少的多处理机系统。
开关枢纽结构形式
蠕虫穿洞寻径网络

简记：总环交开多+蠕虫

总线形式

多个处理机、存储器模块和外围设备通过接口与公用总线相连，采用分时或多路转接技术传送。总线形式有着结构简单、成本低、模块增减方便，但对总线的失效敏感等特点。适用于处理机数少、系统流量较低的场合；可以通过采用优质高频同轴电缆或光纤或多总线方式减少冲突概率。为了解决多个处理机同时访问公用总线的冲突，研制出了了以下几种总线仲裁算法：

静态优先级算法
固定时间片算法
动态优先级算法
先来先服务算法

环形互连形式

环形互连形式适用于高带宽的光纤。

【图】环形互连形式，详见《计算机系统结构（2012版）》/李学干/p242
image-20230228184854894

交叉开关形式

交叉开关形式有着扩充性好，系统流量大，但结构复杂，硬件成本高的特点；适用于处理机较多的情况【处理机数≤32（台）】

【图】交叉开关形式，详见《计算机系统结构（2012版）》/李学干/p245
image-20230228184936673

多端口存储器形式

如果每个存储器模块有多个访问端口，且将分布在交叉开关矩阵中的控制、转移和优先级仲裁逻辑分别移到相应存储器模块的接口中，就构成了多端口存储器形式。适用于机数少的多处理机系统。

【图】多端口存储器形式
image-20230228185540965

蠕虫穿洞寻径网络

机间采用小容量缓冲存储器，实现消息分组寻径存储转发。

中科院计算所国家智能计算机研究开发中心研制的 曙光1000 多处理机就是采用蠕虫网络来减少存储转发所需的通信时间。

开关枢纽结构形式

把互连结构的开关设置在各个处理机或其接口内部，组成分布式结构。

美国加州伯克利分析设计的 树型多处理 X-TREE 。

6、多处理机的硬件结构 -

7、并行性与性能【***^】

7.1 并行算法

并行算法是指可同时执行的多个进程的集合，各进程可相互作用、协调和并发操作。

并行算法的分类【*^】

按运算基本对象分：

数值型。基于代数运算，如矩阵运算、多项式求值、线性方程组。
非数值型。基于关系运算，如选择、排序、查找、字符处理。

按并行进程间的操作顺序分：

同步型。并行的各进程间因相关而导致必须顺序执行。
异步型。各进程间执行时相互独立，互不相关。
独立性。各进程间完全独立，互不影响。

按计算任务的大小分：

细粒度。向量或循环级的并行。
中粒度。较大的循环级并行，确保这种并行的好处可以补偿并行带来的额外开销
粗粒度。子任务间的并行。

7.2 程序并行性

程序并行性分析

假定一个程序包含 $P_1， P_2， \cdots， P_i， \cdots， P_j， \cdots， P_n$ 等 $n$ 个程序段，设 $P_i$ 和 $P_j$ 程序段都是一条语句， $P_i$ 在 $P_j$ 之前执行。那么讨论下述3种相关：

数据相关
数据反相关
数据输出相关

数据相关

【图】数据相关的场景
image-20230301192435885

发生数据相关时，$P_i$ 和 $P_j$ 不能并行。

数据反相关

【图】数据反相关的场景
image-20230301192709367

解决数据反相关的办法：适当同步控制，可以并行。

7.3 并行语言与并行编译

FORK/JOIN【*】

FORK/JOIN 又称为康佳（M.E.Conway）形式：

FORK m： 派生出 $标号m$ 的新进程

JOIN n： 附有计数器，执行时+1，与n 比较：

$=n$ 时，允许进程执行 JOIN 语句并继续执行后续语句，计数器清0
$＜ n$ 时，先让进程结束，将其占用的资源释放出来，分配给其他任务，若无其他任务，则资源会空闲在那。

【图】FORK/JOIN
image-20230301194032068
image-20230301200434683

7.4 多处理的性能

衡量多处理性能的 4 个指标：

$P$ ：可并行处理的处理机数量
$T_p$ ：P台处理机运算的级数（树高）
$S_p$ ：加速比，$S_p=T_1/T_p$
$E_p$ ：效率，$E_p=S_p/P$

霍纳法则【*】

【图】霍纳法则的应用，计算 $E_2=a+b(c+edf+g)+h$
image-20230301191805181
利用交换律和结合律减少树高：$E_2=(a+h)+b((c+g)+def)$
image-20230301191643496
再利用分布律，进一步降低树高：$E_2=(a+h)+bc+bg+bdef$
image-20230301191911503

8、多处理机的操作系统

多处理操作系统有3类：

主从型多处理机操作系统
各自独立型多处理机操作系统
浮动型多处理机操作系统

主从型

简述多处理机主从型操作系统的优缺点、适用场合。1804 1007

管理程序在主处理机上运行，除执行管理功能外。也能做其他方面的应用。由于主处理机是负责管理系统中所有其他从处理机的状态及其工作的分配，只把从处理机看成是一个可调度的资源，实现对整个系统的集中控制，因此，也称为集中控制或专门控制方式。从处理机是通过访管指令或自陷软中断来请求主处理机服务的。

优点

主从型操作系统的结构比较简单；管理程序只在一个处理机上运行，除非某些需递归调用或多重调用的公用程序，一般都不必是可再入的；只有一个处理机访问执行表，简化了管理控制的实现。所有这些均使操作系统能最大限度地利用已有的单处理机多道程序分时操作系统的成果，只需要对它稍加扩充即可。因此，实现起来简单、经济、方便，是目前大多数多处理机操作系统所采用的方式。

简言之：

结构简单；仅有一张访问执行表，简化了管理控制的实现。
管理程序只在一台处理机上运行，一般是不必可再入；

缺点

一旦发生故障，很容易使整个系统瘫痪，这时必须由操作员于预才行。如果主处理机不是设计成专用的，操作员可用其他处理机作为新的主处理机来重新启动系统。整个系统显得不够灵活，同时要求主处理机必须能快速执行其管理功能，提前等待请求，以便及时为从处理机分配任务，否则将使从处理机因长时间空闲而显著降低系统的效率。即使主处理机是专门的控制处理机，如果负荷过重，也会影响整个系统的性能，特别是当大部分任务都很短时，由于频繁地要求主处理机完成大量的管理性操作，系统的效率将会显著降低。

对主处理机的可靠性要求高；
系统不灵活且负荷过重时容易引发性能问题；

适用场合

适用于工作负荷稳定，从处理机能力明显低于主处理机的场合，或功能相差大的异构多处理。

各自独立型

各自独立型操作系统是将控制功能分散给多台处理机，共同完成对整个系统的控制工作。每台处理机都有一个独立的管理程序（操作系统的内核）在运行，即每合处理机都有一个内核的副本，按自身的需要及分配给它的程序需要来执行各种管理功能。由于多合处理机执行管理程序，要求管理程序必须是可再入的，或对每台处理机提供专用的管理程序副本。

优点

很适应分布处理的模块化结构特点，减少对大型控制专用处理机的需求；某个处理机发生故障，不会引起整个系统瘫痪，有较高的可靠性；每台处理机都有其专用控制表格，使访问系统表格的冲突较少，也不会有许多公用的执行表，同时控制进程和用户进程一起进行调度，能取得较高的系统效率。

系统的可靠性和效率都比较高；
不受大型专用处理机的控制；
能够适应分布处理的模块化结构特点。

缺点

实现复杂。尽管每台处理机都有自己的专用控制表格，但仍有一些共享表格，会增加共享表格的访问冲突，导致进程调度的复杂性和开销的加大。某台处理机一旦发生故障，要想恢复和重新执行末完成的工作较困难。每台处理机都有自己专用的输入/输出设备和文件，使整个系统的输入/输出结构变换需要操作员干预。各处理机负荷的平衡比较因难。各台处理机需有局部存储器存放管理程序副本，降低了存储器的利用率。

进程调度复杂且开销大；
各处理机间的负荷难以平衡；
存储器利用率低。

适用场合

适用于松耦合多处理机。

浮动型

浮动型操作系统是介于主从型和各自独立型操作系统之间的一种折中方式，其管理程序可以在处理机之间浮动。在一段较长的时间里指定某一合处理机为控制处理机，但是具体指定哪一台处理机以及担任多长时间控制处理都是不固定的。主控制程序可以从一台处理机转移到另一台处理机，其他处理机中可以同时有多台处理机执行同一个管理服务子程序。因此，多数管理程序是可再入的。由于同一时间里可以有多台处理机处于管态，有可能发生访问表格和数据集的冲突，一般采用互斥访问方法解决。服务请求冲突可通过静态分配或动态控制高优先级方法解决。

优点

各类资源可以较好地做到负荷平衡。一些像 I/0 中断等非专门的操作可交由在某段时间最闲的处理机去执行。它在硬件结构和可靠性上具有分布控制的优点，而在操作系统的复杂性和经济性上则接近于主从型。如果操作系统设计得好，将不受处理机机数多少的影响，因而具有很高的灵活性。

各类资源可以较好地做到负荷平衡
系统具有分布控制的优点且灵活性高

缺点

设计难

9、多处理的发展

系统层面：“性开可资”
1. ① 系统的性能价格比高；（性价比高）
2. ② 系统的开发周期短；（开发周期短）
3. ③ 系统的可扩展性好；（可扩展性好）
4. ④ 系统的资源利用率高；（资源利用率高
用户层面：“投编”
5. ⑤ 用户投资风险小；（投资风险小）
5. ⑥ 用户编程方便。（编程方便）