互联网络课件

互联网络PPT课件1第五章第五章 互连网络互连网络 互连网络互连网络是是现代计算机系统中的一个核心部分和关键部现代计算机系统中的一个核心部分和关键部件。对整个计算机系统的性能有着决定性影响。随着系统件。对整个计算机系统的性能有着决定性影响。随着系统规模、通信要求和线路复杂性的增加规模、通信要求和线路复杂性的增加,其重要性在不断增长。其重要性在不断增长。已经成为计算机组织和系统结构中独立的研究内容。已经成为计算机组织和系统结构中独立的研究内容。 5.3 路由选择和信息传递方式路由选择和信息传递方式 5.4 流量控制策略和通信模式流量控制策略和通信模式 5.1 互连网络的相关概念互连网络的相关概念 5.2 互连网络的结构互连网络的结构 互联网络PPT课件25.1 互连网络的相关概念互连网络的相关概念一、互连网络的组成一、互连网络的组成1 1、互连网络、互连网络( (IN) )定义定义由由开关元件开关元件按照一定按照一定拓扑结构拓扑结构和和控制方式控制方式构成的网络，实现多构成的网络，实现多个节点对之间的相互连接。个节点对之间的相互连接。互连网络互连网络已成并行计算机系统中重要的核心部件。已成并行计算机系统中重要的核心部件。 根据需要，根据需要，有有PPPP及及PMPM的的连接形式连接形式互连网络互连网络INP互连网络互连网络INPPMPPPM互联网络PPT课件32 2、互连网络、互连网络(IN)(IN) 的特性的特性 * *特性特性1 1：实现实现多个端口对多个端口对的互连及通信。的互连及通信。 * *特性特性2 2：具有具有并行端口对的并行端口对的互连方式互连方式. . * *互连网络与总线比较：互连网络与总线比较：互连网络互连网络 : 强调强调多个多个节点对节点对之间的互连及通信。之间的互连及通信。总总 线线 : : 多个设备或单元所共享的多个设备或单元所共享的公共公共通道通道( (分时分时) ) 理论上有理论上有N!种种端口对端口对互连排列互连排列方式方式互联网络PPT课件42、互连网络要素互连网络要素：开关元件、互联结构、控制方式开关元件、互联结构、控制方式。 互联结构互联结构：网络合理布局关键因素，反映系统结构：网络合理布局关键因素，反映系统结构特征。用特征。用有向图有向图或或无向图无向图表示，表示，节点节点对应对应开关元件开关元件或或处理机处理机。边边对应对应通信链路通信链路。 开关元件开关元件：网络中最基本模块，在不同系统和控制：网络中最基本模块，在不同系统和控制中，开关元件所处的中，开关元件所处的物理位置物理位置和和工作状态工作状态不同。不同。 控制方式控制方式：网络中：网络中各种开关各种开关的控制方法的控制方法3 、互连网络的特征、互连网络的特征 1) 拓扑结构拓扑结构 静态 动态 2) 控制策略控制策略 集中式 分散式 3) 定时方式定时方式 同步 异步 4) 交换方法交换方法 线路交换 分组交换互联网络PPT课件5 互连网络的特征互连网络的特征 1) 拓扑结构拓扑结构: 分分静态和动态两种。 静态网:各节点节点间有专用通信线路（链路），运行间不改变或重新组合。又称又称直接网络 (节点通过链路直接连接节点通过链路直接连接) 组成：由链路、结构及网络节点节点组成。 结构: 线性、环形、树形、 立方体等。 互联网络PPT课件6 动态网: 链路可通过设置网络中开关重新组合。节点与节点与节点的连接节点的连接由程序或或控制信号动态地改变，又称动态地改变，又称间接网络(节点与交换开关连接节点与交换开关连接)。 组成：由链路、结构、开关及节点节点组成。 结构: 总线、环状、 开关、(单)多级。 动态网: 互联网络PPT课件7互连网络的特征互连网络的特征 2)控制策略控制策略: 集中控制:全局控制器接收所有通信请求，设置互连网络的开关连接。 分散控制: 通信请求和开关设置由互连网络分散地进行。 3)定时方式定时方式 ： 同步系统：系统使用一个集中的统一时钟. 异步系统：无统一时钟，节点根据各自情况独立工作。 4)交换方法交换方法: 线路交换和分组交换。 线路交换：源结点和目的结点间的物理通路在整个数据传送期间一直保持连接。 分组交换：信息分割成组(包)，各组(包)通过多个不同路径传分别送入互连网络。传送不存在一个实际连接的固定通路。 互联网络PPT课件85.1.2 互连网络的描述 根据输入与输出结点之间的对应关系，有以下表示方法：根据输入与输出结点之间的对应关系，有以下表示方法： 函数表示法函数表示法 变量x表示输入，函数f(x)表示输出，建立输入与输出端的一一对应关系。 自变量和函数常用二进制、十进制表示。互连函数反映网络输入数组和输出数组之间对应的排列关系，也称排列函数排列函数。 输入输出对应表示法输入输出对应表示法 图形表示法图形表示法 用图形表示输入端 与输出端之间的一一对应关系 循环表示法：如循环表示法：如(0 4)(1 5)(2 6)(3 7)互联网络PPT课件9 互连函数 数的排列：N个数的每一种有确定次序的放置方法叫做一个N排列。一般有N！种放置方法。 网络排列：N输入、N输出端网络中，输入端和输出端的放置方法分别为一种排列。 置换：把一个N排列变成另一个N排列的变换叫N阶置换。表示输入端和输出端的连接关系. 复杂的置换方式可用少量基本的互联函数表示互联网络PPT课件10基本的互联函数 恒等函数:输入端与输出端一一对应,且编号相同。 Xn-1 Xn-2Xk X0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：(0)(1)(2)(3)(4)(5)(6)(7)互联网络PPT课件11交换函数 交换函数:函数形式为 主要用于超立方体互联网络中。 超立方体由n个交换函数组成。 K=1二进制地址编码下，某一位的输入与输出端编号相反。00123456712345670kn互联网络PPT课件12 当n=3，结点数N8时，可得到3立方体互连函数： 互连函数变换图形交换函数交换函数典型的立方体网络结构图(0 1) (2 3 ) (4 5) (6 7) (0 2)(1 3 ) (4 6) (5 7) (0 4)(1 5) (2 6) (3 7) 互联网络PPT课件13均匀洗牌函数均匀洗牌函数 把输入端二进制地址循环左移一位。表示为： 逆均匀洗牌函数逆均匀洗牌函数: 输入端二进制地址循环右移一位。函数： (0)(1 2 4)(3 6 5)(7)将输入端分成数目相等的两半，前一半和后一半按序一个隔一个，从头依次与输出端相连，类似洗牌方式。互联网络PPT课件14均匀洗牌函数均匀洗牌函数均匀洗牌函数逆均匀洗牌函数均匀洗牌与开关多级组合起来可构成Omega网络互联网络PPT课件15蝶式函数蝶式函数 蝶式函数蝶式函数: 输入二进制地址的最高位和最低位互换位置，定义为： N=8的蝶式函数变换图形均匀洗牌，蝶式函数不能单独实现任意结点间互连。它们与交换函数多级组合是构成复杂多级网络的基础例如 : 均匀洗牌函数与Cube0的组合(0)(2)(1 4) (3 6)(5)(7)互联网络PPT课件16 反位序函数反位序函数 反位序函数反位序函数: 输入端二进制地址的位序颠倒过来求得相应输出端的地址。其互连函数表示如下： 对于N=8的情况，图形见图5.4（b）互联网络PPT课件17 PM2I移数函数移数函数 移数函数的一般形式为： 如k=2 PM2I函数（加减2i）是一种特殊移数函数移数函数，将输入端数组的十进制编号循环移动特定的位置向输出端传输。 N个结点的移数函数表示为： 如i=1 设 N为结点数。n=log2 N ； 0 xN1，0in1， 共有2n个互连函数0012345671234567(0 2 4 6)(1 3 5 7)互联网络PPT课件18N=8的PM2I函数的变换图形。 (a) PM2： (0 1 2 3 4 5 6 7) (b) PM21： (0 2 4 6) (1 3 5 7)(c) PM2+2： (0 4)(1 5)(2 6)(3 7)实质为1,2,4个环型网移数函数可构成环型网(单向环网、双向环网)、方格网、移数网互联网络PPT课件19课堂练习设PM2I网络有8个结点，写出所有PM2I函数的输入输入输出对表示输出对表示，画出PM21、PM22互连网络的连接图。互联网络PPT课件20【例【例 】设PM2I网络有8个结点，写出所有PM2I函数的，画出PM21、PM22互连网络的连接图。 解解 N=8，则n =3，所以i=0,1,2;j=0,1,7。 根据公式 6个PM2I函数如下： PM2：(0 1 2 3 4 5 6 7) PM2：(7 6 5 4 3 2 1 0) PM21：(0 2 4 6)(1 3 5 7) PM21：(6 4 2 0)(7 5 3 1) PM2 2：(0 4)(1 5)(2 6)(3 7) PM2 2 ：(4 0)(5 1)(6 2)( 7 3)PM2PM2互联网络PPT课件21 PM21：(0 2 4 6)(1 3 5 7) PM21互连网络的连接图。 互联网络PPT课件22(c) PM22：(0 4)(1 5)(2 6)(3 7) (4 0)(5 1)(6 2)(7 3) PM22互连网络的连接图 互联网络PPT课件23【例】【例】Illiac 阵列计算机：采用PM20和PM2n/2四个移数网络构成处理器的连接。16个结点的Illiac 网络表示 PM22：(0 4)(1 5)(2 6) (3 7) (4 8)(5 9)(6 10)(7 11) (8 12)(9 13)(10 14)(11 15) (0 12)(1 13)(2 14) (3 15) PM2+0:( 0 1 2 15 ) PM2-0:( 15 14 13 0 ) 互联网络PPT课件245.1.3互连网络的特性参数 主要特性参数有： 网络规模网络规模: 结点度结点度: 距离距离 网络直径网络直径 结点间线长结点间线长 等分宽度等分宽度 对称性对称性互联网络PPT课件25 网络规模：网络规模：网络中结点个数，表示该网络所能连接的部件多少。 结点度：结点度：与结点相连接的边数(通道数)。进结点的边数叫入度，出结点的边数叫出度。 结点度结点度=出度+入度 距离：距离：两个结点之间相连的最少边数。 网络直径：网络直径：网络中结点间距离的最大值，可用结点间的连接边数表示。 结点间线长：结点间线长：结点间连线的长度，用米、公里等表示。互连网络的特性参数互联网络PPT课件26 等分宽度等分宽度:把把N个结点个结点构成的网络切成结点构成的网络切成结点数相同（数相同（N/2）的两半，在各种切法中，沿的两半，在各种切法中，沿切口边数的最小值。切口边数的最小值。反映网络内部传输带宽。 线等分宽度线等分宽度：传输带宽与通道宽度w(位)的乘积，Bbw。反映网络最大流量。 对称性对称性：从任何结点，拓扑结构都相同的网络称为对称网络。对称网络容易编程和实现。结点上的负载量分布均匀。 互连网络的特性参数互联网络PPT课件27 5.2.1 静态互连网络静态互连网络 静态网络静态网络： 指各节点（处理单元）间有着固定或专用的连接通路的网络网络。在程序执行中，节点到节点的链接保持（或网络）保持不变。 静态网络中，每个开关元件固定地与一个结点相连，或分散在每个节点的内部（看不到开关元件），直接实现两结点之间的通信。 一般是简单的、通信模式可预测的网络系统。 5.2 互连网络的结构互连网络的结构 互连网络可分为静态静态和动态动态互连网络。互联网络PPT课件28静态互连网络 从不同的角度对静态互连网络进行分类1）按通路类型 共享（总线型）通路： 非共享通路：2) 按拓扑维数 所谓维数 n ，指网络画在n维空间时才能保证各条链路不会相交。3) 按网络形状 总线型、线型、 环型、立方体型、树型、全连接等。 4) 按度数互联网络PPT课件29 典型的静态网络 N个结点的线形网（规模），有N-1条链路，距离的最大值为N-1（直径），度为2，等分宽度为1。 一维，不对称（？）。 简单，N很大时，通信效率很低。1.线形网互联网络PPT课件302.环形网 N个结点的环，有双向环和单向环。 双向环：链路数为N，直径N/2，度为2，对称，等分宽度为2。 单向环：链路数为N，直径N-1，度为2，对称，等分宽度为2。互联网络PPT课件313.带弦环图为（12个结点）带弦双向环 结点度为3：链路数为18，直径4（红色结点），度为3，不对称，等分宽度为2。 结点度为4：链路数为24，直径3（红色结点），度为4，对称，等分宽度为8。度为3的带弦环度为4的带弦环互联网络PPT课件324.全链接 全链接中的每个结点和其他结点之间都有单一的直接链路。带弦环的一种特殊情形。 下图中8个结点的全链接： 28条链路，直径1，度为7，对称，等分宽度16。全连接网络是最复杂的拓扑结构，每个结点同其他结点都连接，直径为1，度数是(N-1)。 互联网络PPT课件335.树形4层的二叉树 K层完全二叉树有N = 2K - 1个结点，中间层结点的结点度为3，直径为2（K - 1）。不对称，等分度为1。树形网是一种容易扩展的系统结构。 根部结点和连到根部链路上的负载量较大，为系统的瓶颈。 互联网络PPT课件34 树形的扩展：带环树二叉胖树 两种结构可以缓解根结点的瓶颈问题。互联网络PPT课件356.星形 星形实际上是一种二层树（如右图）。 N个结点的星形网络，有N - 1条链路，直径为2，最大结点度为N - 1，非对称（？），等分宽度为1。互联网络PPT课件36Nr 7.网格 N个结点的rr网格，有2N - 2r条链路，直径为2（r-1)，结点度为4，非对称，等分宽度为r。二维环形拓扑结构互联网络PPT课件37 网格的变形-Illiac 网： N个结点的rr网格 2N条链路（？），直径为r-1，结点度为4。-网格结构扩充性好，易在VLSI芯片上实现。每行尾与下一行的头，每列尾与下一列的头相接-网格卷绕网格卷绕。 互联网络PPT课件38网格的变形-搏动式阵列（Systolic Array）互联网络PPT课件398.超立方体0维-立方体1维-立方体2维-立方体3维-立方体4维-立方体 n-立方体由N = 2n个结点构成。直径为n，结点度为n，对称。结点度随维数线性增加。特点： 相邻的结点编号只差一位 互联网络PPT课件40 9.带环立方体（CCC） 一个带环n-立方体，由N = 2n个结点环构成，每个结点环是一个有n个结点的环，结点总数为n 2n个。直径通常为2n，结点度为3，对称。带环3-立方体互联网络PPT课件41静态网络特性比较 互联网络PPT课件425.2.2 动态互连网络动态互连网络 动态网络动态网络(dynamic Networks)通常由交换开关构成互联网络的，可按运行程序的要求改变网络的网络的连接状态。 特点： 网络中开关元件可以控制（有源）。 链路可通过设置开关的状态来重构。 网络边界上的开关元件可与处理机相连。 有总线网络、多级网络和交叉开关网络等。互联网络PPT课件431 总线系统总线系统总线是一组公用通信通路，通过导线和插座把各台处理机、存储模块和外围设备与总线连接起来。总线是一组公用通信通路，通过导线和插座把各台处理机、存储模块和外围设备与总线连接起来。组成：处理机、存储模块、局部Catch、I/O部件和外围设备等。总线结构在并行处理机系统有重要地位。互联网络PPT课件44总线系统一般特点总线系统一般特点 处理机、存储模块和外围设备均与总线相连，分时工作。价格低。 每台处理机都能访问公共总线，有局部catch。 处理机通过请求访问全局存储器。多请求下总线仲裁逻辑将总线分配给一个请求。 局部Catch数据修改和通信执行“一致性协议” 存在总线和共享存储器两大瓶颈。 主要问题：总线仲裁、中断处理、一致性协议和总线事务处理（带宽窄）。 总线复杂性由总线上连接的分接头数n与数据通路宽度w的和w+n决定.互联网络PPT课件45多级网络多级网络单级网络：由一级开关和一种连接模式构成的互联。多级网络则包含多级开关和多级连接模式。 每一级都用多个ab开关，通过动态设置开关状态，改变或建立输入和输出对之间的连接。 相邻级开关间有固定的级间连接（ISC)。 ab开关: a个输入和b个输出。a和b常为2的整数幂 级控制、单元控制、部分级控制级控制、单元控制、部分级控制 三种控制方式。互联网络PPT课件46 控制方式指对各个开关模块进行控制的方法。 (1)级控制级控制 每一级所有开关只用一个控制信号控制，该级所有开关处于同一种状态； (2)单元控制单元控制 每个开关都有单独的控制信号，各自可处于不同的状态； (3)部分级控制部分级控制 第i级的所有开关分别用i+1个信号控制，控制信号随级数增加而递加。 级间连接(ISC)模式：均匀洗牌、蝶式、交换 常用开关模块：22，44，88。多级互连网络控制方式互联网络PPT课件47【例】【例】Omega网络 88 Omega网络，3级。22开关。级数一般为logkn 网络左侧有8个输入，右侧有8个输出。 级间连接(ISC)是对8个对象的均匀洗牌模式。 控制开关状态可实现从输入到输出的多种连接。 交叉开关复杂性 O(n logkn) w)。w是MIN设计中链路宽度。(假设k*k开关为基本构件)。互联网络PPT课件48Omega网络构造Omega网络的22开关的四种连接方式：直通、交叉、上播和下播。 开关模块及状态：上播和下播不能构成置换 （允许一个输入连接两个输出） 互联网络PPT课件49【例【例4】一个多级立方体网采用二功能开关和交换函数构成，其拓扑结构如图所示。使交换开关的设置处于某一种工作状态，可以得到的不同的多级互连网络。 (1)当所有开关都直通时，实现恒等变换； (2)当A、B、C、D四个开关交换，其余直通时实现C； (3)当E、F、G、H四个开关交换，其余直通时实现C1； (4)当I、J、K、L四个开关交换，其余直通时实现C2。互联网络PPT课件50 交叉开关网络交叉开关网络 可看作单级开关网络。带宽和互连特性最好。交叉点能在(源，目的)之间动态连接，每个交叉点开关根据程序要求动态设置“开”或“关”。如图是多处理机中处理机-存储器间的交叉开关网络。互联网络PPT课件51 交叉开关网络交叉开关网络 在处理机和存储模块间用交叉开关网络构成一个共享存储型多处理机，实际是一个存储器访问网络。支持并行(或交叉)存储器访问。 每个处理机可同时访问不同的存储模块。同时接通几个交叉点开关。 每个存储模块一次只能满足一台处理机的请求。每一列只能接通一个交叉点开关。 在多个请求同时到达同一存储模块时，交叉开关要分解所发生的冲突。 每台处理机可能会产生一系列地址，同时访问多个存储模块。互联网络PPT课件52向量并行处理机(VPP 500)采用大型交叉开关网络。PE为带存储器的处理机，CP代表控制处理机。网络中，每行和一列只能接通一个交叉点开关。处理机间的交叉开关实现处理机之间的置换连接（一对一）。 n*n交叉开关网络一次最多可连通n个(源，目的)处理机对。互联网络PPT课件53三种动态网络比较三种动态网络比较1) 硬件复杂性硬件复杂性 总线互连成本低。连线复杂性由数据总线和地址总线的宽度决定。地址线可为数据总线的一部分。256根数据线和64根地址线代表当今总线的设计水平。总线互连开关的硬件复杂性随分接头数n和数据通路宽w两者线性增加。 交叉开关复杂性随 n*n w乘积而增大，其中n*n 对应交叉开关中的交叉点数，w是交叉开关中的通路宽度。 多级网络(MIN)，硬件复杂性函数为O(nlogkn)w)，复杂性位于总线和交叉开关网络之间。 总线、多级网络、交叉开关硬件复杂性呈增加趋势。互联网络PPT课件542）处理器带宽）处理器带宽 总线系统中总线系统中n个处理器竞争个处理器竞争总线带宽总线带宽。假设时。假设时钟频率为钟频率为f，则总线的每个处理器，则总线的每个处理器带宽带宽在函数在函数O(wf/n)和和O(wf)范围内变化。范围内变化。 MIN和交叉开关具有较宽的处理器带宽，该带和交叉开关具有较宽的处理器带宽，该带宽随函数宽随函数O(wf)线性变化。线性变化。 在多级网络中，数据传输要经过在多级网络中，数据传输要经过多级开关，多级开关，总总线和交叉开关只需线和交叉开关只需较少时间较少时间(1或或2周期周期)来来传输传输单位数据。单位数据。 交叉开关具有最高的处理器带宽。交叉开关具有最高的处理器带宽。 总线、多级网络、交叉开关的处理器带宽呈增加趋势。互联网络PPT课件553 聚集带宽聚集带宽 聚集带宽聚集带宽物理概念是：在一个给定的网络中，从一半结点到另一半结点，每秒传输信息的最大位数。 结论：多级网络（MIN）比总线或交叉开关互连具有更大的聚集带宽聚集带宽。互联网络PPT课件564.动态网络比较动态网络比较 表5.3汇总了构成动态网络的总线、多级网络、交叉开关的主要特性。 表5.3 动态网络的复杂性和带宽性能一览表