资源描述
第7章互连网络,7.1互连网络的基本概念7.2互连网络的种类7.3消息传递机制7.4互连网络实例,7.1互连网络的基本概念,7.1.1互连网络的作用7.1.2互连网络的特性7.1.3互连网络的性能参数7.1.4互连网络的表示方法7.1.5互连函数,7.1.1互连网络的作用,用来实现计算机系统内部多个处理机或多个功能部件之间的相互连接。互连网络已成为并行处理系统的核心组成部分。互连网络对整个计算机系统的性能价格比有着决定性的影响。一个例子：具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构,磁盘,SM1,SM2,SMm,PMN,Cn,Pn,LM,C1,P1,LM,PCN,PION,磁带,打印机,终端,网络,(共享存储器),(共享I/O与外设),互连网络通常是用有向边或无向边连接有限个结点组成。如果用图形表示，一个网络可以表示为若干有相互连线的结点组成的图。互连网络的主要特性有：(1)网络规模：网络中结点的个数(2)结点度：与结点相连接的边数称为结点度进入结点的边数叫入度从结点出来的边数则叫出度(3)距离：两个结点之间相连的最少边数(4)网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数表示,7.1.2互连网络的特性,6,网络规模：即一个网络中所连接的结点数。,该指标可以用于衡量网络可扩展性的一个方面，例如，有没有结点数量限制，如果有，最大能够容纳多少结点。单纯从拓扑结构上讲，一般的网络结构都能够容纳无限多的结点，如果要评估不同网络结构的相对性能优劣，必须给它们指定相同的规模，即网络规模也用作建立一致性评估的基础。,7,结点度：每个结点与外部连接的边数称为一个结点的度，用d表示。图6-3表示了单向和双向通道连接和情况。结点度和结点成本是成正比的，因为度越大，结点上需要构造的接口也越多，因而成本也越高。一般使用平均结点度或最大结点度来衡量一个网络结构中的结点成本。,8,图6-3结点间连接示意图,返回,上一张,9,距离：任意两结点之间相连的最少边数。距离与两结点间最快的信息传输速度是成正比的。平均距离与最长距离可以用于衡量由于网络结构而限定的信息传输速度指标。网络直径：网络中任意结点之间距离中的最大值。即最长距离，它和网络结构中最慢的传输速度成正比，可以在一定程度上衡量网络结构的速度指标。,10,等分宽度：一个网络被切割成对等的两半时（两半网络中结点数相等），沿切口所具有的边数（通道数），称为通道等分宽度，用b表示。（1）等份切割面可能不止一个，得到的等分宽度也可能不止一个。网络的等分宽度一般是指最小的等分宽度。（2）对于其它任意切割面，只要它不与当前讨论的等份切割面相交，则该切割面的宽度必须小于等分宽度，否则网络结构中存在固定瓶颈。等分宽度与网络结构的最大通信带宽成正比，可以从宏观上分析网络结构中的固定瓶颈，衡量网络结构的速度指标。,11,结点间线长：两个结点之间实际连接用的线长。与两结点间的实际信息传输速率成正比，因为信号在传输线上传输需要时间，线长越大，速率越慢。如果只是评估网络拓扑结构的优劣，并不会采用这一指标。,12,链路数量：网络中边的总数量。与网络本身的成本成正比，边数越多，成本越高，可以用于评估网络成本。对称性：如果从任一个结点观察网络，所看到的网络拓扑结构都是相同的，该网络是一个对称网络。网络结构的对称性与结点概念的一致性等价，如果网络是一个对称结构，则所有结点上都使用相同的通信机制或协议软件，即软件可扩展性高。一般而言，在对称网络中添加结点比非对称网络更容易，即硬件扩展性也相对较高，但这并不是绝对的。一定程度上，可以用对称性来衡量网络可扩展性的一个方面。,7.1.3互连网络的性能参数,发送方的步骤如下：(1)用户程序把要发送的数据拷贝到系统缓冲区。(2)缓冲区中的数据打包并发送到网络接口部件。(3)网络接口硬件开始发送消息。数据包的接收步骤如下：(1)把数据包从网络接口部件拷贝到系统缓冲区。(2)检查收到的数据包，如果正确，发回答信号。(3)把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后释放系统缓冲区,1、互连网络的主要性能参数：(1)频带宽度(Bandwidth)：传输信息的最大速率(2)传输时间(Transmissiontime)：等于消息长度除以频宽。(3)飞行时间(Timeofflight)：第一位信息到达接收方所花费的时间。(4)传输时延(Transportlatency)：等于飞行时间与传输时间之和。(5)发送方开销(Senderoverhead)：处理器把消息放到互连网络的时间。(6)接收方开销(Receiveroverhead)：处理器把消息从网络取出来的时间。,15,2、标志网络传输性能的若干参数所谓网络的传输性能主要指一个网络对信息的延迟尺度。以一个消息从发送方操作系统取出开始，到接收方操作系统正确收到该消息为止，,一个消息的总时延可以用下面公式表示：总时延发送方开销飞行时间消息长度/频宽接收方开销,例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)输入输出对应表示法,互连网络,0,0,1,1,n-1,n-1,输入:01234567输出:10325476,7.1.4互连网络的表示方法,7.1.5互连函数,互连函数也称为互连置换或互连排列等。1.交换函数（Exchange）当n3时，有3种函数，每种能表示8个结点之间的连接关系。由于交换函数主要用于超立方体互连网中，因此也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等。,2.全混洗函数（Perfectshuffle）函数关系：把二进制结点号循环左移一位子混洗(subshuffle)S(k),最低k位循环左移一位超混洗(supershuffle)S(k),最高k位循环左移一位显然成立：逆混洗函数：,起始位0终止位K-1右侧k位,起始位n-k终止位n-1左侧k位,3.蝶式函数（Butterfly）蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样。函数关系：将输入端二进制结点号的最高位和最低位互换位置。子蝶式(subbutterfly)B(k)最低k位的高低位互换超蝶式(superbutterfly)B(k)最高k位的高低位互换显然成立：,4.反位序函数（BitReversal）函数关系：将二进制自变量的位序反过来。子反位序函数，最低k位的位序反过来超反位序函数，最高k位的位序反过来对于n3的情况，正好有：RB，R(2)B(2)，R(2)B(2)。,5.移数函数函数关系：将输入端向量循环移动一定的位置经常取r2i，因此移数函数又称为加减2i函数、PM2I函数等。子移数函数：其中：0xN-1，0i,kn-1，n=log2N。Illiac函数包含PM20和PM2n/2等4个互连函数，每个接点与它的上下左右4个相邻接点连接,例6.2：假设16个处理机的编号分别为0、1、15，采用单级互连网络。互连函数分别为：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)Butterfly(6)Reversal第13号处理机分别与哪一个处理机相连？,解：(12)10=(1100)2(1)Cube3，(2)PM2+3，(3)PM2-0，(4)Shuffle，(5)Butterfly，(6)Reversal1100最高位取反得0100，4号处理机(12+8)MOD16=4，4号处理机121=11，11号处理机1100循环左移1位得到1001,9号处理机1100的最高最低位交换0101,5号处理机1100的位序反过来为0011,3号处理机,7.2互连网络的种类,7.2.1静态互连网络7.2.2循环互连网络7.2.3多级互连网络7.2.4全排列互连网络7.2.5全交叉开关网络,静态互连网络：连接通路是固定的，一般不能实现任意结点到结点之间的互连。循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连。多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连。全排列互连网络：能够同时实现任意结点到结点之间的互连。全交叉开关网络：能够同时实现任意结点到结点之间的互连，还能够实现广播和多播。,7.2.1静态互连网络,按照网络的互连特性为特征分类，可分为如下几类：静态互连网络在各结点之间有固定的连接通路，在运行过程中不能改变的网络结构。一般静态互连网络不能实现任意结点到结点之间的互连。一维的有线性阵列结构；二维的有环形、星形、树形、网格形等；三维的有立方体等；三维以上的有超立方体等。,1.超立方体网n维立方体由N2n个结点，分布在n维上超立方体网采用交换函数,网络规模为2n个结点结点度为n直径也为n,2.环形网采用移数函数单向环行网：右环网采用PM2+0函数，左环网采用PM2-0函数，对称，直径是N，结点度是2双向环行网：又称一维邻居网，采用PM2+0，PM2-0函数，对称，直径为N/2，结点度是2弦环网：增加的弦愈多，则结点度愈高，网络直径愈小。循环移数网络：将每个结点与其距离为2的整数幂的结点连接构成。,循环移数网的结点度为2n-1，直径为n/2。,环形网,3.树形和星形网二叉树：一棵k层二叉树有N2k1个结点，结点度是3，直径是2(k-1)。星形：一种特殊的2层树，结点度很高，为d=N-1，直径是2。二叉胖树：缓解了根结点通信速度高的矛盾,4.网格形网二维网格网：结点度为，直径为。k维网格网：网络规模为，结点度为，直径为。环网形网格网：沿阵列每行每列都有环形连接。nn二元环网的结点度为，直径为。环网形网格网是一种的拓扑结构,4,2(n-1),4,2n/2,对称,N=nk,2k,k(n-1),5.二维闭合螺旋线网格网结点度为4，网络直径为n-1。一个nn的Illiac网格的直径为n-1。88网格，结点度为4，直径为7。,7.2.2循环互连网络,一般静态互连网不能实现任意两结点之间的互连。有两种解决办法：循环互连网：多次重复使用同一个单级互连网络多级互连网：将多套相同的单级互连网络连接起来前一种方法是牺牲时间换取设备，后一种方法是以设备换取时间RN为网络连接寄存器，它有三个用处：发送消息，接收消息，转发消息,例如：对于一个3维立方体网，如果要从PE0发送消息到PE3，需要经过如下4步：周期1：PE0RN0，周期2：RN0RN1周期3：RN1RN3，周期4：RN3PE3,7.2.3多级互连网络,循环互连网络虽然能够实现结点到结点之间的任意互连，但是其通信速度低。多级互连网络采用多个相同的或不同的单级互连网络直接连接起来。一个时钟周期就能够实现任意结点到结点之间的互连。多级互连网络采用的关键技术：(1)交换开关，(2)交换开关之间的拓扑连接，(3)对交换开关的不同控制方式。,1.交换开关一个ab交换开关有a个输入和b个输出。最常用的二元开关：a=b=2。每个输入可与一个或多个输出相连，但是在输出端必须避免发生冲突。一对一和一对多映射是容许的；但不容许有多对一映射。只容许一对一映射时称为置换连接，称这种开关为交叉开关。具有直通和交换两种功能的开关称为二功能开关，或交换开关。用一位控制信号控制。具有所有4种功能的交换开关称为四功能开关，用两位控制信号控制。,2.拓扑结构前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构。通常，采用前面介绍过的互连函数实现拓扑结构。实际上，从结点的输出到第一级交换开关的输入，以及从最后一级交换开关的输出到结点的输入也可以采用拓扑结构连接。,3.控制方式有多级交换开关，每一级又有多个交换开关。通常有三种控制方式级控制：同一级交换开关使用同一个控制信号控制。单元级控制：每个交换开关分别控制。部分级控制：第i级使用i+1个控制信号控制（0in-1）。同一个多级互连网络分别采用三种不同的控制方式，可以构成三种不同的互连网络。,4.多级立方体网采用二功能开关，总共需要开关n2n-1个。采用交换函数，各级分别采用E0,E1,En-1函数当所有开关都直通时，实现恒等变换。当A、B、C、D交换，其余直通实现E0函数。当E、F、G、H交换，其余直通实现E1函数。当I、J、K、L交换，其余直通实现E2函数。采用不同的控制方式，可构成不同的互连网络采用级控制可以构成STARAN交换网。采用部分级控制，可以构成STARAN移数网。采用级控制可以构成间接二进制n方体网。,多级立方体网,7.2.4全排列互连网络,循环互连网络和多级互连网络不能实现同时多个结点之间的互连。例如：多级立方体网中，如果要求同时实现05和17的互连，在开关A发生冲突。全排列互连网络不仅能够实现任意结点到结点之间的互连，而且能够实现同时任意结点之间的互连。解决方法：采用多个多级互连网络连接。原理：N个结点的全排列需要有N！，N个结点的多级互连网络共有二功能开关n2n-1个，共有不同的状态种类：,7.2.5全交叉开关网络,全交叉开关网络除了能够实现同时任意结点之间的互连之外，还能够实现广播和多播。在多处理机系统中，处理机、存储器和IOP之间用交叉开关网络连接。,7.3消息传递机制,7.3.1消息寻经方式7.3.2虚拟通道7.3.3流控制策略7.3.4选播与广播,7.3.1消息寻径方式,1.线路交换(circuitswitch)先建立一条从源结点到目的结点的物理通路，然后传递消息。传输时延用公式：T(Lt/B)D+L/B，其中：Lt为建立路径所需的小信息包的长度，L为信息包的长度，D为经过的结点数，B为带宽。优点：实际通信时间较短，使用缓冲区少。缺点：建立物理通路的开销很大，占用物理通路的时间长。,2.存储转发(storeandforward)每个结点有一个包缓冲区，包从源结点经过中间结点到达目的结点。存储转发网络的时延与源和目的地之间的距离成正比。时延用公式：T(L/B)D+L/B=(D+1)L/B优点：占用物理通路的时间比较短。缺点：包缓冲区大，时延大（与结点距离成正比）。,3.虚拟直通(virtualcutthrough)当接收到用作寻径的消息头部时，即开始路由选择。通信时延公式：T=(Lh/B)D+L/B=(LhD+L)/BL/B其中：Lh是寻径头部的长度，一般LLhD当出现寻径阻塞时，只能将整个消息存储在寻径结点中。优点：通信延迟与结点数无关。缺点：每个结点需要有足够大的缓冲区。在最坏的情况下与存储转发方式的通信时延相同，经过的每个结点都阻塞，都需要缓冲。,4.虫蚀寻径(wormhole)把包分成更小的片。每个结点的寻径器中设置有片缓冲区。用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动”。当消息的头片到达一个结点的寻径器后，寻径器根据头片的寻径消息立即做出路由选择如果所选择的通道或结点的片缓冲区不可用时，头片必须在该结点的片缓冲区中等待，其它数据片也在原来的结点上等待。,时延公式：T=TfD+L/B=(Lf/B)DL/B=(LfDL)/B,其中：Lf是片的长度，Tf是片经过一个结点所需时间。一般有LLfD，时延近似为：TL/B，与结点数无关。优点：每个结点的缓冲区较小。较低的网络传输时延；通道共享性好，利用率高；易于实现选播和广播通信方式。缺点：当消息的一个片被阻塞时，整个消息都被阻塞。,7.3.2虚拟通道,1.虚拟通道虚拟通道是两个结点间的逻辑链路，由源结点的片缓冲区、结点间的物理通道及接收结点的片缓冲区组成。,2.死锁的产生与避免缓冲区或通道上的循环等待会引起死锁。利用虚拟通道可以减少死锁。虚拟通道可能会使每个请求可用的有效通道频宽降低。,7.3.3流控制策略,在相邻结点间传送片时，必须具备三个条件：(1)源缓冲区已存有该片；(2)通道已分配好；(3)接收缓冲区准备接收该片。接收缓冲区或输出通道冲突的仲裁：(1)把后一个包暂时存放在缓冲区。(2)阻塞后一个包。(3)场弃后一个包。(4)绕道。,维序寻径算法：,按照特定顺序选择后继通道。在二维网格网络中称为X-Y寻径：例如，X优先于Y在超立方体中称为E立方体寻径：逐维改变。,采用双虚拟通道和X-Y寻经可以完全避免死锁,7.3.4选播与广播寻径算法,四种通信模式：(1)单播(unicast)，一对一传送。(2)选播(multicast)，从一个源结点发送同一消息到多个目的结点(3)广播(broadcast)，从一个源结点发送同一消息到全部结点。(4)会议(conference)，多到多的通信情况。扩充选播树的原则：选择某些维使剩余目的结点的集合最小。贪婪选播算法所需的通道数，与多次单播或广播树所需的通道数相比要少。,7.4互连网络实例,7.4.1总线互连7.4.2多端口存储器7.4.3STARAN交换网和STARAN移数网7.4.4Omega互连网,7.4.1总线互连,总线的优点：结构简单，很方便实现广播。总线的缺点：带宽低，发生冲突的可能性大。总线冲突的解决办法有：(1)设置静态优先级(2)在同步方式中采用时间片(3)采用动态优先级（如LRU法等）(4)先来先服务提高总线通信带宽的方法有：(1)采用多总线结构(2)层次总线结构(3)多维总线结构,多总线：西门子公司的SMS系统（StracturedMultiprocessorSystem）通过8条总线连接128个处理机。,层次总线：卡内基梅隆大学的Cm*多处理机系统采用层次总线结构。三级总线：群总线、Map总线、处理机总线每群14台处理机,7.4.2多端口存储器,多个多端口存储器与多个CPU和IOP连接。多端口存储器用于处理机个数不多的系统中。把复杂的互连网络移到了存储器中。,7.4.3STARAN交换网和移数网,多级立方体网，应用在巨型机STARAN中。采用级控制可以构成STARAN交换网。采用部分级控制，可以构成STARAN移数网。,子洗2蝶1+逆洗,STARAN交换网实现交换函数关系例如：输入端：012345674G2E：103254782G4E：23016745结果为：(0,2)(1,3)(4,6)(5,7),STARAN移数网实现移数函数关系因为第i级用i+1个控制信号，因此共有6个控制信号。有64种不同的控制。表中仅列出了一小部分。,7.4.4Omega互连网,采用全混洗函数和交换函数，又称混洗交换网络。N个输入的Omega网络有log2N级，每级有N/2个22的四功能交换开关，每级的拓扑结构相同，采用单元控制（每一级的控制信号均相同）。Omega网能够实现任意一个输入端到任意一个输出端的连接。但不能同时实现多个输入端到多个输出端的连接。当有N个输入端时，共有NN/2个种变换。如果要同时实现任意一个输入端到任意一个输出端的连接，共需要N！种变换换。Omega网能够实现从任意一个输入端到所有输出端的广播。,同时实现06和47有冲突，同样还有：30和51，30和73，50和71等。8个输入端的Omega网络实际上只能实现全部变换的10%,84/8!=4096/40320=0.1016。,本章重点：1.主要的互连函数2.几种典型互连网络的构成方法及特点3.寻径方式的原理及优缺点练习题:7.37.57.197.237.27/(1)(2),
展开阅读全文