第一节 概述 第二节 静态互连网络 第三节 单级动态互连网络 第四节 多级动态互连网络 计算机组成与系统结构 第七章 互连网络 第一节 概述 第二节 静态互连网络 第三节 单级动态互连网络 第四节 多级动态互连网络

第一节 概述 定义 作用 Inter-connection network 连接计算机内部的部件 ALU与ALU 存储体与存储体 处理机与处理机

互连网络结构分类 拓扑结构 控制方式 传递方式 链路类型 实现方式 静态网络 单播 多播 广播 动态网络 共享链路 专用链路 集中控制 一维 二维 多维 动态网络 单级 多级 控制方式 集中控制 分布控制 传递方式 单播 多播 广播 链路类型 共享链路 专用链路 实现方式 片内网络 板内网络 机架内网络 机架间网络

互连网络的数据通信方式 电路交换 串行 并行 单字 猝发 复用 消息转发 寻径算法routing algorithms

二、互连网络的特性 互连网络特性 静态网络的参数 连接性 规整性 度 直径 带宽总和aggregate bandwidth 阻塞 冲突 规整性 静态网络的参数 度 直径 带宽总和aggregate bandwidth 对分带宽bisection bandwidth

第二节 静态互连网络 全互连网络fully connected network 优点：结点间通信距离短 缺点：成本高，实现困难 度=N-1 直径=1 链路数=N(N-1)/2 对分带宽? 优点：结点间通信距离短 缺点：成本高，实现困难

一、总线型网络 单总线结构single bus 度=1 分时使用 优点 结构简单 成本低廉 容易实现 缺点 使用冲突

一、总线型网络 多总线结构 度=总线数 多级总线结构 分级的多总线结构 二维总线结构 总线的分割

二、环型网络 单环网络single ring x (x1) mod N 双环网络：增加吞吐率和可靠性 层次多环网络：可伸缩性 直径=? 度=? 寻径算法简单，可同时传送多个信息，吞吐率比单总线高。 双环网络：增加吞吐率和可靠性 层次多环网络：可伸缩性 带弦环型网络chordal ring

层次多环网络

三、二维网格型网络mesh 度=4 直径=2(n-1) 对分带宽 = n 链路总数=？ 优点：寻址简单，度不变 缺点：流量不对称，伸缩性差 绞带环、双绞螺面、带环网格和闭合螺面 网格的推广：网孔形

绞带环

双绞螺面

带环网格torus 度=4 直径=？ 对分带宽=？ 链路总数=？

闭合螺面

这是什么* * ?

四、立方体网络 二进制超立方体binary hypercube 度为n 直径k=n=log2N 优点 缺点 结点间的通信距离较短 寻径算法简单 缺点 可扩充性差 度随N的增加而增大

四、立方体网络 带环立方体网络 Cube connected cycle 度=3 总结点数N=n2n 链路总数=3N/2 优点 缺点 度固定为3 直径较小 缺点 环成为瓶颈 寻径算法较复杂

四、立方体网络 一般化的超立方体网络generalized hyper cube 采用混合基数制表示结点的地址 每一维的基数为Mi，1≤i≤n，节点总数N= 。 结点的度d为各维链路数之和 总的链路数为L = N*d/2 直径D=k=n

四、立方体网络 超矩形网络hyper-rectangular x’i=(xi±1) mod Mi 度=2n 直径d = 链路总数L=nN 每一维内环形连接 度=2n 直径d = 链路总数L=nN 结点总数N =

四、立方体网络 k-ary n-cube网络 每一维的基数均为k的n维正方体 N=kn 度d=2n 链路总数L=n*kn=nN 对分带宽为=2*kn-1 （k为大于2的偶数） 直径D=n k/2 （k为大于2的数） 结点(xnxn-1…xi+1xixi-1…x1)与结点 (xnxn-1…xi+1((xi±1) mod k)xi-1…x1)连接 n维立方体网络是k-ary n-cube网络的特例（k=2） 带环网格是k-ary n-cube网络的特例（n=2）

例1 对于不带环的3维网格网络，设每一维方向上有r个节点，求： (1) 节点总数 (2) 网络的直径 (3) 链路总数 (4) 对分带宽 (5) 网络的度 = r3 = 3(r-1) = 3(r-1)r2 = r2 = 6

习题7-1 对于k-ary 3-cube网络，求 (1) 网络中的结点总数； (2) 网络的直径； (3) 网络中链路总数； (4) 网络的对分带宽； (5) 网络的度。

第三节 单级动态互连网络 一、网络的互连函数 互连函数 表示方法 函数表示法 表格表示法 循环表示法 图形表示法 端口地址的一个一到一的(bijection)映射 表示方法 函数表示法 用f(x)表示互连函数 表格表示法 循环表示法 如(0 1)(2 3)(4 5)(6 7) 图形表示法 用连线表示映射关系

常见的基本互连函数： (1) 恒等置换identity permutation I(x) = x (0)(1)(2)(3)(4)...(N-1)

常见的基本互连函数： (2) 交换置换exchange permutation E(xn-1xn-2…x1x0) = xn-1xn-2…x1 例 (0 1)(2 3)(4 5)(6 7)

常见的基本互连函数： 方体置换cube permutation Ck(xn-1xn-2…xk+1 xk xk-1 …x1x0) = xn-1xn-2…xk+1 xk-1 …x1x0 C1: (0 2)(1 3)(4 6)(5 7) C2: (0 4)(1 5)(2 6)(3 7)

常见的基本互连函数： 均匀洗牌perfect shuffle permutation σ(xn-1xn-2…x1x0) = xn-2xn-3…x1x0xn-1 例： (0)(1 2 4)(3 6 5)(7)

常见的基本互连函数： 逆洗牌reverse shuffle σ-1(xn-1xn-2…x1x0) = x0xn-1xn-2…x1 例 (0)(1 4 2)(3 5 6)(7)

常见的基本互连函数： 子洗牌subshuffle 将端口分成若干个组，对每个组进行均匀洗牌置换。 σ(k)(xn-1xn-2…xk+1xkxk-1…x1x0) = xn-1xn-2…xk+1xk-1…x1x0xk 0≤k≤n-1 例：σ(2) (0)(1 2 4)(3 6 5)(7)(8) (9 10 12)(11 14 13)(15)

常见的基本互连函数： 子逆洗牌reverse subshuffle 将端口分成若干个组，对每个组进行逆洗牌置换。 σ-1(k)(xn-1xn-2…xk+1xkxk-1…x1x0) = xn-1xn-2…xk+1x0xkxk-1…x1 0≤k≤n-1 例：σ-1(2) (0)(1 4 2)(3 5 6)(7)(8) (9 12 10)(11 13 14)(15)

常见的基本互连函数： 超洗牌supershuffle 以组为单位洗牌 σ(k)(xn-1xn-2...xn-kxn-k-1...x1x0) = xn-2xn-3...xn-k-1xn-1xn-k-2...x1x0 0≤k≤n-1 例：σ(1) (0)(1)(2 4 8)(3 5 9)(6 12 10) (7 13 11)(14)(15)

常见的基本互连函数： 蝶式置换butterfly permutation β(xn-1xn-2…x1x0) = x0xn-2…x1xn-1 例： (0)(2)(1 4) (3 6)(5)(7)

常见的基本互连函数： 子蝶式置换：将端口分组，组内进行蝶式置换。 常见的基本互连函数： 子蝶式置换：将端口分组，组内进行蝶式置换。 β(k)(xn-1xn-2…xk+1xkxk-1…x1x0) = xn-1xn-2…xk+1x0xk-1…x1xk 例: (0)(1 4)(2)(3 6)(5)(7) (8)(9 12)(10)(1114)(13)(15)

常见的基本互连函数： 超蝶式置换 β(k)(xn-1xn-2...xn-kxn-k-1xn-k-2...x1x0) = xn-k-1xn-2...xn-kxn-1xn-k-2...x1x0 例 (0)(1)(2 8)(3 9)(4)(5)(6 12) (7 13)(10)(11)(14)(15)

常见的基本互连函数： 位序颠倒置换bit reversal permutation ρ(xn-1xn-2…x1x0) = x0x1…xn-2xn-1 例 (0)(1 8)(2 4)(3 12)(5 10)(6)(7 14) (9)(11 13)(15) N=8时与蝶式置换相同 子位序颠倒置换 低位段颠倒 超位序颠倒置换 高位段颠倒

常见的基本互连函数： 移数置换shift permutation α(x) = (x+k) mod N, 0≤x≤N 例： (0 2 4 6)(1 3 5 7)

常见的基本互连函数： 加减2i置换plus-minus 2i permutation PM2+i(x) = (x + 2i ) mod N PM2-i(x) = (x - 2i ) mod N 其中0≤x≤N-1，0≤i≤log2N-1。

二、常用单级网络 单级动态网络的一般模型 循环网 循环网 循环网

衡量动态互连网络的因素 连接特性要好 能实现的互连函数要多 网络延迟要短 开关设备量要少 控制方法要简单 便于用集成电路实现

二、常用单级网络 交叉开关crossbar 非阻塞 扇出：N 步数：1 置换数？

二、常用单级网络 洗牌交换网络Shuffle-Exchange 一次洗牌，一次交换

二、常用单级网络 立方体网络 分时实现C0, C1, C2,…置换函数 如果链路始终连通则构成静态网络 扇出 log2N 步数

习题7-2 设16个处理器的编号分别为0、1、…、15，用单级互连网络互连，若互连函数为： (1) 交换置换 (2) 加减2i置换PM2+3和PM2-1 (3) 洗牌置换 (4) 蝶式置换 时，第9号处理器各与哪一个处理器相连?

习题7-3 设128个处理器的编号分别为0，1，2，…，127，当复合互连函数为 s(C0(PM2-2))时，第8号处理器将与哪个处理器相连。

第四节 多级动态互连网络 多级动态网参数 开关元件 连接模式 控制方式 2x2, 4x4, axb 恒等、洗牌、蝶式 级控、部分级控、单元控制

s-1 s-1 s-1(x2x1x0) = s-1 s-1(x0x2x1) = s-1(x1x0x2) = x2x1x0 一、STARAN网络 开关元件：两功能 连接模式：输入恒等，级间和输出逆洗牌 控制方式：级控 置换数：N 开关元件直通时实现恒等置换： s-1 s-1 s-1(x2x1x0) = s-1 s-1(x0x2x1) = s-1(x1x0x2) = x2x1x0 输入端与输出端的连通性 011101 连通规律

s-1 b b1(x2x1x0) = s-1 b(x2x0x1) = s-1(x1x0x2) = x2x1x0 二、间接二进制n维立方体网络 开关元件：两功能 连接方式：输入恒等，级间子蝶式，输出逆洗牌 控制方式：单元控制 置换数：N(N/2) < N! 开关元件直通时实现恒等置换： s-1 b b1(x2x1x0) = s-1 b(x2x0x1) = s-1(x1x0x2) = x2x1x0 与STARAN网的类似之处

sss(x2x1x0) = ss(x1x0x2) = s(x0x2x1) = x2x1x0 三、Ω网络 开关元件：四功能 连接模式：输入与级间洗牌，输出恒等 控制方式：单元控制 寻径算法：目标地址 开关元件直通时实现恒等置换： sss(x2x1x0) = ss(x1x0x2) = s(x0x2x1) = x2x1x0 与STARAN网的类似之处

四、Delta网络 开关元件 连接模式 q洗牌： 0≤i≤q×r - 1 控制方式 输入输出端口数 a×b交叉开关 级间a洗牌 输入与输出恒等 q洗牌： 0≤i≤q×r - 1 控制方式 不限 输入输出端口数 anbn

五、数据变换网络 开关元件 连接方式 级间PM2I，输入与输出恒等 控制方式 级控

五、数据变换网络

六、榕树网络 底结点base，顶结点apex，中间结点intermediates 特点 从一个底结点到一个顶结点一定存在一条而且也只存在一条路径 连接线是从下向上单向的 底节点在下 顶结点在上

榕树网的参数 级数Layer 展开度Spread 扇出度Fanout 从底结点到顶结点的距离 输出数，结点向上引出的边的数量 输入数，结点下面引入的边的数量

榕树分类 均匀榕树uniformed banyan 每一级中各结点的F相同，S相同 非均匀榕树non-uniformed banyan 非规则 非均匀榕树non-uniformed banyan 矩形榕树rectangular banyan 每级结点数相同 强矩形(F=S) 弱矩形 扩展收缩形榕树 SW榕树：递归生成

榕树网络的例子

榕树网络的例子

榕树网络与其他多级动态网 榕树网的例子 STARAN网络 间接二进制n方体网络 Ω网络 SW榕树网 强矩形类 F=S=2

七、树型网络 特点：双向，单边 分类：二叉，三叉，四叉等 二叉数 度d=3 直径=2log2N 寻径简单、伸缩性好 无冗余通路，容错能力差（对分带宽=1）

超树hypertree

超树hypertree

八、Clos网络 开关元件 连接方式 输入级r1个n1×m交叉开关 中间级m个r1×r2交叉开关 输出级r2个m×n2交叉开关 输入与输出恒等 级间r1洗牌和m洗牌

八、Clos网络

Bennus网络：采用2×2开关元件的Clos网络

8端口Bennus网络

习题7-4 试画出8个输入端口和27个输出端口的Delta网络的结构，采用2×3的开关元件。

习题7-5 当编号分别为0、1、2、、F的16个处理器之间要求按下列配对通信： (B, 1), (8, 2), (7, D), (6, C), (E, 4), (A, 0), (9, 3), (5, F) 试选择所用互连网络的类型、控制方式及相应的控制信号。

习题7-6 设F=3, S=3, 画出9个底结点的规则榕树网络