计算机系统结构（2月8日）

互联与通信

互连网络的作用

互连网络：由开关元件按一定拓扑结构和控制方式构成的网络以实现计算机系统内部多个处理机或多个功能部件间的相互连接

操作方式：同步通信（Synchronous Communication）、异步通信（Asynchronous Communication）

控制策略：集中控制（Centralized control）、分布控制（Distributed Control）

静态互连网络：

特点：

静态网络由点-点直接相连而成，这种连结方式在程序执行过程中不会改变

如果用图来表示，结点代表开关，边代表通信链路，则：

（1）结点间的链路无源，不能重构

（2）开关元件与处理机相连

（3）不直接相连结点间的通信需通过中间节点中转

静态网络的指标：

结点度：与结点相连接的边（链路或通道）数，表示节点所需要的IO端口数，模块化要求结点度保持恒定。根据通道到结点的方向，结点度可以进一步表示为：结点度 = 入度 + 出度

其中入度是进入结点的通道数，出度是从结点出来的通道数。

距离：与两个结点之间相连的最少边数

网络直径：网络中任意两个结点间距离的最大值

希望结点度是恒定的

网络规模：网络中结点数，表示该网络功能连结部件的多少

等分宽度：某一网络被切成相等的两半时，沿切口的最小边数称为该网络的等分宽度

结点间的线长：两个结点间的线的长度

对称性：从任何结点看，拓扑结构都一样，这种网络实现和编程都很容易

结点是否同构

通道是否有缓冲

典型的静态网络

1、线性阵列 对N个结点的线性阵列，有N-1条链路，直径为N-1（任意两点之间距离的最大值），度为2，不对称，等分宽度为1.N很大时，通信效率很低

线性阵列与总线的区别：

线性阵列：允许不同的源结点和目的结点对并发使用系统的不同部分

总线：通过切换与其相连的许多结点来实现时分特性，同一时刻只有一对结点在传送数据

2、环 对N个结点的环，考虑相邻结点数据传送方向：

双向环：链路数为N，直径N/2(向下取整)，度为2，对称，等分宽度为2

单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2

3、带弦环

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

5、树型 一棵K层完全二叉树应有N=2的k次方-1个结点，对大结点度为3，直径为2（K-1）（即右边任意一个叶子结点到左边任意一个叶子结点）。不对称，等分度为1，由于结点度为常数，所以树是一种可扩展的系统结构

树型的扩展：带环树，同一层构成一个环；二叉胖树，这两种结构都可以缓解根结点的瓶颈问题

6、星形 星形实际上是一种二层树，有N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非堆成，等分宽度为1

7、网格型和环网型 有N个结点的r×r网（其中r的N的开平方），有2N-2r条链路，直径为2（r-1），结点度为4，非对称，等分宽度为r

a.llliac网：有N个结点的r×r网（其中r=N的开平方），有2N条链路，直径为r-1，结点度为4

b.环形网 2D-Torus 有N个结点的r×r网，其中r=N的开平方，有2N条链路，直径为2（r/2向下取整），结点度为4，对称

c.搏动式阵列（Systolic Array）

8、超立方体 0-立方体；1-立方体；2-立方体；3-立方体；4-立方体

一个n-立方体由N=2的n次方个结点构成，它们分布在n维上，每维有两个结点。直径为n，结点度为n，对称。由于结点度随维数线性增加，所以超立方体不是一种可扩展结构

例子：Intel的iPSC/1、iPSC/2、nCUBE

结点数增加，度数不增加为佳

9、带环立方体

一个带环n-立方体由N=2的n次方个结点环构成，每个结点环是一个有n个结点的环，所以结点总数为n×2的n次方个，直径通常为2n，结点度为3，对称

10、k元n-立方体网络

在一个k元n-立方体网络中，结点的数目N=k的n次方，k=N开n次方，其中k称为基数（radix），n称为维数（dimension）

k元n-立方体的结点可以用基数为k的n位地址A=a0a1a2...an来表示，其中ai代表第i维结点的位置

传统的环网等价于4元2-立方体

动态网络

互连函数：