静态互连网络

全链接
　　■全链接是带弦环的一种特殊情形。链接中的每个结点和其他结点之间都有单一的直接链路。

　　■如下图中8个结点的全链接：有28条链路，直径为1，度为7，对称，等分宽度为16。

树形
　　■一棵K层完全二叉树应有N = 2^K - 1个结点，最大结点度为3，直径为2（K - 1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分宽度为1。

树形的扩展

这两种结构都可以缓解根结点的瓶颈问题

静态互连网络

星形
　　■星形实际上是一种二层树（如右图）。有N个结点的星形网络，有N - 1条链路，直径为2，最大结点度为N - 1，非对称，等分宽度为1。

网格形
　　■有N个结点的r*r网，有2N - 2r条链路，直径为2(r-1)，结点度为4，非对称，等分宽度为r。

　　■其中　

二维环网形
　　■有N个结点的r*r网，有2N条链路，直径为2[r/2]，结点度为4，对称。

　　■其中　

超立方体
　　■一个n-立方体由N = 2ⁿ个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。

带环立方体
　　■一个带环n-立方体由N = 2n个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n2ⁿ个，结点度为3，对称。

静态互连网络特性一览表

动态互连网络

网络特点
　　■动态网络中的连接不固定，在程序执行过程中可根据需要改变。
　　■网络的开关元件有源，链路可通过设置这些开关的状态来重构。
　　■只有在网络边界上的开关元件才能与处理机相连。
　　■动态网络主要有总线、交叉开关、多级交换网络。

总线（Bus）
　　■总线实际上是连接处理器、存储器和I/O等外围设备的一组导线和插座。
　　■它在某一时刻只能用于一对源和目的之间传输数据。
　　■当有多对源和目的请求使用总线时，要进行总线仲裁。当CPU数目较多时对总线争用严重（<=32个）。
线性阵列与总线的区别
　　■线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分。
　　■总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据。

交叉开关（Crossbar Switcher）
　　■交叉开关是一种高带宽网络，它可以在输入端和输出端之间建立动态连接
　　■在每个输入端和输出端的交叉点上都有交叉点开关。该开关可以根据需要置为“开”或“关”状态，从而使不同的输入端和输出端导通。
　　■交叉开关的硬件复杂性为n²数量级，造价昂贵。但是其带宽和寻径性能在这三种动态网络中最好。如果网络规模小，它是一种理想的选择（<=64个）。

动态互连网络

多级交换网络
　　■开关单元：a个输入a个输出的开关单元记作a*a的开关单元，其中，a是2的整数倍。常见的有2*2、4*4、8*8等。
　　■根据开关单元功能的多少，2*2又可以分为两功能和四功能开关。

多级交换网络
　　■级间互连模式
　　　　◆均匀洗牌、蝶式、多路洗牌、纵横开关及立方体连结等

　　■控制方式
　　　　◆级控制：每级只有一个控制信号
　　　　◆单元控制：每个开关一个控制信号
　　　　◆部分级控制：几个开关合用一个控制信号

　　■多级交换网络是总线和交叉开关的折衷。它的主要优点在于采用模块结构，可扩展性好（>64）

Ω多级交换网络