计算机系统结构考纲

1. 各级指令执行时间计算

答案：第2级需(N \times K) ns，第3级需(N^2 \times K) ns，第4级需(N^3 \times K) ns。

分析：

第1级1条指令需(K) ns，且第1级1条指令由第2级(N)条指令解释，因此第2级1条指令的时间为(K \div N)？（此处需注意逻辑：“每一级执行1条指令需要下一级(N)条指令解释”→ 第1级1条指令 = 第2级(N)条指令的执行时间，因此第2级1条指令时间 = 第1级1条指令时间(\div N = K/N)？
若题目描述为“第1级1条指令需要第2级(N)条指令解释，且第1级1条指令总时间为(K) ns”，则第2级1条指令时间为(K/N)，第3级为(K/N^{2)，第4级为(K/N}3)。
需明确：“执行第一级的一条指令需(K) ns”是总时间，该总时间由第2级(N)条指令的时间之和构成，因此第(i)级1条指令时间 = (K / N^{i-1})。

2. 加速比与可向量化比例的关系

定义：设可向量化比例为(f)（(0 \leq f \leq 1)），标量方式总时间为(T)，则向量化后时间为(T \times (1-f) + T \times f / 20)。

加速比(S)：
[
S = \frac{T}{T \times (1-f) + \frac{T \times f}{20}} = \frac{1}{1 - f + \frac{f}{20}} = \frac{20}{20 - 19f}
]

曲线特征：

当(f=0)（无向量化），(S=1)；
当(f=1)（全向量化），(S=20)；
曲线随(f)增大单调递增，且增速逐渐放缓（因为分母的“(19f)”边际效益递减）。

3. Cache存储系统加速比

答案：加速比约为4.17。

分析：
用阿姆达尔定律：设Cache访问时间为(t)，则主存时间为(5t)；命中概率(p=90%=0.9)，不命中概率(1-p=0.1)。

存储系统平均访问时间(T_{\text{avg}})：
[
T_{\text{avg}} = p \times t + (1-p) \times 5t = 0.9t + 0.1 \times 5t = 1.4t
]

原主存系统访问时间为(5t)，因此加速比：
[
S = \frac{5t}{T_{\text{avg}}} = \frac{5t}{1.4t} \approx 4.17
]

4. 数据类型、数据表示和数据结构的关系

数据类型：是对数据的“分类”（如整数、浮点数、字符），定义了数据的语义和操作规则（如整数支持加减乘除，字符支持拼接）。
数据表示：是数据在计算机中的“编码方式”（如整数用补码，浮点数用IEEE 754标准），是数据类型的物理实现。
数据结构：是数据的“组织方式”（如数组、链表、树），基于数据类型，通过组合/关联不同数据类型的元素，实现特定功能（如链表实现动态存储）。

关系：数据类型定义“是什么/能做什么”，数据表示定义“怎么存”，数据结构定义“怎么组织”；数据表示是数据类型的底层支撑，数据结构是数据类型的上层组合。

5. 指令编码与格式设计

(1) 操作码的最短平均长度（哈夫曼编码）

7条指令的使用频率为：35%、25%、20%、10%、5%、3%、2%。

哈夫曼编码步骤：
将频率从小到大排序，逐步合并（每次合并最小的两个节点），最终得到编码（频率越高，编码越短）：

指令1（35%）：00（2位）
指令2（25%）：01（2位）
指令3（20%）：10（2位）
指令4（10%）：110（3位）
指令5（5%）：1110（4位）
指令6（3%）：11110（5位）
指令7（2%）：11111（5位）

平均长度：
[
\begin{align}
\text{平均长度} &= 0.35 \times 2 + 0.25 \times 2 + 0.2 \times 2 + 0.1 \times 3 + 0.05 \times 4 + 0.03 \times 5 + 0.02 \times 5 \
&= 0.7 + 0.5 + 0.4 + 0.3 + 0.2 + 0.15 + 0.1 = 2.35 \text{位}
\end{align}

(2) 指令格式设计（16位字长）

寄存器-寄存器型（3条）：无需地址，用寄存器号。
格式：操作码（x位） + 源寄存器1（4位） + 源寄存器2（4位） + 目的寄存器（4位）
操作码长度：(16 - 4 \times 3 = 4)位（可编码16条，足够3条）。
寄存器-存储器型（4条）：变址范围≥127（需8位偏移量，因为(2^7-1=127)）。
格式：操作码（y位） + 源寄存器（4位） + 变址寄存器（2位，因为有2个变址寄存器） + 偏移量（8位）
操作码长度：(16 - 4 - 2 - 8 = 2)位（可编码4条，恰好匹配）。

6. 指令操作码分配（16位字长）

(1) 双地址指令15条，单/零地址指令数量基本相同

双地址指令：操作码占(k)位，最多编码(2^{k)条。15条需(k=4)位（(2}4=16)，用15条）。
剩余操作码空间：(16 - 15 = 1)种（即操作码为1111），用于扩展单/零地址指令。
单地址指令：操作码扩展后，新增地址字段占16位（地址长度），因此操作码实际为“原4位+新16位”？（题目描述“每个字地址段的长度均为6位”→ 地址段是6位）。

修正：地址段长度为6位。
- 双地址指令：操作码长度(16 - 6 \times 2 = 4)位（编码15条，剩余1种：1111）。
- 单地址指令：操作码为“4位扩展码 + 6位地址”中的操作码部分？实际应为：
  双地址指令用4位操作码的15种，剩余1种作为“扩展标记”，单地址指令的操作码为“扩展标记 + 6位地址中的操作码扩展位”，即操作码长度为(4 + (16 - 4 - 6) = 12)位？（此部分需明确：16位字长，地址段6位，因此：
  - 双地址指令：操作码(16 - 6 \times 2 = 4)位（15条）。
  - 单地址指令：操作码(16 - 6 = 10)位，其中前4位为扩展标记（1111），因此数量为(2^{10 - 4} = 64)条。
  - 零地址指令：操作码16位，前10位为单地址的扩展标记，数量为(2^{16 - 10} = 64)条（与单地址数量相同）。

(2) 三类指令比例1:9:9

总比例(1+9+9=19)，总编码数(2^{16}=65536)（但实际用操作码扩展）。

双地址指令：占1份，数量为(x)，则单地址为(9x)，零地址为(9x)。
双地址指令操作码长度：(16 - 6 \times 2 = 4)位（最多16条），取(x=16)（但比例为1:9:9，需调整）。

正确逻辑：
- 双地址指令：操作码4位，编码(2^4=16)条（占1份）。
- 单地址指令：用双地址的剩余操作码扩展，数量为(16 \times 9 = 144)条（操作码长度(4 + (16 - 4 - 6) = 10)位）。
- 零地址指令：用单地址的剩余操作码扩展，数量为(144 \times 9 = 1296)条（操作码长度16位）。

三、思考题（续）答案与分析

7. CISC和RISC的概念及特点

CISC（复杂指令集计算机）
- 概念：指令系统复杂，包含大量功能复杂的指令（如多操作数、存储器-存储器操作）。
- 特点：指令数量多（数百条）、指令长度可变、寻址方式丰富、依赖微程序控制、硬件复杂度高、指令执行效率差异大。
RISC（精简指令集计算机）
- 概念：指令系统精简，仅保留常用简单指令（如寄存器-寄存器操作）。
- 特点：指令数量少（数十条）、指令长度固定、寻址方式简单、依赖硬件布线控制、采用流水线/Load-Store结构、指令执行周期短且效率稳定。

8. RISC处理器的关键技术

Load-Store结构：仅通过Load/Store指令访问存储器，其余指令均为寄存器-寄存器操作，简化数据通路。
指令流水线：将指令执行分解为多个阶段（取指、译码、执行等）并行处理，提高吞吐率。
固定指令长度：便于流水线同步和硬件译码，减少控制复杂度。
大量通用寄存器：减少存储器访问次数，配合寄存器窗口技术（如SPARC）进一步降低开销。
硬布线控制：替代微程序控制，缩短指令执行的控制延迟。
优化编译技术：通过编译器调度指令、分配寄存器，充分发挥硬件效率。

9. 两层存储器层次结构分析

已知：M1命中概率(h)，M1成本(c_1)（每字节）、容量(s_1)；M2成本(c_2)、容量(s_2)；访问时间(t_1)、(t_2)；速度比(r = t_2/t_1)，存取效率(E = t_1/t_{\text{avg}})。

(1) 平均成本接近(c_2)的条件

总平均成本：
[
\bar{c} = \frac{c_1 s_1 + c_2 s_2}{s_1 + s_2}
]
要(\bar{c} \approx c_2)，需满足(c_1 s_1 \ll c_2 s_2)（即M1的总成本远小于M2的总成本），通常实际条件是(s_2 \gg s_1)（M2容量远大于M1）。

(2) 有效存取时间(t_{\text{avg}})

根据命中/不命中的时间加权：
[
t_{\text{avg}} = h t_1 + (1-h) t_2
]

(3) 存取效率(E)与(h)、(r)的关系

由(E = \frac{t_1}{t_{\text{avg}}})，代入(t_2 = r t_1)：
[
E = \frac{t_1}{h t_1 + (1-h) r t_1} = \frac{1}{h + (1-h) r}
]

(4) (r=100)、(E>0.95)时的命中概率(h)

代入(r=100)、(E>0.95)：
[
\frac{1}{h + (1-h) \times 100} > 0.95 \implies h + 100 - 100h < \frac{1}{0.95} \implies 100 - 99h < 1.0526 \
\implies 99h > 98.9474 \implies h > \frac{98.9474}{99} \approx 0.9995
]
即命中概率需高于99.95%。

10. 两级存储系统的容量设计

已知：M1（Cache）容量(s_1 \in {64KB, 128KB, 256KB})，M2（主存）容量(s_2=4MB)；成本(c_1=20c_2)、(c_2=0.2)元/KB；访问时间(t_1=20ns)、(t_2=10t_1=200ns)；命中率(h \in {0.7, 0.9, 0.98})（对应64KB、128KB、256KB）。

(1) 平均存取时间(t_{\text{avg}})

[
t_{\text{avg}} = h t_1 + (1-h) t_2
]

64KB（(h=0.7)）：(t_{\text{avg}} = 0.7 \times 20 + 0.3 \times 200 = 14 + 60 = 74ns)
128KB（(h=0.9)）：(t_{\text{avg}} = 0.9 \times 20 + 0.1 \times 200 = 18 + 20 = 38ns)
256KB（(h=0.98)）：(t_{\text{avg}} = 0.98 \times 20 + 0.02 \times 200 = 19.6 + 4 = 23.6ns)

(2) 平均字节成本

总平均成本(\bar{c} = \frac{c_1 s_1 + c_2 s_2}{s_1 + s_2})，其中(c_1=20 \times 0.2=4)元/KB：

64KB：(\bar{c} = \frac{4 \times 64 + 0.2 \times 4096}{64 + 4096} = \frac{256 + 819.2}{4160} \approx 0.258)元/KB
128KB：(\bar{c} = \frac{4 \times 128 + 0.2 \times 4096}{128 + 4096} = \frac{512 + 819.2}{4224} \approx 0.315)元/KB
256KB：(\bar{c} = \frac{4 \times 256 + 0.2 \times 4096}{256 + 4096} = \frac{1024 + 819.2}{4352} \approx 0.423)元/KB

(3) 综合排序（成本×时间）

64KB：(0.258 \times 74 \approx 19.09)
128KB：(0.315 \times 38 \approx 11.97)
256KB：(0.423 \times 23.6 \approx 10.00)

排序：

平均成本：64KB < 128KB < 256KB
平均时间：256KB < 128KB < 64KB
综合乘积：256KB < 128KB < 64KB → 最佳设计为256KB Cache。

11. Cache写操作的一致性解决方法

解决Cache与主存内容不一致的方法及开销：

写直达（Write-Through）
- 方法：写Cache时同时写主存。
- 开销：每次写操作都访问主存，增加总线带宽占用。
写回（Write-Back）
- 方法：写Cache时仅标记“脏位”，替换时才写回主存。
- 开销：需额外硬件维护“脏位”，替换时可能产生突发写操作。
写分配（Write-Allocate）
- 方法：写不命中时，先将主存块调入Cache再写。
- 开销：写不命中时增加一次Cache块调入操作，延迟略高。
非写分配（No-Write-Allocate）
- 方法：写不命中时直接写主存，不调入Cache。
- 开销：连续写同一地址时，需多次访问主存，效率低。
总线监听（Snooping）
- 方法：多处理器中，Cache监听总线操作，同步其他Cache的修改。
- 开销：增加Cache控制器的总线监听逻辑，复杂度高。

12. LFU替换算法的最高命中率

页地址流：P4, P5, P3, P2, P5, P1, P3, P2, P5, P3, P1, P3

(1) 最高命中率

LFU（最少使用）的最高命中率需让频繁访问的页留在Cache中。
地址流中各页访问次数：

P3：4次；P5：3次；P2：2次；P1：2次；P4：1次。
若Cache能容纳前4个高频页（P3、P5、P2、P1），则仅P4不命中：
总访问次数：12次；不命中次数：1次；命中率：(\frac{12-1}{12} \approx 91.7%)。

(2) 最少主存页面数

需容纳高频页：P3、P5、P2、P1（共4个页），因此至少分配4个主存页面。

三、思考题（续）答案与分析

13. 组相联Cache的映射与命中率分析

已知：主存8块（B0~B7），Cache2组（每组2块），块大小16字节，LRU替换；块地址流：B6,B2,B4,B1,B6,B3,B0,B5,B7,B3

(1) 主存地址格式

主存地址分为3部分：

块标记：主存块号中“组号之外的部分”。主存块号共3位（8块），Cache组号1位（2组），因此块标记长度=3-1=2位；
组号：1位（对应Cache的2组）；
块内地址：4位（16字节，(2^4=16)）。

格式：块标记（2位） + 组号（1位） + 块内地址（4位）

(2) Cache地址格式

Cache地址分为2部分：

组内块号：1位（每组2块）；
块内地址：4位（同主存块内地址）。

格式：组号（1位） + 组内块号（1位） + 块内地址（4位）

(3) 主存与Cache的映射关系

组相联映射规则：主存块号 (\mod \text{Cache组数}) = 目标组号。
Cache组号为0、1，因此：

主存块B0、B2、B4、B6 → 组0（块号(\mod 2=0)）；
主存块B1、B3、B5、B7 → 组1（块号(\mod 2=1)）。

(4) LRU替换下的Cache块地址流情况

Cache组0（容纳B0/B2/B4/B6）、组1（容纳B1/B3/B5/B7），每组2块，LRU替换：

访问B6（组0）：组0空，装入→Cache组0：[B6]
访问B2（组0）：组0空，装入→Cache组0：[B6, B2]
访问B4（组0）：组0满，LRU是B6→替换B6，装入B4→Cache组0：[B2, B4]
访问B1（组1）：组1空，装入→Cache组1：[B1]
访问B6（组0）：组0满，LRU是B2→替换B2，装入B6→Cache组0：[B4, B6]
访问B3（组1）：组1空，装入→Cache组1：[B1, B3]
访问B0（组0）：组0满，LRU是B4→替换B4，装入B0→Cache组0：[B6, B0]
访问B5（组1）：组1满，LRU是B1→替换B1，装入B5→Cache组1：[B3, B5]
访问B7（组1）：组1满，LRU是B3→替换B3，装入B7→Cache组1：[B5, B7]
访问B3（组1）：组1满，LRU是B5→替换B5，装入B3→Cache组1：[B7, B3]

(5) FIFO替换下的块命中率

FIFO按“先入先出”替换，统计命中次数：

B6（未命中）、B2（未命中）、B4（替换B6，未命中）、B1（未命中）、B6（替换B2，未命中）、B3（未命中）、B0（替换B4，未命中）、B5（替换B1，未命中）、B7（替换B3，未命中）、B3（替换B5，未命中）
命中次数=0 → 命中率=0%

(6) LRU替换下的块命中率

统计命中次数：

访问B6（命中，第5次）、B3（命中，第10次）→ 命中次数=2
总访问次数=10 → 命中率=2/10=20%

14. 存储系统相关概念

存储系统：由多种不同速度、容量的存储器构成的层次结构，通过管理策略使整体性能接近高速存储器、容量接近低速存储器。
虚拟存储器：将主存与辅存逻辑上统一，通过分页/分段技术，让程序可使用远大于主存容量的地址空间，由硬件+操作系统协同管理。
高速缓冲存储器（Cache）：位于CPU与主存之间的高速小容量存储器，通过局部性原理缓存常用数据，减少CPU访问主存的延迟。

15. Cache加速比及提升方法

Cache加速比：CPU访问无Cache主存的时间与访问有Cache存储系统的平均时间的比值，公式为：
[
\text{加速比} = \frac{t_{\text{主存}}}{h \cdot t_{\text{Cache}} + (1-h) \cdot t_{\text{主存}}}
]
其中(h)为Cache命中率。
提升方法：
1. 提高Cache命中率（如增大Cache容量、优化替换算法）；
2. 减小Cache与主存的速度差（如采用更高速的Cache器件）；
3. 优化Cache映射方式（如组相联替代直接映射）。

16. 中断处理的主要工作及实现方式

主要工作：
1. 中断请求：外设/内部事件向CPU发中断信号；
2. 中断响应：CPU暂停当前程序，保存断点（PC、状态字）；
3. 中断判优：选择优先级最高的中断；
4. 中断服务：执行中断服务程序（处理事件）；
5. 中断返回：恢复断点，继续执行原程序。
实现方式：
- 必须硬件实现：中断请求、中断响应、断点保存、中断判优；
- 必须软件实现：中断服务程序（如数据传输、错误处理）；
- 可硬/软件实现：中断屏蔽、中断嵌套控制。

17. 指令执行方式的区别

执行方式	顺序方式	一次重叠方式	流水线方式
特点	一条指令执行完再取下一条	同时执行“取指”和“执行”（部分重叠）	将指令分解为多阶段，多指令并行执行
优点	控制简单	吞吐率提升约1倍	吞吐率接近“指令数×单阶段时间”
缺点	效率低	仅两阶段重叠，提升有限	存在数据/控制冲突，需额外硬件解决

18. 流水线分类及区别

流水线级别：
1. 指令流水线（按指令执行阶段分）；
2. 运算流水线（按运算步骤分，如浮点加法流水线）；
3. 处理机流水线（多处理机级联，如取指→译码→执行→存储）。
线性流水线 vs 非线性流水线：
- 线性流水线：各阶段仅经过一次，无反馈/前馈；
- 非线性流水线：包含反馈/前馈通路，某阶段可被多次使用（如乘法流水线的累加阶段）。

19. 5功能段浮点加法流水线的时空图与性能

以计算(F = \sum_{i=1}^{10} A_i)为例（5功能段：对阶→尾数加→规格化→舍入→判溢出）：

时空图：第1个操作占5个周期，之后每个操作占1个周期，总周期数=5+9=14个周期。
实际吞吐率：完成10个操作的时间为14个周期，吞吐率=10/14 ≈ 0.714操作/周期。
加速比：顺序执行时间=10×5=50周期，加速比=50/14≈3.57。
效率：流水线利用率=（10×5）/(5×14)≈71.4%。

20. 6功能段乘法流水线的时空图与性能

计算(F = \sum_{i=1}^{6} (A_i \times B_i))（6功能段：取数→乘阶码→尾数乘→规格化→舍入→判溢出）：

时空图：第1个乘法占6周期，之后每个乘法占1周期，6个乘法总周期=6+5=11；累加需额外周期，总周期≈11+5=16。
吞吐率：6个乘法的吞吐率=6/16≈0.375操作/周期。
加速比：顺序时间=6×6=36周期，加速比=36/16≈2.25。

21. 超标量、超流水处理机的异同

相同点：均通过并行执行指令提高吞吐率，基于指令级并行（ILP）。
不同点：
- 超标量：同一周期发射多条指令，需多套执行部件；
- 超流水：将流水线阶段拆分更细，周期缩短，同一阶段可并行处理多条指令的不同阶段。

22. 超流水调度方法及特点

静态调度：由编译器在编译时调度指令，避免冲突；特点：硬件简单，依赖编译器优化。
动态调度：由硬件在运行时调度指令（如Tomasulo算法）；特点：能处理运行时冲突，硬件复杂度高。

23. 提升向量处理机性能的技术

向量流水技术：将向量操作分解为流水线阶段，并行执行；
向量多处理技术：多个向量处理器并行处理；
向量寄存器技术：增大向量寄存器长度，减少访存次数；
链接技术：将相关向量操作的流水线链接，减少延迟；
稀疏矩阵优化：对稀疏向量采用压缩存储，提高效率。

24. 向量链接、向量递归

向量链接：当后一条向量指令的源操作数是前一条指令的结果时，直接将前一条指令的流水线输出作为后一条的输入，无需等待前一条指令完成，减少延迟。
向量递归：向量操作的结果作为自身的操作数（如向量累加），需通过寄存器或存储转发实现，需避免数据冲突。

25. 互连函数及表示

互连函数：描述多处理机/存储器中，处理单元之间的连接关系（即输入到输出的映射）。
表示方法：通常用函数式表示（如Cube(_k)、Shuffle），或用连接图、置换表表示。

26. 静态/动态互连网络

静态互连网络：连接关系固定，不随时间改变；特点：结构简单，成本低；如网格网络、超立方网络。
动态互连网络：连接关系可通过开关动态调整；特点：灵活性高，成本高；如交叉开关、多级互连网络。

27. 单级互连网络的连接（处理机0~15）

(1) Cube(_2)：第2位取反（从0开始）。处理机10（二进制1010）→ 第2位取反为1000（8）。
(2) PM2(_+2)：模16加2。10+2=12。
(3) PM2(_-2)：模16减2。10-2=8。
(4) Shuffle：循环左移1位。10（1010）→ 0101（5）。
(5) Shuffle(Shuffle)：两次Shuffle。10→5→1010循环左移→0101→1010（10）。

28. SMP系统中UMA、NUMA、COMA的含义及特点

UMA（统一内存访问）：所有CPU访问主存的延迟相同；特点：结构简单，适合小规模SMP。
NUMA（非统一内存访问）：CPU访问本地内存延迟低，访问远程内存延迟高；特点：可扩展至大规模系统，需软件优化数据分布。
COMA（高速缓存一致性非统一内存访问）：主存以Cache块形式分布，无物理本地内存；特点：灵活性高，硬件复杂度极高。

29. 不同计算机系统的运算时间计算

计算(S = \sum_{i=1}^{8} (A_i + B_i))，加法30ns，乘法50ns，PE间传输10ns（SISD忽略）。

(1) 单PE的SISD

顺序执行8次加法：时间=8×30=240ns。

(2) 含加法器+乘法器的SISD

仍顺序执行（仅加法）：时间=8×30=240ns（乘法器未使用）。

(3) 8PE的SIMD（线性连接）

每个PE完成1次加法：8个加法并行执行，时间=30ns；
结果需从PE0→PE1→…→PE7（线性传输）：传输次数=7次，时间=7×10=70ns；
总时间=30+70=100ns。

(4) 8CPU的MIMD（全互连）

每个CPU完成1次加法：并行执行，时间=30ns；
结果通过全互连网络汇总（无需逐次传输）：传输时间≈10ns；
总时间=30+10=40ns。