并行计算机体系结构第六章课件.ppt

第六章第六章 互互联网网络互互连网网络的作用的作用用来实现计算机系统内部多个处理机或多个功用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着互连网络对整个计算机系统的性能价格比有着决定性的影响。决定性的影响。一个例子：具有本地存储器、私有高速缓存、一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系共享存储器和共享外围设备的一般处理机系统的互连结构统的互连结构磁盘SM1SM2SMmPMNCnPnLMC1P1LMPCNPION磁带打印机终端网络(共享存储器)(共享I/O与外设)互连网络通常是用有向边或无向边连接有限个互连网络通常是用有向边或无向边连接有限个结点的组成。互连网络的主要特性有：结点的组成。互连网络的主要特性有：(1)(1)网络规模：网络中结点的个数网络规模：网络中结点的个数(2)(2)结点度：与结点相连接的边数称为结点度结点度：与结点相连接的边数称为结点度 进入结点的边数叫入度进入结点的边数叫入度 从结点出来的边数则叫出度从结点出来的边数则叫出度(3)(3)距离：两个结点之间相连的最少边数距离：两个结点之间相连的最少边数(4)(4)网络直径：网络中任意两个结点间距离的网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示最大值。用结点间的连接边数表示互互连网网络的特性的特性互互连网网络的性能参数的性能参数发送方的步骤如下：发送方的步骤如下：(1)(1)用户程序把要发送的数据拷贝到系统缓冲区。用户程序把要发送的数据拷贝到系统缓冲区。(2)(2)缓冲区中的数据打包并发送到网络接口部件。缓冲区中的数据打包并发送到网络接口部件。(3)(3)网络接口硬件开始发送消息。网络接口硬件开始发送消息。数据包的接收步骤如下：数据包的接收步骤如下：(1)(1)把数据包从网络接口部件拷贝到系统缓冲区。把数据包从网络接口部件拷贝到系统缓冲区。(2)(2)检查收到的数据包，如果正确，发回答信号。检查收到的数据包，如果正确，发回答信号。(3)(3)把接收到的数据拷贝到用户地址空间。把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区发送方接收到回答信号后释放系统缓冲区互连网络的主要性能参数：互连网络的主要性能参数：(1)频带宽度频带宽度(Bandwidth)：传输信息的最大速率：传输信息的最大速率(2)传输时间传输时间(Transmission time)：等于消息长度除：等于消息长度除以频宽。以频宽。(3)飞行时间飞行时间(Time of flight)：第一位信息到达接收方：第一位信息到达接收方所花费的时间。所花费的时间。(4)传输时延传输时延(Transport latency)：等于飞行时间与传：等于飞行时间与传输时间之和。输时间之和。(5)发送方开销发送方开销(Sender overhead)：处理器把消息放：处理器把消息放到互连网络的时间。到互连网络的时间。(6)接收方开销接收方开销(Receiver overhead)：处理器把消息：处理器把消息从网络取出来的时间。从网络取出来的时间。一个消息的总时延可以用下面公式表示：一个消息的总时延可以用下面公式表示：总时延发送方开销飞行时间总时延发送方开销飞行时间 消息长消息长度度/频宽接收方开销频宽接收方开销例例7.1：假设一个网络的频宽为：假设一个网络的频宽为10Mb/S，发，发送方开销为送方开销为230us，接收方开销分别为，接收方开销分别为270us。如果两台机器相距。如果两台机器相距100米，现在要米，现在要发送一个发送一个1000字节的消息给另一台机器，字节的消息给另一台机器，试计算总时延。如果两台机器相距试计算总时延。如果两台机器相距1000公公里，那么总时延为多大？里，那么总时延为多大？解解：光光的的速速度度为为299792.5KM/S，信信号号在在导导体体中中传递速度大约是光速的传递速度大约是光速的50。相距相距100米时总时延为：米时总时延为：相距相距1000公里时的总时延为：公里时的总时延为：为了在输入结点与输出结点之间建立对应为了在输入结点与输出结点之间建立对应关系，互连网络有三种表示方法：关系，互连网络有三种表示方法：(1)互连函数表示法：互连函数表示法：如：如：f(xn-1x1x0)=x0 xn-2x1xn-1(2)图形表示法图形表示法(3)输入输出对应表示法输入输出对应表示法互连网络0011n-1n-1输入:0 1 2 3 4 5 6 7输出:1 0 3 2 5 4 7 6互互连网网络的表示方法的表示方法互互连函数函数互连函数也称为互连置换或互连排列等。1.交换函数（交换函数（Exchange）当n3时，有3种函数，每种能表示8个结点之间的连接关系。由于交换函数主要用于超超立立方方体体互互连连网网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。2.2.全混洗函数（全混洗函数（Perfect shufflePerfect shuffle）函数关系：把二进制结点号循环左移一位函数关系：把二进制结点号循环左移一位子混洗子混洗(subshuffle)S(subshuffle)S(k)(k),最低最低k k位循环左移一位位循环左移一位 超混洗超混洗(supershuffle)S(supershuffle)S(k)(k),最高最高k k位循环左移一位位循环左移一位 3.蝶式函数（蝶式函数（Butterfly）蝶蝶式式函函数数的的名名称称来来自自于于FFT变变换换时时的的图图形形，如如蝴蝴蝶式样。函数关系：蝶式样。函数关系：将将输输入入端端二二进进制制结结点点号号的最高位和最低位互换位置。的最高位和最低位互换位置。子蝶式子蝶式(subbutterfly)B(k)最低最低k位的位的高低位互换高低位互换超蝶式超蝶式(superbutterfly)B(k)最高最高k位的位的高低互换高低互换 显然成立：显然成立：4.反位序函数（反位序函数（Bit Reversal）函数关系：将二进制自变量的位序反过来。函数关系：将二进制自变量的位序反过来。子反位序函数，子反位序函数，最低最低k位的位的位序反过来位序反过来超反位序函数，超反位序函数，最高最高k位的位的位序反过来位序反过来5.移数函数移数函数函数关系：将输入端向量循环移动一定的位置函数关系：将输入端向量循环移动一定的位置经经常常取取r2 2i i，因因此此移移数数函函数数又又称称为为加加减减2i函函数数、PM2I函数等。函数等。子移数函数：子移数函数：其中：其中：0 x N-1，0 i,k n-1，n=log2N。Illiac函数包含函数包含PM2 0和和PM2 n/2等等4个互连函数个互连函数 每个接点与它的上下左右每个接点与它的上下左右4个相邻接点连接个相邻接点连接例例6.2：假假设设16个个处处理理机机的的编编号号分分别别为为0、1、15，采采用用单单级级互互连连网网络络。互互连连函函数数分分别别为：为：(1)Cube3 (2)PM2+3 (3)PM2-0 (4)Shuffle (5)Butterfly (6)Reversal 第第12号处理机分别与哪一个处理机相连？号处理机分别与哪一个处理机相连？解：解：(12)10=(1100)2 (1)Cube3，(2)PM2+3，(3)PM2-0，(4)Shuffle，(5)Butterfly，(6)Reversal 1100最高位取反得最高位取反得0100，4号处理机号处理机 (12+8)MOD 16=4，4号处理机号处理机 12 1=11，11号处理机号处理机 1100循环左移循环左移1位得到位得到1001,9号处理机号处理机 1100的最高最低位交换的最高最低位交换0101,5号处理机号处理机 1100的位序反过来为的位序反过来为0011,3号处理机号处理机 补充补充:基本的单级互连网络基本的单级互连网络1.立方体单级网络立方体单级网络立立方方体体的的每每个个顶顶点点代代表表一一个个结结点点，结结点点的的编编号号用用二二进制码（进制码（C2C1C0）表示。）表示。N8的三维立方体结构 立立方方体体单单级级网网络络的的互互连连函函数数实实现现二二进进制制编编号号中中第第k位位值值不不同同的的结结点点之之间间的的连连接接。故故三三维维的的立立方方体体单单级级网网络络有有三三种种互互连连函函数数：Cube0、Cube1和和Cube2，分分别别建建立立结结点点编编号号中中C0不不同同或或C1不不同同或或C2不不同同的的结结点点之之间间的的连结。连结。N8的三维立方体三种互连方式的三维立方体三种互连方式一般情况下，一个一般情况下，一个n维立方体有维立方体有N2n个结个结点，共有点，共有n种互连函数，分别由种互连函数，分别由n位编号中的每位编号中的每一位的位值求反来确定。当维数一位的位值求反来确定。当维数n3时，称为时，称为超立方体超立方体(Hyper Cube)网络。对于网络。对于n维立方体维立方体单级网络，要实现任意两个结点之间的连接，单级网络，要实现任意两个结点之间的连接，最多需使用最多需使用n次不同的互连函数次不同的互连函数 因此因此n维立方维立方体单级网络的最大距离为体单级网络的最大距离为n。2PM2I（是加减（是加减2i的简称，的简称，plusminus2i）PM2I单级网络能实现单级网络能实现j号结点与号结点与j2i mod N号结点号结点的直接相连，的直接相连，N为处理器的个数，为处理器的个数，nlog2N。因此，它。因此，它共有共有2n个互连函数，即个互连函数，即PM2i（j）j2i mod NPM2i（j）j2i mod N式中，式中，0jN1，0in1。设设N8，则各互连循环为，则各互连循环为PM20：（：（01234567）PM20：（：（76543210）PM21：（：（0246）（）（1357）PM21：（：（6420）（）（7531）PM22：（：（04）（）（15）（）（26）（）（37）N8的的PM2I互连网络的部分连接图互连网络的部分连接图 网网络络的的最最大大距距离离为为 n/2 =log2N/2 ，这这里里 表表示示向向上上取取整整。由由三三维维PM2I互互连连网网络络可可以以看看出出，最最多多只要两次使用，即可实现任意一对入出端号间的连接。只要两次使用，即可实现任意一对入出端号间的连接。PM2I互连特性互连特性3.3.混洗交换混洗交换(shuffle exchange)(shuffle exchange)混洗交换互连网络包含全混洗和交换两种互连函数。混洗交换互连网络包含全混洗和交换两种互连函数。（1 1）全混洗）全混洗全混洗的互连函数为全混洗的互连函数为ShuffleShuffle（P Pn n1 1P Pn n2 2PP1 1P P0 0）P Pn n2 2PP1 1P P0 0P Pn n1 1 全混洗互连示意图全混洗互连示意图（2）交换）交换由于单一的全混洗互连网络不能实现二进制编号为全由于单一的全混洗互连网络不能实现二进制编号为全“0”和全和全“1”的结点与其他任何结点的连接，所以又增加了的结点与其他任何结点的连接，所以又增加了Cube0交换互连函数。同时采用了全混洗和交换的单级互连网络称为混交换互连函数。同时采用了全混洗和交换的单级互连网络称为混洗交换单级互连网络。洗交换单级互连网络。N8的全混交换互连网络连接图的全混交换互连网络连接图 在在混混洗洗交交换换网网络络中中，最最远远的的两两个个入入出出端端号号是是全全“0”和和全全“1”，它们的连接需要，它们的连接需要n次交换和次交换和n-1次混洗，所以其最大距离为次混洗，所以其最大距离为2n-1。互互连网网络的种的种类静静态互互连网网络 循循环互互连网网络多多级互互连网网络静静态态互互连连网网络络：在在各各结结点点之之间间有有固固定定的的连连接接通通路路，在在运运行行过过程程中中不不能能改改变变。一一般般不不能能实实现现任任意意结结点点到到结结点点之之间的互连。间的互连。循环互连网络：通过多次重复使用同一个单级互连网络循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连以实现任意结点到结点之间的互连。多级互连网络：将多套相同的单级互连网络连接起来，多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连，是动态互连网络的实现任意结点到结点之间的互连，是动态互连网络的一种，适用于一种，适用于SIMD和和MIMD。静静态互互连网网络 在各结点之间有固定的连接通路，在运行过程中不能在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。改变的网络结构。一般静态互连网络不能实现任意结点到结点之间的互连。一般静态互连网络不能实现任意结点到结点之间的互连。一维的有线性阵列结构；二维的有环形、星形、树形、一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方网格形等；三维的有立方体等；三维以上的有超立方体等。体等。循循环互互连网网络一般静态互连网不能实现任意两结点之间的互连。一般静态互连网不能实现任意两结点之间的互连。有两种解决办法：有两种解决办法：循环互连网：多次重复使用同一个单级互连网络循环互连网：多次重复使用同一个单级互连网络多级互连网：将多套相同的单级互连网络连接起来多级互连网：将多套相同的单级互连网络连接起来前一种方法是牺牲时间换取设备，后一种方法是以前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间。设备换取时间。多多级互互连网网络 多级网络互连是将多套单级互连网络通过关模块多级网络互连是将多套单级互连网络通过关模块串连扩展成多级互连网络（简称串连扩展成多级互连网络（简称MINMIN）的方式。与单）的方式。与单级网络相比，多级网络可以通过改变开关的控制方式级网络相比，多级网络可以通过改变开关的控制方式灵活地实现各种连接，满足系统应用的需要灵活地实现各种连接，满足系统应用的需要 。多级互连网络采用多个相同的或不同的单级互连多级互连网络采用多个相同的或不同的单级互连网络直接连接起来。一个时钟周期就能够实现任意结网络直接连接起来。一个时钟周期就能够实现任意结点到结点之间的互连。点到结点之间的互连。常见的有多级立方体互连网络、多级混洗交换网常见的有多级立方体互连网络、多级混洗交换网络（络（OmegaOmega网络）、多级网络）、多级PM2IPM2I网络、多级网络、多级BENESBENES可重排可重排网络及多级网络及多级CLOSCLOS网络等。网络等。多级互连网络采用的关键技术：多级互连网络采用的关键技术：(1)(1)交换开关，交换开关，(2)(2)交换开关之间的拓扑连接，交换开关之间的拓扑连接，(3)(3)对交换开关的不同控制方式。对交换开关的不同控制方式。1.1.交换开关交换开关一个一个abab交换开关有交换开关有a a个输入和个输入和b b个输出。最常用的二个输出。最常用的二元开关：元开关：a=b=2a=b=2。每个输入可与一个或多个输出相连，但是在输出端必每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为交只容许一对一映射时称为置换连接，称这种开关为交叉开关。叉开关。具具有有直直通通和和交交换换两两种种功功能能的的开开关关称称为为二二功功能能开开关关，或或交换开关。用一位控制信号控制。交换开关。用一位控制信号控制。具具有有所所有有4 4种种功功能能的的交交换换开开关关称称为为四四功功能能开开关关，用用两两位控制信号控制。位控制信号控制。交换开关的四种功能交换开关的四种功能2.2.拓扑结构拓扑结构 又称为级间连接模式又称为级间连接模式ISC(interstage ISC(interstage connection)connection)，是前一级交换开关的输出端与后一级，是前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。交换开关的输入端之间的连接模式称为拓扑结构。级间连接是固定的，可以用互连函数表示级间连级间连接是固定的，可以用互连函数表示级间连接模式。常用的级间连接模式包括混洗、交叉、立方接模式。常用的级间连接模式包括混洗、交叉、立方体连接等，从而构成具有不同连接特性的多级互连网体连接等，从而构成具有不同连接特性的多级互连网络。络。3.控制方式控制方式 控控制制方方式式是是指指通通过过对对开开关关模模块块的的状状态态控控制制来来实实现现多多级级网网络络间间互互连连要要求求的的方方式式，称称之之为为互互连连网网络络拓拓扑扑结结构构可可动动态态重重构构。有有多多级级交交换换开开关关，每每一一级级又又有有多多个个交交换开关。换开关。通常有三种控制方式通常有三种控制方式级控制：同一级交换开关使用同一个控制信号控制。级控制：同一级交换开关使用同一个控制信号控制。单元级控制：每个交换开关分别控制。单元级控制：每个交换开关分别控制。部部分分级级控控制制：第第i级级使使用用i+1个个控控制制信信号号控控制制（0 i n-1）。）。同同一一个个多多级级互互连连网网络络分分别别常常用用三三种种不不同同的的控控制制方方式式，可可以构成三种不同的互连网络。以构成三种不同的互连网络。4.4.多级立方体网络多级立方体网络 是将是将Cube0Cube0、Cube1Cube1和和Cube2Cube2三种函数构成的单级网络串接三种函数构成的单级网络串接起来，是一种起来，是一种STARANSTARAN网络。使用二功能交换开关，即直通和网络。使用二功能交换开关，即直通和交换，分级控制，可实现交换网络功能。采用不同方式控制，交换，分级控制，可实现交换网络功能。采用不同方式控制，可实现不同连通功能。即当第可实现不同连通功能。即当第i i级控制信号为级控制信号为0 0时，开关直通；时，开关直通；若控制信号为若控制信号为1 1，则开关交换，实现，则开关交换，实现CubeiCubei的功能。若采用部的功能。若采用部分级控，则实现移数网络功能，若采用单元控制，则是间接分级控，则实现移数网络功能，若采用单元控制，则是间接二进制二进制n n方体网络。方体网络。N N8 8立方体多级互连网络立方体多级互连网络级级控制信号（控制信号（K2K1K0）000001010011100101110111入入端端号号012345670123456710325476230167453210765445670123547610326745230176543210执执行行的的交交换换函函数数功功能能恒等恒等四四组组二元二元四四组组二元二元二二组组四元四元二二组组四元四元二二组组四元四元一一组组八元八元四四组组二元二元二二组组四元四元一一组组八元八元四四组组二元二元一一组组八元八元一一组组八元八元iCube0Cube1Cube0Cube1Cube2Cube0Cube2Cube1Cube2Cube0Cube1Cube2三级STARAN交换网络（N8）级控制信号的组合及所实现的功能5.5.多级混洗交换网络多级混洗交换网络 又称为又称为OMEGAOMEGA网络，由网络，由n n级相同的网络组成，各级相同的网络组成，各级包含一个全混洗拓扑和一列四功能的交换开关，级包含一个全混洗拓扑和一列四功能的交换开关，采用单元控制方式。对于一个采用单元控制方式。对于一个N=2N=2n n个输入输出端的个输入输出端的OMEGAOMEGA网络，共需要网络，共需要n n级级2222开关，每一级包含开关，每一级包含N/2N/2个采用单元控制的四功能交换开关。个采用单元控制的四功能交换开关。N N8 8多级混洗交换网络多级混洗交换网络6.6.多级多级PM2IPM2I网络网络 包含包含n n级单元连接，每一级都是把前后两列各级单元连接，每一级都是把前后两列各N N2 2 n n个单元按个单元按PM2IPM2I拓扑相互连接起来的。对于第拓扑相互连接起来的。对于第i i级级 (0in-1),(0in-1),每一个输入端每一个输入端j j都有三条输出线与之连都有三条输出线与之连接，即接，即j j、(j+2(j+2i i)mod N)mod N和和(j-2(j-2i i)mod N)mod N，也就是通，也就是通过交换开关选择直通、上播和下播。过交换开关选择直通、上播和下播。三级三级PM2IPM2I网络中第网络中第0 0级完成的是级完成的是PM2IPM2I00的函数功的函数功能，第能，第1 1级完成的是级完成的是PM2IPM2I11的函数功能，第的函数功能，第2 2级完成级完成的是的是PM2IPM2I22的函数功能。的函数功能。系系统互互连结构构系统互连结构：计算机子系统互连在一起或构系统互连结构：计算机子系统互连在一起或构造多处理机或多计算机的静态和动态网络。造多处理机或多计算机的静态和动态网络。我们先介绍组成网络的拓扑结构，再讨论互连我们先介绍组成网络的拓扑结构，再讨论互连网络的通信特性（时延、等分带宽、数据寻径网络的通信特性（时延、等分带宽、数据寻径功能）。功能）。网路的通信效率对并行计算机的性能十分重要。网路的通信效率对并行计算机的性能十分重要。网络数据传送率高、时延低、通信频带宽。网络数据传送率高、时延低、通信频带宽。网网络特性和特性和寻径功能径功能互连网络的拓扑可以采用静态或动态结构。互连网络的拓扑可以采用静态或动态结构。静态网路由点静态网路由点-点直接相连而成，这种连接方点直接相连而成，这种连接方式在程序执行过程中不会改变。动态网路是式在程序执行过程中不会改变。动态网路是用开关通道实现的，它可以动态改变结构，用开关通道实现的，它可以动态改变结构，使之与用户程序中的通信要求匹配使之与用户程序中的通信要求匹配网网络特性和特性和寻径功能径功能静态网络常用来实现集中式系统的子系统之静态网络常用来实现集中式系统的子系统之间或分布式系统的多个计算结点之间的固定间或分布式系统的多个计算结点之间的固定连接。连接。动态网络包括总线、交叉开关和多级网络，动态网络包括总线、交叉开关和多级网络，常用于共享存储型多处理机中。常用于共享存储型多处理机中。网网络特性和特性和寻径功能径功能网路是用有向边或无向边连接有限个结点的图表网路是用有向边或无向边连接有限个结点的图表示的。图中结点的数量成为网络规模示的。图中结点的数量成为网络规模结点度：与结点相连接的边的数量。入度、出度。结点度：与结点相连接的边的数量。入度、出度。网路直径：网络中任意两个结点之间最短路径的网路直径：网络中任意两个结点之间最短路径的最大值。网络直径的度量：链路数。网络直径应最大值。网络直径的度量：链路数。网络直径应该尽可能小该尽可能小网网络特性和特性和寻径功能径功能等分带宽：网络被切成相等的两部分，沿切口的等分带宽：网络被切成相等的两部分，沿切口的最小边数成为通道等分宽度。通信网络中，每条最小边数成为通道等分宽度。通信网络中，每条边相当于一条线宽为边相当于一条线宽为w位的通道。线等分宽度位的通道。线等分宽度B=b*w。B反映了网络的布线密度。等分带宽反反映了网络的布线密度。等分带宽反映沿等分网络最大通信带宽。映沿等分网络最大通信带宽。结点之间的线长：影响信号的时延结点之间的线长：影响信号的时延网网络特性和特性和寻径功能径功能数据寻径功能：数据寻径网络用来进行数据寻径功能：数据寻径网络用来进行PE间数间数据交换。寻径网路可以是动态的，也可以是静态据交换。寻径网路可以是动态的，也可以是静态的。的。寻径网络的功能强大，有利于减少数据交换所需寻径网络的功能强大，有利于减少数据交换所需要的时间，能够显著改善系统性能。要的时间，能够显著改善系统性能。常见的寻径功能：移数、循环、置换、广播、选常见的寻径功能：移数、循环、置换、广播、选播、洗牌、交换等播、洗牌、交换等网网络特性和特性和寻径功能径功能置换：对置换：对n个对象来说，有个对象来说，有n！种置换，！种置换，n个对象个对象可以按照置换排序。可以按照置换排序。=(a,b,c)(d,e)。循环。循环(a,b,c)的周期为的周期为3，(d,e)的周期为的周期为2。则。则的周期为的周期为6网网络特性和特性和寻径功能径功能均匀洗牌和交换均匀洗牌和交换:均匀洗牌是为平行处理应用提均匀洗牌是为平行处理应用提出的一种特殊置换功能。出的一种特殊置换功能。均匀洗牌均匀洗牌逆均匀洗牌逆均匀洗牌网网络特性和特性和寻径功能径功能超立方体寻径功能超立方体寻径功能网网络特性和特性和寻径功能径功能广播是一种一对全体的映射广播是一种一对全体的映射 选播是一种一个子集到另一个子集的映射。选播是一种一个子集到另一个子集的映射。个人广播：只将个人信息传送给选定的接收者。个人广播：只将个人信息传送给选定的接收者。网网络特性和特性和寻径功能径功能网络性能：网络性能：功能特性功能特性网络如何支持数据寻径、中断处理等网络如何支持数据寻径、中断处理等网络时延网络时延单位消息通过网络传送时最坏情况下的单位消息通过网络传送时最坏情况下的时间延迟时间延迟带宽带宽通过网络的最大数据传输率通过网络的最大数据传输率硬件复杂性硬件复杂性硬件造价（导线、开关硬件造价（导线、开关静静态连接网接网络线性阵列：内部结点度线性阵列：内部结点度2，外部，外部1。直径为。直径为N-1，等分宽度，等分宽度b=1静静态连接网接网络线性阵列：内部结点度线性阵列：内部结点度2，外部，外部1。直径为。直径为N-1，等分宽度，等分宽度b=1。当当n很大时，通信很大时，通信效率很低。效率很低。N=2，线性阵列经济，线性阵列经济线性阵列可以由多个线性阵列可以由多个结点并发使用线路结点并发使用线路不同部分。总线不行不同部分。总线不行静静态连接网接网络环和带弦环：结点度环和带弦环：结点度2。单向环直径为。单向环直径为N，双，双向环直径为向环直径为N/2。静静态连接网接网络带弦环：增加的链路越多，节点度越高，网带弦环：增加的链路越多，节点度越高，网络直径越小。络直径越小。静静态连接网接网络循环移数网络：将环上每个结点到与其距离循环移数网络：将环上每个结点到与其距离为为2整数幂的结点之间增加一条附加链构成的整数幂的结点之间增加一条附加链构成的设网络规模N=2n结点度d=2n-1直径D=n/2静静态连接网接网络树形和星形树形和星形结点度结点度=3直径直径2（k-1）其中规模其中规模N=2k-1胖树是对二叉树的改进，胖树是对二叉树的改进，通向根节点的瓶颈问题通向根节点的瓶颈问题静静态连接网接网络网格型和环形网格型和环形 静静态连接网接网络超立方体：超立方体：n-立方体结点度等于立方体结点度等于n，网络直径，网络直径等于等于n。静静态连接网接网络超立方体：超立方体：n-立方体结点度等于立方体结点度等于n，网络直径，网络直径等于等于n。静静态连接网接网络带环立方体：带环立方体：k-带环立方体直径为带环立方体直径为2k。结点度数为结点度数为3，与维数无关，与维数无关静静态连接网接网络网络吞吐量：网络吞吐量：单位时间内网络能处理的总信息量。可以用单位时间内网络能处理的总信息量。可以用网络通量来衡量，也就是网络中能同时容纳网络通量来衡量，也就是网络中能同时容纳的信息总量。网络的最大吞吐量是容量的一的信息总量。网络的最大吞吐量是容量的一部分部分动态连接网接网络为了得到多用或通用的目的，需要采用动为了得到多用或通用的目的，需要采用动态链接网络、它能够根据程序要求实现通态链接网络、它能够根据程序要求实现通信模式，不用固定连接，而是沿着连接通信模式，不用固定连接，而是沿着连接通路使用开关或国际网络以进行节点之间的路使用开关或国际网络以进行节点之间的动态连接。动态连接。动态连接网接网络 1.动态互连网络的三个主要操作特征 定时 开关 控制2.根据级间连结方式，动态互连网络分为(1)单级网络 也称循环网络 (2)多级网络 由一级以上的开关元件构成。这类网络可以把任一输入与任一输出相连。阻塞网络阻塞网络 如果同时连接多个输入输出对时如果同时连接多个输入输出对时,可能会引可能会引 起开关和通信链路使用上的冲突。起开关和通信链路使用上的冲突。大多数多级网络都是阻塞网络。大多数多级网络都是阻塞网络。非阻塞网络非阻塞网络 如果多级网络通过重新安排连接方式可以如果多级网络通过重新安排连接方式可以 建立所有可能的输入输出之间的连接。建立所有可能的输入输出之间的连接。动态连接网接网络数字总线：一组导线和插座用于处理与总线数字总线：一组导线和插座用于处理与总线相连的处理机、存储模块和外围设备间的数相连的处理机、存储模块和外围设备间的数据业务。据业务。总线主设备、从设备、争用总线主设备、从设备、争用动态连接网接网络开关模块：开关状态直送、交叉，上翻、下翻开关模块：开关状态直送、交叉，上翻、下翻动态连接网接网络开关模块和合法状态开关模块和合法状态Module SizeLegitimate StatesPermutation Connection动态连接网接网络多级网络：多级网络：网络。注意构成方法。网络。注意构成方法。级数：级数：log2n每级每级n/2个开关个开关动态连接网接网络多级网络：多级网络：基准基准网络。注意构成方法。网络。注意构成方法。动态连接网接网络多级网络：多级网络：交叉开关网络交叉开关网络三种三种动态网网络比比较总线造价最低，但是每台处理机可用的带宽较总线造价最低，但是每台处理机可用的带宽较窄。总线容易产生故障。窄。总线容易产生故障。交叉开关的硬件复杂性成交叉开关的硬件复杂性成n2上升，造价昂贵。上升，造价昂贵。但是交叉开关的带宽和寻径性能最好。对于小但是交叉开关的带宽和寻径性能最好。对于小规模网络，是理想选择规模网络，是理想选择多级网络是两个极端的折中。采用模块结构，多级网络是两个极端的折中。采用模块结构，可扩展性好。但是时延随网络级数可扩展性好。但是时延随网络级数logn上升上升互互连网网络切切换技技术