计算机系统结构 第一章 基本概念 第二章 指令系统 第三章 存储系统 第四章 输入输出系统** 第五章 标量处理机 第六章 向量处理机 第七章 互连网络 第八章 并行处理机 第九章 多处理机

第七章 互连网络 7.1 互连网络的基本概念 7.2 消息传递机制 7.3 互连网络实例

第七章 互连网络 定义: 一种由开关元件按照一定的拓扑结构和控制方式构成的网络 作用:实现计算机系统内部多个处理机或多个功能部件之间的相互连接

7.1 互连网络的基本概念 7.1.1互连网络的作用 7.1.2互连函数 7.1.3互连网络的特性和传输的性能参数 7.1.4互连网络的种类

7.1.1互连网络的作用 计算机系统内部多个处理机或多个功能部件间的相互连接 并行处理系统的核心组成部分 对整个计算机系统的性能价格比有决定性的影响

具有本地存储器、私有高速缓存、共享存储器和共享外围设备的一般处理机系统的互连结构 1 IPMN(处理机-存储器网络) 2 PION(处理机-I/O网络) 3 IPCN(处理机之间通信网络) P(处理机)C(高速缓冲存储器)SM(共享存储器)LM(本地存储器) 磁盘 SM1 SM2 SMm IPMN …… Cn Pn LM C1 P1 IPCN PION 磁带 打印机 终端 网络 … (共享存储器) (共享I/O与外设)

互连网的N个输入和N个输出端分别用整数(0, 1, 2, ..., N-1)表示，互连函数表示相互连接的输出端号和输入端号之间的一一对应关系 7.1.2互连函数 互连函数 互连网的N个输入和N个输出端分别用整数(0, 1, 2, ..., N-1)表示，互连函数表示相互连接的输出端号和输入端号之间的一一对应关系 表示方法：互连函数法，图形表示法, 输入输出对应表示法 函数表示法： f(x)表示互连函数，为：f(xn-1xn-2...x1x0 ) x表示输入端号，常用n位二进制形式表示 xn-1xn-2...x1x0 图形表示法: 用图形表示输入和输出端之间的连接 输入输出对应(矩阵)表示法 循环表示法: 把互连函数f(x)表示为 (x0，x1，...，xj) (xk，xk+1，...，xl) ... 第1个括号表示循环 f(x0)=x1，f(x1)=x2，...，f(xj)=x0 j+1称为该循环的长度 0 1 2 ... N-1 f(0) f(1) f(2)...f(N-1)

常用的互连函数 1 恒等置换 I( xn-1xn-2 ... x1x0 )= xn-1xn-2 ...x1x0

2 交换置换Exchange 二进制地址编号中第0位位值不同的输入和输出端间的连接 E(xn-1xn-2 ... x1x0 )= xn-1xn-2 ... x1x0 其他互连函数还有：方体置换、均匀洗牌置换、蝶式置换、位序颠倒置换、移数置换、加减2i置换

3 方体置换Cube 当n=3时，共有3种函数，每种函数能够表示8个结点之间的连接关系 交换函数主要用于超立方体互连网中，也称为超立方体函数，用Cube表示，如：Cube0、Cube1、Cube2等

3 方体置换Cube C0 C2 C1 C0, C1, C2 变化发生在0, 1, 2位 分别是高 2, 1, 0位相同的为一个组 组数 4, 2, 1 组内加/减 1, 2, 4 C0循环表示(0,1), (2,3), (4,5), (6,7)

4 均匀洗牌置换Perfect shuffle 把二进制位循环左移一位 子混洗(subshuffle)S(k) 最低k位循环左移一位 超混洗牌(supershuffle) S(k) 最高k位循环左移一位 显然成立 逆混洗函数 教材P397L2,3,5,6错

4 均匀洗牌置换Perfect shuffle Ω 均匀洗牌: 由上到下分两组，两组互相交错 0,1,2,3接至0,2,4,6 4,5,6,7接至1,3,5,7 输入端由上到下分两组，输出端分四组 组0,1,2,3接至输出端各组的上, 0,2,4,6 组4,5,6,7接至输出端各组的下, 1,3,5,7 均匀洗牌循环表示(0), (1,2,4), (3,6,5), (7) 子洗牌是将整组数据分成若干个子组，对每个子组完成均匀洗牌变换。S(2) 以最高位分两组0，1，2，3；4，5，6，7 逆均匀洗牌是均匀洗牌的逆函数，两者的输入端和输出端正好互换

4 均匀洗牌置换Perfect shuffle 只用均匀洗牌函数不能实现任意结点之间的互连 通常与其他函数，如交换函数一起构成互连网络 0--->0 7--->7 均匀洗牌与逆均匀洗牌是两种十分有用的互连函数 以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega(Ω)网络与逆Omega(Ω^-1)网络

5 蝶式置换Butterfly 蝶式函数的名称来自于FFT变换时的图形，如蝴蝶式样 将输入端二进制结点号的最高位和最低位互换位置 子蝶式(subbutterfly) B(k)最低k位的最高位与最低位互换位置 超蝶式(superbutterfly) B(k)最高k位的最高位与最低位互换位置 显然成立 教材P397倒数L2,3错 教材P398L1,2错

5 蝶式置换Butterfly 与全混洗函数类似，只用蝶式函数也不能实现任意结点之间的互连 蝶式函数循环表示(0), (2), (5), (7), (1,4), (3,6)

6 位序颠倒置换Bit Reversal 将输入端二进制地址的位序反过来就得相应输出的地址 子反位序函数：最低k位的位序反过来 超反位序函数：最高k位的位序反过来 对于n=3的情况，正好有 R=B，R(2)=B(2)，R(2)=B(2) 教材P398 6. L5,6错

7 移数置换 将输入端数组循环移动一定的位置向输出端传输 可将整个输入数组分成若干个子数组，在子数组内进行循环移数置换，这种段内循环移数的表达式可写成两个式子 (a)移数量k=2　　 　(b)段内移数置换k=1,r=2

8 加减2i置换 其中：0  x  N-1，0  i  n-1，n = log2 N i=+0 循环表示(0,1,2,3,4,5,6,7) i=+1 循环表示(0,2,4,6), (1,3,5,7)

8 加减2i置换 采用移数函数可构成环型网(包括单向环网、双向环网、弦环网)、方格网、移数网 如Illiac函数是构成Illiac IV阵列的基础，包含PM20和PM2n/2四个互连函数 采用全部移数函数构成网络称为移数网

7.1.3互连网络的特性和传输的性能参数 1 互连网络的特性 互连网络通常是用有向边或无向边连接有限个结点的组成 互连网络的主要特性 (1) 网络规模：网络中结点的个数 (2) 结点度：与结点相连接的边数。包括入度和出度 入度： 进入结点的边数 出度：从结点出来的边数 (3) 距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距离的最大值 用结点间的连接边数表示

7.1.3互连网络的特性和传输的性能参数 (5) 等分宽度 当某一网络被切成相等的两半时，沿切口的最小边数(通道)称为通道等分宽度，用b表示 线等分宽度B=b×w，w为通道宽度(用位表示) 等分宽度是说明沿等分网络最大通信带宽的一个参数 网络的所有其它横截面都应限在等分宽度之内 (6) 结点间的线长 两个结点间连线的长度。用米、公里等表示 (7) 对称性 从任何结点看到拓扑结构都是一样的网络称为对称网络。 对称网络比较易实现，编程也较容易

2 互连网络传输的性能参数 一台机器发送消息给另一台机器时，发送方的步骤 (1) 用户程序把要发送的数据拷贝到操作系统的缓冲区 (2) 操作系统把缓冲区中的数据打包，发送到网络接口部件 (3) 网络接口硬件开始发送消息 数据包的接收步骤 (1) 把数据包从网络接口部件拷贝到操作系统缓冲区 (2) 检查收到的数据包，如果正确，给接收方发回答信号 (3) 把接收到的数据拷贝到用户地址空间。发送方接收到回答信号后，释放系统缓冲区

互连网络在传输方面的主要性能参数 (1) 频带宽度(Bandwidth)：互连网络传输信息的最大速率 (2) 传输时间(Transmission time)：等于消息长度除以频宽 (3) 飞行时间(Time of flight)：第1位信息到达接收方所花费的时间 (4) 传输时延(Transport latency)：等于飞行时间与传输时间之和 (5) 发送方开销(Sender overhead)：处理器把消息放到互连网络的时间 (6) 接收方开销(Receiver overhead)：处理器把消息从网络取出来的时间

一个消息的总时延 总时延=发送方开销+飞行时间+消息长度/频宽+接收方开销

例7.1 假设一个网络的频宽为10Mb/S，发送方开销为230us，接收方开销为270us。如果两台机器相距100米，现在要发送一个1000字节的消息给另一台机器，试计算总时延。如果两台机器相距1000公里，那么总时延为多大？ 解 光的速度为299792.5KM/S，信号在导体中传递速度大约是光速的50%，相距100米时总时延 相距1000公里时的总时延

7.1.4互连网络的种类 互连网络的种类很多，分类方法也很多 以互连特性为特征，可分为 静态互连网络：连接通路是固定的，一般静态互连网络不能实现任意结点到结点之间的互连 循环互连网络：通过多次重复使用同一个单级互连网络以实现任意结点到结点之间的互连 多级互连网络：将多套相同的单级互连网络连接起来，实现任意结点到结点之间的互连 全排列互连网络：不仅能够实现任意结点到结点之间的互连，而且能够同时实现任意结点到结点之间的互连 全交叉开关网络：除了能够同时实现任意结点到结点之间的互连之外，还能够实现广播和多播

1静态互连网络 静态互连网络是指在各结点间有专用的连接通路，且在运行中不能改变的网络 静态互连网络中，每一个开关元件固定地与一个结点相连，建立该结点与邻近结点之间的连接通路，直接实现两结点间的通信 一维: 线性阵列结构 二维: 环形、星形、树形、网格形 三维: 立方体 三维以上: 超立方体

(1)线性阵列 一种一维网络，其中N个结点用N-1条链路连成一行 内部的结点度为2，端点的结点度为1。直径为N-1 当N大时，直径也比较大。等分宽度b=1 线性阵列是最简单的拓扑结构, 结构不对称，N很大时，通信效率很低 N很小，如N=2，实现线性阵列是相当经济的 直径随N线性增大，当N比较大时，就不应使用这种网络

线性阵列与总线的区别很大，后者是通过切换与其连接的许多结点来实现时分特性的 (1)线性阵列 线性阵列与总线的区别很大，后者是通过切换与其连接的许多结点来实现时分特性的 线性阵列允许不同的源结点和目的结点对并发使用系统的不同部分(通道) 无循环表示 7 6 5 4 8 9 10 11 15 14 13 12 0 1 2 3

(2)环和带弦环(3)循环移数网络 采用移数函数。使用不同的移数函数，可构成多种环形网 单向环行网 右环网，采用PM2+0函数 左环网，采用PM2-0函数 双向环行网：又称一维邻居网，采用{PM2+0，PM2-0}函数 环行网是对称的，结点度是常数2 双向环网的直径为N/2，单向环形网的直径是N 结点度由2提高至3，可得到弦环网 增加的弦愈多，则结点度愈高，网络直径愈小 循环移数网络也是一种环形网，将环上每个结点与其距离为2的整数幂的结点之间连接构成 循环移数网N=2^n的结点度为d=2n-1，直径为 D=n/2

1 2 3 4 5 7 6 (2)环和带弦环(3)循环移数网络 环循环表示(0,1,2,...,14,15) 度为3的带弦环 循环移数网 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 环循环表示(0,1,2,...,14,15) 度为3的带弦环 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 7 6 循环移数网

(4)树形和星形(5)胖树形 二叉树网 二叉胖树网 星形网 一棵k层完全平衡二叉树有N=2^(k-1)个结点，结点度3，直径2(k-1) 星形是一种特殊的2层树，结点度很高，为d=N-1，直径2 星形结构用于有集中监督结点的系统 二叉胖树的结点度从叶子结点往根结点逐渐增加 胖树缓解了一般二叉树根结点通信速度高的矛盾

(6)网格和环网形 网格网是一种比较流行的网络结构，有各种变体形式 在Illiac IV、MPP、DAP、CM-2和Inetl Paragon中得到实现 一般网格网，N=n^k 结点的k维网格的结点度为2k，直径为k(n-1) 环网形网格网沿阵列每行每列都有环形连接 一个n×n二元环网的结点度为4，直径为2[n/2] 环网是一种对称的拓扑结构。附加的回绕连接使直径减至的网格的一半 一个n×n Illiac网格直径为d=n-1，为纯网格直径的一半 Illiac IV的8×8 Illiac网格，其结点度为4，直径为7

(6)网格和环网形 网格形 Illiac网 环形网

(7)搏动式阵列 一类为实现确定算法而设计的多维流水线阵列结构 图7.15(d) 是为完成矩阵相乘而专门设计的搏动式阵列。内部结点度为6 静态搏动式阵列在多个方向上使数据流以流水线方式工作 商用Intel iWarp系统用搏动式结构设计而成 1978年Kung和Leiserson提出搏动式阵列后，已成为广泛研究的领域 通过确定的互连和同步操作，搏动式阵列可与算法的通信结构相匹配 信号/图象处理等特殊应用，提供更好的性能/价格比 结构的实用性有限，编制程序很难

(8)超立方体 n维立方体由N=2^n个结点, 分布在n维上, 每维有两个结点 超立方体网采用交换函数，结点度为n，直径也为n 4-立方体可通过将两个3-立方体的相应结点互连组成 Y X Z 011 000 010 110 111 101 100

(9)带环立方体 从超立方体改进而来 从一个k-立方体构成一个有n=2^k个结点环的带环k-立方体 用k个结点的环取代k维超立方体的每个顶角, 一个k-立方体变成k×2^k个结点的k-CCC 一个3-立方体可改成带环3-立方体(CCC)。构成的办法是将3-立方体的角结点(顶角)用一个结点环来代替 一般说来，k-CCC的网格直径2k。CCC的主要改进在其结点度为常数3，与超立方体的维数无关 3-CCC的直径为6，比原来3-立方体的直径大一倍 一个超立方体有N=2^n结点。一个有同样N结点数的CCC一定是由低维k-立方体组成，即2^n=k×2^k，其中k<n 对应于n=6和k=4的情况，一个64结点的CCC可用4结点的环取代4-立方体的角结点组成。CCC的直径为2k=8，比6-立方体的6要长些。但是，CCC的结点度为3，比6-立方体的结点度6要小 容许一定的时延,CCC是一种构造可扩展系统的较好的结构

(9)带环立方体 Y X Z 011 000 010 110 111 101 100

(10)k元n-立方体网络 环形、网格形、环网形、二元n-立方体(超立方体)和W网络都是k元n-立方体网络系列的拓扑同构体 参数n是立方体的维数，k是基数或者说是沿每个方向的结点数(多重性)。与网络中结点数N的关系 k元n-立方体的结点可用基数为k的n位地址A=a1a2…an来表示，其中ai代表第i维结点位置 为简单起见，所有链路都认为是双向的 网络中每条线代表两个通信通道，每个方向一个

机器的摆放是否也要相应立体格局? 如何连接繁杂的接线? 2 图7.17 k=4和n=3的k元n-立方体网络 (1)4结点串成绿色环 (2)4绿色环并排成面，同一列用黄色环连接 (3)4黄色面堆成体，同一行用蓝色环连接 机器的摆放是否也要相应立体格局? 如何连接繁杂的接线? 2 3 编号，展平 1

环网 (a)传统环网(4元2-立方体) (b)折叠连接的环网

2动态互连网络 动态互连网络设置有源开关 通过控制信号对连接通路重新组合，实现所要求的通信模式 包括总线、多级互连网和交叉开关网络

(1)总线 总线系统是一组导线和插座用于处理与总线相连接的处理机、存储器模块和外围设备间的数据业务 总线被称为多个功能模块间争用总线或时分总线 总线系统与其它两种动态连接网络相比，价格较低，带宽较窄 有很多可用的工业和IEEE总线标准

(2)开关模块 一个ab开关模块有a个输入和b个输出 一个二元开关则与a=b=2的22开关模块相对应 实际中a和b通常选为a=b=2^k，k>=1 最常用的二元开关：a=b=2 每个输入可与一个或多个输出相连，在输出端必须避免发生冲突。容许一对一和一对多映射；不容许多对一映射 只容许一对一映射时称为置换连接，称为n×n交叉开关 具有直通和交换两种功能的交换开关称为二功能开关，或交换开关。用一位控制信号控制 具有所有四种功能的交换开关称为四功能开关，用两位控制信号控制

交换开关和合法状态 直通 交换 上播 下播 模块大小 合法状态 交换连接 2×2 4 2 4×4 256 24 8×8 16777216 40320 n×n nn n!

(3)多级网络 互连网络的一种基本功能: 实现结点到结点之间的任意互连 多级互连网络采用多个相同或不同的互连网络直接连接起来 属组合逻辑线路，同一个时钟周期能实现任意结点到结点之间的互连 多级互连网络的关键技术 (1) 交换开关 (2) 交换开关之间的拓扑连接 (3) 对交换开关的不同控制方式

(3)多级网络 (3a)拓扑结构(级间连接) 前一级交换开关的输出端与后一级交换开关的输入端之间的连接模式称为拓扑结构 通常采用前面介绍的互连函数实现拓扑结构 从结点的输出到第一级交换开关的输入，及从最后一级交换开关的输出到结点的输入也可采用拓扑结构连接 (3b)控制方式 多级互连网络中有多级交换开关，每一级有多个交换开关 (1)级控制：同一级交换开关使用同一个控制信号控制 (2)单元级控制：每个交换开关分别控制 (3)部分级控制：如，第i级使用i+1个控制信号控制(0<=i<=n-1) 由粗到细逐步切换之目的节点 同一个多级互连网络分别使用三种不同的控制方式，可构成三种不同的互连网络

图7.20 一种由a×b开关模块和级间连接模式ISC

(3c)多级立方体网 采用二功能开关，共需开关 n 2^(n-1)个 由多个单级立方体网组成，某级开关处于交换状态时, 各级分别实现E0、E1、…En-1交换函数 所有开关都直通时，实现恒等变换 第0级A、B、C、D开关交换，其余直通实现 E0 互连函数 第1级E、F、G、H开关交换，其余直通实现 E1 互连函数 第2级I、J、K、L开关交换，其余直通实现 E2 互连函数 采用三种不同的控制方式，可构成三种不同的互连网络 采用级控制， 构成STARAN交换网 采用部分级控制，构成STARAN移数网 采用单元控制， 构成间接二进制n方体网

(3c)多级立方体网 A B C D E F G H I J K L 1 2 3 4 5 6 7 k=0 k = 1 k = 2 B(2) B(3) S -1 A B C D E F G H I J K L 1 2 3 4 5 6 7 k=0 k = 1 k = 2

1 2 3 4 5 6 7 8 9 A B C D E F 级 k0 k2 k3 k1 B(2) B(3) B(4) S -1

(3d)全排列互连网络 循环互连网络和多级互连网络都能实现任意一个结点到另一个结点之间的互连，但同时有两个或两个以上结点要求与其他结点互连时，有可能发生冲突 在上面的多级立方体网中，如果要求同时实现0-->5和1-->7的互连，在开关A发生冲突 全排列互连网络能同时实现任意结点到结点之间的互连 解决方法：采用多个多级互连网络连接 原理：N个结点的全排列共有N！ N=2n个结点的多级互连网络有n级，二功能开关n 2n-1个，有不同的状态种类

(4)Ω网络 16×16Ω网络，共需4级2×2开关 网络左侧有16个输入，右侧有16个输出 ISC是对16个对象的2路(组)均匀洗牌模式 一个n输入的Ω网络需log2n级2×2开关，每级需n/2个开关模块，网络共需(nlog2n)/2个开关 不同开关状态组合可实现各种置换、广播或从输入到输出的其它连接 每级的拓扑结构相同 采用单元控制 能实现任意一个输入端到任意一个输出端的连接 有冲突时不能同时实现多个输入端到多个输出端的连接 检查二进制目的地址编码来控制数据路径 目的地址编码从高位开始 第i位为0时，第i级的2×2开关输入端与上输出端连接 第i位为1时，第i级的2×2开关输入端与下输出端连接

(4)Ω网络 均匀洗牌置换 输入1可连接到哪个输出?

(5)基准网络 Wu和Feng研究多级互连网络之间的关系 基准网络如图7.22(a)所示递归生成 第1级为一个N×N模块 第2级为两个(N/2)×(N/2)子模块，以C0和C1表示 以上构成方法递归用于子模块 直至得到2×2的N/2子模块为止 各小框和最终的子模块构件是2×2开关 每个有两个合法连接状态：两个输入和两个输出间的直送和交叉连接

(5)基准网络 N结点S -1 每个2×2交换开关的输出分成上下两组，分别连到两个N/2 递归分组的过程是逐步细化到达目的结点的过程

(5)基准网络 1组16结点S -1 2组8结点S -1 4组4结点S -1 递归终点为1个2x2子模块，即仅有两个结点

(6)交叉开关网络 全交叉开关网络能够同时实现任意结点到结点之间的互连 还能实现广播和多播 带宽和互连特性最好 多处理机系统中，处理机、存储器和IOP之间用交叉开关网络连接 可看作是一个单级开关网络 象电话交换机一样，交叉点开关能在对偶(源、目的)之间形成动态连接，每个交叉点开关在对偶间提供一条专用连接通路，开关可根据程序的要求动态地设置“开”或“关”

另一种分类

7.2 消息传递机制 研究各种寻径方法，分析它们的通信时延问题 引入虚拟通道的概念，用虚拟通道来避免死锁 确定的和自适应两种寻径算法 拓扑结构与寻径策略有一定的关系

7.2.1 消息寻径方式 四种寻径方式 线路交换、存储转发、虚拟直通、虫蚀寻径 1. 消息格式 消息 结点间通信的逻辑单位, 由任意数目的长度固定的包组成 包是包含寻径目的地址的基本单位 每个包需要一个序号，以重新组装消息 包可分成固定长度的片 寻径信息和序号形成头片，其余的片是数据片

消息传递网络中通信的信息单位：消息、包和片 R：导径信息 S：序号 D：数据片 b：位 消息 包 片 D S R b

包 采用存储转发寻径方式的多计算机系统中，包是信息传送的最小单位 采用虫蚀寻径网络的多计算机中，包可进一步分成片。片的长度受网络大小的影响 256个结点的网络需要片长为8位 包的长度取决于寻径方式和网络的实现方法 典型的包的长度为64～512位 序号可能占用1～2个片，取决于消息的长度 包和片的大小还与通道频宽、寻径器设计以及网络流量密度等有关

2、四种寻径方式 两大类 线路交换 包交换(存储转发、虚拟直通和虫蚀寻径 ) (1)线路交换(circuit switch) 先建立一条从源结点到目的结点的物理通路，再传递消息 传输时延公式 T = (Lt/B)*D+L/B 其中： Lt为建立路径所需小信息包的长度 L为信息包的长度 D为经过的结点数 B为带宽 优点：实际通信时间较短，使用缓冲区少 缺点：建立源结点到目的结点的物理通路开销很大，占用物理通路时间长

(2)存储转发(store and forward) 每个结点有一个包缓冲区，包从源结点经过中间结点到达目的结点 存储转发网络的时延与源和目的地之间的距离成正比 传输时延公式 T = (L/B) *D + L/B = (D + 1) * L/B 优点：占用物理通路的时间比较短 缺点：包缓冲区大，时延大(与结点距离成正比)

(3)虚拟直通(virtual cut through) 接收到用作寻径的消息头部时，开始路由选择 通信时延公式 T=(Lh/B) * D + L/B = (Lh * D+ L)/B 其中 Lh是消息的寻径头部的长度 一般有，L>>Lh×D；通信时延可以近似为 T=L/B 与结点数无关 出现寻径阻塞时，只能将整个消息存储在寻径结点 主要优点 通信延迟与结点数无关 主要缺点 每个结点需有足够大的缓冲区来存储最大信息包 最坏情况下与存储转发方式的通信时延一样，经过的每个结点都发生阻塞，都需缓冲

(4)虫蚀寻径(wormhole) 把包分成更小的片。每个结点的寻径器中有片缓冲区 用头片直接开辟一条从输入结点到输出结点的路径。每个消息中的片以流水方式在网络中向前“蠕动” 消息的头片到达一个结点A的寻径器后，寻径器根据头片的寻径消息立即做出路由选择 如所选择的通道空闲且所选择的结点B的片缓冲区可用，头片就不必等待，直接通过结点A传向下一个结点B 随后的其它数据片跟着相应地向前“蠕动”一步 消息的尾片向前“蠕动”一步之后，它刚才所占有的结点就被放弃 如所选择的通道或的结点的片缓冲区不可用，头片须在该结点的片缓冲区等待，其它数据片也在原来的结点等待 通信时延 T=Tf×D+L/B=(Lf/B)×D+L/B=(Lf×D+L)/B 其中：Lf是头片的长度，Tf是头片经过一个结点所需时间 一般有L>>Lf×D，可近似为T=L/B 通信时延与结点数无关

虫蚀寻径的优点 每个结点的缓冲区较小，易于VLSI实现 较低的网络传输时延 所有的片以流水方式向前传输，利用时间并行性 存储转发方式的消息包整个地从一个结点“跳”到另一个结点，通道的使用是串行的，所以它的传输时延基本上正比于消息在网络中传输的距离 虫蚀寻径方式的网络传输时延正比于消息包的长度，传输距离对它的影响很小 通道共享性好，利用率高 对通道的预约和释放是结合在一起的一个完整的过程 有一段新的通道后将立即放弃用过的一段旧通道 易于实现选播和广播通信方式 允许寻径器复制消息包的片并把它们从多个输出通道输出

虫蚀寻径的缺点 虫蚀寻径的缺点 消息的一个片被阻塞时，整个消息都被阻塞，占用了结点资源 需采用虚拟通道的方式来避免由此引起的一连串的阻塞 虫蚀寻径方式也可分为无缓冲和有缓冲两类，区别在于缓冲的大小 缓冲大有利于性能的提高，但会增加结点的复杂度 IBM SP2的寻径方式是带缓冲的虫蚀寻径方式，采用共享的存储区对输入/输出消息缓冲

图7.25 几种寻径方式的时空图 (a) 线路交换寻径 T = (Lt/B)*D+L/B D=3, L包含Lt N1-->N4 (1)通过识别消息头部，N1接到N2，N2接到N3，N3接到N4 (2)N1发送，以极小的延迟通过中间结点N2、N3到达N4

(b) 存储转发寻径 T = (L/B) *D + L/B D=3 N1-->N4 (1)N1发送到N2存储 (2)N2转发到N3存储 (3)N3转发到N4

(c) 虫蚀寻径 T=(Lf/B)×D+L/B D=3, L包含Lf N1-->N4 (1)头片由N1寻径至N2，N1发送头片到N2存储 (2)头片由N2寻径至N3，N2发送头片到N3存储 N1发送1号片到N2存储 (3)头片由N3寻径至N4，N3发送头片到N4 N2发送1号片到N3存储 N1发送2号片到N2存储 N1,N2,N3类似流水线的三段，头片,1号片,2号片类似流水线的三条指令-------流水方式，蠕动 包传送完成前，蠕动路径不能和其他包的蠕动路径交叉 头片逐个结点寻径，尾片逐个结点放弃蠕动路径

7.2.2死锁和虚拟通道 1虚拟通道 虚拟通道是两个结点间的逻辑链 由源结点的片缓冲区、结点间的物理通道以及接收结点的片缓冲区组成 物理通道由所有的虚拟通道分时共享 如图四条虚拟通道分时共享一条物理通道

四条虚拟通道以片传递为基础分时地共享一条物理通道

采用存储转发寻径的四个结点间出现缓冲区死锁 2死锁的产生和避免 缓冲区或通道上的循环等待引起死锁 采用存储转发寻径的四个结点间出现缓冲区死锁 D D D D D 包缓冲区 C C C C C B B B B B A A A A A

虫蚀寻径的四个结点之间出现通道死锁 结点A 结点D 结点B 结点C m3 m2 m1 m4 寻径器C 寻径器B 片缓冲区 消息1 消息2 消息3 寻径器A 消息4 寻径器D

如何避免死锁 缓冲区或通道上的循环等待引起死锁 利用虚拟通道方法可减少死锁 虚拟通道可用单向通道或者双向通道实现 两条单向通道组合在一起可构成一条双向通道 虚拟通道可能会使每个请求可用的有效通道频宽降低 确定虚拟通道数目，需对网络吞吐量和通信时延折衰考虑 实现数目很大的虚拟通道需高速多路选择开关

避免死锁 (b)包含循环的通道相关图 (d)利用虚拟通道后修改的通道相关图

7.2.3流控制策略 1包冲突的解决 在两个相邻结点之间传送片时，必须具备三个条件 (1) 源缓冲区已存有该片 (2) 通道已分配好 (3) 接收缓冲区准备接收该片 接收缓冲区或输出通道冲突的仲裁 (1) 把后一个包暂时存放在缓冲区 (2) 阻塞后一个包 (3) 扬弃后一个包 (4) 绕道

图7.31解决两个包请求同一条输出通道发生冲突时的流控制方法 (a)用缓冲实现虚拟直通寻径 (b)阻塞流控制 (c)扬弃并重发 (d)阻塞后绕道

2确定寻径和自适应寻径 如何找出一条从源结点到目的结点的路径来传送消息？ 寻径可分为确定和自适应两类 采用确定寻径时，通信路径完全由源和目的地址确定 即寻找的路径是预先唯一确定的，与网络的状况无关 自适应寻径与网络的状况有关，可能会有几条路径 两种寻径都需要无死锁算法

(1)确定寻径 维序寻径算法 按照多维网络维序的特定顺序来选择后继通道 在二维网格网络中称为X-Y寻径 首先沿X维方向确定路径，然后沿Y维方向选择路径 超立体(或n立方体)网络，Sullivan和Bashkow 1977年提出E立方体寻径(E-cube routing)方法----逐维改变 (a) 二维网格网络的X-Y寻径 从任意源结点s=(x1，y1)到任意目的结点d=(x2，y2) 寻径从s开始 首先沿X方向前进一直到d所在的第x2列为止 然后沿Y方向前进直到y2, 即d 总是首先沿X维方向寻径，然后再沿Y维方向寻径，寻径就不会出现死锁或循环等待

(a)二维网格网络的X-Y寻径 与东-北、东-南、西-北及西-南的路径方向对应，X-Y寻径共有4种模式 (2,1;7,6)东-北 (0,7;4,2)东-南 ...

(a)二维网格网络的X-Y寻径 按照维序，可很容易地将X-Y寻径扩充到n维网络 以三维网格为例，可类似地说明X-Y-Z寻径方法 X-Y方式不会产生死锁寻径，可用于存储转发或虫蚀寻径网络，在源和目的结点之间形成一条距离最短的路径 对于环网网络，采用维序寻径方法不能得到最短路径 为减少网络流量或其它原因，不会产生死锁的非最短寻径算法有时会使包通过的路径较长

(b)超立方体网络的E立方体寻径 设有N=2n个结点的n方体。结点的二进制编码为b=bn-1bn-2…b1b0。源结点为s=sn-1sn-2…s1s0，目的结点d=dn-1bn-2…d1d0 现要确定一条从s到d的步数最小的路径 将n维表示成i=1，2，…，n，其中第i维对应于结点地址中的第i-1位。设u=un-1un-2…u1u0是路径中的任一结点 路径根据以下方法唯一地确定 ①计算方向位ri=si-1⊕di-1，其中i=1，2，...，n。使i=1，v=s ②如果ri=1，从当前结点u寻径到下一结点。如果ri=0，则跳过这一步 ③ i←i+1。如果i≤n，则转第②步，否则退出 寻径从维1到维4的顺序进行 如果s和d的第i位相同，则沿维i方向不需寻径 否则从当前结点沿着这一维方向走到其它结点 重复这一过程直到到达目的结点 E立方体寻径也不会产生死锁寻径，也可用于存储转发和虫蚀网络，在源和结点之间形成一条距离最短的路径

图中n=4，k=2，2元4立方体，每维坐标0，1 s=0110，d=1101 r=r4r3r2r1=s⊕d=0110⊕1101=1011 i=1, r1=1，v=s=0110寻径到v=v⊕2^0=0110⊕1=0111 i=2, r2=1，v=0111寻径到v=v⊕2^1=0111⊕10=0101 i=3, r3=0，跳过维i=3这一步 i=4, r4=1，v=0101寻径到v=v⊕2^3=0101⊕1000=1101=d

(2)自适应寻径 自适应寻径要特别注意避免死锁 虚拟通道的概念使实现自适应寻径更经济和更灵活 网格连接网络中，同一维的所有连接都使用虚拟通道 图7.34是一个用X-Y寻径的网格网络，Y维上用了2对虚拟通道 图7.34(c)中的虚拟网络可用来避免消息在向西传输出现的死锁，因为所有向东的X通道都没有使用 图7.34(d)中的虚拟网络使用另一组Y方向虚拟通道来支持只向东的传输 不同的时刻使用两个虚拟网络，死锁就可自动避免 P424L3，X 改成 Y

图7.34 利用虚拟通道避免死锁的自适应X-Y寻径 (a)没有虚拟通道的原形网络 (b)Y维方向有两对虚拟通道 (c)向西方向传输信息 (d)向东方向传输信息 c,d有循环等待吗

两条虚拟通道的网格形网络 图7.35是在X维和Y维方向各有两条虚拟通道的网格形网络 这些虚拟通道可生成4个虚拟网络 西-北方向通信应使用图7.35(b)所示的虚拟网络 类似地，其它方向的通信可构造另外3个虚拟网络 任何一个虚拟网络都不会出现环路 在这些网络上实现X-Y寻径方法时，可完全避免死锁 如果相邻结点之间的两对通道都是物理通道，那么4个虚拟网络中任何两个都可同时使用而不会产生冲突 如果相邻结点之间两对虚拟通道只能共享一对物理通道 只有(b)和(e)或(c)和(d)可同时使用 其它组合如(b)和(c)，或(b)和(d)，或(c)和(e)，或(d)和(e)都不能同时存在，因为缺少通道 网络的通道数增加，寻径的自适应性也将增加 成本的增加将很可观，要避免使用过多的资源 P425L3，第1个b和c 改成 b和e

图7.35 双通道网格网络可实现4个虚拟网络 (a)双通道的3×3网络 (b)西-北子网 (c)东-北子网 (d)西-南子网 (e)东-南子网 b,c,d,e有循环等待吗

7.2.4选播与广播寻径算法 四种通信模式 (1)单播(unicast),一对一传送 (2)选播(multicast),一个源结点发送同一个消息到多个目的结点 (3)广播(broadcast),一个源结点发送同一个消息到全部结点 (4)会议(conference),对应于多到多的通信情况

广播与选播算法 广播 将一个结点的数据复制到全部N个结点 选播 将一个结点的数据复制到多个(N'个)结点，1≤N'≤N 研究广播与选播算法的目的是尽量利用互连网的并行传输能力，寻找花费时间最少或者动用信道次数(又称"流量"或"通道数")最少的方案 这里的并行传输，指多个结点向同一方向的相邻结点发送自己的数据副本。向不同方向进行的发送不能同时进行(具有这种能力的互连网不属于现在的讨论范围) 不同的网络，适用的广播与选播算法也不同

选播 选播算法的设计目标有3种 时间最少 流量最少 在时间最少的多个方案中选取流量最少方案 选播时间最少算法是通过单播时间最少算法裁剪而成(P426图7.36(a)→(b)) 选播流量最少算法是最小成本生成树算法，可先短边后长边“长树”，也可先长边后短边“砍树”(P426图7.36(c)) 实现第3种目标的一种重要算法是贪婪算法(P426图7.36(b)) 不论何种网络，贪婪算法总是重复使用一个固定的操作规则 从当前拥有数据的结点出发，向需要数据的结点数最多的方向并行传送一步 对剩余目的结点如此循环，直至传遍所有需要数据的结点 如果最后发现某个通道(即一次数据发送操作)不在通往给定目标结点的路径上，则应将其删去

图7.36 贪婪算法 5次点对点, 1个流量为相邻结点一次传输 向可达结点数最多的方向移动1步 向最近的结点的方向移动1步 扩散 4 3 4 2 4 1 4 6 向最近的结点的方向移动1步 5 扩散 4 1 2 3

图7.37 贪婪算法4立方体广播树和选播树 (a)根结点为0000的4立方体。超立方体广播树的流量最小 (b)一棵贪婪选播树，从结点0101发送包到7个目的结点1100, 0111, 1010, 1110, 1011, 1000, 0010

贪婪选播算法 贪婪选播算法的基本思想 向那些可达到最多剩余目的结点的维方向发送包 图7.37(a)是一个根结点为0000的4立方体。超立方体广播树的流量最小 图7.37(b)是一棵贪婪选播树，从结点0101发送包到7个目的结点1100, 0111, 1010, 1110, 1011, 1000, 0010 从源结点S=0101开始，由维4方向可达到最多的5个目的结点，剩余2个目的结点, 由维2方向可到达最多的2个目的结点。第1层所用的通道是0101→0111和0101→1101 从结点1101 ，由维1方向可到达最多的4个目的结点，剩余3个目的结点, 由维2方向可到达3个目的结点。第2层所用的通道是1101→1111，1101→1100和0111→0110 同理，第3层所用的通道是1111→1110，1111→1011，1100→1000和0110→0010 第4层所用的通道是1110→1010

贪婪选播算法 扩充选播树 首先比较所有各维方向的可达性(reachability) 然后选择某些维使剩余目的结点的集合最小 如果两维之间有连线，那么选择其中任何一维都可。因此，所生成的树不唯一 已证明贪婪选播算法所需的通道数比多次单播或广播树少 虫蚀寻径网络实现选播操作时，每个结点的寻径器应有复制片缓冲区中数据的能力 为与选播树或广播树的增长同步，树中同一层的所有输出通道必须在传输向前推进一层之前处于就绪状态，否则中间结点需要增加缓冲区

P426图7.36 (a)指出总共有1个源结点S和5个目的结点 图(b)指出从S出发 (1)单级网格网(Mash网)贪婪算法 P426图7.36 (a)指出总共有1个源结点S和5个目的结点 图(b)指出从S出发 首先向右邻结点发送数据，因为S的左方只有1个目的结点、上方有3个目的结点、右方有4个目的结点 第二步从这2个拥有数据的结点出发，可再向右发送(有3个目的结点)，也可改向上发送(也有3个目的结点)，…… 只要每步遵守贪婪算法的规则，最后形成的不同路径树的时间和流量都相同 5次点对点, 1个流量为相邻结点一次传输 向可达结点数最多的方向移动1步

(2)单级立方体网络贪婪算法 P426图7.37(a)指出广播算法的时间是4，流量是15。Cube0 ～Cuben-1的使用顺序对广播算法的时间和流量没有影响，但对图(b)的选播算法的时间和流量有影响 简单的例子(下图)：已知N=4，维数n=2，源结点是0，目的结点是1和3 源结点编号的二进制形式00在bit0位与两个目的结点的二进制形式01、11都不相同，而在bit1位仅与一个目的结点的二进制形式不同，所以应该先传bit0方向、再传bit1方向，如图(a)所示，流量=2 如果先传bit1方向、再传bit0方向，如图(b)所示，流量=3

P427采用Cube3、Cube1、Cube0、Cube2的发送顺序，如下图所示，时间=4，总流量=10 P426图7.37(b)的例子 源结点编号的二进制形式0101在Cube0 ～Cube3位分别与5、5、4、5个目的结点的二进制形式不同，所以Cube2方向应该最后发送，其它3个方向的发送先后顺序则没有限制 P427采用Cube3、Cube1、Cube0、Cube2的发送顺序，如下图所示，时间=4，总流量=10 可达到最多的5个目的结点 可达到剩余2个目的结点最多的2个目的结点 7 3 2 5 1 结果

7.3 互连网络实例 着重研究几种多处理机的互连网络 总线结构、环形互连、交叉开关、混洗交换互连 处理机系统采用哪种互连结构主要取决于系统的最大通信量 反过来，系统的最大通信量受到互连结构的限制

7.3.1 总线互连 目前，大部分处理机内部采用总线结构 CPU与存储器之间有系统总线 存储器与输入输出设备之间有I/O总线 总线与总线之间通过总线桥连接 优点：结构简单，能很方便实现广播通信 缺点：带宽低，发生总线冲突的可能性大 总线冲突的解决办法 (1) 设置静态优先级 (2) 在同步方式中采用时间片 (3) 采用动态优先级(如LRU法等) (4) 先来先服务

总线结构的多处理机 本地 存储器 全局

总线结构的多处理机 提高总线的通信带宽的方法 (1) 采用多总线结构 (2) 层次总线结构 (3) 多维总线结构 多总线 西门子公司的SMS系统(Stractured Multiprocessor System) 8条总线连接128个处理机 层次总线 卡内基梅隆大学的Cm*多处理机系统采用层次总线结构 三级总线：群总线、Map总线、处理机总线 每群14台处理机

SMS多总线结构 主机 P1 P2 P16 P17 P18 P32 P113 P114 P128 …… 总线驱动器

群间总线 卡内基梅隆大学的Cm*层次总线结构 Cm … Km B M IO P

7.3.2环形互联 既具有总线型互连的简单性，又可克服总线所固有的缺点 信息的传送过程是发送进程把信息放到环上，通过环形网络不断向下一台处理机传播，直到此信息回到发送者为止

IEEE 802.5令牌环(Token Ring) IEEE 802.5令牌环(Token Ring)标准是把环形网络看作逻辑总线的协议 发送信息的处理机拥有一个唯一的令牌，同一时刻只有一台处理机持有这个令牌 发送者发送信息时，环形网络的作用如同总线一样，其它处理机都处于接收信息的状态 信息传送结束时，发送者播送一个令牌，这个令牌是在普通信息中不会出现的特定信号。每台处理机依次看到令牌 如果某台处理机等待发送信息，那么它接收这个令牌而不再传递给下一台处理机，这时这台处理机就可通过环形网络发送信息 假如没有需发送信息的处理机，那么令牌就在环形网络上不断循环，直到某台处理机需发送信息为止

令牌环 令牌环的优点是点点连接，而不是总线连接，其物理参数更容易控制 令牌环形互连非常适于高带宽的光纤通信。N较小的总线互连系统很难采用光纤通信，N较大的系统也还未实现 令牌环形互连的主要缺点 每个总线接口都有延迟, 通常是1位的延迟 互连处理机台数增加，环中的信息传输延迟正比例地增加 系统负载很重时，系统的带宽不会像总线互连系统那样下降

7.3.3 交叉开关互连 交叉开关网络，把N台处理机和N个存储器连接起来 图中处理机台数与存储器个数相等，一般情况是存储器数目等于或是处理机数目的几倍 网络中每个交叉点是一个允许任何一台处理器与任何一个存储器连接的开关

交叉开关互连 系统允许N个存取操作并行执行 任意两个存取操作不能涉及同一台处理机或同一个存储器 如果两个或两个以上存取操作同时要访问某个存储器，就发生争用现象 如处理机P1和P2同时要访问存储器M1 减少争用，在系统结构方面大有文章可做 如果争用是多台处理机同时要访问同一存储模块中不同单元的数据而引起的 一种解决争用的方法是尽量使这些数据平均地分配到多个不同的存储模块，而不要把它们集中在一个存储模块 把一个数据块中数据依次分配到相继的存储模块 共享程序代码也应这样分配 这样，当两台或两台以上的处理机同时访问共享程序代码或数据时，争用只使其中一台处理机延迟一个周期 只要两台处理机顺序地不断地访问，两者不会再发生冲突 这种寻址技术也可用于流水线多处理机中，使各台处理机能彼此步调一致地存取向量数据

7.3.4 混洗交换互连和合并开关 混洗交换网络能提供一种重要的功能，称为合并开关 它使某些操作在网络一级并行地执行，从而减少争用现象 否则这些需要访问存储器的操作只能串行地执行 对需互斥地访问共享变量的进程，这种方法很有潜力 互斥地访问共享变量限制了大部分多处理机系统的性能 当出现多个进程要存取某个共享变量时，无论系统再增加多少台处理机也不可能再提高其速度

8台处理器和8个存储器通过混洗交换互连网络连接

7.3.5Omega网络 采用全混洗函数和交换函数，又称混洗交换网络 Omega网已用于伊利诺依大学的Cedar多处理机、IBM的RP3系统和纽约大学Ultracomputer N个输入的Omega网络有log2N级 每级有N/2个2×2的四功能交换开关 每级的拓扑结构相同 采用单元控制 能实现任意一个输入端到任意一个输出端的连接 不能同时实现多个输入端到多个输出端的连接 通过检查二进制目的地址编码来控制数据路径 目的地址编码从高位开始的第i位为0时，第i级的2×2开关的输入端与上输出端连接，否则输入端与下输出端连接

2路洗牌相当于8个输入分成2个子组，2个子组均匀洗牌 同时实现06和47有冲突 8个输入端的Omega网络 一个开关两个输入， 2路(组)洗牌 2组 每组各接同一开关的两个输入 2路洗牌相当于8个输入分成2个子组，2个子组均匀洗牌 同时实现06和47有冲突 冲突的还有：30和51，30和73，50和71等 1 2 3

开关设置 从输入端001到输出端011的路径。使用开关A、B、C 目的地址编码011的最高位“0”，输入端001与开关A的上输出端(编号为2)连接, 开关A设置成直送状态 011的次高位是“1”，输入端4和下输出端连接，开关B设置成交换状态 011的最低位是“1”，输入端4和下输出端连接，开关C设置成直送状态 输入端101到输出端101的路径 ？

阻塞

Omega网络 如果采用级控制，是STARAN交换网的逆网 如果采用部分级控制，是STARAN移数网的逆网 因此，Omega网的许多性质与多级立方体网相反，如发生冲突的情况 Omega网属于多级互连网 当有N个输入端时，共有N^(N/2)个变换 要同时实现任意一个输入端到任意一个输出端的连接，共需N!个变换 8个输入端的Omega网络实际上只能实现全部变换的10%(8^4/8! = 4096/40320=0.1016)，有90%的变换将引起阻塞 Omega网络是一种阻塞网络，采用多次通过来解决冲突 有N个输入端时，实现连接的通过次数最多为log2N

Omega网能够实现从任意一个输入端到所有输出端的广播 采用上播或下播开关设置

4×4开关元件作为构成块的Omega网络，级间是4路洗牌连接，而不是2路洗牌连接 16个输入端的Omega网络的级数为log416=2 4路洗牌相当于16个输入端平均地分成4个子组，然后4个子组均匀地洗牌 采用k×k开关元件时，可定义k路洗牌函数来构造更大的级数为logkn的Omega网络 1 2 3

蝶式网络 16个8×8交叉开关构成的两级64×64碟式网络 1 64个输入端的蝶式网络 1 7 16个8×8交叉开关构成的两级64×64碟式网络 64个输入端的蝶式网络 由2级(2=logkn=log864)8×8交叉开关组成 开关数16=8+8=n/k*logkn=64/8*log864 级间采用8路洗牌连接，64/8组(路)=8个结点/组 第0个8×8模块的输出连至第1级的各个开关的第0个输入 0输出连至第1级的第0个开关的第0个输入 1输出连至第1级的第1个开关的第0个输入 ... 7输出连至第1级的第7个开关的第0个输入 第1个8×8模块的输出连至第1级的各个开关的第1个输入 0输出连至第1级的第0个开关的第1个输入 1输出连至第1级的第0个开关的第1个输入 7输出连至第1级的第7个开关的第1个输入 第7个8×8模块的输出连至第1级的各个开关的第7个输入 0输出连至第1级的第0个开关的第7个输入 1输出连至第1级的第0个开关的第7个输入 7输出连至第1级的第7个开关的第7个输入

级间采用8路洗牌连接(从第2级向左看，8个结点一个开关，8路， 512/8=64个结点/路) 192个8×8交叉开关构成的三级512×512碟式网络 0 8 0 x8 1 x8 7 =512 63 512个输入端的蝶式网络 级间采用8路洗牌连接(从第2级向左看，8个结点一个开关，8路， 512/8=64个结点/路) 从第0,1级向右看，64个结点一组，512/64=8组(路)，8路洗牌，第2级8个8×8开关构成一个64个结点的组 3级(3=logkn=log8512)8×8开关组成 0,1级为16个8×8开关构成的两级64×64碟式网络，64×64碟式网络共8个 第2级8个8×8交叉开关构成64路连接 64路连接共512/64=8组 用这种模块结构构造更大的蝶式网络只要增加级数即可 开关数192=16x8+8x8=n/k* logkn =512x3/8 蝶式网络不允许广播连接，所以蝶式网络是Omega网络的一个有限的子集 每个64×64的方框相当于图7.45(a)的两级蝶式网络

级间采用8路洗牌连接 级间采用8路洗牌连接(从第2级向左看，8个结点一个开关，8路， 512/8=64个结点/路) 从第0,1级向右看，64个结点一组，512/64=8组(路)，8路洗牌 第0个64×64模块的输出连至第2级的各个开关的第0个输入 0输出连至第2级的第0个开关的第0个输入 1输出连至第2级的第1个开关的第0个输入 ... 63输出连至第2级的第63个开关的第0个输入 第1个64×64模块的输出连至第2级的各个开关的第1个输入 0输出连至第2级的第0个开关的第1个输入 1输出连至第2级的第1个开关的第1个输入 63输出连至第2级的第63个开关的第1个输入 第7个64×64模块的输出连至第2级各个开关的第7个输入 0输出连至第2级的第0个开关的第7个输入 1输出连至第2级的第1个开关的第7个输入 63输出连至第2级的第63个开关的第7个输入

7.3.6 蝶形操作 略

7.3.7合并网络和取与加指令 略