第1页：互连网络封面
互连网络封面
互连网络
第2页：互连网络目录
互连网络目录
第3页：互连网络是一种由开关元件按照一定的拓扑结
互连网络是一种由开关元件按照一定的拓扑结
- 结点
- 处理器、存储模块或其他设备。
- 互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。
- 互连网络在系统中的位置，如图所示。
- 在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。
第4页：互连网络的基本概念：中的位置
互连网络的基本概念：中的位置
第5页：可以从4个不同的方面来描述互连网络
可以从4个不同的方面来描述互连网络
- 定时方式
- 有同步和异步两种。
- 交换方法
- 有线路交换和分组交换两种。
第6页：这些数据包可以通过不同的路径传送
这些数据包可以通过不同的路径传送
- 控制策略
- 有集中式和分散式两种
- 这些数据包可以通过不同的路径传送，到达目的结点后再拼合成原来的数据。
- 结点之间不存在固定连接的物理通路。
第7页：互连网络的基本概念：拓扑结构
互连网络的基本概念：拓扑结构
- 拓扑结构
- 有静态和动态两种。
第8页：输入（设x=0，1，
输入（设x=0，1，
- 输入（设x=0，1，…，N－1）函数f(x)
- 输出通过数学表达式建立输入端与输出端的一一对应关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。
- 互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。（有时也称为置换函数或排列函数）
第9页：互连函数f(x)有时可以采用循环表示即
互连函数f(x)有时可以采用循环表示即
- 互连函数f(x)有时可以采用循环表示即
- （x0x1x2…xj-1）表示：f(x0)=x1，f(x1)=x2，…，f(xj-1)=x0j称为该循环的长度。几种常用的基本互连函数及其主要特征：1.交换函数
- 交换函数
- 实现二进制地址编码中第k位互反的输入端与输出端之间的连接。
第10页：主要用于构造立方体互连网络和各种超立方体
主要用于构造立方体互连网络和各种超立方体
- 主要用于构造立方体互连网络和各种超立方体互连网络。
- 它共有n＝log2N种互连函数。（N为结点个数）
- 当N＝8时，n＝3，可得到常用的立方体互连函数
第11页：变换图形N=8的立方体交换函数
变换图形N=8的立方体交换函数
第12页：互连网络的基本概念
互连网络的基本概念
第13页：均匀洗牌函数
均匀洗牌函数
- 均匀洗牌函数
- 将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。
第14页：N=8的均匀洗牌和逆均匀洗牌函数N=8的
N=8的均匀洗牌和逆均匀洗牌函数N=8的
- N=8的均匀洗牌和逆均匀洗牌函数N=8的均匀洗牌和逆均匀洗牌函数
第15页：逆均匀洗牌函数
逆均匀洗牌函数
- 逆均匀洗牌函数
- 将输入端的二进制编号循环右移一位而得到所连接的输出端编号。
- 蝶式互连函数
- 把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。
第16页：互连网络的基本概念：反位序函数
互连网络的基本概念：反位序函数
- 反位序函数
- 将输入端二进制编号的位序颠倒过来求得相应输出端的编号。
第17页：N＝8的蝶式函数的变换图形N=8的碟式函
N＝8的蝶式函数的变换图形N=8的碟式函
- N＝8的蝶式函数的变换图形N=8的碟式函数和反位序函数
第18页：PM2I函数
PM2I函数
- PM2I函数
- 一种移数函数，它是将各输入端都循环移动一定的位置连到输出端。
- PM2I函数
- 互连函数PM2+i(x)＝x＋2imod NPM2-i(x)＝x－2imod N其中：0≤x≤N－1，0≤i≤n－1，n＝log2N，N为结点数。
- PM2I互连网络共有2n个互连函数。
第19页：互连网络的基本概念数据表
互连网络的基本概念数据表
本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。
当N＝8时，有6个PM2I函数：PM2+0：（0 1 2 3 4 5 6 7）PM2-0：（7 6 5 4 3 2 1 0）PM2+1：（0 2 4 6）（1 3 5 7）PM2-1：（6 4 2 0）（7 5 3 1）PM2±2：（0 4）（1 5）（2 6）（3 7）
第20页：=8的PM2I函数
=8的PM2I函数
第21页：阵列计算机ILLIAC Ⅳ采用PM2±0
阵列计算机ILLIAC Ⅳ采用PM2±0
- 阵列计算机ILLIAC Ⅳ采用PM2±0和PM2±n/2构成其互连网络，实现各处理单元之间的上下左右互连。用移数函数构成ILLIAC Ⅳ阵列机的互连网络
第22页：网络通常是用有向边或无向边连接有限个结点
网络通常是用有向边或无向边连接有限个结点
- 网络规模
- 网络中结点的个数。表示该网络所能连接的部件的数量。
- 结点度
- 与结点相连接的边数（通道数），包括入度和出度。
- 网络通常是用有向边或无向边连接有限个结点的图来表示。2.互连网络的主要特性参数有
第23页：互连网络的基本概念：距离
互连网络的基本概念：距离
- 距离
- 对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。
- 网络直径
- 网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。
- 结点之间的线长
- 两个结点之间连线的长度，用米、千米等表示。
- 等分宽度
- 当某一网络被切成相等的两半时，沿切口的边数（通道数）的最小值称为通道等分宽度，用b表示。
第24页：互连网络的基本概念：线等分宽度
互连网络的基本概念：线等分宽度
- 线等分宽度
- B＝b×w
- 对称性
- 从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。
第25页：互连网络通常可以分为两大类
互连网络通常可以分为两大类
- 互连网络通常可以分为两大类
- 静态互连网络各结点之间有固定的连接通路且在运行中不能改变的网络。
- 动态互连网络由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。下面介绍几种静态互连网络。（其中：N表示结点的个数）
第26页：线性阵列一种一维的线性网络
线性阵列一种一维的线性网络
- 线性阵列一种一维的线性网络，其中N个结点用N-1个链路连成一行。
- 端结点的度：1
- 其余结点的度：2
- 直径：N－1
- 等分宽度b=1
第27页：互连网络的结构
互连网络的结构
第28页：互连网络的结构：对称
互连网络的结构：对称
- 对称
- 结点的度：2
- 双向环的直径：N/2
- 单向环的直径：N2.环和带弦环
- 环用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。
第29页：带弦环增加的链路愈多
带弦环增加的链路愈多
- 带弦环增加的链路愈多，结点度愈高，网络直径就愈小。
第30页：互连网络的结构：全连接网络
互连网络的结构：全连接网络
第31页：循环移数网络
循环移数网络
- 循环移数网络
- 通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。N=16
第32页：一般地，如果｜j-i｜=2r
一般地，如果｜j-i｜=2r
- 一般地，如果｜j-i｜=2r（r=0,1,2,…,n-1，n=log2N），则结点i与结点j连接。
第33页：互连网络的结构：树形和星形
互连网络的结构：树形和星形
- 树形和星形
- 一棵5层31个结点的二叉树一般说来，一棵k层完全平衡的二叉树有N=2k-1个结点。
- 星形
- 结点度较高，为N－1。
- 直径较小，是一常数2。
- 可靠性比较差，只要中心结点出故障，整个系统就会瘫痪。
第34页：互连网络的结构
互连网络的结构
第35页：互连网络的结构：胖树形
互连网络的结构：胖树形
第36页：网格形和环网形
网格形和环网形
- 结点度
- 4
- 直径
- 2×n/2
- 网格形和环网形
- 网格形
- 一个3×3的网格形网络
- 一般来说，N=nk个结点的k维网络的内部结点度是2k，网络直径为k(n-1)。
- 环形网
- 可看作是直径更短的另一种网格。
- 将环形和网格形组合在一起，并能向高维扩展。
- 沿阵列的每行和每列都有环形连接。
- 一个n×n二元环网
第37页：互连网络的结构
互连网络的结构
第38页：互连网络的结构：超立方体
互连网络的结构：超立方体
- 超立方体
- 一种二元n维立方体结构
- 一般来说，一个二元n维立方体由N=2n个结点组成，它们分布在n维上，每维有两个结点。例8个结点的3维立方体4维立方体
- 为实现一个n维立方体，只要把两个（n－1）维立方体中相对应的结点用链路连接起来即可。共需要2n-1条链路。
- n维立方体中结点的度都是n，直径也是n。
第39页：互连网络的结构
互连网络的结构
第40页：互连网络的结构数据表
互连网络的结构数据表
本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。
静态互连网络一览表网络规格说明对称性等分宽度B链路数l网络直径D结点度d网络类型N个结点非1N-1N-12线线阵列N个结点是2N[N/2]2环形N个结点是(N/2)2N(N-1)/21N-1全连接树高h=[log2N]非1N-12(h-1)3二叉树N个结点非[N/2]N-12N-1星形r×r网格，非r2N-2r2(r-1)42D网格与的带弦环等效非2r2Nr-14Illiac网r×r网格，是2r2N2[r/2]42D环网N个结点n=[log2N]是N/2nN/2nn超立方体N=k×2k结点环长k≥3是N/(2k)3N/22k-1+[k/2]3CCC
第41页：动态互连网络：总线
动态互连网络：总线
- 总线
- 一组导线和插座，用于进行与总线相连的处理机、存储模块和外围设备等之间的数据传送。
- 每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。
- 多个功能模块之间的争用总线或时分总线。
- 特点
第42页：一种由总线连接的多处理机系统
一种由总线连接的多处理机系统
第43页：多级互连网络
多级互连网络
- 多级互连网络
- MIMD和SIMD计算机都使用多级互连网络MIN（Multistage Interconnection Network）
- 一种通用的多级互连网络
- 由a×b开关模块和级间连接构成的通用多级互连网络结构
- 每一级都用了多个a×b开关
- a个输入和b个输出
- 在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即a＝b＝2k，k≥1。
第44页：互连网络的结构
互连网络的结构
第45页：互连网络的结构数据表
互连网络的结构数据表
本页含数据表/图示，源文件文字与数字粘连，未能安全切分为表格，以下为原文提取文字，具体数值请对照原课件图片核对。
几种常用的开关模块置换连接合法状态模块大小242×2242564×440 32016 777 2168×8n!nnn×n
第46页：最简单的开关模块
最简单的开关模块
- 最简单的开关模块
- 2×2开关2×2开关的4种连接方式
第47页：各种多级互连网络的区别在于所用开关模块
各种多级互连网络的区别在于所用开关模块
- 级控制
- 每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态；
- 单元控制
- 每一个开关都有一个独立的控制信号，可各自处于不同的状态；
- 部分级控制
- 第i级的所有开关分别用i＋1个信号控制，0≤i≤n－1，n为级数。
- 各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。
第48页：两种多级互连网络
两种多级互连网络
第49页：一个N输入的Omega网络有log2N级
一个N输入的Omega网络有log2N级
- 一个N输入的Omega网络有log2N级，每级用N/2个2×2开关模块，共需要Nlog2N/2个开关。
- 每个开关模块均采用单元控制方式。
- 不同的开关状态组合可实现各种置换、广播或从输入到输出的其他连接。
第50页：多级立方体网络
多级立方体网络
- 多级立方体网络
- 采用二功能（直送和交换）的2×2开关和交换函数构成
- 级间互连按从左到右的次序分别是C0、C1、C2互连函数例如：①当所有开关都直送时，实现恒等变换；②当A、B、C、D四个开关交换、其余直送时，实现C0互连函数；③当E、F、G、H四个开关交换、其余直送时，实现C1互连函数；④当I、J、K、L四个开关交换、其余直送时，实现C2互连函数。
第51页：互连网络的结构
互连网络的结构
第52页：通过选择不同的控制方式
通过选择不同的控制方式
- 通过选择不同的控制方式，可以构成不同的互连网络。例如：采用以下3种不同的控制方式可以构成3种不同的互连网络：①级控制：构成交换网；②部分级控制：构成移数网；③单元控制：构成间接二进制n方体网。
第53页：交叉开关网络
交叉开关网络
- 交叉开关网络
- 单级开关网络
- 交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接。
- 带宽和互连特性最好。
- 一个n×n的交叉开关网络，可以无阻塞地实现n!种置换。
- C.mmp多处理机的互连结构（一种交叉网络）
第54页：互连网络的结构
互连网络的结构
第55页：动态网络的比较交叉开关多级网络总线系统网
动态网络的比较交叉开关多级网络总线系统网
- 动态网络的比较交叉开关多级网络总线系统网络特性O(w)至O(nw)O(w)至O(nw)O(w/n)至O(w)每台处理机的带宽O(n2w)O(nwlogkn)O(w)连线复杂性O(n2)O(nlogkn)O(n)开关复杂性全置换，一次一个只要网络不阻塞，可实现某些置换和广播一次只能一对一连接特性和寻径性能假定n×n交叉开关的线宽为w位n×n MIN采用k×k开关，其线宽为w位总线上假定有n台处理机；总线宽度为w位说明
