---

一、互连网络

1.1 互连网络概述

什么是互连网络？

互连网络（Interconnection Network）是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。

上述定义中：

• **结点：**处理器、存储模块或者其他设备
• 在拓扑上，互连网络为输入节点到输出节点之间的一组互连或映像
• SIMD(单指令流多数据流)计算机和MIMD(多指令流多数据流)计算机的关键组成部分
• **三大要素：**互联结构、开关元件、控制方式

定义是严谨而又枯燥的，我们不妨假设目前有若干处理器，若干存储器，处理器要访问数据，那么处理器和存储器之间的就是互连网络：

互连网络要快速的根据处理器需求建立与存储器的连接。可以想到总线似乎就有类似的功能，假如我们将NetWork换成总线，那么自然可以实现数据的访问，不过每次只能有一个处理器进行数据访问，所以总线可以看作是最简单的互连网络实现方式。

我们将设备用结点来抽象表示，分为两部分，左部为输入端号，右部为输出端号，互连网络来建立左部点和右部点的映像，就得到了拓扑结构：

可以从4个不同的方面来描述互连网络

1. 定时方式：有同步和异步两种。
   1. 同步系统：使用一个统一的时钟。SIMD阵列处理机就属于这一种类型。
   2. 异步系统：没有统一的时钟，系统中的各个处理机都是独立地工作。
2. 交换方法：有线路交换和分组交换两种
   1. 线路交换：源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。就像老式电话机。
   2. 分组交换：把信息分割成许多组(又称为包)，将它们分别送入互连网络。
      1. 这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据
      2. 结点之间不存在固定连接的物理通路。
3. 控制策略：有集中式和分散式两种
   1. **集中控制方式：**有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。
   2. **分散控制方式：**不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。
4. 拓扑结构：有静态和动态两种
   1. 静态拓扑结构：在各结点之间有专用的连接通路，且在运行过程中不能改变。
   2. 动态拓扑结构：可根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。

---

1.1 互连函数

1.1.1 互连函数

互连网络是输入结点到输出结点之间的一组互连，这种互连可以用互连函数来表示。假设互连网络有N个输入端和N个输出端，分别用0，…，N - 1来表示，则互连函数表示了输入端号和输出端号的连接关系。

互连函数反映了网络输入端数组和输出端数组之间对应的置换关系或排列关系，所以互连函数有时也称为置换函数(Permutation)或排列函数。

互连函数f (x)有时可以采用循环表示，即：
$$(x_0,x_1,\dots \dots x_{j-1})$$
表示：
$$f(x_0)=x_1,f(x_1)=x_2,\dots \dots ，f(x_{j-1})=x_0$$
，j称为该循环的长度

设n=logN，则可以用 n 位二进制来表示N 个输入端和输出端的二进制地址，互连函数表示为:
$$f(x_{n-1}{x}_{n-2}\dots \dots x_1{x}_0)$$

1.1.2 几种基本的互连函数

1.1.2.1 恒等函数

恒等函数实现同号输入端和输出端之间的连接。
$$I(x_{n-1}{x}_{n-2}\dots \dots x_1{x}_0)=x_{n-1}{x}_{n-2}\dots \dots x_1{x}_0$$

1.1.2.2 交换函数

交换函数实现二进制地址编码中第k位互反的输入端与输出端之间的连接。
$$E(x_{n-1}{x}_{n-2}\dots \dots x_{k+1}{x}_k{x}_{k-1}\dots \dots x_1{x}_0)=x_{n-1}{x}_{n-2}\dots \dots x_{k+1}{\bar{x}}_k{x}_{k-1}\dots \dots x_1{x}_0$$
主要用于构造立方体互连网络和各种超立方体互连网络。

它共有n = logN种互连函数。（N为结点个数）

当N = 8，n = 3，可得到常用的立方体互连函数：
$$\begin{gathered} Cub{e}_0(x_2{x}_1{x}_0)=x_2{x}_1{\bar{x}}_0 \\ Cub{e}_1(x_2{x}_1{x}_0)=x_2{\bar{x}}_1{x}_0 \\ Cub{e}_2(x_2{x}_1{x}_0)={\bar{x}}_2{x}_1{x}_0 \end{gathered}$$
变换图形如下：

结构如下：

还是比较好理解的，交换函数实现二进制地址编码中第k位互反。那么对于Cube0，而言，只有第0位互反的输入输出端号会建立连接：

000 - 001 010 - 011 100 - 101 110 - 111，这是变换图形的解释

对于结构图形，三个坐标轴的方向代表了三个位互反的连接端号，交换函数还是很巧妙的。Cube1的解释如下：：

1.1.2.3 均匀洗牌函数

均匀洗牌函数（Shuffle）：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。也称为混洗函数（置换） 。

函数关系如下：
$$\sigma (x_{n-1}{x}_{n-2}\dots x_1{x}_0)=x_{n-2}{x}_{n-3}\dots x_1{x}_0{x}_{n-1}$$
即输入端的二进制编号循环左移一位

原输入上下均分为两半，交替往右边放，我们发现左边输入和自己循环左移一位的输出端号建立连接

既然可以循环左移一位，我们自然也可以通过循环右移一位来构造互连函数，我们称之为逆均匀洗牌函数，显然它是均匀洗牌函数的逆函数。
$$\sigma (x_{n-1}{x}_{n-2}\dots x_1{x}_0)=x_1{x}_{n-1}{x}_{n-2}\dots x_2{x}_1$$

1.1.2.4 碟式函数

蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。
$$B(x_{n-1}{x}_{n-2}...x_1{x}_0)=x_0{x}_{n-2}...x_1{x}_{n-1}$$

解释：000 - 000 001 - 100 010 - 010 - 011 - 110 100 - 001 101 - 101 110 - 011 111 - 111

1.1.2.5 反位序函数

反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。
$$\rho (x_{n-1}{x}_{n-2}...x_1{x}_0)=x_0{x}_1...x_{n-2}{x}_{n-1}$$

N = 8时碟式函数和反位序函数结构表示相同。

1.1.2.6 移数函数

**移数函数：**将各输入端都错开一定的位置（模N）后连到输出端
$$\alpha (x)=(x\pm k)modN,1\le N-1,1\le k\le N-1$$

1.1.2.7 PM2I函数

P和M分别表示加和减，2I表示2^{i。该函数又称为**”加减2}i“函数**。

**PM2I函数：**一种移数函数，将各输入端都错开一定的位置（模N）后连到输出端。
$$
PM2_{+i}(x)=x+2_{}^{i} \space mod \space N \

PM2_{-i}(x)=x-2_{}^{i} \space mod \space N \
其中：0 \le x \le N-1, 0\le i\le n-1, n = \log_{2}N,N为结点数
$$
PM2I互连网络共有2 n 个互连函数。

举例-阵列计算机ILLIAC Ⅳ

1.2 互连网络的结构参数与性能指标

1.2.1 互连网络的结构参数

互连网络通常是用有向边或无向边连接有限个结点的图来表示的，其主要结构参数包含以下6个。

1. 网络规模N：网络规模(NetworkSize)是指互连网络中结点的个数。它表示该网络所能连接的部件的数量。网络规模越大，则这个互连网络的连接能力越强，就能连接更多的部件。
2. 结点度：结点度(Node Degree)d是指互连网络中结点所连接的边数(通道数)，包括入度(InDegree)和出度(Out Degree)。进入结点的边数叫入度，从结点出来的边数叫出度。
3. 结点距离：对于互连网络中的任意两个结点，其距离是指从一个结点出发到另一个结点终止所需要跨越的边数的最小值。
4. 网络直径D：（可以类比数据结构中树的直径）网络直径(Network Diameter)D是指互连网络中任意两个结点之间距离的最大值。网络中任意两个结点之间传送的信息通过的边数都不会大于网络直径。显然，网络直径应当尽可能的小。
5. 等分宽度b：（可以类比网络流种的最小割）把由N个结点构成的网络切成结点数相同(N/2)的两半，在各种切法中，沿切口边数的最小值称为该网络的等分宽度(BisectionWidth)，用b表示。而线等分宽度为B=b × w。其中w为通道宽度(用位数表示)。该参数主要反映了网络的最大流量。
6. 对称性：如果从任意结点来看，网络的结构都是相同的，则称该网络为**对称网络(Symmetric Network)。**对称网络实现比较容易，编程也比较容易。

1.2.2 互连网络的性能指标

**时延(Latency)和带宽(Bandwidth)**是用来评估互连网络性能的两个基本指标。

1.通信时延

通信时延是指从源结点到目的结点传送一条消息所需的总时间，它由以下4部分构成。

1. 软件开销。在源结点和目的结点用于收发消息的软件所需的执行时间。
2. 通道时延。通过通道传送消息所花的时间。通路时延 = 消息长度/通道带宽。
3. 选路时延。消息在传送路径上所需的一系列选路决策所需的时间开销。
4. 竞争时延。多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。

软件开销主要取决于两端结点处理消息的软件内核。通道时延通常由瓶颈链路的通道带宽决定。选路时延与传送路径上的结点数成正比。竞争时延很难预测，它取决于网络的传输状态。

2.网络时延

网络时延是指通道时延与选路时延的和。它是由网络硬件特征决定的，与程序行为和网络传输状态无关。而软件开销和竞争时延则与程序的行为有关。

3.端口带宽

对于互连网络中的任意一个端口来说，其端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。

在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同。而非对称网络的端口带宽则是指所有端口带宽的最小值。

4.聚集带宽

网络的聚集带宽(Aggregate Bandwidth)是指网络从一半结点到另一半结点，单位时间内能够传送的最大信息量。例如，HPS是一种对称网络，网络规模N的上限是512，端口带宽是40MB/S，因此，HPS的聚集带宽是(40MB/s×512)/2=10.24GB/s。

5.等分带宽

与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量称为该网络的等分带宽(Bisection Bandwidth)。

1.3 互连网络的结构

互连网络通常可以分为两大类：静态互连网络(Static Interconnection Network)和动态互连网络(Dynamic Interconnection Network)。

静态互连网络是指各结点之间有固定的连接通路、且在运行中不能改变的网络。而动态互连网络则是指由交换开关构成、可按运行程
序的要求动态改变连接状态的网络。

1.3.1 静态互连网络

静态互连网络比较适合于构造通信模式可预测或可用静态连接实现的计算机。线性阵列结构是一维的静态互连网络；二维的有环状、星状、树状、网格状等；三维的有立方体等；三维以上的有超立方体等。下面介绍几种静态互连网络，其中N表示网络的规模，即结点的个数

1.3.1.1 线性阵列

一种一维的线性网络，其中N个结点用N - 1个链路连成一行。

• 端结点的度：1
• 其余结点的度：2
• 直径：N－1
• 等分宽度b = 1

线性阵列与总线的区别
总线是通过切换与其连接的许多结点来实现时分特性的
线性阵列允许不同的源结点和目的结点对并行地使用其不同的部分

1.3.1.2 环和带弦环

环

用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。

• 对称
• 结点的度：2
• 双向环的直径：N/2
• 单向环的直径：N
• 环的等分宽度 b = 2

带弦环

在环的基础上，给每个结点增加一条或两条链路便可得到带弦环，增加的链路愈多，结点度愈高，网络直径就愈小。

全连接网络

结点度：15

直径最短，为1

1.3.1.3 循环移数网络

通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。

• N=16
• 结点度：7
• 直径：2

一般地，如果｜j - i｜= 2^r（r=0，1，2，…，n-1，n = logN），则结点 i 与结点 j 连接。

• 结点度：2n－1
• 直径：n / 2
• 网络规模N = 2^n

1.3.1.4 树形和星形

树形

一棵5层31个结点的二叉树
一般说来，一棵k层完全平衡的二又树有N = 2^k - 1个结点。

• 最大结点度：3
• 直径：2(k-1)
• 等分宽度b = 1

星形

星状网络是一种两层的树

• 结点度较高，为N - 1。
• 直径较小，是一常数2。等分宽度b - [N / 2]
• 可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。

胖树形

1985年，Leiserson提出将计算机科学中所用的一般树结构修改为胖树状。树状网络的一个主要缺点是其根部结点以及连到根部的链路上的负载比较重，有可能会成为整个系统的瓶颈。胖树的提出使该问题得到了缓解。

胖树的通道宽度从叶节点到根节点的宽度逐渐增宽，它更像真实的树，越靠近树根，树干就越粗。此结构已经在CM-5计算机上得到应用。

1.3.1.5.网格形和环网形

网格形

网格状是一种比较流行的结构，它已经以各种变体形式在Illiac IV、CM-2和IntelParagon等机器中得到了实现。如下图是一个3x3的二维网格状网络。

对于一个规模为N= n × n 的二维网格状网络来说，

• 其内部结点的度d=4
• 边结点的度d = 3
• 角结点的度d = 2
• 网络直径D= 2 ( n一1 )
• 等分宽度b = n
• 这个网络是不对称的
• q一个由N=n^k 个结点构成的 k 维网格形网络（每维 n 个结点）的内部结点度d = 2k，网络直径D = k(n-1) 。

环网形

• 可看作是直径更短的另一种网格

• 把2维网格形网络的每一行的两个端结点连接起来，把每一列的两个端结点也连接起来。

• 将环形和网格形组合在一起，并能向高维扩展。

• 一个n×n的环网形网

  • 结点度：4

  • 网络直径：2 x [ n / 2 ]

  • 等分宽度b = 2n

1.3.1.6 超立方体

这是一种二元n-立方体结构，它已在iPSC、nCUBE和CM-2等计算机系统中得到了实现。一般来说，一个二元n-立方体由N = 2 ^ n个结点组成，它们分布在n维上，每维有两个结点。

如我们可以用两个3-立方体，对应结点相连来得到一个4-立方体，如上图。

为实现一个n-立方体，只要把两个(n-1)立方体中相对应的结点用链路连接起来即可。共需要2^n-1条链路。

n-立方体中结点的度都是n，直径也是n，等分宽度为b = N / 2

1.3.2 动态互连网络

动态互连网络设置有有源开关，因而能够根据需要借助控制信号对连接通路加以重新组合，实现所要求的通信模式。下面介绍总线网络、交叉开关网络和多级互连网络。

1.3.2.1 总线网络

总线网络由一组导线和插座构成，经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。

• 每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。
• 多个功能模块之间的争用总线（Contention Bus）或时分总线（Time-sharing Bus）。

特点：

• 结构简单、实现成本低、带宽较窄

下图为一种由总线连接的多处理机系统示意图

• 系统总线在处理机、I/O子系统、主存储器以及辅助存储设备（磁盘、磁带机等）之间提供了一条公用通路
• 系统总线通常设置在印刷电路板底板上。处理器板、存储器板和设备接口板都通过插座或电缆插入底板

解决总线带宽较窄问题：采用多总线或多层次的总线

• 多总线是设置多条总线
  • 有两种做法：
    • 为不同的功能设置专门的总线
    • 重复设置相同功能的总线
• 多层次的总线总是按层次的架构设置速度不同的总线，使得不同速度的模块有比较适合的总线连接。

1.3.2.2 交叉开关网络

可以把交叉开关网络(Crossbar)看作一个单级开关网络。

• 交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接。
• 带宽和互连特性最好。
• 一个n×n的交叉开关网络，可以无阻塞地实现n!种置换。
• 对一个n×n的交叉开关网络来说，需要n^2套交叉点开关以及大量的连线。n很大时，交叉开关网络所需要的硬件数量非常巨大。因此一般只有n <= 16的小型交叉开关网络用在商品化机器中。

我们以C.mmp多处理机的交叉开关网络为例：

• 用16×16的交叉开关网络把16台PDP-11处理机与16个存储模块连在一起
• 最多可同时实现16台处理机对16个不同存储模块的并行访问
  • 每个存储模块一次只能满足一台处理机的请求
  • 当多个请求要同时访问同一存储模块时，交叉开关就必须分解所发生的冲突，每一列只能接通一个交叉点开关。
  • 为了支持并行（或交叉）存储器访问，可以在同一行中接通几个交叉点开关。

处理机之间的交叉开关可以实现处理机之间的置换连接，但这只是一对一的连接。所以n×n交叉开关网络一次最多可实现n个“源-目的”对的连接。

1.3.2.3 多级互连网络

MIMD 和 SIMD计算机一般都采用多级互连网络(Multistage Interconnection Network，MIN)。

下面是一种通用的多级互连网络：

• 由a×b开关模块和级间连接构成的通用多级互连网络结构
• 每一级都用了多个a×b开关
  • a个输入和b个输出
  • 在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即a＝b＝2^k，k ≥ 1
• 相邻各级开关之间都有固定的级间连接

下表列出了几种常用的开关模块：2x2,4X4,8X8。这些块中。每个输人可与一个或多个输出相连，但是在输出端不许发生冲突。换句话说,一对一和一对多的映射是允许的，但不允许有多对一映射，否则输出端将发生冲突。

我们以最简单的开关模块：2×2开关 为例，四种连接方式：

各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。

• 控制方式：对各个开关模块进行控制的方式。
  • 级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态。
  • **单元控制：**每一个开关都有一个独立的控制信号，可各自处于不同的状态。
  • **部分级控制：**第 i 级的所有开关分别用i＋1个信号控制，0 ≤ i ≤ n－1，n为级数。
• 常用的级间互联模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等

多级立方体网络

多级立方体网络包括STARAN网络和间接二进制n方体网络等。

• 两者仅在控制方式上不同，在其他方面都是一样的。
• 都采用二功能（直送和交换）的2×2开关。
• 当第 i 级（0 ≤ i ≤ n - 1）交换开关处于交换状态时，实现的是Cubei 互连函数。

一个N输入的多级立方体网络有logN级，每级用N/2个2×2开关模块，共需要logN × N/2个开关。

下面是一个8个入端的多级立方体网络：

不难看出级间互连分别为交换、均匀洗牌，逆均匀洗牌

STARAN网络采用级控制和部分级控制

• 采用级控制时，所实现的是交换功能
• 采用级控制时，所实现的是交换功能

间接二进制n方体网络则采用单元控制

• 具有更大的灵活性

交换：将有序的一组元素头尾对称地进行交换。

例如：对于由8个元素构成的组，各种基本交换的图形：

3级STARAN网络在各种级控制信号的情况下所实现的入出端连接以及所实现的交换函数和功能。

其中：

• K2k1k0：控制信号，ki(i = 0，1，2)为第i级的级控制信号。
• 从表中可以看出下面的4行中每一行所实现的功能可以从级控制信号为其反码的一行中所实现的功能加上1组8元变换来获得。

例如：级控制信号为110所实现的功能是其反码001所实现的4组2元交换再加上1组8元交换来获得。

当STARAN网络用作移数网络时，采用部分级控制，控制信号的分组和控制结果。

Omega网络

一个8×8的Omega网络：

• 每级由4个4功能的2 x 2开关构成
• 级间互连采用均匀洗牌连接方式

一个N输入的Omega网络

• 有logN级，每级用N/2个2x2开关模块，共需要logN * N/2个开关。
• 每个开关模块均采用单元控制方式。
• 不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。
• 假设上图是画在玻璃上的，那么从正面看，是Omega网络；如果到玻璃的背后看过来，就是下图所示的三级立方体网络。所以，如果mega网络也采用2功能交换开关，那么〇mega网络和间接二进制n方体网络就互为逆网络。

动态互连网络的比较

二、多处理机

自20世纪80年代中期以来，随着微处理器的发展，单处理机的性能达到了前所未有的高速增长。然而，从2003年开始，单处理机的性能的年增长率下降到了约20%。

Intel于2004年宣布放弃了其高性能单处理器项目，转向多核（multi-core）的研究和开发。IBM、Sun、AMD等公司也纷纷采用了这一途径。

如今，并行计算机应用软件已有了稳定的发展。这些计算机能够充分利用商品化微处理器所具有的高性能价格比的优势。

接下来主要介绍多处理机设计的主流——中小规模的计算机(处理器的个数＜32)。

2.1 并行计算机系统结构的分类

按照Flynn分类法，可把计算机分为SISD、SIMD、MISD和MIMD四类（单/多指令流、单/多数据流）。

很多早期并行计算机为SIMD计算机，但近年来MIMD已经成为了通用多处理机系统结构的选择。

• SIMD是一个指令程序控制多个数据流的运算，它比较适合数组运算那样大量的相同运算
• 而MIMD具有更好的灵活性，每个处理机可以执行自己的程序，处理自己的数据
• MIMD可以充分利用商品化微处理器在性能价格比方面的优势，市场上有大量可用的CPU且这些CPU更新换代快，如果是SIMD很可能遇到市场上缺少所需CPU，还要自己设计。
• 计算机机群系统（Cluster）是一类被广泛采用的MIMD计算机。采用标准组件和标准网络技术，这样可以尽可能地采用已经商业化了的技术（而不是专门技术）。

2.1.1 MIMD计算机

现有的MIMD计算机分为两类，每一类代表了一种存储器的结构和互连策略。

1、集中式共享存储器结构（Centralized Shared-Memory Architecture）

这类多处理机目前最多由几十个处理器构成，由于处理器数目较少，所以它们共享一个集中式的物理存储器。

由于只有单一主存，且该主存相较于各处理器的关系为对称的，所以这类机器经常被称为对称式共享存储器多处理机（Symmetric shared-memory Multi Processor，SMP）。这种系统结构也被称为UMA（Uniform Memory Access），这是因为从各处理器访问存储器所花的时间相同。SMP结构是当前最流行的结构。

2、分布式存储器多处理机

• 这类机器中，存储器在物理上是分布的
• 存储器分布到各个处理器上，否则，如果使用集中式存储器，则不能满足因处理器个数过多而导致的带宽要求。
• 每个结点包括：
  • 处理器及Cache
  • 存储器
  • I/O
  • 互连网络接口
• 在许多情况下，分布式存储器结构优于集中式共享存储器结构

存储器分布到各个结点有两个优点：

• 如果大多数的访存都是针对本地结点的存储器进行的，就可以降低存储器和互连网络对于带宽的要求
• 对本地存储器的访问延迟时间小。分布式存储器系统结构最主要的缺点是处理器之间的通信较为复杂，且各处理器之间的访问延迟大。

通常情况下，I/O和存储器一样也分布于多处理机的各结点当中。每个结点内还可能包含个数较少（如2~8个）的处理器，这些处理器之间可采用另一种互连技术（例如总线），相互连接形成簇，这样形成的结点叫做超级节点。

2.1.2 存储器系统结构和通信机制

如上所述，在大规模的多处理机中，存储器在物理上是分布于各个处理结点中的。但在逻辑地址空间的组织方式以及处理器之间通信的实现方法上，有以下两种方案。

2.1.2.1 共享地址空间

把物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址，这样任何一个处理器就都可以访问该共享空间中的任何一个单元（如果有访问权的话），不同处理器上的同一个物理地址指向的是同一个存储单元。

这类计算机被称为 分布式共享存储器系统（Distributed Shared-Memory，DSM）。注意，这里的共享指的是地址空间上的共享而非共享同一个存储器。与UMA相反，DSM计算机被称为 NUMA(Non-Uniform Memory Access)计算机，因为其访问时间取决于数据在存储器中的存放位置。

共享地址空间计算机系统，采用共享存储器通信机制：处理器之间的通信是通过用load 和 store 指令对相同存储器地址进行读写操作来实现的。

2.1.2.2 采用多个独立地址空间

把每个结点中的存储器编址为一个独立的地址空间，不同结点的地址空间之间是相互独立的。

• 整个系统的地址空间是由多个独立的地址空间构成的
• 每个结点中的存储器只能由本地的存储器进行访问，远程的处理器不能直接对其进行访问
• 每一个”处理器-存储器“模块实际上是一台单独的计算机
• 现在这种计算机系统多以机群的方式存在

采用多个独立地址空间计算机系统，采用消息传递通信机制：数据通信要通过在处理器之间显式地传递消息来完成，这称为消息传递通信机制。

消息传递多处理机中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数据。

例如：一个处理器要对远程存储器上的数据进行访问或操作：

• 发送消息，请求传送数据或对数据进行操作：远程进程调用（RPC，Remote Process Call）
• 目的处理器接收到消息后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。

这里又引出两种消息传递方式：

同步消息传递 ：请求处理器发送一个消息后一直要等到应答结果才继续运行。

异步消息传递 ：数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。这种消息传递往往是可以异步地进行，发送方在发出消息后，可立即继续执行原来的程序。

2.1.2.3 通信机制的性能指标

• 通信带宽
  • 理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。
• 通信延迟
  • 理想状态下通信延迟应尽可能地小。
  • 通信延迟 = 发送开销 + 跨越时间 + 传输延迟 + 接收开销

通信延迟的隐藏

• 如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通信延迟的隐藏。如接收一个数据后紧接着接收下一个数据，这样在上一个数据处理完毕后可以直接拿到下一个数据。
• 通常的原则：只要可能就隐藏延迟，通信延迟隐藏是一种提高性能的有效途径，但它对操作系统和编程者来讲增加了额外的负担。

2.1.2.4 不同通信机制的优点

共享存储器通信的主要优点

• 与常用的对称式多处理机使用的通信机制兼容。
• 易于编程，同时在简化编译器设计方面也占有优势。
• 采用大家所熟悉的共享存储器模型开发应用程序，而把重点放到解决对性能影响较大的数据访问上。
• 当通信数据量较小时，通信开销较低，带宽利用较好。
• 可以通过采用Cache技术来减少远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。

消息传递通信机制的主要优点

• 硬件较简单
• 通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少
• 显式通信可以让编程者重点注意并行计算的主要通信开销，使之有可能开发出结构更好、性能更高的并行程序。
• 同步很自然地与发送消息相关联，能减少不当的同步带来错误的可能性。

2.2 对称式共享存储器系统结构

在之前的缓存优化部分提到过，多级cache可以降低处理器对存储器带宽的要求。

• 如果，每个处理器对存储器的带宽需求都降低了，那么多个处理器就可以共享一个存储器
• 当处理机规模较小时，这种计算机十分经济
• 以往这种计算机一般是CPU和cache做在一块板上，然后插入底板总线。近些年，能在一个单独的芯片上实现2～8个处理器核。
  • 如：Sun公司 2006年 T1 8核的多处理器
• 对称式共享存储器系统结构 支持对共享数据和私有数据的Cache缓存
  • 私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。
• 共享数据进入Cache也带来了一个新的问题，即Cache的一致性问题

2.2.1 多处理机 Cache 一致性

如果允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本的情况，当其中某个处理器对其Cache中数据进行修改后，就会导致其Cache中数据和其它处理器中Cache数据不同。这就是多处理机的Cache一致性（Cache Coherence）问题。

以下面动图中情况为例：

CPUA 和CPUB 的Cache中都有存储单元X的副本，其值都是1，假设两个Cache都采用写直达方式。

当A对X进行写入，更改为0，此时A的Cache和存储器中的X都变为了0，而BCache中X为1，这就出现了问题。

存储器的一致性（非正式定义）：如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。

存储系统行为的两个不同方面：

• What：读操作得到的是什么值
• When：什么时候才能将已写入的值返回给读操作。

需满足以下条件

• 处理器P对单元X进行一次写之后，又对单元X进行读，读和写之间没有其它处理器对单元X进行写，则P读到的值总是前面写进去的值。
• 处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其它写，则Q读到的值应为P写进去的值
• 对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度来看顺序都是相同的。（写串行化）

在后面的讨论中，我们假设：

• 直到所有处理器均看到了写的结果，这个写操作才算是完成
• 处理器的任何访问均不能改变写的顺序。即，允许处理器对读进行重排序，但必须以程序规定的顺序执行。

2.2.2 实现一致性的基本方案

2.2.2.1 Cache一致性协议

在一致的多处理机中，Cache提供两种功能：

1、共享数据的迁移

减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求

2、共享数据的复制

不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。

在多个处理器中用来维护一致性的协议称为Cache一致性协议（Cache-coherent Protocol）。

关键：跟踪共享数据块的状态。

目前有两类协议：

1. 目录式协议（directory）。
   1. 物理存储器中数据块的共享状态被保存在一个称为目录的地方。
2. 监听式协议（snooping）。
   1. 每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享信息。
   2. Cache通常连接在共享存储器的总线上，当某个Cache需要访问存储器，它会把请求放到总线上广播出去，其它各个Cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行响应操作。

2.2.2.2 解决Cache一致性问题的方法

1、写作废协议

在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权，即作废其它的副本，让其它Cache的该数据块失效。

我们给出一个例子，监听总线、写作废协议（采用写直达法）：

初始状态：CPU A、CPU B、CPUC都有X的副本。在CPU A要对X进行写入时，需先通过监听总线作废CPU B和CPU C中的副本，然后再将p写入Cache A中的副本，同时用该数据更新主存单元X。

2、写更新协议

当一个处理器对某数据项进行写入时，通过广播使其它Cache中所有对应于该数据项的副本进行更新。

给出监听总线、写更新协议的例子（采用写直达法）：

假设3个Cache都有X的副本，当CPUA将数据p写入CacheA中的副本时，将p广播给所有的Cache，这些Cache用p更新其中的副本。
由于这里是采用写直达法，所以CPUA还要将p写入存储器中的X。如果采用写回法，则不需要写入存储器

写更新和写作废协议性能上的差别:

• 在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。
• 在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。写作废是针对Cache块进行操作，而**写更新则是针对字(或字节)**进行。
• 考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。

2.2.3 监听协议的实现

• 实现监听协议的关键有3个方面：

  • 处理器之间通过一个可以实现广播的互连机制相连。通常采用的是总线。

  • 当一个处理器的Cache响应本地CPU的访问时，如果它涉及到全局操作，其Cache控制器就要在获得总线的控制权后，在总线上发出相应的消息。

  • 所有处理器都一直在监听总线，它们检测总线上的地址在它们的Cache中是否有副本。若有，则响应该消息，并进行相应的操作。

• 写操作的串行化：由总线实现

  • （获取总线控制权的顺序性）

Cache发送到总线上的消息主要有以下两种：

• RdMiss——读不命中
• WtMiss——写不命中

此时都需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。

• 写直达Cache：因为所有写入的数据都同时被写回主存，所以从主存中总可以取到其最新值。
• 写回Cache：得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中（后面的讨论中，只考虑写回法）

有的监听协议还增设了一条Invalidate消息，用来通知其它处理器作废其Cache中响应的副本。

• 与WtMiss的区别：Invalidate不引起调块

Cache的标识（tag）可直接用来实现监听，作废一个块只需将其有效位置为无效。

给每个Cache块增设一个共享位：

• 为“1”：该块是被多个处理器共享
• 为“0”：仅被某个处理器所占

**块的拥有者：**拥有该数据块的唯一副本的处理器。

实现监听协议通常是在每个结点内嵌入一个有限状态控制器，该控制器根据来自处理器或总线的请求以及Cache块的状态，做出相应的响应。

每个数据块的状态取以下三种状态中的一种：

• 无效（简称I）：Cache中该块的内容为无效
• 共享（简称S）：该块可能处于共享状态
  • 在多个处理器中都有副本。这些副本都相同，且与存储器中相应的块相同。
• 已修改（简称M）：该块已经被修改过，并且还没写入存储器
  • （块中的内容是最新的，系统中唯一的最新版本）

监听协议举例

写作废、写回法。

为简单起见，对 Write hit 和 Write miss 不加区分，都按 Write miss 处理

现有CPU P CPU Q，CPU P可释放三种信号，CPU Q的Cache中数据块有三种状态：

情况一：请求来自处理器

则有状态机：

状态转换解释如下：

情况二：请求来自总线：

则有状态机：

状态转换解释如下：

2.3 分布式共享存储器系统结构

监听协议直接利用系统中的总线和Cache中的状态位，易于实现，成本较低，但当系统规模变大，大量总线广播会使得总线成为系统瓶颈。广播和监听的机制使得监听一致性协议的可扩放性很差。

2.3.1 目录协议的基本思想

• 广播和监听的机制使得监听一致性协议的可扩放性很差。
• 寻找替代监听协议的一致性协议。（采用目录协议）

2.3.2 目录协议

目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。

特点：对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关信息。这使一致性协议避免了广播操作。

**位向量：**记录哪些Cache中有副本

1. 每一位对应于一个处理器
2. 长度与处理器的个数成正比
3. 由位向量指定的处理机的集合称为共享集S

分布式目录

• 目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。

目录法最简单的实现方案：对于存储器中每一块都在目录中设置一项。目录中的信息量与M * N成正比。

其中：

• M：存储器中存储块的数量
• N：处理器的个数
• 由于M = K * N，K是每个处理机中存储块的数量，所以如果K保持不变，则目录中的信息量就与N^2成正比

2.3.3 目录协议存储块的状态

在目录协议中，存储块的状态有3种：

• **未缓冲：**该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。
• **共享：**该块在一个或多个处理机上都有这个块的副本，且这些副本与存储器中的该块相同。
• **独占：**仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已经过时
  • 该处理机被称为该块的拥有者

2.3.4 本地结点、宿主结点以及远程结点的关系

本地结点：发出访问请求的结点

• 宿主结点：包含所访问的存储单元及其目录项的结点
• 远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。

2.3.5 在结点之间发送的消息

• 本地结点发给宿主结点(目录)的消息

  • 说明：括号中的内容表示所带参数。P：发出请求的处理机编号 K：所要访问的地址

  • RdMiss(P，K)

  • 处理机P读取地址为A的数据时不命中，请求宿主结点提供数据(块)，并要求把P加入共享集。

  • WtMiss(P，K)

    • 处理机P对地址A进行写入时不命中，请求宿主结点提供数据，并使P成为所访问数据块的独占者。

  • Invalidate(K)

    • 请求向所有拥有响应数据块副本（包含地址K）的远程Cache发Invalidate消息，作废这些副本

• 宿主节点（目录）发送给远程结点的消息

  • Invalidate(K)

    • 作废远程Cache包含地址K的数据块

  • Fetch(K)

    • 从远程中取出包含地址K的数据块，并将之送到宿主结点。把远程Cache中那个块的状态改为“共享”。

  • Fetch&Inv(K)

    • 从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。然后作废远程Cache中的那个块。

• 宿主结点发送给本地结点的消息

  • Reply(D)
    • D表示数据内容。
    • 把从宿主存储器获得的数据返回给本地Cache。

• 远程结点发送给宿主结点的消息

  • WtBack(K, D)
    • 把远程Cache中包含地址K的数据块写回到宿主结点中， **该消息是远程结点对宿主结点发来的“取数据”或“取作废”消息的响应。
      **

• 本地结点发送给被替换块的宿主结点的消息

  • MdSharer(P, K)

    • 用于当本地Cache中需要替换一个包含地址K的块、且该块未被修改过的情况。这个消息发给该块的宿主结点，请求它将P从共享集中删除。如果删除后共享集变为空集，则宿主结点还要将该块的状态改变为“未缓存”(U)

  • WtBack2(P，K，D)

    • 用于当本地Cache中需要替换一个包含地址K的块、且该块已被修改过的情况。这个消息发给该块的宿主结点，完成两步操作：①把该块写回；②进行与MdSharer相同的操作。

了解这些后，就可以看几张dio图了（bushi

*2.3.6 目录协议系统Cache块状态图

2.3.6.1 响应本地CacheCPU请求

M: Modified I：Invalid S：Shared

2.3.6.2 远程结点Cache块响应来自宿主结点的请求的状态转换图

*2.3.7 目录协议系统目录状态转换图

先前已经提过：

目录中存储器块的状态有3种

1. 未缓存
2. 共享
3. 独占

位向量记录拥有其副本的处理器的集合。这个集合称为共享集合。

对于从本地结点发来的请求，目录所进行的操作包括：

1. 向远程结点发送消息以完成相应的操作。这些远程结点由共享集合指出；
2. 修改目录中该块的状态；
3. 更新共享集合。

**目录可能接收到3种不同的请求 **（假设这些操作是原子的）

1. 读不命中
2. 写不命中
3. 数据写回

我们对上图进行解释：

• 块处于共享状态（数据是当前最新）接收到的请求及处理操作
  • RdMiss
    • 将存储器数据送往请求方处理机，并将其加入共享集合
  • WtMiss
    • 将数据送往请求方处理机，对共享集合中所有的处理机发送作废消息，且将共享集合改为仅含有该处理机，该块的状态变为独占。
• 块处于独占状态（最新值保存在唯一拥有者处理机）接收到的请求及处理操作
  • RdMiss
    • 将“取数据”的消息发往拥有者处理机，将它所返回给宿主结点的数据写入存储器，并进而把该数据送回请求方处理机，将请求方处理机加入共享集合。
    • 此时共享集合中仍保留原拥有者处理机(因为它仍有一个可读的副本)
    • 将该块的状态变为共享。
  • WtMiss
    • 该块将有一个新的拥有者
    • 给旧的拥有者处理机发送消息，要求它将数据块送回宿主结点写入存储器，然后再从该结点送给请求方处理机。同时还要把旧拥有者处理机中的该块作废。把请求处理机加入共享者集合，使之成为新的拥有者。
    • 该块的状态仍旧是独占。
  • WtBack（写回）
    • 当一个块的拥有者处理机（独占态）要从其Cache中把该块替换出去时，必须将该块写回其宿主结点的存储器中，从而使存储器中相应的块中存放的数据是最新的(宿主结点实际上成为拥有者)
    • 该块的状态变成未缓冲，其共享集合为空。

2.3.8 目录的三种结构

不同目录协议的主要区别主要有两个

• 所设置的存储器块的状态及其个数不同同
• 目录的结构

根据目录的结构，可以将目录协议分为三类：全映象(Full mapped)目录、有限映象(Limited-mapped)目录、链式(Chained)目录

2.3.8.1 全映象目录

全映象目录：每一个目录项都包含一个N位（N为处理机的个数）的位向量，其每一位对应于一个处理机.

优点：处理比较简单，速度也比较快。

缺点：

• 存储空间的开销很大。
• 目录项的数目与处理机的个数N成正比，而目录项的大小(位数)也与N成正比，因此目录所占用的空间与N成正比。
• 可扩放性很差（处理机数目一旦改变就很难维护）。
• 当位向量中的值为“1”时，就表示它所对应的处理机有该数据块的副本；否则就表示没有。
• 在这种情况下，共享集合由位向量中值为“1”的位所对应的处理机构成。

2.3.8.2 有限映象目录

有限映象目录：提高其可扩放性和减少目录所占用的空间。

核心思想：采用位数固定的目录项目

1. 限制同一数据块在所有Cache中的副本总数。
2. 限定为常数m。则目录项中用于表示共享集合所需的二进制位数为:m * logN。
3. 目录所占用的空间与N * [1og2N]成正比。

缺点：

当同一数据的副本个数大于m时，必须做特殊处理。当目录项中的m个指针都已经全被占满，而某处理机又需要新调入该块时，就需要在其m个指针中选择一个，将之驱逐，以便腾出位置，存放指向新调入块的处理机的指针。

2.3.8.3 链式目录

1. 用一个目录指针链表来表示共享集合。当一个数据块的副本数增加(或减少)时，其指针链表就跟着变长(或变短)
2. 由于链表的长度不受限制，因而带来了以下优点既不限制副本的个数，又保持了可扩展性。

链式目录的两种实现方法：

单链法

当Cache中的块被替换出去时，需要对相应的链表进行操作——把相应的链表元素(假设是链表中的第i个)删除。实现方法有以下两种:

• 沿着链表往下寻找第i个元素，找到后，修改其前后的链接指针，跳过该元素。
• 找到第i个元素后，作废它及其后的所有元素所对应的Cache副本。

双链法

• 在替换时不需要遍历整个链表。
• 节省了处理时间，但其指针增加了一倍，而且一致性协议也更复杂了。

2.4 大规模并行处理机MPP

2.4.1 并行计算机系统结构

目前流行的高性能并行计算机系统结构通常可以分成以下5类：

• 并行向量处理机(PVP)
• 对称式共享存储器多处理机(SMP)
• 分布式共享存储器多处理机(DSM)
• 大规模并行处理机(MPP)
• 工作站机群(Cluster of Workstations)

接下来的图片中的缩写含义如上图

2.4.1.1 并行向量处理机(PVP)

典型的 PVP 的结构如上图。

• PVP 系统一般由若干台高性能向量处理机(VP)构成，这些向量处理机是专门设计和定制的，每个至少有 1G flops的处理能力
• 存储器以兆字节每秒的速度向处理器提供数据
• 向量处理器 VP 和共享存储模块通过高带宽的交叉开关网络互连
• 这样的机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器

如：Cray90、NECSX-4和我国的银河一号都是 PVP

2.4.1.2 对称式共享存储器多处理机(SMP)

SMP在前面已经详细讨论过了，也介绍了监听协议解决cache一致性问题。

• SMP系统使用商品微处理器（具有片上或外置高速缓存）
• 它们经由高速总线（或交叉开关）连向共享存储器和 I/O
• 这种机器主要用于商务，例如数据库、在线事物处理系统和数据仓库等
• 因为存储器唯一，其相对个各个CPU而言关系对称，访问时间相同所以称为对称
• 但是处理器不能太多（一般少于64个），否则存储器带宽压力太大
• 总线和交叉开关网络一旦作成也难以扩展

例如：IBM R50、SGI Power Challenge、DEC Alpha 服务器 8400 和我国的曙光 1 号等都是这种类型的机器。

2.4.1.3 分布式共享存储器多处理机(DSM)

DSM我们也进行了详细介绍，还介绍了目录协议

• 物理上有分布在各节点中的局部存储器，但是对用户而言，系统硬件和软件提供了逻辑上单地址的编程空间。
• 高速缓存目录 DIR用以支持分布高速缓存的一致性。
• DSM 相对于 MPP的优越性是编程较容易。

例如:Stanford DASH、Cray T3D 和SGI/Cray 0rigin 2000等。

2.4.1.4 大规模并行处理机(MPP)

MPP往往是超大规模的计算机系统，它具有以下特点：

• 处理结点使用商用微处理器，而且每个结点可以有多个微处理器
• 具有较好的可扩放性，能扩展成具有成百上千个处理器的系统
• 系统中采用分布非共享的存储器，各结点有自己的地址空间。
• 采用专门设计和定制的高性能互连网络
• 是一种异步的MIMD机器，程序系由多个进程组成，采用消息传递的通信机制。
• MPP的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。

例如：Intel Paragon、Cray T3E、IntelOption Red和我国的曙光-1000等都是这种类型的机器。

2.4.1.5 工作站机群(Cluster of Workstations)

• 在有些情况下，集群往往是低成本的变形的MPP
• COW的重要界线和特征是：
  • COW的每个节点都是一个完整的工作站(不包括监视器、键盘、鼠标等)，这样的节点有时叫作“无头工作站”，一个节点也可以是一台PC或SMP;
  • 各节点通过一种低成本的商品(标准)网络(如以太网、FDDI和 ATM 开关等)互连(有的商用机群也使用定做的网络);
  • 各节点内总是有本地磁盘，而MPP节点内却没有
  • 节点内的网络接口是松散耦合到I/O总线上的，而 MPP内的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式的;
  • 一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核，COW的操作系统是工作站UNIX，加上一个附加的软件层以支持单一系统映像并行度、通信和负载平衡等。

Berkeley NOW、Alpha Farm、Digital Truclster等都是 COW 结构。

2.4.2 五种MIMD特征比较