计算机系统结构复习

互联网络

互联网络要同时会背概念、会算图指标、会做互连函数变换、会按 Omega 网络寻径。复习时把“拓扑 + 函数 + 寻径”分开整理。

来源：周粤嘉——互联网络.pdf 互连函数静态网络动态网络超立方体Omega寻径

9复习段落

21讲义截图

5自测问题

怎么用本页

先看主线，再背公式，最后做题

每个专题页都按“概念框架、公式变量、典型题型、原讲义对照、自测问题”组织。复习时从左侧目录跳转，遇到计算题直接回到高亮公式段。

本页材料 9 个复习段落

21 页原讲义截图可展开核对，适合考前查原表、原图和例题。

重点标签

011. 基本概念与指标 022. 互连函数 033. 静态互连网络 044. 寻径

原资料预览 周粤嘉——互联网络.pdf

正文已经把知识点重新组织；这里保留讲义页面缩略图，方便你在需要时回看原版题目、图和表。

1. 基本概念与指标

互联网络是计算机部件、节点或系统之间的连接，目标是在延迟、成本、能耗等约束下传输尽可能多的数据，避免成为瓶颈。

指标	含义	复习用途
网络规模 N	网络中结点个数。	确定可连接部件数量。
结点度 d	与结点相连的边数，包括入度和出度。	反映单结点连接复杂度。
结点距离	两结点之间最短路径长度。	用于寻径和延迟分析。
网络直径 D	任意两结点距离的最大值。	越小，最坏通信路径越短。
等分宽度 b	把网络切成两半所需切断的最少边数。	反映最大流量潜力。
对称性	从任意结点看拓扑结构都相同。	对称网络更容易分析和扩展。

2. 互连函数

互连函数描述输入端编号 x 会连接到哪个输出端 f(x)。它可以用输入输出对、连线图、循环表示法、二进制位变换等方式表示。

函数	变换规则	记忆方式
恒等函数	f(x) = x。	同号直连。
交换函数	二进制地址第 k 位取反。	按某一位配对交换。
均匀洗牌函数	二进制编号循环左移一位。	像洗牌一样交叉。
逆均匀洗牌	二进制编号循环右移一位。	洗牌函数的逆。
蝶式函数	最高位与最低位互换。	多级立方体网络基础。
反位序函数	二进制位序颠倒。	如 001 变 100。
移数函数/PM2I	编号按模 N 加减某个偏移。	环上平移。

做函数题先把编号写成固定长度二进制串，按规则变换，再转回十进制。

3. 静态互连网络

静态网络的结点连接在运行中不变，适合用图来分析度、直径、等分宽度和最短路径。

网格/环/线性阵列

结构直观，适合考察结点距离和直径。

超立方体

N = 2^n 个结点，每个结点用 n 位二进制编号，相邻结点通常只差 1 位。

超立方体的 E-cube 寻径可以按源地址和目的地址不同的位逐位翻转，路径长度等于两者二进制编号的汉明距离。

4. 寻径

类型	含义	例子
确定性寻径	路径完全由源结点和目的结点地址决定，不看当前拥塞。	二维网格 X-Y 寻径，超立方体 E-cube 寻径。
自适应寻径	根据资源、拥塞或故障状态动态选择路径。	可避开拥塞结点，提高网络利用率。

静态网络最短路题：把网络当图，优先看二进制编号差异或坐标差异。

网格 X-Y：先沿 X 方向，再沿 Y 方向。

超立方体 E-cube：逐位翻转不同位，直到到达目的地址。

5. 动态互连网络

网络	特点	代价
总线	结构简单、成本低。	每次只能支持有限传送，带宽窄，争用明显。
交叉开关	可同时建立多个无冲突连接，带宽和互连能力强。	n × n 需要 n^2 个交叉点，规模大时代价高。
多级互连网络 MIN	用多级小开关实现较丰富的置换。	可能阻塞，寻径和控制更复杂。

多级网络的控制方式包括级控制、单元控制、部分级控制；级间互连模式包括均匀洗牌、蝶式、多路洗牌、立方体连接等。

6. Omega 网络

Omega 网络是多级混洗-交换网络。N 个输入时有 log2N 级，每级 N/2 个 2×2 开关，级间采用均匀洗牌连接，每个开关可直送或交换。

把源和目的写成 n 位二进制。

每一级根据目的地址的某一位决定开关直送或交换。

也可用源和目的异或来判断各级需要改变哪些位。

画路径时按“混洗连接 + 开关状态”逐级推进。

考试重点资料最后的习题 9.13 就是 Omega 网络寻径：通过异或得到两个处理机经过的开关应有连接方式。

7. 考前抓手

8. 公式与习题精讲

互连函数公式

Cube_i(x) = x xor 2^i

均匀洗牌：二进制循环左移 1 位；逆均匀洗牌：二进制循环右移 1 位

n 维超立方体：N = 2^n，结点度 = n，直径 = n，两点距离 = 汉明距离

函数	公式/操作	例子
交换函数 Cube_i	f(x) = x xor 2^i	8 个端口中，x=3(011)，i=0，则 f=2(010)。
均匀洗牌	二进制循环左移 1 位	abc -> bca。
逆均匀洗牌	二进制循环右移 1 位	abc -> cab。
蝶式函数	最高位与最低位互换	abcde -> ebcda。
反位序	二进制位序完全反转	abcde -> edcba。
移数/PM2I	f(x) = x ± 2^i mod N	环形编号上前后移动。

静态网络常用结论

网络	结点度	直径/距离	做题抓手
n 维超立方体，N=2^n	n	直径 n，两点距离为汉明距离。	源和目的二进制有几位不同，最短路就几步。
混洗交换网络	按题图判断	常见直径 2n - 1	资料例题中 2^5 结点直径为 2n - 1 = 9。
网格	内部结点通常为 4	曼哈顿距离	X-Y 寻径先横后竖。

Omega 网络寻径题

N 输入 Omega 网络有 log2N 级，每级 N/2 个 2x2 开关，总开关数为：

开关数 = (N/2)log2N

把输入和输出编号写成 n 位二进制。

按目的地址位逐级决定每个 2x2 开关直送或交换；教材级编号常写作 n-1 到 0。

若题目给多条连接请求，分别画出路径，看是否在同一开关同一输出端发生冲突。

资料习题 9.13 的简法：用源地址 xor 目的地址判断路径中需要改变哪些位，再映射到各级开关状态。

例题模板

N=8 时有 3 级，每级 4 个 2x2 开关。若请求 P6(110) 到 P0(000)，先写出源/目的二进制，再按目的位 0、0、0 逐级选择输出方向，并检查与其他请求是否争用同一开关输出。

9. 原题练习区

习题 9.9原题截图：p.20 解答：p.21

互连函数、混洗交换网络与移数网络

设函数的自变量是十进制数表示的处理机编号。现有 32 台处理机，其编号为 0,1,2,...,31。

分别计算：Cube2(12)、σ(8)、β(9)、PM2I+3(28)、Cube0(σ(4))、σ(Cube0(18))。
用 Cube0 和 σ 构成混洗交换网，每步只能使用 Cube0 和 σ 一次。网络直径是多少？从 5 号处理机发送数据到 7 号处理机，最短路径要经过几步？请列出经过的处理机编号。
采用移数网络构成互连网，网络直径是多少？结点度是多少？与 2 号处理机距离最近的是哪几个处理机？

展开答案要点

第1问：Cube2(12)=8，σ(8)=16，β(9)=24，PM2I+3(28)=4，Cube0(σ(4))=9，σ(Cube0(18))=7。

混洗交换网络直径为 2n - 1 = 9。5 到 7 的最短路径为 6 步：00101B -> 01010B -> 10100B -> 01001B -> 10010B -> 10011B -> 00111B。

移数网络直径为 floor(5/2)=3，结点度为 2n - 1 = 9。与 2 号处理机距离最近的是 13、15、21、23 号处理机。

习题 9.13原题截图：p.21