计算机系统结构-第六章(互连网络)PPT课件.ppt

幻灯片 1/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络w基本概念基本概念w互连网络种类互连网络种类w消息传递机制消息传递机制幻灯片 2/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系基本概念本章内容w互连网络的作用互连网络的作用w互连网络的表示互连网络的表示w常用互连函数常用互连函数w互连网络的特性互连网络的特性w传输性能参数传输性能参数幻灯片 3/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的作用本章内容基本概念 互连网络是一种由互连网络是一种由开关元件开关元件按照一定的按照一定的拓扑结构拓扑结构和和控制方式控制方式构成的网络，构成的网络，用于实现用于实现计算机系统内部多个处理机或多个功能部件计算机系统内部多个处理机或多个功能部件之间的相互连接之间的相互连接。互连网络已成为并行处理。互连网络已成为并行处理系统的核心组成部分。系统的核心组成部分。互连网络对整个计算互连网络对整个计算机系统的性能价格比有着决定性的影响机系统的性能价格比有着决定性的影响。3 之 1幻灯片 4/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系举例说明(多处理机)本章内容基本概念3 之 2磁盘磁盘SM1SM2SMmIPMNIPMNCnPnLMC1P1LMIPCNIPCNP PI IOON N磁带磁带打印机打印机终端终端网络网络(共享存储器共享存储器)(共享共享I/O与外设与外设)SM:SM:共享存储器共享存储器LM:LM:本地存储器本地存储器 P :P :处理机处理机C :C :高速缓存高速缓存IPMNIPMN：内部处理内部处理机机-存储器网络存储器网络 IPCNIPCN：内部处理内部处理机间通信网络机间通信网络PIONPION：处理机处理机-输输入输出间网络入输出间网络 幻灯片 5/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系本章内容基本概念3 之 3基本模型幻灯片 6/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的表示本章内容基本概念 为了在输入结点与输出结点之间建立对应关系，互连为了在输入结点与输出结点之间建立对应关系，互连网络有两种表示方法：网络有两种表示方法：w w 互连函数表示法互连函数表示法互连函数表示法互连函数表示法 自变量和函数常用二进制表示。自变量和函数常用二进制表示。例如：例如：f(xn-1x1x0)=x0 xn-2x1xn-1。w w 输入输出对应表示法输入输出对应表示法输入输出对应表示法输入输出对应表示法互连互连网络网络0011n-1n-1输入输入:0 1 2 3 4 5 6 7输出输出:0 4 2 6 1 5 3 7 输入输入:0 1 2 .n 输出输出:f(0)f(1)f(2).f(n)幻灯片 7/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系常用互连函数w恒等置换恒等置换w交换置换交换置换w方体置换方体置换w均匀洗牌置换均匀洗牌置换w蝶式置换蝶式置换w位序颠倒置换位序颠倒置换w移数置换移数置换w加减加减2i置换置换本章内容基本概念幻灯片 8/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系恒等置换I(xn-1xn-2.x1x0)=xn-1xn-2.x1x00 01 12 23 34 45 56 67 7本章内容基本概念常用互连函数N=8 的恒等置换幻灯片 9/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系交换置换E(xn-1xn-2.x1x0)=xn-1xn-2.x1x00 01 12 23 34 45 56 67 7本章内容基本概念常用互连函数N=8 的交换置换幻灯片 10/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系方体置换 互连函数Ck(xn-1xn-2.xk.x1x0)=xn-1xn-2.xk.x1x0例如：当例如：当N=8时，有时，有3种函数，每种能表示种函数，每种能表示8个结点之间的连接关系。个结点之间的连接关系。C2(x2x1x0)=x2x1x0 C1(x2x1x0)=x2x1x0C0(x2x1x0)=x2x1x0 C0就是交换置换。就是交换置换。本章内容基本概念常用互连函数3 之 1幻灯片 11/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系方体置换 图示（N=8）0000001 111112 222223 333334 444445 555556 666667 77777C0方体置换方体置换 C1方体置换方体置换 C2方体置换方体置换本章内容基本概念常用互连函数3 之 2幻灯片 12/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系方体置换 提示 由于方体置换函数主要用于超立方体互连网由于方体置换函数主要用于超立方体互连网中，因此也称为中，因此也称为超立方体函数超立方体函数超立方体函数超立方体函数，用，用Cube表示，如：表示，如：Cube0、Cube1、Cube2等。等。本章内容基本概念常用互连函数3 之 3zyx010011110111000001101100 CubeCube0 0=(b=(b2 2b b1 1b b0 0)CubeCube1 1=(b=(b2 2b b1 1b b0 0)CubeCube2 2=(b=(b2 2b b1 1b b0 0)001幻灯片 13/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换 互连函数本章内容基本概念常用互连函数w 均匀洗牌均匀洗牌均匀洗牌均匀洗牌(shuffle:(shuffle:循环左移一位循环左移一位循环左移一位循环左移一位)(x xn-1n-1x xn-2n-2.x.xk k.x.x1 1x x0 0)=)=x xn-2n-2.x.xk k.x.x1 1x x0 0 x xn-1n-1w 子洗牌子洗牌子洗牌子洗牌(subshuffle:(subshuffle:最低最低最低最低k k位循环左移一位位循环左移一位位循环左移一位位循环左移一位)(k)(k)(x(xn-1n-1x xn-2n-2.x.xk kx xk-1k-1x xk-2k-2.x.x1 1x x0 0)=)=x xn-1n-1x xn-2n-2.x.xk kx xk-2k-2.x.x1 1x x0 0 x xk-1k-1w 超洗牌超洗牌超洗牌超洗牌(supershuffle:(supershuffle:最高最高最高最高k k位循环左移一位位循环左移一位位循环左移一位位循环左移一位)(k)(k)(x xn-1n-1x xn-2n-2.x.xn-kn-kx xn-k-1n-k-1.x.x1 1x x0 0)=)=x xn-2n-2.x.xn-kn-kx xn-1n-1x xn-k-1n-k-1.x.x1 1x x0 04 之 1幻灯片 14/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换 图示（N=8）本章内容基本概念常用互连函数4 之 20000001 111112 222223 333334 444445 555556 666667 77777均匀洗牌均匀洗牌 子洗牌子洗牌(2)超洗牌超洗牌(2)幻灯片 15/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换 提示本章内容基本概念常用互连函数4 之 3w三种置换之间的关系三种置换之间的关系w逆洗牌逆洗牌（二进制结点号循环右移一位）（二进制结点号循环右移一位）-1(xn-1xn-2.x1x0)=x0 xn-1xn-2.x1幻灯片 16/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系均匀洗牌置换 应用 均匀洗牌与逆均匀洗牌是两个十分有用均匀洗牌与逆均匀洗牌是两个十分有用的互连函数，以它们代表的链路与以交换置的互连函数，以它们代表的链路与以交换置换代表的开关多级组合起来可构成换代表的开关多级组合起来可构成Omega（）网络网络与与逆逆Omega（）网络网络。函数在实现多项式求值、矩阵转置和函数在实现多项式求值、矩阵转置和FFT等并行运算以及并行排序等方面都得到广泛等并行运算以及并行排序等方面都得到广泛的应用。的应用。本章内容基本概念常用互连函数4 之 4幻灯片 17/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系蝶式置换 互连函数本章内容基本概念常用互连函数3 之 1w 蝶式蝶式蝶式蝶式(butterfly:(butterfly:高低位互换高低位互换高低位互换高低位互换)(x xn-1n-1x xn-2n-2.x.xk k.x.x1 1x x0 0)=)=x x0 0 x xn-2n-2.x.xk k.x.x1 1x xn-1n-1w 子蝶式子蝶式子蝶式子蝶式(subbutterfly:(subbutterfly:最低最低最低最低k k位高低位互换位高低位互换位高低位互换位高低位互换)(k)(k)(x(xn-1n-1x xn-2n-2.x.xk kx xk-1k-1x xk-2k-2.x.x1 1x x0 0)=)=x xn-1n-1x xn-2n-2.x.xk kx x0 0 x xk-2k-2.x.x1 1x xk-1k-1w 超蝶式超蝶式超蝶式超蝶式(superbutterfly:(superbutterfly:最高最高最高最高k k位高低位互换位高低位互换位高低位互换位高低位互换)(k)(k)(x xn-1n-1x xn-2n-2.x.xn-k+1n-k+1x xn-kn-kx xn-k-1n-k-1.x.x1 1x x0 0)=)=x xn-kn-kx xn-2n-2.x.xn-k+1n-k+1x xn-1n-1x xn-k-1n-k-1.x.x1 1x x0 0幻灯片 18/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系蝶式置换 图示（N=8）本章内容基本概念常用互连函数0000001 111112 222223 333334 444445 555556 666667 77777 蝶式蝶式子蝶式子蝶式(2)(2)超蝶式超蝶式(2)(2)3 之 2幻灯片 19/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系蝶式置换 提示本章内容基本概念常用互连函数3 之 3w 三种置换之间的关系三种置换之间的关系w 应用应用 蝶式与子蝶式置换和交换置换多级组合可蝶式与子蝶式置换和交换置换多级组合可作为构成方体多级网络的基础。作为构成方体多级网络的基础。幻灯片 20/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系位序颠倒置换 互连函数本章内容基本概念常用互连函数w 位序颠倒置换位序颠倒置换位序颠倒置换位序颠倒置换（Bit Reversal:Bit Reversal:位序颠倒）位序颠倒）位序颠倒）位序颠倒）(x(xn-1n-1x xn-2n-2.x.xk k.x.x1 1x x0 0)=x)=x0 0 x x1 1.x.xk k.x.xn-2n-2x xn-1n-1w 子位序颠倒置换子位序颠倒置换子位序颠倒置换子位序颠倒置换（最低（最低（最低（最低k k位的位序颠倒）位的位序颠倒）位的位序颠倒）位的位序颠倒）(k)(k)(x(xn-1n-1x xn-2n-2.x.xk kx xk-1k-1x xk-2k-2.x.x1 1x x0 0)=)=x xn-1n-1x xn-2n-2.x.xk kx x0 0 x x1 1.x.xk-2k-2x xk-1k-1w 超位序颠倒置换超位序颠倒置换超位序颠倒置换超位序颠倒置换（最高（最高（最高（最高k k位的位序颠倒）位的位序颠倒）位的位序颠倒）位的位序颠倒）(k)(k)(x xn-1n-1x xn-2n-2.x.xn-k+1n-k+1x xn-kn-kx xn-k-1n-k-1.x.x1 1x x0 0)=)=x xn-kn-kx xn-k+1n-k+1.x.xn-2n-2x xn-1n-1x xn-k-1n-k-1.x.x1 1x x0 02 之 1幻灯片 21/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系位序颠倒置换 图示（N=8）本章内容基本概念常用互连函数0000001 111112 222223 333334 444445 555556 666667 77777位序颠倒位序颠倒 子位序颠倒子位序颠倒(2)(2)位序颠倒位序颠倒(2)(2)2 之 2幻灯片 22/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系移数置换 互连函数w移数函数移数函数移数函数移数函数w子移数函数子移数函数子移数函数子移数函数本章内容基本概念常用互连函数2 之 1幻灯片 23/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系移数置换 图示（N=8）本章内容基本概念常用互连函数00001 1112 2223 3334 4445 5556 6667 777 移数置换移数置换k=2 子移数置换子移数置换（k=1,r=2）2 之 2幻灯片 24/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系加减2i置换 实际上是一种移数置换。实际上是一种移数置换。其中：其中：00 xN-1xN-1，00in-1in-1，n=logn=log2 2N N。本章内容基本概念常用互连函数幻灯片 25/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系你掌握了吗？本章内容基本概念常用互连函数 假设假设16个处理机的编号分别为个处理机的编号分别为0、1、15，采用单级互连网络。互连函数分别为：，采用单级互连网络。互连函数分别为：Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal问：问：问：问：第第12号处理机分别与哪一个处理机相连？号处理机分别与哪一个处理机相连？2 之 1幻灯片 26/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系你掌握了吗？本章内容基本概念常用互连函数2 之 2解：解：解：解：(12)10=(1100)2 Cube3 PM2+3 PM2-0 Shuffle Butterfly Reversal1100最高位取反得最高位取反得01004号处理机号处理机(12+23)MOD 16=4 4号处理机号处理机(1220)MOD 16=1111号处理机号处理机1100循环左移循环左移1位得到位得到1001 9号处理机号处理机1100的最高最低位交换的最高最低位交换01015号处理机号处理机1100的位序反过来为的位序反过来为00113号处理机号处理机幻灯片 27/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的特性本章内容基本概念 互连网络通常是用有向边或无向边连接有限互连网络通常是用有向边或无向边连接有限个结点，主要特性有：个结点，主要特性有：w 网络规模网络规模网络规模网络规模：网络中结点的个数。：网络中结点的个数。w 结点度结点度结点度结点度：与结点相连接的边数称为结点度，包：与结点相连接的边数称为结点度，包括入度和出度。进入结点的边数叫括入度和出度。进入结点的边数叫入度入度入度入度，从结点，从结点出来的边数则叫出来的边数则叫出度出度出度出度。w 距离距离距离距离：两个结点之间相连的最少边数。：两个结点之间相连的最少边数。w 网络直径网络直径网络直径网络直径：网络中任意两个结点间距离的最大：网络中任意两个结点间距离的最大值。用结点间的连接边数表示。值。用结点间的连接边数表示。2 之 1幻灯片 28/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络的特性本章内容基本概念w 等分宽度等分宽度等分宽度等分宽度 当网络被切成相等的两半时，沿切口的最小边数当网络被切成相等的两半时，沿切口的最小边数（通道）称为通道等分长度。（通道）称为通道等分长度。w 结点间的线长结点间的线长结点间的线长结点间的线长 两个结点间连线的长度，用米等表示。两个结点间连线的长度，用米等表示。w 对称性对称性对称性对称性 从任何结点看到拓扑结构都是一样的网络称为对从任何结点看到拓扑结构都是一样的网络称为对称网络。对称网络比较易实现，编程也较容易。称网络。对称网络比较易实现，编程也较容易。2 之 2幻灯片 29/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数本章内容基本概念5 之 1 一个连接两台机器的简单网络模型为：一个连接两台机器的简单网络模型为：机器机器A机器机器B幻灯片 30/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数本章内容基本概念5 之 2发送方开销发送方开销传输时间传输时间飞行时间飞行时间传输时间传输时间接收方开销接收方开销传输时延传输时延总时延总时延时间时间发送方发送方发送方发送方接收方接收方接收方接收方幻灯片 31/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数本章内容基本概念5 之 3w频带宽度频带宽度频带宽度频带宽度(Bandwidth)Bandwidth)互连网络传输信息的最大速率，单位为互连网络传输信息的最大速率，单位为Mbps。w传输时间传输时间传输时间传输时间(Transmission time)Transmission time)等于消息长度除以频宽。等于消息长度除以频宽。w飞行时间飞行时间飞行时间飞行时间(Time of flight)Time of flight)第一位信息到达接收方所花费的时间。第一位信息到达接收方所花费的时间。w传输时延传输时延传输时延传输时延(Transport latency)Transport latency)等于飞行时间与传输时间之和。等于飞行时间与传输时间之和。幻灯片 32/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系传输性能参数本章内容基本概念5 之 4w发送方开销发送方开销发送方开销发送方开销(Sender overhead)Sender overhead)处理器把消息放到互连网络的时间。处理器把消息放到互连网络的时间。w接收方开销接收方开销接收方开销接收方开销(Receiver overhead)Receiver overhead)处理器把消息从互连网络取出来的时间。处理器把消息从互连网络取出来的时间。w总时延总时延总时延总时延总时延总时延=发送方开销传输时延接收方开销发送方开销传输时延接收方开销=发送方开销飞行时间传输时间接收方开销发送方开销飞行时间传输时间接收方开销幻灯片 33/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系举 例本章内容基本概念5 之 5问：问：问：问：假设一个网络的频宽为假设一个网络的频宽为10Mbps，发送方开销发送方开销为为230s，接收方开销为接收方开销为270s。如果两台机如果两台机器相距器相距100m，信号传播速度为信号传播速度为200m/s，现在要发送一个现在要发送一个1000Byte的消息给另一台机的消息给另一台机器，试计算总时延。器，试计算总时延。解：解：解：解：幻灯片 34/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系互连网络种类本章内容w静态互连网络静态互连网络w动态互连网络动态互连网络幻灯片 35/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系静态互连网络本章内容互连网络种类 在各结点之间有固定的连接通路，在运在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。行过程中不能改变的网络结构。按拓朴结构按拓朴结构又可分为一维、二维、三维等，一维的有又可分为一维、二维、三维等，一维的有线线性阵列性阵列结构；二维的有结构；二维的有环形环形、树形树形、星形、星形、网格形网格形等；三维的有立方体等；三维以上的等；三维的有立方体等；三维以上的有有超立方体超立方体等。静态互连网络灵活性和适应等。静态互连网络灵活性和适应性较差，很少使用。性较差，很少使用。幻灯片 36/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系线性阵列本章内容互连网络种类静态互连网络w有有N个结点，结点度等于个结点，结点度等于2，网络直径为，网络直径为N-1，等分宽度为等分宽度为1，拓扑结构不对称。，拓扑结构不对称。w线性阵列结构最简单，但网络的延迟比较线性阵列结构最简单，但网络的延迟比较大，大，S0有信息发送到有信息发送到SN-1必需通过所有其必需通过所有其他结点。他结点。S0SN-2S4S3S2S1SN-1幻灯片 37/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系环 形本章内容互连网络种类静态互连网络w 单向环单向环单向环单向环 右环网采用右环网采用PM2+0函数，左环网采用函数，左环网采用PM2-0函数，函数，对称，直径是对称，直径是N-1，结点度是结点度是2。w 双向环双向环双向环双向环 又称一维邻居网，采用又称一维邻居网，采用PM2+0，PM2-0-0函数，函数，对称，直径为对称，直径为N/2，结点度是结点度是2。w 弦环网弦环网弦环网弦环网 将结点度由将结点度由2提高至提高至3。增加的弦愈多，则结点。增加的弦愈多，则结点度愈高，网络直径愈小。极端情况是全连接，网度愈高，网络直径愈小。极端情况是全连接，网络直径为络直径为1。3 之 1幻灯片 38/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系环 形本章内容互连网络种类静态互连网络3 之 210234576环形网环形网234576度为度为3的弦环网的弦环网10234576全连通全连通10234576循环移数网循环移数网幻灯片 39/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系循环移数网络本章内容互连网络种类静态互连网络 循环移数网络是将环上每个结点与其距循环移数网络是将环上每个结点与其距离为离为2的整数幂的结点之间连接构成。的整数幂的结点之间连接构成。即，即，采用采用2n-1个互连函数：个互连函数：PM2i(j)=(j2i)mod N，n=log2N，0in-1,0jN-1；其中：其中：PM2+(n-1)=PM2-(n-1)。若循环移数网的网络规模是若循环移数网的网络规模是2n，则结则结点度点度d=2n-1，网络直径网络直径D=n/2。例如：结点例如：结点数数64，n=6，d=11，D=3。3 之 3幻灯片 40/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系树 形本章内容互连网络种类静态互连网络w 二叉树二叉树 一棵一棵k层二叉树有层二叉树有N2k1个结点，结点个结点，结点度是度是3，直径是，直径是2(k-1)。w 星形星形 一种特殊的一种特殊的2层树，结点度很高，为层树，结点度很高，为d=N-1，直径是直径是2。w 二叉胖树二叉胖树 缓解了根结点通信速度高的矛盾。缓解了根结点通信速度高的矛盾。2 之 1幻灯片 41/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系树 形本章内容互连网络种类静态互连网络2 之 2二叉树网二叉树网二叉胖树网二叉胖树网星形网星形网幻灯片 42/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系网格形本章内容互连网络种类静态互连网络 网格形是一种比较流行的网络结构，网格形是一种比较流行的网络结构，有各种变体形式在有各种变体形式在Illiac IV、MPP、DAP、CM-2和和Intel Paragon等中得到了实现。等中得到了实现。5 之 1幻灯片 43/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系二维网格本章内容互连网络种类静态互连网络 一般的二维网格有一般的二维网格有一般的二维网格有一般的二维网格有N Nn1n2 n1n2 个结点组成个结点组成个结点组成个结点组成，直径是直径是D=（n1 1）+（n2 1）。）。实际实际上经常是上经常是n1=n2=n。结结点度为点度为4，是一种非对，是一种非对称的拓扑结构。称的拓扑结构。1234567895 之 2幻灯片 44/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系环形二维网格本章内容互连网络种类静态互连网络 环形二维网格沿阵环形二维网格沿阵环形二维网格沿阵环形二维网格沿阵列每行每列都有环形连列每行每列都有环形连列每行每列都有环形连列每行每列都有环形连接。接。接。接。nn二元环网的结二元环网的结点度为点度为4，直径为，直径为D=2 n/2 。环网是环网是一种对称的拓扑结构。一种对称的拓扑结构。5 之 3幻灯片 45/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系Illiac网格本章内容互连网络种类静态互连网络 二维网格逐行（或二维网格逐行（或二维网格逐行（或二维网格逐行（或列）串形连接。列）串形连接。列）串形连接。列）串形连接。nn Illiac 网格的直径为网格的直径为D=n-1，为纯网格直径为纯网格直径的一半。例如：的一半。例如：Illiac IV的的88 Illiac网格，其结网格，其结点度为点度为4，直径为，直径为7。5 之 4幻灯片 46/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系Illiac网格本章内容互连网络种类静态互连网络 Illiac网络的结点连网络的结点连接按一定的算法进行接按一定的算法进行:Illiac+1(j)=(j+1)mod(N)Illiac-1(j)=(j-1)mod(N)Illiac+n(j)=(j+n)mod(N)Illiac-n(j)=(j-n)mod(N)1023458765 之 5幻灯片 47/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系超立方体本章内容互连网络种类静态互连网络 超立方体也称超立方体也称 n 维立方体维立方体，由，由N2n 个个结点组成，分布在结点组成，分布在n维上，每维有两个结点。维上，每维有两个结点。超立方体结点度为超立方体结点度为n，直径也为直径也为n，每个结每个结点由点由n个二进制数实行编号，相邻结点只能个二进制数实行编号，相邻结点只能有一个数字不同。有一个数字不同。超立方体缺乏可扩展性，难以组成高维超立方体缺乏可扩展性，难以组成高维超立方体。超立方体。3 之 1幻灯片 48/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系超立方体本章内容互连网络种类静态互连网络3 之 2YXZ011000010110111101100001110010012维立方体维立方体3维立方体维立方体231067320154011维立方体维立方体01幻灯片 49/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系超立方体本章内容互连网络种类静态互连网络3 之 3001100000010011001110101010000014维立方体维立方体673201541011100010101110111111011100100114151110891312幻灯片 50/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系总 结本章内容互连网络种类静态互连网络网络类型网络类型 结点度结点度 网络直径网络直径 链路数链路数 等分带宽等分带宽 对称性对称性网络规模网络规模线性阵列线性阵列2N-1N-11非非N个结点个结点环形环形2 N/2 N2是是N个结点个结点全连接全连接N-11N(N-1)/2(N/2)2是是N个结点个结点二叉树二叉树32(h-1)N-11非非树高树高h=log2N 星形星形N-12N-1 N/2 非非N个结点个结点2D网格网格42(r-1)2N-2rr非非 rr网络，网络，Illiac网网4r-12N2r非非 rr网络，网络，2D环网环网42 r/2 2N2r是是 rr网络，网络，超立方体超立方体nnnN/2N/2是是N个结点个结点,n=log2N幻灯片 51/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系动态互连网络本章内容互连网络种类 动态互连网络中的连接通路是可变的，动态互连网络中的连接通路是可变的，结点之间的连接可以重新配置结点之间的连接可以重新配置。一般由开关。一般由开关和连线组成，通过控制开关来建立不同的连和连线组成，通过控制开关来建立不同的连接。接。幻灯片 52/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系分 类本章内容互连网络种类动态网络动态网络动态网络动态网络交叉开关交叉开关多级网络多级网络全排列全排列网络网络总线网络总线网络幻灯片 53/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系总线网络 多个处理机、存储器模块和外围设备通过接多个处理机、存储器模块和外围设备通过接口与公用总线相连，多个结点将争用总线，口与公用总线相连，多个结点将争用总线，必需必需必需必需裁决或分时使用裁决或分时使用裁决或分时使用裁决或分时使用。但连接可以任意、动态地变化。但连接可以任意、动态地变化。本章内容互连网络种类动态互连网络4 之 1P1P2PnM1M2Mm总线总线幻灯片 54/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系问题及解决问题：问题：公用总线上的结点数目增多会导致系公用总线上的结点数目增多会导致系统效率急剧下降。统效率急剧下降。解决：解决：w采用优质高频同轴电缆来提高总线的传输采用优质高频同轴电缆来提高总线的传输速率；速率；w采用多总线方式来减少访问总线的冲突概采用多总线方式来减少访问总线的冲突概率。率。本章内容互连网络种类动态互连网络4 之 2幻灯片 55/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系问题及解决问题：问题：问题：问题：存在访问冲突。存在访问冲突。解决：解决：解决：解决：w w静态优先级算法：静态优先级算法：静态优先级算法：静态优先级算法：为连接到总线的每个部件分配一个固为连接到总线的每个部件分配一个固定的优先级。定的优先级。w w固定时间片算法：固定时间片算法：固定时间片算法：固定时间片算法：将总线按时间分成固定大小的时间片，将总线按时间分成固定大小的时间片，轮流提供给部件使用。轮流提供给部件使用。w w动态优先级算法：动态优先级算法：动态优先级算法：动态优先级算法：让总线上各部件优先级根据情况和一让总线上各部件优先级根据情况和一定规则动态地改变。例如：定规则动态地改变。例如：LRU。w w先来先服务算法：先来先服务算法：先来先服务算法：先来先服务算法：按接受到访问总线请求的先后顺序来按接受到访问总线请求的先后顺序来响应。响应。本章内容互连网络种类动态互连网络4 之 3幻灯片 56/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系举 例本章内容互连网络种类动态互连网络4 之 4P1P2PnM1M2Mm共享总线共享总线总线接口总线接口 总线接口总线接口总线接口总线接口总线控制器总线控制器（仲裁逻辑）（仲裁逻辑）总线忙总线忙总线许可总线许可总线请求总线请求幻灯片 57/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系交叉开关网络 一组纵横开关阵列构成多总线一组纵横开关阵列构成多总线一组纵横开关阵列构成多总线一组纵横开关阵列构成多总线（总线数为（总线数为m+n+i，且且mn+i；可同时通信的总线数为可同时通信的总线数为m），交叉点开关能在对），交叉点开关能在对偶（源和目的）之间形成动态连接。偶（源和目的）之间形成动态连接。本章内容互连网络种类动态互连网络5 之 1P1PnM1M2MmI/O1I/Oi幻灯片 58/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系举 例 C.mmp多处理机本章内容互连网络种类动态互连网络P1P2P16M1M2M16开关开关处理机处理机处理机处理机-存储器交叉开关网络存储器交叉开关网络存储器交叉开关网络存储器交叉开关网络5 之 2幻灯片 59/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系问题及解决问题：问题：问题：问题：交叉开关网络很复杂，代价大交叉开关网络很复杂，代价大交叉开关网络很复杂，代价大交叉开关网络很复杂，代价大。因为开关阵。因为开关阵列的每个交叉点上均有一套开关，每套开关内部列的每个交叉点上均有一套开关，每套开关内部含有多选一的仲裁模块和多路转换器模块。含有多选一的仲裁模块和多路转换器模块。解决：解决：解决：解决：通过用多个较小规模的交叉开关通过用多个较小规模的交叉开关“串联串联”和和“并联并联”来构成多级交叉开关网络，以取代单级的来构成多级交叉开关网络，以取代单级的大规模的交叉开关。大规模的交叉开关。本章内容互连网络种类动态互连网络5 之 3幻灯片 60/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系Delta网本章内容互连网络种类动态互连网络 用用ab的交叉开关模块构成的交叉开关模块构成anbn的交的交叉开关网络，其中指数叉开关网络，其中指数n为互连网络的级数。为互连网络的级数。例如：用例如：用44的交叉开关模块构成的交叉开关模块构成4242的交叉开关网络，其中指数的交叉开关网络，其中指数2为互连网络的为互连网络的级数。级数。5 之 4幻灯片 61/120Computer ArchitectureV3同济大学.电子与信息工程学院.计算机科学与工程系图 示本章内容互连网络种类动态互连网络0347811121503478111215出出出