系统结构笔记第九章

系统结构笔记第九章

五月 08, 2023

第9章 互连网络

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

互连网络三要素：

  • 开关元件：网络中最基本模块，在不同系统和控制中，开关元件所处的物理位置和工作状态不同。
  • 互连结构:网络合理布局关键，反映系统结构特征。用有向图或无向图表示，节点对应开关元件或处理机。边对应通信链路。
  • 控制方式：网络中各种开关的控制方法

互连网络的基本特征

特征 分类
拓扑结构 静态
动态
控制策略 集中式
分散式
定时方式 同步
异步
交换方法 线路交换
分组交换

拓扑结构

  • 静态网
    各节点间有专用通信线路（链路），运行间不改变或重新组合。又称直接网络 (节点通过链路直接连接)
    • 组成：由链路、结构及网络节点组成。
    • 结构: 线性、环形、树形、 立方体等。
  • 动态网
    各节点间有专用通信线路（链路）,可通过网络中开关重新组合。节点与节点的连接由程序或控制信号动态地改变，又称间接网络(节点与交换开关连接)。
    • 组成：由链路、结构、开关及节点组成。
    • 结构: 总线、环状、 开关、(单)多级。

控制策略

  • 集中控制:全局控制器接收所有通信请求，设置互连网络的开关连接。
  • 分散控制: 通信请求和开关设置由互连网络分散地进行。

定时方式

  • 同步系统：系统使用一个集中的统一时钟.
  • 异步系统：无统一时钟，节点根据各自情况独立工作。

交换方法

  • 线路交换：源结点和目的结点间的物理通路在整个数据传送期间一直保持连接。
  • 分组交换：信息分割成组(包)，各组(包)通过多个不同路径传分别送入互连网络。传送不存在一个实际连接的固定通路。

9.1 互连函数

互连网络的描述
description

基本的互连函数

  1. 恒等函数
    $I(x_{n-1}x_{n-2}…x_1x_0)=x_{n-1}x_{n-2}…x_1x_0$
  2. 交换函数:实现二进制地址编码中第k位互反的输入端与输出端之间的连接。
    $E(x_{n-1}x_{n-2}…x_{k+1}x_kx_{k-1}…x_1x_0)=(x_{n-1}x_{n-2}…x_{k+1}\overline{x_k}x_{k-1}…x_1x_0)$
  3. 均匀洗牌函数:输入端二进制地址循环左移一位。poker
  4. 逆均匀洗牌函数: 输入端二进制地址循环右移一位。（左右左右，先左后右）poker2
  5. 蝶式函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。
    $\beta(x_{n−1}x_{n−2}…x_1x_0)=x_0x_{n−2}…x_1x_{n−1}$butterfly
  6. 反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。
    $\rho(x_{n−1}x_{n−2}…x_1x_0)=x_0x_{1}…x_{n−2}x_{n−1}$
  7. 移数函数：将各输入端都错开一定的位置(k)（别忘了模N）后连到输出端。
    $\alpha(x)=(x±k)mod N, 1≤x≤N-1，1≤k≤N-1$
  8. PM2I函数:P和M分别表示加和减，2I表示$2^i$
    $PM2+i(x) = x＋2^i mod N$
    $PM2-i(x) = x－2^i mod N $
    $0≤x≤N－1，0≤i≤n－1，n=log_2N$，N为结点数。PM2I PM2I互连网络共有2n个互连函数:一加一减就两倍啦 2n ex

逆函数
对于任意一种函数f(x)，如果存在g(x)，使得
$f(x)·g(x)=I(x)$
则称g(x)是f(x)的逆函数，记为$f^{-1}(x)$。
$f^{-1}(x)=g(x)$

均匀洗牌，蝶式函数不能单独实现任意结点间互连。
它们与交换函数多级组合是构成复杂多级网络的基础.

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

互连网络的结构参数——互连网络的主要特性参数

  • 网络规模N：网络中结点的个数。表示该网络所能连接的部件的数量。
  • 结点度d：与结点相连接的边数（通道数），包括入度和出度。
    • 进入结点的边数叫入度。
    • 从结点出来的边数叫出度。
  • 结点距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。
  • 网络直径D：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。
  • 等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。
    • 线等分宽度：B＝b×w
    • 其中：w为通道宽度（用位表示）
    • 该参数主要反映了网络最大流量。
  • 对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。

互连网络的性能指标
评估互连网络性能的两个基本指标：时延和带宽

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

    1. 软件开销：在源结点和目的结点用于收发消息的软件所需的执行时间。
      1. 主要取决于两端端结点处理消息的软件内核。
    2. 通道时延：通过通道传送消息所花的时间。
      1. 通路时延 = 消息长度/通道带宽
      2. 通常由瓶颈链路的通道带宽决定。
    3. 选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销。
      1. 与传送路径上的结点数成正比。
    4. 竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。
      1. 很难预测，它取决于网络的传输状态。

  2. 网络时延:通道时延与选路时延的和。

    1. 由网络硬件特征决定，与程序行为和网络传输状态无关。

  3. 端口带宽

    1. 对互连网络中的任意一个端口，端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。
      1. 在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同。
      2. 非对称网络的端口带宽则是指所有端口带宽的最小值。

  4. 聚集带宽
    网络从一半结点到另一半结点，单位时间内能够传送的最大信息量。

  5. 等分带宽
    与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量

9.3 静态互连网络

典型的静态互连网络

1. 线性阵列

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

特征 数值
非对称
端结点的度 1
其余结点的度 2
直径 N－1
等分宽度b 1

2. 环和带弦环

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

特征 数值
对称
结点度 2
双向环的直径 N/2
单向环的直径 N
环的等分宽度b 2
circle

带弦环：增加的链路愈多，结点度愈高，网络直径就愈小。
circlewitharcs
circlewitharcs
全连接网络：
alltoall

特征 数值
对称
结点度 15
直径 1

3. 循环移数网络

环上每个结点到所有与其距离为2的整数幂的结点之间都有一条链路。
2
一般地，如果结点i和j间距离为2的整数幂，则结点i与结点j连接

特征 数值
结点度 2n-1
直径 n/2
网络规模 $N=2^n$

如, N=16 n=4
结点度：7
直径：2

4. 树形和星形

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

特征 数值
最大结点度 3
直径 2(k-1)=8
等分宽度b 1
btree
星形
特征 数值
最大结点度 N-1
直径 2
等分宽度b $\lfloor N/2\rfloor$

可靠性较差，中心结点出故障，整个系会瘫痪。
star
胖树形：叶节点到根节点链路（通道宽度）逐渐增多
fattree

5. 网格形和环网形

一个规模为N=n×n的2维网格形网络

特征 数值
内部结点的度 4
边结点的度 3
角结点的度 2
网络直径D 2（n-1）
等分宽度b n

一个由N=nk 个结点构成的k维网格形网络（每维n个结点）的内部结点度d=2k，网络直径D=k(n-1)(几维就走几条边)

Illiac网络
把2维网格形网络的每一列的两个端结点连接起来，
再把每一行的尾结点与下一行的头结点连接起来，
并把最后一行的尾结点与第一行的头结点连接起来。
一个规模为n×n的Illiac网络

特征 数值
所有结点的度d 4
网络直径D （n-1）只有纯网格形网络直径的一半
等分宽度b 2n

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

pic

一个n×n的环网形网

特征 数值
结点的度d 4
网络直径D 2×（n-1）
等分宽度b 2n

6. 超立方体

2 带环k-立方体（简称k-CCC） k-立方体的变形，它通过用k个结点构成的环取代k-立方体中的每个结点而形成的。
特征 数值
网络规模 $N=k×2^k$
网络直径D 2k-1+ $\lfloor k/2\rfloor$
等分宽度b N/（2k）

summary

summary

9.4 动态互连网络

动态网络(dynamic Networks): 由交换开关构成的互连网络，可按运行程序的要求改变网络的连接状态。

总线结构网络

略

交叉开关网络

  1. 单级开关网络
    交叉点开关在对偶节点(源，目的)之间动态连接，每个交叉点开关根据程序要求动态设置“开”或“关”。可同时实现多个对偶之间的无阻塞连接。带宽和互连特性最好。
    一个n×n的交叉开关网络，可以无阻塞地实现n!种置换
  2. 多处理机中处理机-存储器间的交叉开关网络。
  3. 向量并行处理机(VPP 500)采用大型交叉开关网络。
    PE为处理机，CP代表控制处理机。网络中每一行和一列只能接通一个交叉点开关。交叉开关实现处理机之间的置换连接（一对一）。n*n交叉开关网络一次最多可连通n个(源，目的)处理机对。

多级互连网络

MIMD和SIMD计算机都采用多级互连网络MIN（Multistage Interconnection Network）

一种通用的多级互连网络

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

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

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

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

9.5 消息传递机制

image-20230620014007093

信息传递方式

  1. 线路交换：传递信息之前，建立一条从源结点到目的结点 的物理通路( Lt ×（D+1）/B)，然后再传递信息( L/B) 。源结 点和目的结点间的通路在整个数据传送期间一直保持连接。

  2. 分组交换

    信息分割成组(包)，包通过多个不同路径传分别 送入互连网络。传送不存在一个实际连接的固定通路。包 括存储转发、虚拟直通和 虫孔方式。

    1. 存储转发

      最简单的分组交换方式

    2. 虚拟直通

      存储转发中包存储的时延大，包不必全部存入缓冲后再做路由判断，只要接收到寻径信息（头部），即进行路由选择

    3. 虫孔方式

      包可分为更小的的单位“片” 。而且使信息包中各片的传送按 流水方式进行。

  1. 第9章 互连网络
    1. 9.1 互连函数
    2. 9.2 互连网络的结构参数与性能指标
    3. 9.3 静态互连网络
      1. 1. 线性阵列
      2. 2. 环和带弦环
      3. 3. 循环移数网络
      4. 4. 树形和星形
      5. 5. 网格形和环网形
      6. 6. 超立方体
      7. summary
    4. 9.4 动态互连网络
      1. 总线结构网络
      2. 交叉开关网络
      3. 多级互连网络
    5. 9.5 消息传递机制