第7章 互连网络

1.   互连网络

一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。这些结点可以是处理器、存储模块或其他设备。

 

2.   线路交换

源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。

 

3.   分组交换

把信息分割成许多组（又称为包），将它们分别送入互连网络。这些数据包可以通过不同的路径传送，到目的结点后再拼合出原来的数据。在分组交换中，结点之间不存在固定连接的物理通路。

 

4.   集中控制方式

集中控制方式中，有一个全局的控制器接收所有的通信请求，并由它设置互连网络的开关连接。

 

5.   分散控制方式

分散控制方式中，不存在全局的控制器，通信请求的处理和开关的设置由互连网络分散地进行。

 

6.   静态拓扑结构

在各结点之间有专用的连接通路，且在运行过程中不能改变。

 

7.   动态拓扑结构

根据需要设置互连网络中的开关，从而对结点之间的连接通路进行重新组合，实现所要求的通信模式。

 

8.   互连函数

用变量x表示输入（设x=0，1，…，N－1），用函数f(x)表示输出，通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。也称为置换函数或排列函数。

 

9.   循环

互连函数f(x)有时可以采用循环表示，即：（x₀ x₁x₂… x_j-1）。它表示

f(x₀)=x₁，f(x₁)=x₂，…，f(x_j-1)=x₀

j称为该循环的长度。

 

10. 交换函数

实现二进制地址编码中第k位互反的输入端与输出端之间的连接。其表达式为

11. 均匀洗牌函数

将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。其函数关系可表示为

                              

即把输入端的二进制编号循环左移一位。

 

12. 逆均匀洗牌函数

将输入端的二进制编号循环右移一位而得到所连接的输出端编号。其互连函数为

 

逆均匀洗牌是均匀洗牌的逆函数。

 

13. 蝶式互连函数

把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。

定义为

 

14. 反位序函数

将输入端二进制编号的位序颠倒过来求得相应输出端的编号。其互连函数为

 

15. PM2I函数

一种移数函数，它是将各输入端都循环移动一定的位置连到输出端。其函数为

           

其中，0≤x≤N－1，0≤i≤n－1，n＝log₂N，N为结点数。

 

16. 网络规模

一般说来，网络用图来表示。这种图由用有向边或无向边连接的有限个结点构成。其结点数称为网络规模。

 

17. 结点度

与结点相连接的边的数目。

 

18. 入度

在单向通道的情况下，进入结点的通道数。

 

19. 出度

在单向通道的情况下，从结点出来的通道数。

 

20. 距离

对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。

 

21. 网络直径

网络中任意两个结点间最短路径长度的最大值。

 

22. 等分宽度

在将某一网络切成相等两半的各种切法中，沿切口的最小通道边数。

 

23. 结点之间的线长

两个结点之间连线的长度，用米、千米等表示。

 

24. 对称网络

对于一个网络，如果从其中的任何一个结点看，拓扑结构都是一样的，则称此网络为对称网络。

 

25. 线性阵列

一种一维的线性网络，其中N个结点用N-1个链路连成一行。内部结点度为2，端结点度为1，直径为N-1，等分宽度b=1。

 

26. 环

用一条附加链路将线性阵列的两个端点连接起来而构成的。可以单向工作，也可以双向工作。它是对称的，结点度是常数2。双向环的直径为N/2，单向环的直径是N。

 

 

27. 带弦环

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

 

28. 全连接网络

一种环网。其中任何两个结点之间都有链路相连。

 

29. 循环移数网络

通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成的。这就是说，如果｜j-i｜=2 ^r，r=0,1,2,…,n-1，网络规模N=2ⁿ，则结点i与结点j连接。这种循环移数网络的结点度为d=2n-1，直径D=n/2。

 

30. 超立方体

一种二元n立方体结构。一般说来，一个n立方体由N=2ⁿ个结点组成，它们分布在n维上，每维有两个结点。

 

31. 交叉开关网络

每个输入端通过一个交叉点开关无阻塞地与一个空闲输出端相连。它是单级无阻塞置换网络，带宽和互连特性最好。