2024 计算机系统结构复习
#

Tongji University. 2024/12/24
Author: Hyoung Yan

本文框架
#

本文按照 2024 计算机系统结构考纲整理。

考试题型：

单项选择题（每题 2 分，共 26 分）
填空题（每空 1 分，共 14 分）
大题（6 题，共 60 分）

大题的复习范围
#

会利用 CPU 性能公式比较多种设计方案的优劣，尤其是 CPI 的计算 CPU 性能公式
- 公式一 $$CPU时间=一个程序的CPU时钟周期数 \times 时钟周期长度$$
- 公式二 $$CPU时间=指令数 \times CPI \times 时钟周期长度$$
- 公式三 $$CPU时间=(\sum_{i=1}^{n} CPI_i \times IC_i)\times 时钟周期长度$$ 推导出 CPI 的公式： $$CPI=\frac{CPU时钟周期数}{指令数}=\frac{\sum_{i=1}^{n} (CPI_i \times IC_i)}{IC}=\sum_{i=1}^{n}(CPI_i \times \frac{IC_i}{IC})$$

Amdahl 定律计算加速比 Amdahl 定律：计算机系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率火占总执行时间的比例有关。 $$S_n=\frac{T_0}{T_n}=\frac{1}{(1-F_e)+\frac{F_e}{S_e}}$$
- Sn: 整个系统的加速比
- T0: 系统在原有执行方式下的执行时间
- Tn: 系统在新的执行方式下的执行时间
- Fe: 增强比例（改进部分占整个任务的时间比例）
  Fe=可改进部分占用的时间/改进前整个任务的执行时间
- Se: 增强加速比（改进部分的加速比）
  Se=改进前改进部分的执行时间/改进后改进部分的执行时间

指令系统设计：设计操作码（3 种方法都要）、设计指令字（操作码+若干地址码）格式 操作码的评价方法
- 平均码长：$ p_i $频率，$ l_i $编码长度 $$L=\sum_{i=1}^{n} p_i \times l_i$$
- 信息冗余量： $$R=1-\frac{H}{l}$$
- 信息熵： $$H=-\sum_{i=1}^{n} p_i \times \log_2 p_i$$
操作码的优化设计
- 固定长度操作码：所有指令的操作码长度都是相同的。如果需要编码的指令有 n 条，则固定长度操作码的位数至少需要 $log_2n$ 位。目前许多的 RISC 采用该思想。
  - 优点：非常规整，硬件译码简单
  - 缺点：操作码长度过长，浪费存储空间
- Huffman 编码：概率高的用短位数表示，概率低的用长位数表示。.
  - 特点：是最优化的编码方式（平均码长最短，信息的冗余量最小），但操作码很不规整。
- 扩展编码法：是固定长度操作码和 Huffman 编码法相结合形成的。即：先根据指令使用频率的宏观分布，将指令分成有限几类；然后根据 Huffman 编码原理，对使用频率高的指令类采用短位数，使用频率低的指令类采用长位数；同一类指令内采用固定长度操作码。
  - 等长扩展编码法：每类指令的操作码长度相同
    - 等长（4-8-12）15/15/15
    - 等长（4-8-12）8/64/512
  - 不等长扩展编码法：每类指令的操作码长度不同
指令字设计优化
- 问题：操作码和地址码的优化，会造成指令字的不定长，无法同时满足速度快和空间省。可以合理结合，形成定长或多种长度的指令字，例如长操作码+短地址码。
- 变长编码格式：寻址方式通过设置专门的地址描述符给出，因为指令有多个操作数，无法在操作码中进行编码。
- 定长编码格式：将操作类型和寻址方式一起编码到操作码中。当寻址方式和操作类型非常少时，这种编码格式非常好。可以有效降低译码的复杂度。
- 混合型编码格式：提供若干种固定的指令字长。以期达到既能够减少目标代码长度又能降低译码复杂度的目标。

Cache 存储系统的性能分析，重点是 AMAT
- CPU 执行时间
- 平均存储器访问时间（AMAT）

Cache 缺失率与块大小之间的关系，会计算最佳块大小
- 增加块大小会先降低后增加缺失率：增加块大小会降低强制缺失率，这是利用了空间局部性原理。但因为它减少了 Cache 中的块数，加重了冲突缺失，如果 Cache 容量较小时，甚至会有容量缺失。
- 增加块大小会增加缺失代价
- 块大小的选择取决于较低层存储器的延迟和带宽。
  - 低延迟和高带宽存储器使得块大小要大些，因为这样在每次缺失时 Cache 可以获得更多的字节，而缺失代价只有少量的增加；
  - 相反，高延迟和低带宽存储器希望块大小要小些，因为较大的块并不能节省多少时间。
- 最佳块大小：使缺失率和缺失代价的乘积最小

掌握提高 Cache 存储系统性能的途径及具体方法，每种方法只需了解原理即可 根据 AMAT 公式可以看出，提高 Cache 性能的途径有：
- 降低缺失代价
  - 多级 Cache
  - 请求字处理技术：尽早重启动，请求字优先
  - 让读缺失优先于写
  - 合并写缓冲区
  - 牺牲者 Cache
- 降低缺失率
  - 增加 Cache 块大小
  - 增加 Cache 容量
  - 增加相联度
  - 路预测和伪相联 Cache
  - 编译优化
- 通过并行性降低缺失代价/缺失率
  - 非阻塞 Cache 技术
  - 指令和数据硬件预取
  - 编译控制的预取
- 降低 Cache 命中时间
  - 小而简单的 Cache
  - 虚拟 Cache
  - 流水 Cache 存取
  - 跟踪 Cache

流水线的性能分析，要求会根据具体流水线进行计算，重点掌握消除瓶颈功能段的方法
- 吞吐率：单位时间内流水线所能流出的任务数或能流出的结果数。
  - 各段时间相等
  - 各段时间不等
- 加速比：完成同样一批任务，不使用流水线完成所用的时间与使用流水线完成所用的时间之比。
  - 各段时间相等
  - 各段时间不等
- 效率：是指流水线的设备利用率。在时空图上，流水线的效率定义为 n 个任务占用的时空区与 m 个功能段总的时空区之比。
  - 各段时间相等
  - 各段时间不等
- 流水线最佳段数的选择：从性价比角度出发流水线存在着最佳段数。
流水线瓶颈：流水线的 TP 和 TPmax 主要由流水线中执行时间最长的那个功能段来决定，这个功能段就成了整个流水线的“瓶颈”。
- 将流水线中的瓶颈再细分；
- 通过重复设置多套瓶颈功能段，让多个瓶颈功能段并行工作。

流水线中相关性分析，会分析数据相关（3 种）和控制相关，并掌握它们的解决方法 相关（Correlation or Dependency）也称为冲突（Hazard）是指邻近指令之间存在着某种关系，影响指令的重叠执行或流水线的正常运行。
- 资源相关：争用部件
- 数据相关：改变操作数的读写顺序，使得顺序执行与流水执行时结果不同。 “先写后读”相关在流水线顺序执行和乱序执行时都可能发生，“先读后写”相关和“写写”相关只有在流水线乱序执行时才可能发生，而“读读”相关无需处理。
  数据相关类型：
  - 先写后读相关（RAW）
  - 先读后写相关（WAR）
  - 写写相关（WW）
  解决方法
- 控制相关：分支、转子程序、中断因程序的执行方向可能被改变而引起的相关，也称为全局相关（而将前面介绍的其他相关称为局部相关）。可能改变程序执行方向的指令主要包括：无条件转移、条件转移、子程序调用、中断等。
  条件转移的处理：
  - 条件出来前：提前形成条件码，预测
  - 条件出来后：停顿
  中断的处理：
  - 不精确断点
  - 精确断点

超长指令字处理机的工作原理，会结合循环展开进行指令调度
- 在编译时，编译程序找出指令间潜在的并行性，将多个能并行执行的不相关或无关的操作先行压缩组合在一起，形成一条有多个操作段的超长指令；
- 运行时，不再用软件/硬件来检测其并行性，直接由这条超长指令控制机器中多个相互独立的功能部件并行操作。
- 每个操作段控制其中的一个功能部件，相当于同时执行多条指令。

超标量流水线的工作原理，会进行调度 超标量处理机必须有两条或两条以上能够同时工作的指令流水线，采用多发射方式：
- 每个周期同时取多条指令、同时译码多条指令、同时执行多条指令、同时写回多个运算结果。
- 需要多个取指令部件、多个指令译码部件和多个写结果部件，设置多个指令执行部件，复杂的指令执行部件一般采用流水线结构。
- 设计目标是每个时钟周期平均执行多条指令，ILP 的期望值大于 1。
调度方法
- 顺序发射顺序完成
- 顺序发射乱序完成
- 乱序发射乱序完成

向量处理机中的向量链接技术，会计算整个向量程序的执行时间 对于有写读数据相关的向量指令，可以采用“相关专用通道”：从一个流水线部件得到的结果直接送入另一个流水线部件的操作数寄存器，这样多条向量指令可以并行执行，这种技术称为流水线的链接技术。

多级互连网络的设计，需掌握其基本原理方可进行设计
多级互连网络用若干个较小规模的开关模块组成开关级，开关级之间有固定连接的级间连接，通过控制信号改变开关模块的输入端与输出端之间的连接状态，从而可改变网络输入端与输出端之间的连接。

阻塞型网络（阻塞原因的分析）和全排列网络（实现方法） 在同时实现两对或多对入端和出端之间的连接时，有可能因争用数据传送通路而发生冲突的网络称为阻塞型网络。反之，将能够实现所有可能的入、出端间的连接而不发生冲突的互连网络称为非阻塞型网络或全排列网络。例如：在 Omega 网络中，如果同时进行 5→0（JGA=101）和 7→1（LGA=110）连接时，产生冲突，不能同时进行（见后图）；则 Omega 网络就是阻塞型网络。
阻塞原因：
全排列网络的实现
- 多次经过同一多级网络：将这种只要经过重新排列已有入出端对的连接，就可以完成所有可能的入出端间的连接而不发生冲突的互连网络称为可重排列网络。
- 多个多级网络串联使用：例如：将多级立方体网络和它的逆网络连在一起，省去中间重复的一级后，构成的全排列网络称为 Benes 网络。

Omega 网络：会画出其拓扑结构 Omega 网络：采用 $ 2 \times 2 $ 的四功能开关，对于 $ N \times N $ 网络，有 $ n = \log_2 N $ 个开关级，每级有 $ N / 2 $ 个开关； $ n $ 个开关级从输入端到输出端依次为 $ K_{n-1}, \dots, K_1, K_0 $，$ n+1 $ 个级间连接依次为 $ C_n, \dots, C_1, C_0 $，
其中 $ C_0 $ 为恒等置换，$ C_1 \sim C_n $ 都为均匀洗牌置换；开关采用单元控制方式。本网络也称为：多级洗牌置换网络或多级混洗网络。

其他题的复习范围
#

计算机系统层次结构：分层的思想
分层的目的：
- 有利于正确地理解计算机系统的工作，明确软件、硬件和固件在计算机系统中的地位和作用；
- 有利于理解各种语言的实质及其实现；
- 有利于探索虚拟机器新的实现方法，设计新的计算机系统。

衡量机器性能的唯一固定而且可靠的标准是什么？ 真正执行程序的时间

常用的基准测试程序有哪些？ 主要有 5 类测试程序（以测量准确程度递减的次序排列）：
- 真实程序
- 改造/模拟程序
- 核心测试程序
- 小测试程序
- 合成测试程序
基准测试程序套件：把应用程序中用得最频繁的那部分核心程序作为评价计算机性能的标准程序（benchmark）。
- 桌面机 benchmarks：SPEC CPU，SPECviewperf
- 服务器 benchmarks：SPEC CPU，TPC
- 嵌入式 benchmarks：EEMBC

并行性的常用实现技术，并结合本课程的内容进行举例
- 时间重叠：让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而提高效率。
  - 指令流水线
- 资源重复：通过重复设置资源（硬件、软件、信息、时间）来提高可靠性或性能。
  - N 模冗余结构（提高可靠性）、多值存储器（提高信息存储密度）、多处理机（提高速度和可靠性）
- 资源共享：利用软件的方法让多个用户按一定的时间顺序轮流地使用同一套资源，以提高资源利用率，从而提高整个系统的功能。
  - 多道程序分时系统

设计计算机系统的常用定量准则
- 加快经常性事件的速度：使用 Amdahl 定律
- CPU 性能公式：通过公式计算和比较不同设计方案的性能
- 局部性原理：程序执行中频繁重复使用最近已使用过的数据和指令，分为时间局部性和空间局部性
- 利用并行性：通过并行处理提高系统性能

Flynn 分类法 指令流是机器执行的指令序列，数据流是指令所操作的数据序列。 Flynn 分类法是根据指令流和数据流的多倍性来划分的，分为四类：
- SISD：单指令流单数据流
- SIMD：单指令流多数据流
- MISD：多指令流单数据流
- MIMD：多指令流多数据流

什么是数据表示？什么是数据结构？
- 数据类型：计算机系统中可以使用和处理的各种数据的类型，主要有：整数、布尔数、字符、文件、图、表、树、阵列、队列、链表、栈、向量、串等；
- 数据表示：能由硬件直接识别和引用（即有相应运算指令和有硬件支持）的数据类型，例如：定点数据表示、逻辑数据表示、浮点数据表示等。数据表示是数据类型中最常用、也是相对较简单，用硬件实现相对比较容易的；
- 数据结构：带有结构的数据元素的集合，例如：串、队列、栈、向量、阵列、链表、树、图等。数据结构由软件进行实现，转换成数据表示。

RISC 的思想、特点和常用技术，重点掌握重叠寄存器窗口技术 RISC 的思想：减少指令总数和简化指令的功能来降低硬件设计的复杂度，提高指令的执行速度。
RISC 的特点：指令集简单，硬件实现容易
RISC 的关键技术：
- 硬件为主固件为辅
- 在 CPU 中设置数量较大的寄存器组：采用重叠寄存器窗口技术提高使用效率
- 指令的执行采用流水：采用延时转移技术和指令取消技术来降低（条件）转移指令的影响
- 采用认真设计和优化编译系统设计的技术：例如指令流调整技术
重叠寄存器窗口技术：将设置的大量寄存器，分为多个组和一个全局区；每组中分高、本、低三个区；相邻组的高、低区重叠；不同的过程使用不同的组和共享全局区，这样可以加速参数与结果的传递。

常用 Cache 的替换算法的硬件实现，重点掌握比较对法，以及如何降低成本 为什么需要 Cache 替换算法？：当发生块失效，且可以装入新调入块的几个 Cache 块都已经被装满时，此时需要 Cache 替换算法。直接映象方式实际上不需要替换算法，而全相联映象方式的替换算法最复杂。Cache 替换算法全部用硬件实现。
- 轮换法： 本质上是一种FIFO 算法，通常用于组相联映像和地址变换方式中，常见的实现有：
  - 每块一个计数器
    - 装入或替换时，被装入或替换的块计数器置 0，同组其他块的计数器加 1；
    - 命中时，块计数器不变
    - 需要替换时，替换计数器最大的块。
  - 每组一个计数器：本组有替换时，计数器加 1，计数器的值就是要被替换出去的块号。
- LRU 算法： 在块表中为 Cache 的每块都设置一个替换计数器，长度与“组内块号”字段相同。
  - 装入或替换时，被装入或替换的块计数器置 0，同组其他块计数器加 1；
  - 命中时，命中块计数器置 0，同组中比他置 0 前的值小的计数器加 1，其他不变；
  - 需替换时，同组中计数器值最大（一般为全 1）的块被替换。
- 堆栈法： 堆栈法本质上是一种 LRU 算法，用栈顶到栈底的先后次序来记录 Cache 同一组内的各个块被访问的先后次序，栈顶是最近被访问过的块，栈底是最久没有被访问过的块。
- 比较对法： 比较对法本质上是一种 LRU 算法，采用硬联逻辑实现。一个两态的器件（触发器）能够记录两个块之间的先后顺序，多个块之间的先后顺序可以用多个两态器件的组合来实现，从而可以在多个块中找出最久没有被访问过的那个块。

导致缺失的原因分析
- 强制缺失(Compulsory)：对第一个块的第一次访问一定不在 Cache 中，所以该块必须被调入到 Cache 中。也叫作冷启动缺失，首次访问缺失。
- 容量缺失:(Capacity)：如果 Cache 容纳不了一个程序持续执行所需要的所有块，当某些块被替换后，若又重新被访问就会发生缺失。
- 冲突缺失:(Confict)：如果采用组相联/直接相联，若太多的块映射到同一组(块)中，则会出现该组中某块被别的块替换后又被重新访问，这就发生冲突缺失。
规律
- 相联度越高，冲突缺失越少
- 强制缺失和容量缺失不受相联度影响
- 强制缺失不受 Cache 大小影响，但容量缺失却随着容量的增加而减少
减少三种缺失的方法
- 强制缺失（本身很少）：增加块大小，预取
- 容量缺失：增加容量
- 冲突缺失：增加相联度（理想情况下全相联）
许多降低缺失率的方法会增加命中时间或缺失代价

多级 Cache 中的局部缺失率和全局缺失率，会进行计算
- 局部缺失率 本级 Cache 的缺失数除以对本级 Cache 的存储器访问总数。例如：第一级 Cache 的局部缺失率为$缺失率_{L1}$，第二级 Cache 的局部缺失率为$缺失率_{L2}$
- 全局缺失率 本级 Cache 的缺失数除以 CPU 产生的存储器访问总数。例如：第一级 Cache 的全局缺失率为$ 缺失率_{L1} $，第二级 Cache 的全局缺失率为 $缺失率_{L1} \times 缺失率_{L2} $

流水线的特点、常用分类 流水线的特点
- 空间并行性、时间并行性
- 只有连续提供同类任务才能发挥流水线的效率。 尽量减少因条件分支而造成的断流，可以通过编译技术提供连续的相同类型操作
- 每个流水线段都要设置一个流水寄存器。 用于保存本流水线段的执行结果，会使流水线的执行时机加长，是流水线中需要增加的主要硬件
- 各流水线段的时间应该尽量相等。 流水线处理机的基本始终周期等于时间最长的流水段的时间长度
- 流水线需要有装入时间和排空时间
流水线的分类
- 单功能流水线 | 多功能流水线
  多功能流水线细分：
  - 静态流水线 | 动态流水线（同一时间内连接成多种方式、同时执行多种功能）
  - 线性流水线 | 非线性流水线（各个功能段间是否有反馈信号）
  - 部件级流水线 | 处理机级流水线 | 系统级流水线
  - 标量流水线 | 向量流水线
  - 顺序流水线 | 异步流水线

常见的数据相关有哪些？通常在哪些流水线上会出现？
- 先写后读相关 RAW ：写读相关，正相关，数据相关。在流水线顺序执行和乱序执行时都可能发生
- 先读后写相关 WAR ：读写相关，反相关。在流水线乱序执行时可能发生
- 先写后读相关 WAW ：输出相关。在流水线乱序执行时可能发生
- 读读相关不需要处理
数据相关的解决方法
- 先写后读相关 RAW：设置专用路径、退后处理、指令调度
- 先读后写相关 WAR 和写写相关 WW：寄存器换名

对条件转移指令指令引起的全局相关通常是如何处理的？
- 条件出来前：提前形成条件码，预测
- 条件出来后：停顿

动态预测技术有哪四个？基本思想是什么？

动态预测技术	基本思想
转移预测缓冲器	依赖本条件转移指令的历史信息（局部）
相关转移预测器	依赖于已经发生过的其他条件转移指令的历史信息（全局）
自适应预测器	设置两个预测器，一个基于局部信息，另一个基于全局信息，并使用一个选择器组合，根据指令选择合适的预测器
分支目标预测器 BTB	采用一个小容量的高速缓冲器保存最近转移成功的 k 条转移指令的指令地址和分支目标地址

相关转移预测器：思想、实现，会计算所需容量，特别（2，2）相关转移预测器 思想：依靠已经发生过的其他条件转移指令的历史信息（全局信息）来预测当前的条件转移指令的转移方向，可以提高预测的准确性。 Num of bits in an (m,n) predictor: $2^m \times n \times N$,
N:number of prediction entries selected by the branch address.
(2,2) predictor

Tomasulo 算法和前瞻执行机制中的换名功能分别是如何实现的？ Tomasulo 算法的寄存器换名是通过保留站实现的前瞻执行机制是通过 ROB 缓冲器实现的

指令流水线对循环进行优化技术有哪些？它们的原理是什么？
- 调度技术
- 循环展开：多次复制循环体代码，并调整循环出口代码。
  - 循环展开通常展开成一对循环：设循环次数为 n，每次展开 k 次。
    - 第一个循环：循环体与原来一样，循环次数为：n mod k。
    - 第二个循环：循环体是原来循环体展开 k 次而得，循环次数为：n/k。
- 软件流水：软件流水是一种重组循环的技术，如果循环体间是相互独立的，可以将来自不同循环体间的指令（循环控制指令除外）组成一个新循环体，在保证循环体中的相关关系的同时提高并行性。

多发射处理机主要有哪些？它们的工作原理是什么？
- 超标量流水处理机
- 超长指令字处理机
比较：
- 超标量处理机通过重复设置硬件来提高性能（空间并行性）
- 超流水线处理机只需要增加少量硬件，通过各部分硬件的充分重叠工作来提高性能（时间并行性）

向量处理机的常见的相关和冲突有哪些？

向量链接技术：会判断是否可以采用本技术，并计算执行时间 向量链接技术：对于有写读数据香港的向量指令，可采用相关专用通道，从一个流水线部件得到的结果直接送入另一个流水线部件的操作数寄存器中。
- 没有向量寄存器冲突和运算部件冲突；
- 只有当前一条指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接，否则只能串行执行；
- 若一条向量指令的两个源操作数分别是两条先行指令的结果时，要求：
  - 先行的两条指令产生结果的时间必须相等；
  - 先行的两条指令的向量长度必须相等。
- 要进行链接执行的向量指令的向量长度必须相等，否则无法进行链接。

评价向量处理机性能的参数有哪些（会进行计算，尤其第一个参数）？及其具体用途是什么？
- 向量指令处理时间
  一条向量指令的处理时间： $$T_{\text{vp}}=T_s+T_{vf}+(n-1)T_c$$ $$T_{vp}=(T_{start}+n)T_c$$
  - $T_s$：向量指令的建立时间
  - $ T_{vf} $：向量指令的流过时间
  - $T_c$：时钟周期时间
  - $n$：向量长度
  - $T_{start}$：向量指令的启动时间一批向量指令的处理时间：
  - 向量长度<=向量寄存器长度时，向量指令的处理时间： $$T_{\text{all}}=(T_{start}+mn)T_c$$
    - $m$：编队数
    - $n$：向量长度
  - 向量长度>向量寄存器长度时，向量指令的处理时间： $$T_{\text{all}}=(T_{start}+mN_{\text{v}})T_c$$ 分段开采，向量长度为 n 的一组向量操作执行时间: $$T_n=\left\lceil \frac{n}{\text{MVL}} \right\rceil \times (T_{loop}+T_{start})+n \times T_{chine}$$
    - $T_{loop}$：标量代码开销
    - $T_{chine}$：编队数
    - $T_{start}$：所有编队向量指令的启动时间
- 最大性能$P_{\infty}$
- 半性能向量长度$N_{\frac{1}{2}}$
  为达到一半 $ R_{\infty} $ 值所需的向量长度称为半性能向量长度 $n_{\frac{1}{2}}$，主要评价向量流水线建立时间对性能的影响。
- 向量长度临界值$N_{\text{v}}$
  $n_v$表示向量流水方式的工作速度优于标量串行方式工作时所需得向量长度临界值。该参数既衡量建立时间，也衡量标量/向量速度比对性能的影响。

常用的互连函数
- 恒等置换
- 交换置换
- 方体置换
- 均匀洗牌置换均匀洗牌与逆均匀洗牌是两个十分有用的互连函数，以它们代表的链路与以交换置换代表的开关多级组合起来可构成 Omega（Ω）网络与逆 Omega（Ω）网络。σ 函数在实现多项式求值、矩阵转置和 FFT 等并行运算以及并行排序等方面都得到广泛的应用。
- 蝶式置换
- 位序颠倒置换
- 移数置换
- 加减$2^i$置换

常用的静态互连网络有哪些，它们的结构参数，重点掌握对称性

ILLIAC-IV 阵列处理机所用的互连函数

Delta 网：思想，会计算减少的开关数
交叉开关网络：
Delta 网： 用$a \times b$的交叉开关模块构成$a^n \times b^n$的交叉开关网络，其中指数$n$为互连网络的级数。 例如：用4×4的交叉开关模块构成42×42的交叉开关网络，其中指数2为互连网络的级数。

Omega 网络的结构和特点 Omega 网络：采用 $ 2 \times 2 $ 的四功能开关，对于 $ N \times N $ 网络，有 $ n = \log_2 N $ 个开关级，每级有 $ N / 2 $ 个开关； $ n $ 个开关级从输入端到输出端依次为 $ K_{n-1}, \dots, K_1, K_0 $，$ n+1 $ 个级间连接依次为 $ C_n, \dots, C_1, C_0 $，
其中 $ C_0 $ 为恒等置换，$ C_1 \sim C_n $ 都为均匀洗牌置换；开关采用单元控制方式。本网络也称为：多级洗牌置换网络或多级混洗网络。

互连网络中常见的消息寻径方式有哪些？重点掌握虫蚀寻径
- 线路交换寻径：
  - 方法：先建立一条从源节点到目的节点的物理通路，然后再传递消息。
  - 优点：传输带宽较大，平均传输时延较小，使用缓冲区少。适合于具有动态和突发性的大规模并行处理数据的传送。
  - 缺点：建立源节点到目的节点的物理通路开销很大，占用物理通路的时间长。
  - 传输时延：$$T_{CS}=(L_t/B)\times(D+1)+L/B$$ 其中,Lt 为建立路径所需小信息包的长度；L 为信息包的长度；D 为经过的中间节点数；B 为带宽。
- 存储转发寻径：
  - 方法：信息流的基本单位是包，每个节点有一个包缓冲区，包从源节点经过中间节点（存储 - 转发）到达目的节点。
  - 优点：占用物理通路的时间比较短。
  - 缺点：包缓冲区大（不利于 VLSI 实现），时延大（与节点距离成正比）。
  - 传输时延：$$T_{SF}=(L/B)\times(D+1)$$ 其中，L 为信息包的长度；D 为经过的中间节点数；B 为带宽。
- 虚拟直通寻径：
  - 方法：当接收到用作寻径的包头部时，即开始路由选择，这样可以降低时延。（是对存储转发寻径的改进）
  - 优点：通信时延与节点数无关。最佳情况下的通信时延同“线路交换寻径”（整条链路都空闲时）。
  - 缺点：出现寻径阻塞时只能将整个包存储在寻径节点中，故节点皆需足够大的缓冲区来存储最大包。最坏情况下的通信时延同“存储转发寻径”，此时经过的每个节点都发生阻塞，都需缓冲。
  - 传输时延：$$T_{VCT}=(L_h/B)\times D + L/B$$ 其中，Lh 为包寻径头部的长度； L 为信息包的长度；D 为经过的中间节点数；B 为带宽。一般有：L>>Lh×D，通信时延可以近似为：TVCT ＝ L/B，与节点数无关。
- 虫蚀寻径：
  - 将包分成更小的片，在每个节点的寻径器中设置片缓冲区。用头片直接开辟一条从输入节点到输出节点的路径，每个包中的片以流水方式在网络中向前“蠕动”（是对虚拟直通寻径的改进）。
  - 当包的头片到达一个节点 A 的寻径器后，寻径器根据头片的寻径消息立即做出路由选择。如果所选择的通道或节点的片缓冲区不可用时，头片必须在该节点的片缓冲区中等待，其它数据片也在原来的节点上等待。
  - 传输时延：$$T_{WH}=(L_f/B)\times D+L/B$$ 其中，Lf 为片的长度； L 为信息包的长度；D 为经过的节点数；B 为带宽。一般有：L>>Lf×D，通信时延可以近似为：TWH＝L/B，与节点数无关。
  - 优点：每个节点的缓冲区较小；较低的网络传输时延，采用了时间并行性；通道共享性好，利用率高；易于实现选播和广播通信方式。
  - 缺点：当包的一个片被阻塞时，整个包都被阻塞在所有节点，占用了节点资源。

互连网络中常见的消息寻径算法有哪些？重点掌握 E 立方体寻径 寻径算法的目的是找出一条从源节点到目的节点的路径以便传送消息。寻径算法可分为两大类（都需要无死锁算法）
- 确定寻径算法：寻找的路径是预先唯一确定额的，完全根据源和目的地址确定，与网络的状况无关。
- 自适应寻径算法：寻找的路径可能会有多条，取决于网络的状况。可采用虚拟通道避免死锁。
确定寻径算法-维序寻径
- 维序寻径在二维网格网络中称为 X-Y 寻径，在三维网格网络中称为 X-Y-Z 寻径
- 维序寻径在超立方体（n 维立方体）网络中称为 E 立方体寻径（E-cube routing）
  - 寻径是按照维的顺序进行的（维 1→ 维 2 → … → 维 n ）
  - 如果源节点和目的节点二进制编号的第 i 位相同，则沿维 i 方向不需要寻径
  - 否则从当前节点沿着这一维方向走到其他节点
  - 重复此过程直至到达目的节点