第6章互连网络 6.1互连网络的基本概 6.2静态互连网络 63动态互连网络 64消息传送与控制
第6章 互连网络 6.1 互连网络的基本概念 6.2 静态互连网络 6.3 动态互连网络 6.4 消息传送与控制
6.1互连网络的基本概念 6.1.1互连网络的功能与特征 61.2互连函数
6.1 互连网络的基本概念 6.1.1 互连网络的功能与特征 6.1.2 互连函数
6.1.1互连网络的功能与特征 1网络功能 互连网络是一种由开关元件按一定的拓扑结构和控制方式构成 的网络,用来实现计算机系统内部多处理机或多功能部件之间的相 互连接。它通过硬件线路,实现设备之间的连接;通过开关选择 构成一对或者对多的信息通路。如果再配以软件,还可实现数 据格式的定义、转换、打包、帧识别、发送与接收控制以及误码检 测等功能。这里主要从硬件的角度讨论互连网络的功能与特征,如 图6.1所示
6.1.1 互连网络的功能与特征 1.网络功能 互连网络是一种由开关元件按一定的拓扑结构和控制方式构成 的网络，用来实现计算机系统内部多处理机或多功能部件之间的相 互连接。它通过硬件线路，实现设备之间的连接；通过开关选择， 构成一对一或者一对多的信息通路。如果再配以软件，还可实现数 据格式的定义、转换、打包、帧识别、发送与接收控制以及误码检 测等功能。这里主要从硬件的角度讨论互连网络的功能与特征，如 图6.1所示
结点机0 结点机1 结点机n-1 处理单元 处理单元 处理单元 存储器 存储器 匚在储器 硬件接口 硬件接口 硬件接口 链路 链路 链路 互连网络 图6.1互连网络示意图 概括起来,互连网络的主要功能有以下两点: ①连接各个结点,构成信息通路,传送数据或者控制命令 ②通过路径选择,实现有目的的信息交换,其中包括-到和 到多的选择与交换。 随着互联网的发展,越来越多的并行计算机系统直接使用台式 计算机作为结点机,通过互联网连接,构成并行计算机系统,这也使 互连网络由专用型发展成为通用型
图6.1 互连网络示意图 概括起来，互连网络的主要功能有以下两点： ① 连接各个结点，构成信息通路，传送数据或者控制命令； ② 通过路径选择，实现有目的的信息交换，其中包括一到一和 一到多的选择与交换。 随着互联网的发展，越来越多的并行计算机系统直接使用台式 计算机作为结点机，通过互联网连接，构成并行计算机系统，这也使 互连网络由专用型发展成为通用型
2主要性能 主要是指网络规模、连接度、结点距离、网络直径、带宽、可靠 性和成本。 (1)网络规模:是指网络中的结点数,它体现网络所能连接的部 件数,随着设备的增加而扩大。 (2)连接度:也称为结点度,是指与该结点连接的边数,也就是 直接连接到该结点的其它结点数,常用a表示。如果一个结点直接连接 的其它结点越多,则该网络的连接度也就越高。 (3)结点距离:结点距离是从一个结点到另一结点所经过的最少边 (4)网络直径:网络直径是指网络中任意两个结点之间的最大距离, 常用D表示。从数据传送的角度来看,网络直径越小越好。 (5)等分宽度:分为通道等分宽度和线等分宽度。把网络切成相等 的两半,沿切口的最小边(通道)数称为通道等分宽度,可用展表示;若 用W表示通道宽度(用位表示),则B=kxw称为线等分宽度
2.主要性能 主要是指网络规模、连接度、结点距离、网络直径、带宽、可靠 性和成本。 （1）网络规模：是指网络中的结点数，它体现网络所能连接的部 件数，随着设备的增加而扩大。 （2）连接度：也称为结点度，是指与该结点连接的边数，也就是 直接连接到该结点的其它结点数，常用d表示。如果一个结点直接连接 的其它结点越多，则该网络的连接度也就越高。 （3）结点距离：结点距离是从一个结点到另一结点所经过的最少边 数。 （4）网络直径：网络直径是指网络中任意两个结点之间的最大距离， 常用D表示。从数据传送的角度来看，网络直径越小越好。 （5）等分宽度：分为通道等分宽度和线等分宽度。把网络切成相等 的两半，沿切口的最小边（通道）数称为通道等分宽度，可用k表示；若 用w表示通道宽度（用位表示），则B=k×w称为线等分宽度
(6)结点间线长:是指两结点之间的线路长度,它影响信号传输中的延 时、扭曲和需要的功率。 (7)对称性:从任何一个结点来看,若网络的拓扑结构都一样,则称为 对称网络。对于这种网络,容易设计和编程。 (8)数据寻径功能:表示互连网络把数据从网络的一端传送到另一端的 方式和匍力,分为静态和动态两种。静态数据寻径网络是指其结构不能用 程序改变;而动态数据寻径网络的结构可用程序改变。不同的网络结构有 着不同的数据寻径功能,常见的有一到一、一到多(广播)、散射、汇合/聚 集、归约(多到一)、循环移位、扫描和全交换等。 3主要参数 (1)带宽 是指网络传送信息的速率,常用Mbps或MBps表示,又分为聚集带宽 和等分带宽。所谓聚集带宽是在网络中,从一半结点到另一半结点,每秒 钟传送信息的最大位数或字节数.。而等分带宽是指每秒钟从最小线等分宽 度(线)上通过信息的最大位数或字节数
（6）结点间线长：是指两结点之间的线路长度，它影响信号传输中的延 时、扭曲和需要的功率。 （7）对称性：从任何一个结点来看，若网络的拓扑结构都一样，则称为 对称网络。对于这种网络，容易设计和编程。 （8）数据寻径功能：表示互连网络把数据从网络的一端传送到另一端的 方式和能力，分为静态和动态两种。静态数据寻径网络是指其结构不能用 程序改变；而动态数据寻径网络的结构可用程序改变。不同的网络结构有 着不同的数据寻径功能，常见的有一到一、一到多(广播)、散射、汇合/聚 集、归约(多到一)、循环移位、扫描和全交换等。 3.主要参数 （1）带宽 是指网络传送信息的速率，常用Mbps或MBps表示，又分为聚集带宽 和等分带宽。所谓聚集带宽是在网络中，从一半结点到另一半结点，每秒 钟传送信息的最大位数或字节数.。而等分带宽是指每秒钟从最小线等分宽 度(线)上通过信息的最大位数或字节数
例如HPS是一个对称式网络,包含512个结点,每个端口的带宽为 40MBps,可计算出聚集带宽为512/2x40MBps=10GBps。 若用表示线等分宽度中每条线上传送信息的速率,则等分带宽可表示为 Pwr (2)传输时间:是指信息通过网络所用的时间,等于信息长度除以带宽 (3)飞行时间:是指消息的第一位数据通过网络到达接收端所用的时间。 (4)传输延时:传输延时等于飞行时间与传输时间之和,是消息通过互 连网络的时间,但不包括网络两端硬件设备发送和接收的时间。 (5)总延时:包括上述传输延时和网络两端的发送与接收时间。 (6)误码率:是传输信息时岀现错误的概率,等于错误码的位数除以总 码长。显然,误码率越低越好。 (7)成本:构建互连网络所花的费用。在保证功能要求的基础上,越低 越好
例如HPS是一个对称式网络，包含512个结点，每个端口的带宽为 40MBps，可计算出聚集带宽为512/2×40MBps=10GBps。 若用r表示线等分宽度中每条线上传送信息的速率，则等分带宽可表示为 P=kwr。 （2）传输时间：是指信息通过网络所用的时间，等于信息长度除以带宽。 （3）飞行时间：是指消息的第一位数据通过网络到达接收端所用的时间。 （4）传输延时：传输延时等于飞行时间与传输时间之和，是消息通过互 连网络的时间，但不包括网络两端硬件设备发送和接收的时间。 （5）总延时：包括上述传输延时和网络两端的发送与接收时间。 （6）误码率：是传输信息时出现错误的概率，等于错误码的位数除以总 码长。显然，误码率越低越好。 （7）成本：构建互连网络所花的费用。在保证功能要求的基础上，越低 越好
4.互连网络设计要素 在设计互连网络时,所考虑的主要因素有以下4个方面。 1)传送方式 传送方式分为同步和异步两种。所谓同步方式,是在数据传送的过程 中采用统的时钟信号。 异步方式则不需要统-的时钟信号在各处理机(或单元)之间进行同 步,各处理机(或单元)根据自身需要相互建立动态连接。 2)控制策略 所谓集中控制,是由统的控制器对各个互连开关实施控制;而分散控制, 是由各个开关自身实施控制。 一般SIMD计算机采用的是集中控制和同步传送方式 (3)交换方式 是指数据传送管理方式,分为线路交换和分组交换。线路交换是在传送 过程中,在源/目标结点间建立固定的物理通路,适合于成批数据传送。分 组交换是对数据进行分组,分别送入互连网络,各分组可通过不同的路由到 达目标结点,适合于短数据报文传送。 SIMD计算机一般采用线路交换,MIMD多处理机多采用分组交换方式
4.互连网络设计要素 在设计互连网络时，所考虑的主要因素有以下4个方面。 （1）传送方式 传送方式分为同步和异步两种。所谓同步方式，是在数据传送的过程 中采用统一的时钟信号。 异步方式则不需要统一的时钟信号在各处理机（或单元）之间进行同 步，各处理机（或单元）根据自身需要相互建立动态连接。 （2）控制策略 是控制互连开关构成信息通路的方式，可分为集中控制和分散控制两种。 所谓集中控制，是由统一的控制器对各个互连开关实施控制；而分散控制， 是由各个开关自身实施控制。 一般SIMD计算机采用的是集中控制和同步传送方式。 （3）交换方式 是指数据传送管理方式，分为线路交换和分组交换。线路交换是在传送 过程中，在源/目标结点间建立固定的物理通路，适合于成批数据传送。分 组交换是对数据进行分组，分别送入互连网络，各分组可通过不同的路由到 达目标结点，适合于短数据报文传送。 SIMD计算机一般采用线路交换，MIMD多处理机多采用分组交换方式
(4)拓扑结构 是指互连网络中各结点之间的连接关系,可分为静态拓扑和动态拓 扑。静态拓扑是在网络运行中其结构不能改变;而在动态拓扑结构中设有 有源开关,在网络运行中可借助于控制信号对连接通路重新组合。 维静态拓扑有线性结构,二维有圆型、星型、树状和网格型等结 构,三维及以上有超立方体结构等。在动态拓扑中主要分为单级循环网络 和各种多级互连网络,其连接形式与互连函数密切相关。 5.互连函数 为反映互连网络的连接特征,常用函数的形式进行描述,称为互连 函数,它反映的是从输入端到输出端的映象关系。设用扆示具有M个输入 端的网络输入序号,则输出端的序号用函数八x)表示。 设是一个m位的二进制数,即Xb1b-2.bb0,其中m=og2N 则x因函数的不同,而有不同的表达式,例如 交换互连函数)=加-12.b1b0=加n-加-2.b1b0 全混洗互连函数()=加-加n=2.b1b0=bn2.b1b0bn-1
（4）拓扑结构 是指互连网络中各结点之间的连接关系，可分为静态拓扑和动态拓 扑。静态拓扑是在网络运行中其结构不能改变；而在动态拓扑结构中设有 有源开关，在网络运行中可借助于控制信号对连接通路重新组合。 一维静态拓扑有线性结构，二维有圆型、星型、树状和网格型等结 构，三维及以上有超立方体结构等。在动态拓扑中主要分为单级循环网络 和各种多级互连网络，其连接形式与互连函数密切相关。 5.互连函数 为反映互连网络的连接特征，常用函数的形式进行描述，称为互连 函数，它反映的是从输入端到输出端的映象关系。设用x表示具有N个输入 端的网络输入序号，则输出端的序号用函数f(x)表示。 设x是一个n位的二进制数，即x=bn-1bn-2…b1b0，其中n=log2N。 则f(x)因函数的不同，而有不同的表达式，例如： 交换互连函数f(x)=f(bn-1bn-2…b1b0)= bn-1bn-2…b1b¯0 全混洗互连函数f(x)=f(bn-1bn-2…b1b0)=bn-2…b1b0bn-1
61.2互连函数 1恒等互连函数 也称为直通互连函数,是指输出端与相同序号的输入端对应连接。 其表达式为: 1(x=I(bnbn2bb)=bnbn2bb 其示意如图6.2所示,左边表示输入端,右边表示输出端。 000 000 2交换互连函数 001 001 交换互连函数( Exchange)实现输入 010 010 端与地址中某一位取反的输出端连接: 011 Exchange(b,,bn.26,b0)=bn.,b 100 100 扩展交换互连函数是把地址中的任位 101 101 变反,其表达式为 110 110 11 Exchange(bhn,bn2…b-bb)k=bn,bn2…bk…bb 0图6.2恒等互连示意图
6.1.2 互连函数 1.恒等互连函数 也称为直通互连函数，是指输出端与相同序号的输入端对应连接。 其表达式为： I(x)=I(bn-1 bn-2…b1 b0 )=bn-1 bn-2…b1 b0 其示意如图6.2所示，左边表示输入端，右边表示输出端。 图6.2 恒等互连示意图 2.交换互连函数 交换互连函数（Exchange）实现输入 端与地址中某一位取反的输出端连接： Exchange(bn-1 bn-2…b1 b0 )=bn-1 bn-2…b1 b0 扩展交换互连函数是把地址中的任一位 变反，其表达式为： Exchange(bn-1 bn-2…bk…b1 b0 )k=bn-1 bn-2…bk …b1 b0