互联网络的基本概念
此处概念限定为“互连”，与“互联”区分。
互连网络的功能和特征
互联网络（interconnection network）是一种由开关元件按照一定拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。这些节点可以是处理器、存储模块后其他设备。从拓扑结构角度，互联网络是从输入结点到输出结点之间的一组互连或映射（mapping）。
互连网络已经成为并行计算机系统的一个关键组成部分。随着各个领域对高性能计算机的要求越来越高，多处理机和多计算机系统的规模越来越大，对处理器之间或处理单元与存储模块之间通信的速度和灵活性的要求也越来越高。因此，它对计算机系统的性能价格比有着决定性的影响。
可以从以下4个不同的方面来描述互连网络。
（1）定时方式：有同步和异步两种。
同步系统使用一个统一的时钟。它可以将数据同时播送到所有处理器结点中， 也可以使所有结点同时与相邻的结点进行通信（若无冲突）。而异步系统没有统一的时钟，系统中的各个处理机都是独立地工作。
（2）交换方式：有线路交换和分组交换两种。
（3）控制策略：有集中式和分散式两种。
（4）拓扑结构：有静态和动态两种。
互连函数
为反应不同互连函数的连接特性，每种互连网络可用一组互连函数（interconnection function）来描述。用变量x表示输入（设x=0,1，···，N-1），用函数f(x)表示输出，通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f（x）。x和f（x）可以用二进制表示，也可以用十进制表示。
互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系，所以互连函数有事也称为置换（permutation）函数或排列函数。
互连函数f（x）有时可以采用循环表示，即（
其中，j称为该循环的长度。
下面介绍几种常用的基本互连函数及其主要特征。
交换函数
交换函数用于实现二进制地址编码中第k位互反的输入端与输出端的连接。其表达式为：
交换函数主要用来构建立方体网络和各种超立方体互连网络。它共有
均匀洗牌函数
均匀洗牌函数（shuffle）定义为：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉的连接到输出端（输出端相当于混洗的结果），其函数可表示为：
即把输入端的二进制编号循环左移一位。
逆均匀洗牌函数于此类似，是将输入端的二进制编号循环右移一位而得到所连接的输出端编号。
逆均匀洗牌函数是均匀洗牌函数的逆函数。两者的输入端与输出端正好互换位置（互为镜像）。
用它们代表的链路和交换开关多级组合起来可构成Omega网络与逆Omega网络。
蝶式函数
蝶式互连函数（butterfly）定义为：
即把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。
与均匀混洗函数类似，只用蝶式函数不能实现任意结点之间的连接，但是蝶式变换与交换变换的多级组合可作为构成方体多级网络的基础。
反位序函数
反位序函数是将输入端二进制编号的位序颠倒过来求得相应输出端的编号。其互连函数为：
对于N=8的情况，正好B(x)函数等于R(x)函数，其变换图形如下。
PM2I函数
PM2I函数是一种移数函数，它是将各输入端都循环移动一定的位置后连到输出端。其函数为：
其中，0<=x<=N-1, 0<=i<=n-1, n=log_2N, N为结点数。显然，PM2I互连网络共有2n个互连函数。
当N=8时，有6个PM2I函数：
下图画出了其中3个函数的变形图形。
PM2I函数是构成数据变换网络的基础。
阵列计算机ILLIAC IV采用
互连函数的性能参数
网络通常是用有向边或无向边连接有限个结点的图来表示。互连网络的主要特征参数有：
（1）网络规模（network size）：网络中结点的个数。它表示该网络所能连接的部件的数量。
（2）节点度（node degree）：与结点相连接的边数（通道数），包括入度（in degree）和出度（out degree）。进入结点的边数称为入度，从结点出来的边数称为出度。
（3）距离：对于网络中的任意两个结点，从一个结点出发到另一个节点终止所需要跨越的边数的最小值。
（4）网络直径（network diameter）：网络中任意两个结点之间距离的最大值。网络直径应尽可能地小。
（5）结点之间的线长：两个结点之间连线的长度，用米、千米等表示。
（6）等分宽度：当某一网路被分割成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度（channel bisection width），用b表示。而线等分宽度为B=b*w。其中w为通道宽度（用位表示）。该参数主要反映了网络最大流量。
（7）对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络（symmetric network）。对称网络比较容易实现，编程也比较容易。
↶ 返回首页