《互联网络》PPT课件.ppt

《《互联网络》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《互联网络》PPT课件.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第五章第五章互连网络互连网络互连网络互连网络是是现代计算机系统中的一个核心部分和关键部现代计算机系统中的一个核心部分和关键部件。对整个计算机系统的性能有着决定性影响。随着系统规件。对整个计算机系统的性能有着决定性影响。随着系统规模、通信要求和线路复杂性的增加模、通信要求和线路复杂性的增加,其重要性在不断增长。其重要性在不断增长。已经成为计算机组织和系统结构中独立的研究内容。已经成为计算机组织和系统结构中独立的研究内容。路由选择和信息传递方式路由选择和信息传递方式 5.4流量控制策略和通信模式流量控制策略和通信模式5.1互连网络的相关概念互连网络的相关概念5.2互连网络的结构互连网络的结构25

2、.1互连网络的相关概念互连网络的相关概念一、互连网络的组成一、互连网络的组成1 1、互连网络、互连网络(IN)定义定义由由开关元件开关元件按照一定按照一定拓扑结构拓扑结构和和控制方式控制方式构成的网络，实现多构成的网络，实现多个节点对之间的相互连接。个节点对之间的相互连接。互连网络互连网络已成并行计算机系统中重要的核心部件。已成并行计算机系统中重要的核心部件。根据需要，根据需要，有有PPPP及及PMPM的的连接形式连接形式互连网络互连网络INP互连网络互连网络INPPMPPPM32 2、互连网络、互连网络(IN)(IN)的特性的特性 *特性特性1 1：同时同时同时同时实现实现多个端口对多个端口

3、对的互连及通信。的互连及通信。*特性特性2 2：具有具有多种多种多种多种并行端口对的并行端口对的互连方式互连方式.*互连网络与总线比较：互连网络与总线比较：互连网络互连网络 :强调强调多个多个节点对节点对之间的互连及通信。之间的互连及通信。总总 线线:多个设备或单元所共享的多个设备或单元所共享的公共公共通道通道(分时分时)理论上有理论上有N!种种端口对端口对互连排列互连排列方式方式42、互连网络要素互连网络要素：开关元件、互联结构、控制方式开关元件、互联结构、控制方式。互联结构互联结构：网络合理布局关键因素，反映系统结构特：网络合理布局关键因素，反映系统结构特征。用征。用有向图有向图或或无向图

4、无向图表示，表示，节点节点对应对应开关元件开关元件或或处处理机理机。边边对应对应通信链路通信链路。开关元件开关元件：网络中最基本模块，在不同系统和控制中，：网络中最基本模块，在不同系统和控制中，开关元件所处的开关元件所处的物理位置物理位置和和工作状态工作状态不同。不同。控制方式控制方式：网络中：网络中各种开关各种开关的控制方法的控制方法3、互连网络的特征、互连网络的特征1)拓扑结构拓扑结构静态动态2)控制策略控制策略集中式分散式3)定时方式定时方式同步异步4)交换方法交换方法线路交换分组交换5互连网络的特征互连网络的特征1)拓扑结构拓扑结构:分分静态和动态两种。静态网:各节点节点间有专用通信线

5、路（链路），运行间不改变或重新组合。又称又称直接网络(节点通过链路直接连接节点通过链路直接连接)组成：由链路、结构及网络节点节点组成。结构:线性、环形、树形、立方体等。6动态网:链路可通过设置网络中开关重新组合。节点与节点与节点的连接节点的连接由程序或或控制信号动态地改变，又称动态地改变，又称间接网络(节点与交换开关连接节点与交换开关连接)。组成：由链路、结构、开关及节点节点组成。结构:总线、环状、开关、(单)多级。动态网:7互连网络的特征互连网络的特征2)控制策略控制策略:集中控制:全局控制器接收所有通信请求，设置互连网络的开关连接。分散控制:通信请求和开关设置由互连网络分散地进行。3)定时

6、方式定时方式：同步系统：系统使用一个集中的统一时钟.异步系统：无统一时钟，节点根据各自情况独立工作。4)交换方法交换方法:线路交换和分组交换。线路交换：源结点和目的结点间的物理通路在整个数据传送期间一直保持连接。分组交换：信息分割成组(包)，各组(包)通过多个不同路径传分别送入互连网络。传送不存在一个实际连接的固定通路。85.1.2互连网络的描述根据输入与输出结点之间的对应关系，有以下表示方法：根据输入与输出结点之间的对应关系，有以下表示方法：函数表示法函数表示法变量x表示输入，函数f(x)表示输出，建立输入与输出端的一一对应关系。自变量和函数常用二进制、十进制表示。互连函数反映网络输入数组和

7、输出数组之间对应的排列关系，也称排列函数排列函数。输入输出对应表示法输入输出对应表示法图形表示法图形表示法用图形表示输入端与输出端之间的一一对应关系循环表示法：如循环表示法：如(04)(15)(26)(37)9互连函数数的排列：N个数的每一种有确定次序的放置方法叫做一个N排列。一般有N！种放置方法。网络排列：N输入、N输出端网络中，输入端和输出端的放置方法分别为一种排列。置换：把一个N排列变成另一个N排列的变换叫N阶置换。表示输入端和输出端的连接关系.复杂的置换方式可用少量基本的互联函数表示10基本的互联函数恒等函数:输入端与输出端一一对应,且编号相同。Xn-1Xn-2XkX0是PE的地址（通

8、常为二进制）。n为3时的恒等函数的连接情形如下：(0)(1)(2)(3)(4)(5)(6)(7)11交换函数交换函数:函数形式为主要用于超立方体互联网络中。超立方体由n个交换函数组成。K=1二进制地址编码下，某一位的输入与输出端编号相反。0kn12当n=3，结点数N8时，可得到3立方体互连函数：互连函数变换图形交换函数交换函数典型的立方体网络结构图(01)(23)(45)(67)(02)(13)(46)(57)(04)(15)(26)(37)13均匀洗牌函数均匀洗牌函数把输入端二进制地址循环左移一位。表示为：逆均匀洗牌函数逆均匀洗牌函数:输入端二进制地址循环右移一位。函数：(0)(124)(3

9、65)(7)将输入端分成数目相等的两半，前一半和后一半按序一个隔一个，从头依次与输出端相连，类似洗牌方式。14均匀洗牌函数均匀洗牌函数均匀洗牌函数逆均匀洗牌函数均匀洗牌与开关多级组合起来可构成Omega网络15蝶式函数蝶式函数蝶式函数蝶式函数:输入二进制地址的最高位和最低位互换位置，定义为：N=8的蝶式函数变换图形均匀洗牌，蝶式函数不能单独实现任意结点间互连。它们与交换函数多级组合是构成复杂多级网络的基础例如:均匀洗牌函数与Cube0的组合(0)(2)(14)(36)(5)(7)16反位序函数反位序函数反位序函数反位序函数:输入端二进制地址的位序颠倒过来求得相应输出端的地址。其互连函数表示如下

10、：对于N=8的情况，图形见图（b）17PM2I移数函数移数函数移数函数的一般形式为：如k=2PM2I函数（加减2i）是一种特殊移数函数移数函数，将输入端数组的十进制编号循环移动特定的位置向输出端传输。N个结点的移数函数表示为：如i=1设N为结点数。n=log2N；0 xN1，0in1，共有2n个互连函数(0246)(1357)18N=8的PM2I函数的变换图形。(a)PM2：(01234567)(b)PM21：(0246)(1357)(c)PM2+2：(04)(15)(26)(37)实质为1,2,4个环型网移数函数可构成环型网(单向环网、双向环网)、方格网、移数网19课堂练习设PM2I网络有8

11、个结点，写出所有PM2I函数的输入输入输出对表示输出对表示，画出PM21、PM22互连网络的连接图。20【例【例】设PM2I网络有8个结点，写出所有PM2I函数的，画出PM21、PM22互连网络的连接图。解解N=8，则n=3，所以i=0,1,2;j=0,1,7。根据公式6个PM2I函数如下：PM2：(01234567)PM2：(76543210)PM21：(0246)(1357)PM21：(6420)(7531)PM22：(04)(15)(26)(37)PM22：(40)(51)(62)(73)PM2PM221PM21：(0246)(1357)PM21互连网络的连接图。22(c)PM22：(0

12、4)(15)(26)(37)(40)(51)(62)(73)PM22互连网络的连接图23【例】【例】Illiac阵列计算机：采用PM20和PM2n/2四个移数网络构成处理器的连接。16个结点的Illiac网络表示PM22：(04)(15)(26)(37)(48)(59)(610)(711)(812)(913)(1014)(1115)(012)(113)(214)(315)PM2+0:(01215)PM2-0:(1514130)24互连网络的特性参数主要特性参数有：网络规模网络规模:结点度结点度:距离距离网络直径网络直径结点间线长结点间线长等分宽度等分宽度对称性对称性25网络规模：网络规模：网络

13、中结点个数，表示该网络所能连接的部件多少。结点度：结点度：与结点相连接的边数(通道数)。进结点的边数叫入度，出结点的边数叫出度。结点度结点度=出度+入度距离：距离：两个结点之间相连的最少边数。网络直径：网络直径：网络中结点间距离的最大值，可用结点间的连接边数表示。结点间线长：结点间线长：结点间连线的长度，用米、公里等表示。互连网络的特性参数26等分宽度等分宽度:把把N个结点个结点构成的网络切成结点数构成的网络切成结点数相同（相同（N/2）的两半，在各种切法中，沿切的两半，在各种切法中，沿切口边数的最小值。口边数的最小值。反映网络内部传输带宽。线等分宽度线等分宽度：传输带宽与通道宽度w(位)的乘

14、积，Bbw。反映网络最大流量。对称性对称性：从任何结点，拓扑结构都相同的网络称为对称网络。对称网络容易编程和实现。结点上的负载量分布均匀。互连网络的特性参数275.2.1静态互连网络静态互连网络 静态网络静态网络：指各节点（处理单元）间有着固定或专用的连接通路的网络网络。在程序执行中，节点到节点的链接保持（或网络）保持不变。静态网络中，每个开关元件固定地与一个结点相连，或分散在每个节点的内部（看不到开关元件），直接实现两结点之间的通信。一般是简单的、通信模式可预测的网络系统。5.2互连网络的结构互连网络的结构互连网络可分为静态静态和动态动态互连网络。28静态互连网络从不同的角度对静态互连网络进

15、行分类1）按通路类型共享（总线型）通路：非共享通路：2)按拓扑维数所谓维数n，指网络画在n维空间时才能保证各条链路不会相交。3)按网络形状总线型、线型、环型、立方体型、树型、全连接等。4)按度数29典型的静态网络N个结点的线形网（规模），有N-1条链路，距离的最大值为N-1（直径），度为2，等分宽度为1。一维，不对称（？）。简单，N很大时，通信效率很低。1.线形网302.环形网N个结点的环，有双向环和单向环。双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。313.带弦环图为（12个结点）带弦双向环结点度为3：链路数为18，

16、直径4（红色结点），度为3，不对称，等分宽度为2。结点度为4：链路数为24，直径3（红色结点），度为4，对称，等分宽度为8。度为3的带弦环度为4的带弦环324.全链接全链接中的每个结点和其他结点之间都有单一的直接链路。带弦环的一种特殊情形。下图中8个结点的全链接：28条链路，直径1，度为7，对称，等分宽度16。全连接网络是最复杂的拓扑结构，每个结点同其他结点都连接，直径为1，度数是(N-1)。335.树形4层的二叉树K层完全二叉树有N=2K-1个结点，中间层结点的结点度为3，直径为2（K-1）。不对称，等分度为1。树形网是一种容易扩展的系统结构。根部结点和连到根部链路上的负载量较大，为系统的瓶

17、颈。34树形的扩展：带环树二叉胖树两种结构可以缓解根结点的瓶颈问题。356.星形星形实际上是一种二层树（如右图）。N个结点的星形网络，有N-1条链路，直径为2，最大结点度为N-1，非对称（？），等分宽度为1。367.网格N个结点的rr网格，有2N-2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。二维环形拓扑结构37网格的变形-Illiac网：N个结点的rr网格2N条链路（？），直径为r-1，结点度为4。-网格结构扩充性好，易在VLSI芯片上实现。每行尾与下一行的头，每列尾与下一列的头相接-网格卷绕网格卷绕。38网格的变形-搏动式阵列（SystolicArray）398.超立方

18、体0维-立方体1维-立方体2维-立方体3维-立方体4维-立方体n-立方体由N=2n个结点构成。直径为n，结点度为n，对称。结点度随维数线性增加。特点：相邻的结点编号只差一位409.带环立方体（CCC）一个带环n-立方体，由N=2n个结点环构成，每个结点环是一个有n个结点的环，结点总数为n2n个。直径通常为2n，结点度为3，对称。带环3-立方体41静态网络特性比较425.2.2动态互连网络动态互连网络动态网络动态网络(dynamicNetworks)通常由交换开关构成互联网络的，可按运行程序的要求改变网络的网络的连接状态。特点：网络中开关元件可以控制（有源）。链路可通过设置开关的状态来重构。网络

19、边界上的开关元件可与处理机相连。有总线网络、多级网络和交叉开关网络等。431总线系统总线系统总线是一组公用通信通路，通过导线和插座把各台处理机、存储模块和外围设备与总线连接起来。总线是一组公用通信通路，通过导线和插座把各台处理机、存储模块和外围设备与总线连接起来。组成：处理机、存储模块、局部Catch、I/O部件和外围设备等。总线结构在并行处理机系统有重要地位。44总线系统一般特点总线系统一般特点处理机、存储模块和外围设备均与总线相连，分时工作。价格低。每台处理机都能访问公共总线，有局部catch。处理机通过请求访问全局存储器。多请求下总线仲裁逻辑将总线分配给一个请求。局部Catch数据修改和

20、通信执行“一致性协议”存在总线和共享存储器两大瓶颈。主要问题：总线仲裁、中断处理、一致性协议和总线事务处理（带宽窄）。总线复杂性由总线上连接的分接头数n与数据通路宽度w的和w+n决定.45多级网络多级网络单级网络：由一级开关和一种连接模式构成的互联。多级网络则包含多级开关和多级连接模式。每一级都用多个ab开关，通过动态设置开关状态，改变或建立输入和输出对之间的连接。相邻级开关间有固定的级间连接（ISC)。ab开关:a个输入和b个输出。a和b常为2的整数幂级控制、单元控制、部分级控制级控制、单元控制、部分级控制三种控制方式。46控制方式指对各个开关模块进行控制的方法。(1)级控制级控制每一级所有

21、开关只用一个控制信号控制，该级所有开关处于同一种状态；(2)单元控制单元控制每个开关都有单独的控制信号，各自可处于不同的状态；(3)部分级控制部分级控制第i级的所有开关分别用i+1个信号控制，控制信号随级数增加而递加。级间连接(ISC)模式：均匀洗牌、蝶式、交换常用开关模块：22，44，88。多级互连网络控制方式47【例】【例】Omega网络88Omega网络，3级。22开关。级数一般为logkn网络左侧有8个输入，右侧有8个输出。级间连接(ISC)是对8个对象的均匀洗牌模式。控制开关状态可实现从输入到输出的多种连接。交叉开关复杂性O(nlogkn)w)。w是MIN设计中链路宽度。(假设k*k

22、开关为基本构件)。48Omega网络构造Omega网络的22开关的四种连接方式：直通、交叉、上播和下播。开关模块及状态：上播和下播不能构成置换（允许一个输入连接两个输出）49【例【例4】一个多级立方体网采用二功能开关和交换函数构成，其拓扑结构如图所示。使交换开关的设置处于某一种工作状态，可以得到的不同的多级互连网络。(1)当所有开关都直通时，实现恒等变换；(2)当A、B、C、D四个开关交换，其余直通时实现C；(3)当E、F、G、H四个开关交换，其余直通时实现C1；(4)当I、J、K、L四个开关交换，其余直通时实现C2。50交叉开关网络交叉开关网络可看作单级开关网络。带宽和互连特性最好。交叉点能

23、在(源，目的)之间动态连接，每个交叉点开关根据程序要求动态设置“开”或“关”。如图是多处理机中处理机-存储器间的交叉开关网络。51交叉开关网络交叉开关网络在处理机和存储模块间用交叉开关网络构成一个共享存储型多处理机，实际是一个存储器访问网络。支持并行(或交叉)存储器访问。每个处理机可同时访问不同的存储模块。同时接通几个交叉点开关。每个存储模块一次只能满足一台处理机的请求。每一列只能接通一个交叉点开关。在多个请求同时到达同一存储模块时，交叉开关要分解所发生的冲突。每台处理机可能会产生一系列地址，同时访问多个存储模块。52向量并行处理机(VPP500)采用大型交叉开关网络。PE为带存储器的处理机，

24、CP代表控制处理机。网络中，每行和一列只能接通一个交叉点开关。处理机间的交叉开关实现处理机之间的置换连接（一对一）。n*n交叉开关网络一次最多可连通n个(源，目的)处理机对。53三种动态网络比较三种动态网络比较1)硬件复杂性硬件复杂性总线互连成本低。连线复杂性由数据总线和地址总线的宽度决定。地址线可为数据总线的一部分。256根数据线和64根地址线代表当今总线的设计水平。总线互连开关的硬件复杂性随分接头数n和数据通路宽w两者线性增加。交叉开关复杂性随n*nw乘积而增大，其中n*n对应交叉开关中的交叉点数，w是交叉开关中的通路宽度。多级网络(MIN)，硬件复杂性函数为O(nlogkn)w)，复杂性

25、位于总线和交叉开关网络之间。总线、多级网络、交叉开关硬件复杂性呈增加趋势。542）处理器带宽）处理器带宽总线系统中总线系统中n个处理器竞争个处理器竞争总线带宽总线带宽。假设时。假设时钟频率为钟频率为f，则总线的每个处理器，则总线的每个处理器带宽带宽在函数在函数O(wf/n)和和O(wf)范围内变化。范围内变化。MIN和交叉开关具有较宽的处理器带宽，该带和交叉开关具有较宽的处理器带宽，该带宽随函数宽随函数O(wf)线性变化。线性变化。在多级网络中，数据传输要经过在多级网络中，数据传输要经过多级开关，多级开关，总总线和交叉开关只需线和交叉开关只需较少时间较少时间(1或或2周期周期)来来传输传输单位数据。单位数据。交叉开关具有最高的处理器带宽。交叉开关具有最高的处理器带宽。总线、多级网络、交叉开关的处理器带宽呈增加趋势。553聚集带宽聚集带宽聚集带宽聚集带宽物理概念是：在一个给定的网络中，从一半结点到另一半结点，每秒传输信息的最大位数。结论：多级网络（MIN）比总线或交叉开关互连具有更大的聚集带宽聚集带宽。564.动态网络比较动态网络比较表汇总了构成动态网络的总线、多级网络、交叉开关的主要特性。表5.3动态网络的复杂性和带宽性能一览表