多处理机-互连网络教学课件.ppt

1、7.4 互连网络 互连网络是将集中式系统或分布式系统中的结点连 接起来所构成的网络。在拓扑上，互连网络为输入和输出两组结点之间提 供一组互连或映象。本节介绍：构造多处理机的互连网络第章 多处理机虚拟存储器的特点17.4.1 互连网络的性能参数1.互连网络的拓扑结构 (1)静态网络 由点和点直接相连而成，这种连接方式在由点和点直接相连而成，这种连接方式在 程序执行过程中不会改变。程序执行过程中不会改变。(2)动态网络 用开关通道实现，可动态地改变结构，用开关通道实现，可动态地改变结构，使其与用户程序中通信要求匹配。使其与用户程序中通信要求匹配。7.4 互连网络虚拟存储器的特点22.性能参数 (1

2、)网络规模：结点数 (2)结点度：与结点相连接的边的数目。入度：入度：进入结点的通道数进入结点的通道数 出度：出度：从结点出来的通道数从结点出来的通道数 (3)网络直径 网络中任意两个结点间最短路径长度的最大值。(4)等分宽度 在将某一网络切成相等两半的各种切法中，沿切口的最小通道边数。7.4 互连网络虚拟存储器的特点3q 对称网络对称网络 从其中的任何一个结点看，拓扑结构都是一样的。从其中的任何一个结点看，拓扑结构都是一样的。(5)路由 在网络通信中对路径的选择与指定。3.互连函数 如果把互连网络的N个入端和N个出端各自用 整数0，1，N-1代表，则互连函数表示互连的 出端号和入端号的一一对

3、应关系。7.4 互连网络虚拟存储器的特点44.几种数据路由功能 (1)循环 若把互连函数若把互连函数f(x)f(x)表示为：表示为：(x(x0 0,x,x1 1,x,x2 2,x,xj j)则代表对应关系为：则代表对应关系为：f(xf(x0 0)=x)=x1 1,f(x,f(x1 1)=x)=x2 2,f(x,f(xj j)=x)=x0 0 j+1j+1称为该称为该循环的周期循环的周期。(2)置换 指对象的重新排序。对于指对象的重新排序。对于n n个对象来说，个对象来说，有有n!n!种置换。种置换。7.4 互连网络虚拟存储器的特点5 例如例如 置换置换=(a,b,c)(d,e)=(a,b,c)

4、(d,e)表示了置换映射：表示了置换映射：f(a)=b,f(b)=c,f(c)=a,f(d)=ef(a)=b,f(b)=c,f(c)=a,f(d)=e和和f(e)=df(e)=d。这里循环这里循环(a,b,c)(a,b,c)周期为周期为3 3，循环，循环(d,e)(d,e)周期为周期为2 2。(3)均匀混洗 n=8（对象个数）的均匀混洗所对应的映射与其逆过程 对对n=2n=2k k个对象均匀混洗，可用个对象均匀混洗，可用k k位二进制数位二进制数 x=(xx=(xk-1k-1,x,x1 1,x,x0 0)表示定义域中的每个对象表示定义域中的每个对象均匀混洗将均匀混洗将x x映射到映射到f(x)

5、f(x)，得到：，得到：f(x)=(xf(x)=(xk-2k-2,x,x1 1,x,x0,0,x xk-1k-1)（将（将x x循环左移循环左移1 1位）位）7.4 互连网络虚拟存储器的特点6虚拟存储器的特点7(4)超立方体路由功能 例例 一个三维二进制立方体网络 7.4 互连网络虚拟存储器的特点8q 根据最低位根据最低位C C0 0路由路由 q 根据中间位根据中间位C C1 1路由路由q 根据最高位根据最高位C C2 2路由路由 一个一个n n维超立方体共有维超立方体共有n n种路由功能，分别由种路由功能，分别由n n位地位地址中的每一位求反位值来确定。将址中的每一位求反位值来确定。将x=(

6、xx=(xk-1k-1,x,x1 1,x,x0 0)映映射到射到f(x)f(x)，得到，得到f(x)=(xf(x)=(xk-1k-1,x,xk k,x,x1 1,x,x0 0)。有三种路由功能:分别根据结点的二进制地址（C2 C1 C0）中的某一位来确定7.4 互连网络虚拟存储器的特点9虚拟存储器的特点10 (5)广播和选播 q 广播广播 一对全体的映射。一对全体的映射。q 选播选播 一个子集到另一子集一个子集到另一子集(多对多多对多)的映射。的映射。5.影响互连网络性能的因素 (1)功能特性 网络如何支持路由、中断处理、同步、请网络如何支持路由、中断处理、同步、请 求消息组合和一致性。求消息

7、组合和一致性。7.4 互连网络虚拟存储器的特点11(2)网络时延 单位消息通过网络传送时最坏情况下的时间延迟。单位消息通过网络传送时最坏情况下的时间延迟。(3)带宽 通过网络的最大数据传输率，用通过网络的最大数据传输率，用MBMBs s表示。表示。(4)硬件复杂性 诸如导线、开关、连接器、仲裁和接口逻辑等诸如导线、开关、连接器、仲裁和接口逻辑等 的造价。的造价。(5)可扩展性 在增加机器资源使性能可扩展的情况下，网络在增加机器资源使性能可扩展的情况下，网络 具备模块化可扩展的能力。具备模块化可扩展的能力。7.4 互连网络虚拟存储器的特点127.4.2 静态连接网络1.线性阵列 一种一维的线性网

8、络，其中N个结点用N-1个链 路连成一行。q 内部结点度：内部结点度：2 2q 端结点度：端结点度：1 1q 直径：直径：N-1N-1q 等分宽度等分宽度b=1b=17.4 互连网络132.环和带弦环 (1)环 用一条附加链路将线性阵列的两个端点连接起 来而构成的。可以单向工作，也可以双向工作。q 结点度：结点度：2 2q 双向环的直径：双向环的直径：N N2 2q 单向环的直径：单向环的直径：N N7.4 互连网络虚拟存储器的特点14(2)(2)带弦环 增加的链路愈多，结点度愈高，网络直径就愈小。7.4 互连网络虚拟存储器的特点15全连接网络q 结点度结点度:N-1:N-1q 直径最短，为直

9、径最短，为1 17.4 互连网络163.循环移数网络 通过在环上每个结点到所有与其距离为2的整 数幂的结点之间都增加一条附加链而构成的。q 结点数结点数:16:16q 结点度结点度:7:7q 直径直径:2:27.4 互连网络虚拟存储器的特点17 如果如果j-ij-i=2=2 r r，r=0,1,2,r=0,1,2,n-1,n-1，网络规模，网络规模N=2N=2n n，则结点，则结点i i与结点与结点j j连接。这种循环移数网络的结连接。这种循环移数网络的结点度为点度为d=2n-1d=2n-1，直径，直径D=nD=n2 2。7.4 互连网络虚拟存储器的特点184.树形和星形 (1)一棵5层31个

10、结点的二叉树 一般说来，一棵k层完全平衡的二叉树有 N=2k-1个结点。最大结点度是3，直径是2(k-1)。(2)星形q 一种一种2 2层树层树q 结点度较高，为结点度较高，为d=N-1d=N-1q 直径较小，是一常数直径较小，是一常数2 27.4 互连网络虚拟存储器的特点197.4 互连网络205.5.胖树形胖树形7.4 互连网络虚拟存储器的特点216.网格形和环网形 (1)一个33网格形网络 一般说来，N=nk 个结点的k维网络的内 部结点度为2k，网络直径为k(n-1)。边结 点和角结点的结点度分别为3或2。(2)环形网 可看做是直径更短的另一种网格 环形网沿阵列每行和每列都有环形连接

11、一个nn二元环网q 结点度为结点度为4 4q 直径为直径为2 2*n/2n/2 7.4 互连网络虚拟存储器的特点227.4 互连网络237.超立方体 一种二元n-立方体结构 一般说来，一个n-立方体由N=2n 个结点组成，它们分布在n维上，每维有两个结点。例例8 8个结点的个结点的3-3-立方体立方体 4-4-立方体立方体 一个n-立方体的结点度等于n，也就是网络的 直径。7.4 互连网络虚拟存储器的特点247.4 互连网络258.k元n-立方体网络 环形、网络形、环网形、二元n-立方体(超立方 体)等网络都是k元n-立方体网络系统的拓扑同构体。参数n:立方体的维数 k:基数或者说是沿每个方向

12、的结点数(多重性)。N=kn,(n=logkN)K K元元n-n-立方体的结点可用基数为立方体的结点可用基数为k k的的n n位地址位地址 A=aA=a0 0a a1 1a a2 2a an-1n-1来表示，其中来表示，其中a ai i代表第代表第i i维结点的位置。维结点的位置。按照惯例，低维按照惯例，低维k k元元n-n-立方体称为环网，而高维二立方体称为环网，而高维二 元元n-n-立方体则称为立方体则称为超立方体。7.4 互连网络26例例一种一种4 4元元3-3-立方体网络立方体网络7.4 互连网络277.4.3 动态连接网络 1.动态互连网络的三个主要操作特征 定时 开关 控制2.2.

13、根据级间连结方式，动态互连网络分为 (1)单级网络 也称循环网络 (2)多级网络 由一级以上的开关元件构成。这类网络可以把任一输入与任一输出相连。7.4 互连网络28 阻塞网络 如果同时连接多个输入输出对时如果同时连接多个输入输出对时,可能会引可能会引 起开关和通信链路使用上的冲突。起开关和通信链路使用上的冲突。大多数多级网络都是阻塞网络。大多数多级网络都是阻塞网络。非阻塞网络 如果多级网络通过重新安排连接方式可以如果多级网络通过重新安排连接方式可以 建立所有可能的输入输出之间的连接。建立所有可能的输入输出之间的连接。7.4 互连网络29q 总线仲裁总线仲裁q 中断处理中断处理q 一致性协议一

14、致性协议q 总线事务的处理总线事务的处理3.几类主要的开关网络 (1)总线系统 优点：价格较低 带宽较窄 缺点：容易产生故障 总线研制中的重要问题7.4 互连网络30 一种总线连接的多处理机系统 31(2)交叉开关网络 单级无阻塞置换网络 每个交叉点是一个可以打开或关闭的开关，提供源(处理器)和目的(存储器)之间点对点 的连接通路。交叉点开关网络中n对处理器可以同时传送 数据。交叉开关网络的带宽和互连特性最好。一种交叉开关网络 7.4 互连网络327.4 互连网络33(3)多端口存储器 主要思想主要思想 将所有交叉点仲裁逻辑和跟每个存储器模将所有交叉点仲裁逻辑和跟每个存储器模 块有关的开关功能

15、移到存储器控制器中。块有关的开关功能移到存储器控制器中。多端口存储器结构是一个折衷方案，它介于低多端口存储器结构是一个折衷方案，它介于低 成本低性能的总线系统和高成本高带宽的交叉成本低性能的总线系统和高成本高带宽的交叉 开关系统之间。开关系统之间。缺点缺点q 十分昂贵十分昂贵q 不能扩展不能扩展q 当系统配置很大时，需要大量的互连电缆和连接器当系统配置很大时，需要大量的互连电缆和连接器。7.4 互连网络34 用于多处理机系统的用于多处理机系统的多端口存储器结构多端口存储器结构35(4)多级网络 多级网络可用于构造大型多处理机系统。一种通用多级网络一种通用多级网络 各种多级网络的区别就在于所用开关模各种多级网络的区别就在于所用开关模 块和级间连接模式的不同。块和级间连接模式的不同。7.4 互连网络36 由由a ab b开关模块和级间构成的通用多级互连网络结构开关模块和级间构成的通用多级互连网络结构37 2 22 2开关四种可能的连接方式开关四种可能的连接方式 OmegaOmega网络网络 7.4 互连网络38 一个一个161616 Omega16 Omega网络网络39