互联网络技术

1、第三章第三章 互互 联联 网网 络络 技技 术术 互连网络是高度并行计算机系统中的关键部件。本章介绍互连 网络的基本概念、描述工具、互连函数和性能参数等，讨论静态互 连网络的结构与特性，分析动态互连网络的互连形式和几种多级互 连网络结构特点、控制与寻径方式，阐述交叉开关的设计技术和互 连网络消息传递控制策略与机制。 第一节第一节 互连网络的基本概念互连网络的基本概念 第二节第二节 静态互连网络静态互连网络 第三节第三节 动态互连网络动态互连网络 第四节第四节 常用的多级交叉开关动态互连网络常用的多级交叉开关动态互连网络 第五节第五节 互连网络的消息传递互连网络的消息传递 一、互连网络的功能和特

2、征互连网络的功能和特征 二、互连网络的描述工具互连网络的描述工具 三、常用的基本互连函数三、常用的基本互连函数 四、互连网络结构特性和传输性能参数四、互连网络结构特性和传输性能参数 五、互连网络的分类五、互连网络的分类 第一节 互连网络互连网络的基本概念的基本概念 一、一、互连网络的分类互连网络的分类 1.1.互连网络及其组成互连网络及其组成 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构互连网络是一种由开关元件按照一定的拓扑结构和控制方式构 成的网络，用来实现计算机系统内部多个处理机或多个功能部件之成的网络，用来实现计算机系统内部多个处理机或多个功能部件之 间的相互连接及信息交换。间

3、的相互连接及信息交换。所有的互连网络都是由链路、网络接口所有的互连网络都是由链路、网络接口 电路和交叉开关等三部分组成（共享介质的互连网络不使用交叉开电路和交叉开关等三部分组成（共享介质的互连网络不使用交叉开 关），其中交叉开关是核心。关），其中交叉开关是核心。 链路（链路（LinkLink）也称之为通道或电缆，是用来将计算机系统中两）也称之为通道或电缆，是用来将计算机系统中两 个硬件进行物理连接。一条链路可连接两个交叉开关或一个交叉开个硬件进行物理连接。一条链路可连接两个交叉开关或一个交叉开 关和一台处理机或一个功能部件的网络接口。目前链路的介质一般关和一台处理机或一个功能部件的网络接口。目

4、前链路的介质一般 是铜线或光纤。因此，链路除可从使用的介质来分类外，还可从逻是铜线或光纤。因此，链路除可从使用的介质来分类外，还可从逻 辑特性上分。辑特性上分。 从长度来看，有短链路和长链路之分；一条短链路在任何时刻从长度来看，有短链路和长链路之分；一条短链路在任何时刻 仅包含一个逻辑信号，而一长短链路在任何时刻允许传输一串逻辑仅包含一个逻辑信号，而一长短链路在任何时刻允许传输一串逻辑 信号，如同一条传输线。从宽度来看，有串行链路和并行链路之分；信号，如同一条传输线。从宽度来看，有串行链路和并行链路之分； 串行链路（窄链路）只有一位信号线，各种信息以多路分时复用的串行链路（窄链路）只有一位信号

5、线，各种信息以多路分时复用的 方式共享单信号线；并行链路（宽链路）有多位信号线，各种信息方式共享单信号线；并行链路（宽链路）有多位信号线，各种信息 可并行传输。从驱动时钟来看，有同步时钟链路和异步时钟链路之可并行传输。从驱动时钟来看，有同步时钟链路和异步时钟链路之 分；同步时钟链路是指链路两端的结点使用相同的时钟；异步时钟分；同步时钟链路是指链路两端的结点使用相同的时钟；异步时钟 链路是指通过嵌入时钟编码，链路两端的结点可使用不同的时钟。链路是指通过嵌入时钟编码，链路两端的结点可使用不同的时钟。 网络接口电路（网络接口电路（Network Interface CircuitryNetwork

6、Interface Circuitry，即，即NICNIC）也称）也称 之为网卡，是用来将计算机系统中结点（一台处理机或一个功能部之为网卡，是用来将计算机系统中结点（一台处理机或一个功能部 件）连接到网络上。网络接口必须能够处理结点与网络之间的双向件）连接到网络上。网络接口必须能够处理结点与网络之间的双向 传输，其功能主要包括消息包格式化、路由通路选择、一致性检查、传输，其功能主要包括消息包格式化、路由通路选择、一致性检查、 流量与错误控制等。因此，网络接口的成本由端口规模、存储容量、流量与错误控制等。因此，网络接口的成本由端口规模、存储容量、 处理与控制能力等决定。处理与控制能力等决定。 交

7、叉开关（交叉开关（SwitchSwitch）也称之为路由器，是用来建立结点对之间）也称之为路由器，是用来建立结点对之间 连接的开关阵列。交叉开关包括输入输出端口、结点开关阵列及其连接的开关阵列。交叉开关包括输入输出端口、结点开关阵列及其 控制逻辑，如图控制逻辑，如图3-13-1所示为一个所示为一个4 4输入输入4 4输出的交叉开关。输出的交叉开关。 接收器 输入缓 冲器 输出缓冲器 发送器 输 入 端 口 输出端口 开关控制逻辑 2. 2.互连网络功能及其划分互连网络功能及其划分 多处理机系统中每台处理机多处理机系统中每台处理机PiPi与自己的本地存储器与自己的本地存储器LMLM和私有和私有

8、高速缓存储器高速缓存储器CiCi可直接相连，但应通过多处理机可直接相连，但应通过多处理机存储器互连网存储器互连网 络（络（IPMNIPMN）与共享存储器模块）与共享存储器模块SMSM相连，通过多处理机相连，通过多处理机I/OI/O网络网络 （PIONPION）访问共享的）访问共享的I/OI/O和外围设备，多处理机之间通过处理机间和外围设备，多处理机之间通过处理机间 通信网络（通信网络（IPCNIPCN）进行通信。）进行通信。 互连网络 软件接口 硬件接口 软件接口 硬件接口 软件接口 硬件接口 链路链路链路 结点结点结点 根据互连网络连接的结点距离可划分出系统域网络根据互连网络连接的结点距离可

9、划分出系统域网络SANSAN（3 3 25m25m）、局域网络）、局域网络LANLAN（5005002000 m2000 m）、城域网络）、城域网络MANMAN（25km25km） 和广域网络和广域网络WANWAN（全球）。（全球）。 LAN（如以太网、FDDI） 节点1 处理机总线 局部总线,存储器总线 SCSI 接口 I/O总线，系统总线 MP I/O口桥 磁盘 SAN(如Myrinet) 节点2 系统I 系统 节点N 3. 3.互连网络的基本特征互连网络的基本特征 (1)(1)定时方式定时方式 互连网络的定时方式有同步和异步两种。同步系统使用一个互连网络的定时方式有同步和异步两种。同步系

10、统使用一个 集中的统一时钟，它可以把数据同时播送到各结点中。异步系统集中的统一时钟，它可以把数据同时播送到各结点中。异步系统 没有时钟，各结点根据各自的需要进行通信。没有时钟，各结点根据各自的需要进行通信。 (2)(2)交换方法交换方法 互连网络的交换方法有线路交换和分组交换两种。互连网络的交换方法有线路交换和分组交换两种。 (3)(3)控制策略控制策略 互连网络的控制策略有集中式和分散式两种。集中控制有一互连网络的控制策略有集中式和分散式两种。集中控制有一 个全局的控制器接收所有的通信请求，并设置互连网络中相应开个全局的控制器接收所有的通信请求，并设置互连网络中相应开 关的实际连接的物理通路

11、。而分散控制对通信请求处理和设置互关的实际连接的物理通路。而分散控制对通信请求处理和设置互 连网络中相应开关的实际连接的物理通路是由分布在各个功能部连网络中相应开关的实际连接的物理通路是由分布在各个功能部 件中的控制逻辑分散地进行通信实现的。件中的控制逻辑分散地进行通信实现的。 (4)(4)拓扑结构拓扑结构 互连网络的拓扑结构有静态拓扑结构和动态拓扑结构两种。互连网络的拓扑结构有静态拓扑结构和动态拓扑结构两种。 二、二、互连网络的描述工具互连网络的描述工具 1.1.图形表示法图形表示法 图形表示法是把互连网络中输入输出的对应关系用连线图来表图形表示法是把互连网络中输入输出的对应关系用连线图来表

12、 示。该方法虽然直观，但比较烦琐，且难以体现内在规律，因此，示。该方法虽然直观，但比较烦琐，且难以体现内在规律，因此， 一般结合另外两种表示法一起使用。一般结合另外两种表示法一起使用。 2.2.对应表示法对应表示法 0 0变换变换f(0)f(0)，1 1变换为变换为f(1)f(1)，N-1N-1变换为变换为f(N-1)f(N-1)。 01N1 f(0 )f(1 )f(N1 ) 0 1 2 3 4 5 6 70 1 2 3 4 5 6 7 0 2 4 6 1 3 5 70 2 4 6 1 3 5 7 3.3.函数表示法函数表示法 函数表示法是把互连网络中输入输出的变换关系通过数学表函数表示法是把

13、互连网络中输入输出的变换关系通过数学表 达式表示，若用表示输入端变量，则用函数表示输出端变量，函达式表示，若用表示输入端变量，则用函数表示输出端变量，函 数称为互连函数。由于一个结点在一般情况下既可作输入端，也数称为互连函数。由于一个结点在一般情况下既可作输入端，也 可作输出端，所以通常认为输入端数与输出端数是相等的。如果可作输出端，所以通常认为输入端数与输出端数是相等的。如果 互连网络将互连网络将N N个结点连接，则该互连网络有个结点连接，则该互连网络有N N个输入结点和个输入结点和N N个输出个输出 结点，即有结点，即有N N个输入变量和个输入变量和N N个输出变量。输入端与输出端的变量个

14、输出变量。输入端与输出端的变量 通常用对应的二进制数的结点编号来表示，则互连函数与对应表通常用对应的二进制数的结点编号来表示，则互连函数与对应表 示法一样，表示了输入端与输出端之间的一一对应关系。若为位示法一样，表示了输入端与输出端之间的一一对应关系。若为位 二进制数，则互连函数一般写成。二进制数，则互连函数一般写成。 有一种特殊的互连函数称为循环互连函数。有一种特殊的互连函数称为循环互连函数。 01 () j x xx 01 ()f xx 0 () J f xx 12 ()fxx 四、常用的基本互连函数常用的基本互连函数 1.1.恒等置换恒等置换 相同编号的输入端与输出端一一对应互连所实现的

15、置换称为恒相同编号的输入端与输出端一一对应互连所实现的置换称为恒 等置换。等置换。 12101210 (, , ), , nnnn I xxx xxxx x 1 11 1 0 0 0 0 2 22 2 3 33 3 4 44 4 5 55 5 6 66 6 7 77 7 2.2.交换置换交换置换 交换置换是实现二进制地址编号中第交换置换是实现二进制地址编号中第0 0位值不同的输入端和输位值不同的输入端和输 出端之间的连接。出端之间的连接。 0 1210121 (, ,), , nnnn E xxx xxxx x 1 11 1 0 0 0 0 2 22 2 3 33 3 4 44 4 5 55

16、5 6 66 6 7 77 7 3.3.方体置换方体置换 方体置换是实现二进制地址编号中第方体置换是实现二进制地址编号中第k k位值不同的输入端和输位值不同的输入端和输 出端之间的连接。出端之间的连接。 121110121110 (,.,., ,),.,., , nnkkknnkkk C xxxx xx xxxxx xx x 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1

17、2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 4.4.均匀洗牌置换均匀洗牌置换 将输入端二进制地址循环左移一位即得到对应输出端的二进将输入端二进制地址循环左移一位即得到对应输出端的二进 制地址。制地址。 还可分别定义子洗牌还可分别定义子洗牌(k) (k)和超洗牌 和超洗牌(k) (k) 。 。 12102301 (, ,), nnnnn xxx xxxx x ( )12111012110 (, , ), knnkkknnkkk xxxx xx xxxxxx x ( ) 121210231,120 (,), k nnn kn kn

18、 knnn kn knn kk xxxxxx xxxxxxxx x (1) (1) ( )( )( ) n n xxx (0 ) (0 ) ( )( )xxx 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 （a）均匀洗牌置换 （b）子洗牌置换(2) （c）超洗牌

19、置换(2) 逆均匀洗牌是均匀洗牌的逆函数逆均匀洗牌是均匀洗牌的逆函数 另外还有另外还有q q洗牌函数：分成洗牌函数：分成q q组，每组组，每组r r张。张。 1 12100121 (,), nnn xxx xx xx x ( )(/ )mod qr Siqiirqr 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 N=8时的逆均匀洗牌置换 N=8、q=2时的q洗牌置换 5.5.蝶式置换蝶式

20、置换 将输入端二进制地址的最高位和最低位互换位置即可得相应将输入端二进制地址的最高位和最低位互换位置即可得相应 输出端的地址。输出端的地址。 还可分别定义子蝶式和超蝶式还可分别定义子蝶式和超蝶式( )k ( )k 12100211 (, ,), , nnnn xxx xx xx x ( )121110121011 (,), knnkkknnkkk xxxxxx xxxxx xx x ( ) 121210121,210 (,), k nnn kn kn kn knn knn k xxxxxx xxxxxxx x (1) (1) ( )( )( ) n n xxx (0) (0) ( )( )xx

21、x 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 =置换 (2) = (2) 置换 (2) = (2) 置换 6.6.位序颠倒置换位序颠倒置换 将输入端二进制地址的位序颠倒过来求得相应输出端的地址。将输入端二进制地址的位序颠倒过来求得相应输出端的地址。 还可分别

22、定义子位序颠倒和超位序颠倒还可分别定义子位序颠倒和超位序颠倒 12100121 (, ,), , nnnn xxx xx xxx ( )121110121011 (, , ), , , knnkkknnkkk xxxx xx xxxxx xxx ( ) 121210121,210 (,), k nnn kn kn kn kn knnn k xxxxxx xxxxxxx x 7.7.移数置换移数置换 将输入端编号循环移动一定的位置得出输出端编号。将输入端编号循环移动一定的位置得出输出端编号。 可将整个输入端编号分成若干组，在组内进行循环移数置换。可将整个输入端编号分成若干组，在组内进行循环移数置

23、换。 移数置换是循环互连函数。移数置换是循环互连函数。 ()() m od, 01xxkNxN (1):2(1):2 ( )( ) mod 22 rr rr NN xxk (21):0(21):0 ( )( )mod2 rr r xxk 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8.8.加减加减2I2I置换置换 加减加减2I2I置换使输入端编号同输出端编号相连。置换使输入端编号同输出

24、端编号相连。 加减加减2I2I置换置换也是一种移数置换，也是一种移数置换，是循环互连函数，。是循环互连函数，。 ( )2 mod i i PMxxN ()2m o d i i P MxxN 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 （a）i=+0 （b）i=

25、+1 （c）i=+2 四、互连网络结构特性和传输性能参数互连网络结构特性和传输性能参数 1.1.互连网络的结构特性参数互连网络的结构特性参数 物理结构参数物理结构参数 （1 1）网络规模。）网络规模。 （2 2）结点度。）结点度。 （3 3）结点距离。）结点距离。 （4 4）网络直径。）网络直径。 （5 5）结点线长。）结点线长。 逻辑特性参数逻辑特性参数 （1 1）网络等分宽度。当某一互连网络被切分成相等的两半）网络等分宽度。当某一互连网络被切分成相等的两半 时，沿切口的最小边（通道）数称为通道等分宽度，又称对剖宽时，沿切口的最小边（通道）数称为通道等分宽度，又称对剖宽 度，用度，用 b b

26、 表示。相应的切口称为对剖平面（一组连线）。而线等表示。相应的切口称为对剖平面（一组连线）。而线等 分宽度分宽度B=bB=b，为通道宽度（用位表示）。为通道宽度（用位表示）。 （2 2）网络对称性。）网络对称性。 （3 3）网络可扩展性。）网络可扩展性。 2. 2. 互连网络的传输性能参数互连网络的传输性能参数 发送方的步骤为：首先应用程序把要发送的数据拷贝送到操作发送方的步骤为：首先应用程序把要发送的数据拷贝送到操作 系统缓冲区；然后操作系统根据要发送的数据计算出检查和，把系统缓冲区；然后操作系统根据要发送的数据计算出检查和，把 它放在消息中，并启动超时计数器；最后操作系统把缓冲区中的它放在

27、消息中，并启动超时计数器；最后操作系统把缓冲区中的 数据送到网络接口硬件，并通知硬件开始发送消息。数据送到网络接口硬件，并通知硬件开始发送消息。 A机器 B机器 都有一个先进先出的数据队列 接收方开 销 总时延 接收方 传输时间 传送时间 传输时间 发送方开 销 发送方 飞行时间 时延性能参数时延性能参数 总时延总时延= =发送方开销发送方开销+ +飞行时间飞行时间+ +传送时间传送时间+ +接收方开销。接收方开销。 （1 1）发送方开销）发送方开销 （2 2）接收方开销）接收方开销 （3 3）飞行时间：飞行时间是指发送方开始发送消息至第一位）飞行时间：飞行时间是指发送方开始发送消息至第一位

28、信息到达接收方所花费的时间，它包括由于网络中转发或其他硬信息到达接收方所花费的时间，它包括由于网络中转发或其他硬 件所花费的时间。件所花费的时间。 （4 4）传送时间：传送时间是指消息通过网络的时间，它等于）传送时间：传送时间是指消息通过网络的时间，它等于 消息长度除以网络频宽。消息长度除以网络频宽。 （5 5）传输时间）传输时间 带宽性能参数带宽性能参数 （1 1）端口带宽。互连网络中任一端口到另一端口传输信息的）端口带宽。互连网络中任一端口到另一端口传输信息的 最大速率称为端口带宽，单位为最大速率称为端口带宽，单位为MB/sMB/s。对称网络的端口带宽与端。对称网络的端口带宽与端 口位置无

29、关，非对称网络的端口带宽是所有端口带宽的最小值。口位置无关，非对称网络的端口带宽是所有端口带宽的最小值。 （2 2）聚集带宽。互连网络中从一半结点到另外一半结点传输）聚集带宽。互连网络中从一半结点到另外一半结点传输 信息的最大速率称为聚集带宽，单位为信息的最大速率称为聚集带宽，单位为MB/sMB/s。聚集带宽。聚集带宽= =端口带宽端口带宽 结点数结点数/2/2。例如每个端口带宽为。例如每个端口带宽为10MB/s10MB/s，那么，那么512512个结点的聚集个结点的聚集 带宽为带宽为(10(10512)/22.5GB/s512)/22.5GB/s。 （3 3）对剖带宽。互连网络中对剖平面上传

30、输信息的最大速率）对剖带宽。互连网络中对剖平面上传输信息的最大速率 称为对剖带宽，单位为称为对剖带宽，单位为MB/sMB/s。 （4 4）网络频宽（）网络频宽（bandwidthbandwidth）。网络频宽泛指消息进入网络）。网络频宽泛指消息进入网络 频宽网络后，互连网络传输信息的最大速率，单位为频宽网络后，互连网络传输信息的最大速率，单位为MB/sMB/s。 五、互连网络的分类互连网络的分类 总线 环 单总线 多总线 底板总线 争用总线 令牌总线 共享介质网络 非阻塞网络 二维网络交换开关 共享存储器 空分总线 Clos网络 2维网络 3维网络 2维环形网络 3维环形网络 双向环形网络 单

31、向环形网络-1维 网格网络 环形网络 超立方体网络 基于寻径器网络 单向多级网络 双向多级网络 单向环形网络 规则拓扑结构网络 非规则拓扑结构网络 基于开关网络 混合型网络 互连网络 例例3.1 3.1 由由1616个处理单元组成的个处理单元组成的Illiac Illiac 阵列处理机采用的互阵列处理机采用的互 连网络如图连网络如图3-163-16所示，该互连网络采用的是哪一种互连函数。所示，该互连网络采用的是哪一种互连函数。 4567 891011 0123 12131415 解：横向处理单元的连接有两种，一是 01214150，即是（0 1 2 14 15）；另 一是151421015，即

32、是（15 14 2 1 0）。互连函数函数分别为PM2+0和PM2-0。 纵向处理单元的连接有两种，一是048120、 159131、2610142、3711153，即是（0 4 8 12）、（1 5 9 13）、（2 6 10 14）、（3 7 11 15）；另一是1284012、1395113、 14106214、15117315，即是（12 8 4 0）、 （13 9 5 1）、（14 10 6 2）、（15 11 7 3）。互连 函数函数分别为PM2+2和PM2-2。 例例3.2 3.2 设设1616个处理器编号分别为个处理器编号分别为0 0、1 1、1515，用单级互，用单级互 连网

33、络连接，当互连函数分别为：（连网络连接，当互连函数分别为：（1 1）Cube3 Cube3 、（、（2 2）PM+3 PM+3 、 （3 3）ShuffleShuffle（ShuffleShuffle）时，第）时，第1313号处理器分别与哪一个处理器号处理器分别与哪一个处理器 相连相连? ? 解：（1）因为Cube3（X3X2X1X0）=X3X2X1X0 所以13 Cube3（1101）=0101 5 （2）因为PM+3 = X + 23 MOD N 所以13 PM+3（13） = 5 （3）因为Shuffle（Shuffle（X3X2X1X0）= Shuffle （X2X1X0X3）= X1

34、X0X3X2 所以13 Shuffle（Shuffle（1101）= Shuffle （1011）= 0111 7 例例3.3 3.3 假设一个互连网络的频宽为假设一个互连网络的频宽为10Mb/s10Mb/s，发送方和接收方，发送方和接收方 开销分别等于开销分别等于230s230s和和270s270s。如果两台机器相距。如果两台机器相距100m100m，现在要，现在要 一台机器发送一个一台机器发送一个10001000字节的消息给另外一台机器，试计算总时字节的消息给另外一台机器，试计算总时 延。如果两台机器相距延。如果两台机器相距1000km1000km，总时延是多少。，总时延是多少。 解：光的

35、速度为299792.5km/s，信号在导体中传输的速度大约是光 速度的50%，从而可计算出飞行时间。 相距100m总时延T=发送方开销+飞行时间+传送时间+接收方开销 = 230s0.1km/(0.5299792.5km/s)(10008)/10Mb/s270s = 1301s 相距1000km总时延T=发送方开销+飞行时间+传送时间+接收方开销 = 230s1000 km/(0.5299792.5km/s)(10008)/10Mb/s270s = 7971s 一、静态互连网络及其类型一、静态互连网络及其类型 二、静态互连网络的结构二、静态互连网络的结构 三、静态互连网络特性比较三、静态互连网

36、络特性比较 第二节第二节 静态互连网络静态互连网络 一、一、静态互连网络及类型静态互连网络及类型 1.1.什么是静态互连网络什么是静态互连网络 静态互连网络是指在各结点间有专用的连接通路，且在运行静态互连网络是指在各结点间有专用的连接通路，且在运行 中不能改变的网络。中不能改变的网络。网络中的每一个开关元件固定地建立结点之网络中的每一个开关元件固定地建立结点之 间的连接，直接实现结点之间的通信。这种网络一旦构成就是固间的连接，直接实现结点之间的通信。这种网络一旦构成就是固 定不变的，比较适合构成通信模式可预测的并行处理系统和分布定不变的，比较适合构成通信模式可预测的并行处理系统和分布 计算机系

37、统。计算机系统。 2.2.静态互连网络的种类静态互连网络的种类 静态互连网络可以用维数来分类，所谓静态互连网络可以用维数来分类，所谓n n维是指将它们画在维是指将它们画在n n维维 空间上各条链路不会相交。一维的静态互连网络有线性阵列结构空间上各条链路不会相交。一维的静态互连网络有线性阵列结构 ；二维的有环形、星形、树形和网格形等；三维的有带弦环形网；二维的有环形、星形、树形和网格形等；三维的有带弦环形网 络、循环移数网络、全连接和立方体网络及其变形等；三维以上络、循环移数网络、全连接和立方体网络及其变形等；三维以上 的有超立方体等。的有超立方体等。 二、静态互连网络的结构静态互连网络的结构

38、1.1.一维网络一维网络 一维网络又称线性阵列，是互连网络中拓扑结构最简单的。一维网络又称线性阵列，是互连网络中拓扑结构最简单的。 它与总线结构是有区别的，总线结构是通过时分切换使多对结它与总线结构是有区别的，总线结构是通过时分切换使多对结 点分时进行通信，而线性阵列允许不同的结点对并发使用系统的点分时进行通信，而线性阵列允许不同的结点对并发使用系统的 不同部分（通道）。不同部分（通道）。 2 2二维网络二维网络 二维网络拓扑结构容易在二维网络拓扑结构容易在VLSIVLSI芯片上实现，且可扩充性比较好，芯片上实现，且可扩充性比较好， 从而得到广泛应用，二维网络主要有四种，即星形、环形、树形从而

39、得到广泛应用，二维网络主要有四种，即星形、环形、树形 和网格形。和网格形。 树形和网格形二维网络会有许多变形。树形和网格形二维网络会有许多变形。 网格形的典型结构是网格形的典型结构是N=rN=rr r格式，网格形的变形主要有环形网格式，网格形的变形主要有环形网 和和IlliacIlliac网。网。 树形二维网络主要形式有完全平衡的二叉树和二叉胖树。树形二维网络主要形式有完全平衡的二叉树和二叉胖树。 （a）网格形网络 （b）环形网格网络 （c）iac网 （a）完全平衡二叉树 （b）二叉胖树 3.3.三维网络三维网络 三维网络的拓扑结构主要有带弦环形网络、循环移数网络、三维网络的拓扑结构主要有带弦

40、环形网络、循环移数网络、 全连接和立方体网络及其变形。全连接和立方体网络及其变形。 度为3的带弦环 度为4的带弦环 循环移数网络 全连接网络 110 000 001 100 101 010011 111 三维方体网络 带环三维方体网络 4. n4. n维网络维网络 r r维网络的典型结构是维网络的典型结构是r r维方体（维方体（r-cuber-cube或或r-CCCr-CCC）网络或超立）网络或超立 方体网络及其变形结构方体网络及其变形结构( (带环超立方体网络带环超立方体网络 ) )。 立方体和超立方体的拓扑网络有一个特性，即相邻结点的二进立方体和超立方体的拓扑网络有一个特性，即相邻结点的二

41、进 制编号仅差一位，而两个结点间的距离正好等于这两个结点二进制编号仅差一位，而两个结点间的距离正好等于这两个结点二进 制编号间不同的位数。制编号间不同的位数。 三、三、静态互连网络特性的比较静态互连网络特性的比较 N N N rr网络，r = 与r = rr网络，r = 网络类型结点度d网络直径D链路数等分宽度B对称性网络规格评注 线性阵列2N-1N-11非N个结点 环形2N/2N2是N个结点 全连接N-11 N(N- 1)/2 (N/2)2是N个结点 二叉树 32(r-1)N-11非树高r=log2N 星形N-12N-1N/2非N个结点 2D网格42(r-1)2N-2rr非 iac网4r-1

42、2N2r非 的带弦环等效 2D环网42r/22N2r是 超立方体rrrN/2N/2是N个结点，r=log2N（维） CCC32r-1+r/23N/2N/(2r)是N=r2r结点，环长r3 一、一、 动态互连网络及其互连形式动态互连网络及其互连形式 二、总线互连网络二、总线互连网络 三、交叉开关互连网络三、交叉开关互连网络 四、多级交叉开关互连网络四、多级交叉开关互连网络 五、五、 动态互连网络特性的比较动态互连网络特性的比较 第三节第三节 动态互连网络动态互连网络 一、一、动态互连网络及其互连形式动态互连网络及其互连形式 动态互连网络可通过设置有源开关，从而根据需要借助控制动态互连网络可通过设

43、置有源开关，从而根据需要借助控制 信号对连接通路加以重新组合，实现所要求的通信模式。动态互信号对连接通路加以重新组合，实现所要求的通信模式。动态互 连网络的形式主要有总线、交叉开关和多级交叉开关等三种类型连网络的形式主要有总线、交叉开关和多级交叉开关等三种类型 。 二、二、总线互连网络总线互连网络 1.1.总线互连网络及其特点总线互连网络及其特点 总线互连网络是指用一组导线和插座将处理机、存储模块和总线互连网络是指用一组导线和插座将处理机、存储模块和 各种外围设备互连起来，实现功能部件间的数据通信。总线被称各种外围设备互连起来，实现功能部件间的数据通信。总线被称 为争用总线或分时总线。主要特点

44、有以下几个方面。为争用总线或分时总线。主要特点有以下几个方面。 （1 1）功能部件间信息传输的带宽低。）功能部件间信息传输的带宽低。 （2 2）计算机组装方便，扩展性好。）计算机组装方便，扩展性好。 （3 3）计算机体系结构简单，成本低。）计算机体系结构简单，成本低。 （4 4）有很多可用的工业标准，如）有很多可用的工业标准，如IEEEIEEE总线标准。总线标准。 2.2.总线互连网络的基本技术总线互连网络的基本技术 总线互连网络的基本技术主要有总线仲裁、中断处理、总线互连网络的基本技术主要有总线仲裁、中断处理、CacheCache 一致性协议和总线事务的处理等。其中总线仲裁最为重要。一致性协

45、议和总线事务的处理等。其中总线仲裁最为重要。 三、三、 交叉开关互连网络交叉开关互连网络 1. 1.交叉开关互连网络及其特点交叉开关互连网络及其特点 交叉开关（交叉开关（CrossbarCrossbar）互连网络是利用一组纵横交错的开关阵）互连网络是利用一组纵横交错的开关阵 列，把各功能部件互连起来，实现功能部件间的数据通信。交叉列，把各功能部件互连起来，实现功能部件间的数据通信。交叉 开关互连网络实际是多总线向总线数量增加方向发展的极端情况，开关互连网络实际是多总线向总线数量增加方向发展的极端情况， 总线数等于全部相连的模块数，从而大大加宽了互连传输频带，总线数等于全部相连的模块数，从而大大

46、加宽了互连传输频带， 提高了系统的效率。交叉开关实际是一种单级的互连网络，采用提高了系统的效率。交叉开关实际是一种单级的互连网络，采用 无阻塞的形式实现输入输出端的连接。无阻塞的形式实现输入输出端的连接。 M1M2 MN P1 PS I/O1 I/OI 2. 2. 结点开关的结构模型 交叉开关中，每一个交叉点都表示一套开关，即结点开关。结交叉开关中，每一个交叉点都表示一套开关，即结点开关。结 点开关不仅要有多路转接逻辑，还要具有处理访问存储器冲突的点开关不仅要有多路转接逻辑，还要具有处理访问存储器冲突的 仲裁硬件，加上总线本身有一定的宽度，使得整个交叉开关阵列仲裁硬件，加上总线本身有一定的宽度

47、，使得整个交叉开关阵列 相当复杂。相当复杂。 多路转换 模块 数据 读写 来自处理机 地址 P1P16 仲裁模块 请求应答1 请求应答2 请求应答16 存 储 器 模 块 数据n 读写2 地址m 控制4 存储器使能 3.3.交叉开关模块交叉开关模块 一个一个a ab b交叉开关模块有交叉开关模块有a a个输入端和个输入端和b b个输出端。理论上个输出端。理论上a a和和 b b不一定相等，但实际上经常选不一定相等，但实际上经常选a=ba=b，且为，且为2 2的整数幂，即：的整数幂，即：a=b=2a=b=2k k， k1k1。常用的为。常用的为2 22 2、4 44 4和和8 88 8开关模块。

48、交叉开关模块的每开关模块。交叉开关模块的每 个输入端可与一个或多个输出端相连，而且容许一对一或一对多个输入端可与一个或多个输出端相连，而且容许一对一或一对多 的连接或映射，但不容许有多对一的连接，因为多个输入端同时的连接或映射，但不容许有多对一的连接，因为多个输入端同时 争用一个输出端的冲突会导致通过这个开关传送信息被阻塞。争用一个输出端的冲突会导致通过这个开关传送信息被阻塞。 只容许一对一映射的只容许一对一映射的n nn n的交叉开关模块，有的交叉开关模块，有n n个输入端和个输入端和n n 个输出端，结点开关数为个输出端，结点开关数为n n2 2，输入端与输出端的合法状态（连接模，输入端与

49、输出端的合法状态（连接模 式）为式）为n nn n，可实现的连接或置换为，可实现的连接或置换为n!n!。例如。例如4 44 4的交叉开关，含有的交叉开关，含有 1616个结点开关，合法的状态个结点开关，合法的状态256256，可实现的连接为，可实现的连接为2424。 四、多级交叉开关互连网络四、多级交叉开关互连网络 1.1.多级交叉开关互连网络的基本概念多级交叉开关互连网络的基本概念 交叉开关互连网络是一种单级的互连网络，输入端的数据经交叉开关互连网络是一种单级的互连网络，输入端的数据经 过一个开关元件就被输出，而交叉开关阵列是非常复杂的。当纵过一个开关元件就被输出，而交叉开关阵列是非常复杂的

50、。当纵 向和横向的总线数都为向和横向的总线数都为n n时，交叉开关阵列的所有交叉点的设备量时，交叉开关阵列的所有交叉点的设备量 是是O(nO(n2 2) )。n n很大时，其成本可能会超过连接的很大时，其成本可能会超过连接的2n 2n 个部件的成本。个部件的成本。 改进的基本思想是：通过采用多个较小规模的交叉开关的改进的基本思想是：通过采用多个较小规模的交叉开关的 “串连串连”和和“并连并连”来构成一个多级交叉开关互连网络，以取代来构成一个多级交叉开关互连网络，以取代 单个的大规模交叉开关。单个的大规模交叉开关。 多级交叉开关互连网络是把重复设置的多套动态单级交叉开多级交叉开关互连网络是把重复

51、设置的多套动态单级交叉开 关网络串并联起来，级间串联的交叉开关之间采用固定的级间连关网络串并联起来，级间串联的交叉开关之间采用固定的级间连 接模式，同级的交叉开关之间相互独立，通过动态控制各级上的接模式，同级的交叉开关之间相互独立，通过动态控制各级上的 交叉开关的结点开关状态来实现多级交叉开关互连网络的输入端交叉开关的结点开关状态来实现多级交叉开关互连网络的输入端 和输出端之间所需的连接。多级交叉开关互连网络简称为多级互和输出端之间所需的连接。多级交叉开关互连网络简称为多级互 连网络。连网络。 2. 2.多级交叉开关互连网络的多级交叉开关互连网络的结构模型结构模型 bn-b bn-1 a a+

52、1 2a-1 0 1 a-1 ab 开关 ab 开关 an-a an-1 ab 开关 ab 开关 ab 开关 ab 开关 ab 开关 ab 开关 ab 开关 I S C 1 I S C 2 I S C n 0 1 b-1 b b+1 2b-1 开关模块开关模块 在多级交叉开关互连网络中一般采用最简单的在多级交叉开关互连网络中一般采用最简单的2 22 2开关模块，开关模块， 2 22 2开关模块有开关模块有4 4种合法的工作状态，即直送、交叉、上播和下播，种合法的工作状态，即直送、交叉、上播和下播， 如图如图3-283-28所示，但它有两种类型。一是只有所示，但它有两种类型。一是只有“直送直送”

53、和和“交叉交叉” 两种工作状态的开关，则称为二功能交叉开关；另一是具有两种工作状态的开关，则称为二功能交叉开关；另一是具有4 4种合种合 法的工作状态的开关，则称为四功能交叉开关。法的工作状态的开关，则称为四功能交叉开关。 0 0 0 000 0 0 1 1 1 111 1 1 级间连接模式级间连接模式 级间连接模式（级间连接模式（ISCISC）是指多级交叉开关互连网络中上一级开）是指多级交叉开关互连网络中上一级开 关模块的输出端和下一级开关模块的输入端相互连接的模式。级关模块的输出端和下一级开关模块的输入端相互连接的模式。级 间连接是固定的，可以用互连函数表示级间连接模式。常用的级间连接是固

54、定的，可以用互连函数表示级间连接模式。常用的级 间连接模式有均匀洗牌、蝶式、多路洗牌、纵横交叉和立方体连间连接模式有均匀洗牌、蝶式、多路洗牌、纵横交叉和立方体连 接等。接等。 控制方式控制方式 为了使各级交叉开关的输入端和输出端建立所需的连接，可为了使各级交叉开关的输入端和输出端建立所需的连接，可 通过控制信号动态控制开关模块的工作状态来实现，即通过对开通过控制信号动态控制开关模块的工作状态来实现，即通过对开 关模块的状态控制来实现对多级互连网络要求实现的互连，这称关模块的状态控制来实现对多级互连网络要求实现的互连，这称 之为互连网络拓扑结构的可动态重构，其控制的方式有之为互连网络拓扑结构的可

55、动态重构，其控制的方式有3 3种。种。 （1 1）级控制。）级控制。 （2 2）组控制。）组控制。 （3 3）单元控制。）单元控制。 3. 3. 多级交叉开关互连网络的种类多级交叉开关互连网络的种类 阻塞网络是指一对以上输入端和输出端可同时实现互连的网阻塞网络是指一对以上输入端和输出端可同时实现互连的网 络中，可能发生两个或两个以上的输入端对输出端的连接要求产络中，可能发生两个或两个以上的输入端对输出端的连接要求产 生路径争用冲突。生路径争用冲突。 可重排非阻塞网络是指如果改变开关状态，一方面重新安排可重排非阻塞网络是指如果改变开关状态，一方面重新安排 现有连接的通路，另一方面为新连接安排通路

56、，满足一个新的端现有连接的通路，另一方面为新连接安排通路，满足一个新的端 点对的连接请求，从而就可实现无阻塞的任意端点对的连接，即点对的连接请求，从而就可实现无阻塞的任意端点对的连接，即 可实现任意的互连函数。可实现任意的互连函数。 非阻塞网络是指不必改变原来的开关状态就可满足任意输入非阻塞网络是指不必改变原来的开关状态就可满足任意输入 端和输出端之间的连接请求。它与可重排非阻塞网是不同的，可端和输出端之间的连接请求。它与可重排非阻塞网是不同的，可 重排非阻塞网要通过改变原来的开关状态来改变连接的路径，才重排非阻塞网要通过改变原来的开关状态来改变连接的路径，才 能满足新的连接请求。因此，非阻塞

57、网是连接能力最强的多级互能满足新的连接请求。因此，非阻塞网是连接能力最强的多级互 连网络。连网络。 特别地所谓互连网络实现了某种互连函数是指该互连函数表特别地所谓互连网络实现了某种互连函数是指该互连函数表 示的连接关系在该互连网络中可同时建立而不会产生路径争用冲示的连接关系在该互连网络中可同时建立而不会产生路径争用冲 突的现象。突的现象。 五、五、动态互连网络特性的比较动态互连网络特性的比较 (log)On (/)()OnO到()()OOn到()()OOn到 ()O 2 ()On(log) k Onn ()O n 2 ()On(log) k Onn 网络特性总线交叉开关多级交叉开关 单位数据传

58、输的最小时延恒定恒定 每台处理机的带宽 连线的复杂性 开关的复杂性 连接特性和寻径性能一次只能一对一全置换，一次一个只要不阻塞，可实 现某些置换和广播 1 1硬件复杂性硬件复杂性 用连线和交换开关表示复杂性。用连线和交换开关表示复杂性。 总线互连的成本最低。连线的复杂性主要由总线设计的数据总线互连的成本最低。连线的复杂性主要由总线设计的数据 通路的宽度和地址线的宽度决定。设通路的宽度和地址线的宽度决定。设为总线上数据通路的宽度，为总线上数据通路的宽度， 总线互连的硬件复杂性随总线互连的硬件复杂性随n n和和两者线性增加，可用函数两者线性增加，可用函数O O（n+n+） 表示。表示。 交叉开关是

59、最昂贵的，因为它的硬件复杂性随交叉开关是最昂贵的，因为它的硬件复杂性随n n2 2的乘积增的乘积增 大。对于相同的数据通路宽度，大。对于相同的数据通路宽度，n nn n交叉开关的价格几乎是总线交叉开关的价格几乎是总线 互连的互连的n n2 2倍。倍。 一个一个n n输入的多级交叉开关，硬件复杂性的函数为输入的多级交叉开关，硬件复杂性的函数为O O （nlognlogk kn n），其中），其中nlognlogk kn n相应于所使用的交叉开关的数目。多级相应于所使用的交叉开关的数目。多级 交叉开关硬件复杂性位于总线和交叉开关网络这两种极端的情况交叉开关硬件复杂性位于总线和交叉开关网络这两种极端

60、的情况 之间。对于相同的通路宽度，可以粗略地估计多级交叉开关价格之间。对于相同的通路宽度，可以粗略地估计多级交叉开关价格 比交叉开关便宜比交叉开关便宜n/logn/logk kn n倍。倍。 2 2每台处理器带宽每台处理器带宽 总线由总线由n n个功能部件分时共享，因此个功能部件分时共享，因此n n个处理器竞争总线带宽。个处理器竞争总线带宽。 假设相同的时钟频率为假设相同的时钟频率为f f，在，在3 3种互连网络中每单位数据传输都仅种互连网络中每单位数据传输都仅 需一个时钟周期，那么总线的每处理器带宽在函数需一个时钟周期，那么总线的每处理器带宽在函数O(f/n)O(f/n)和和 O(f)O(f