《互联网络》PPT课件

《《互联网络》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1第五章互连网络互连网络是现代计算机系统中的一个核心部分和关键部件。对整个计算机系统的性能有着决定性影响。随着系统规模、通信要求和线路复杂性的增加,其重要性在不断增长。已经成为计算机组织和系统结构中独立的研究内容。5.3路由选择和信息传递方式5.4流量控制策略和通信模式5.1互连网络的相关概念5.2互连网络的结构25.1互连网络的相关概念一、互连网络的组成1、互连网络(IN)定义由开关元件按照一定拓扑结构和控制方式构成的网络，实现多个节点对之间的相互连接。互连网络已成并行计算机系统中重要的核心部件。根据需要，有P→P及P←→M

2、的连接形式互连网络IN···P互连网络INPPMPPPM······32、互连网络(IN)的特性*特性1：同时实现多个端口对的互连及通信。*特性2：具有多种并行端口对的互连方式.*互连网络与总线比较：互连网络:强调多个节点对之间的互连及通信。总线:多个设备或单元所共享的公共通道(分时)理论上有N!种端口对互连排列方式42、互连网络要素：开关元件、互联结构、控制方式。互联结构：网络合理布局关键因素，反映系统结构特征。用有向图或无向图表示，节点对应开关元件或处理机。边对应通信链路。开关元件：网络中最基本模块，在不同系统和控制中，开

3、关元件所处的物理位置和工作状态不同。控制方式：网络中各种开关的控制方法3、互连网络的特征1)拓扑结构静态动态2)控制策略集中式分散式3)定时方式同步异步4)交换方法线路交换分组交换5互连网络的特征1)拓扑结构:分静态和动态两种。静态网:各节点间有专用通信线路（链路），运行间不改变或重新组合。又称直接网络(节点通过链路直接连接)组成：由链路、结构及网络节点组成。结构:线性、环形、树形、立方体等。6动态网:链路可通过设置网络中开关重新组合。节点与节点的连接由程序或控制信号动态地改变，又称间接网络(节点与交换开关连接)。组成：由链路

4、、结构、开关及节点组成。结构:总线、环状、开关、(单)多级。动态网:7互连网络的特征2)控制策略:集中控制:全局控制器接收所有通信请求，设置互连网络的开关连接。分散控制:通信请求和开关设置由互连网络分散地进行。3)定时方式：同步系统：系统使用一个集中的统一时钟.异步系统：无统一时钟，节点根据各自情况独立工作。4)交换方法:线路交换和分组交换。线路交换：源结点和目的结点间的物理通路在整个数据传送期间一直保持连接。分组交换：信息分割成组(包)，各组(包)通过多个不同路径传分别送入互连网络。传送不存在一个实际连接的固定通路。85.1

5、.2互连网络的描述根据输入与输出结点之间的对应关系，有以下表示方法：函数表示法变量x表示输入，函数f(x)表示输出，建立输入与输出端的一一对应关系。自变量和函数常用二进制、十进制表示。互连函数反映网络输入数组和输出数组之间对应的排列关系，也称排列函数。输入输出对应表示法图形表示法用图形表示输入端与输出端之间的一一对应关系循环表示法：如(04)(15)(26)(37)9互连函数数的排列：N个数的每一种有确定次序的放置方法叫做一个N排列。一般有N！种放置方法。网络排列：N输入、N输出端网络中，输入端和输出端的放置方法分别为一种排列

6、。置换：把一个N排列变成另一个N排列的变换叫N阶置换。表示输入端和输出端的连接关系.复杂的置换方式可用少量基本的互联函数表示10基本的互联函数恒等函数:输入端与输出端一一对应,且编号相同。Xn-1Xn-2XkX0是PE的地址（通常为二进制）。n为3时的恒等函数的连接情形如下：(0)(1)(2)(3)(4)(5)(6)(7)11交换函数交换函数:函数形式为主要用于超立方体互联网络中。超立方体由n个交换函数组成。K=1二进制地址编码下，某一位的输入与输出端编号相反。0kn12当n=3，结点数N＝8时，可得到3立方体互连函数

7、：互连函数变换图形交换函数典型的立方体网络结构图(01)(23)(45)(67)(02)(13)(46)(57)(04)(15)(26)(37)13均匀洗牌函数把输入端二进制地址循环左移一位。表示为：逆均匀洗牌函数:输入端二进制地址循环右移一位。函数：(0)(124)(365)(7)将输入端分成数目相等的两半，前一半和后一半按序一个隔一个，从头依次与输出端相连，类似洗牌方式。14均匀洗牌函数均匀洗牌函数逆均匀洗牌函数均匀洗牌与开关多级组合起来可构成Omega网络15蝶式函数蝶式函数:输入二进制地址的最高位和最低位互换位置，定义

8、为：N=8的蝶式函数变换图形均匀洗牌，蝶式函数不能单独实现任意结点间互连。它们与交换函数多级组合是构成复杂多级网络的基础例如:均匀洗牌函数与Cube0的组合(0)(2)(14)(36)(5)(7)16反位序函数反位序函数:输入端二进制地址的位序颠倒过来求得相应输出端的地址。其