Mock Paper: CSC3050 Final (2025S)

CSC3060 Final Revision

Final Exam

时间	05/12，Tuesday，8:30–10:30
地点	TD 201, 202, 203, 206, 208, 209
形式	Open Book/Notes, No E-devices
范围	Textbook Chapters 1–7，Reference book Chapter 2/4, All lecture notes
比例	Week 1–10 占 30%，Chapter 5/6/7 占 70%
题型	单选 18 题 36 分；多选 11 题 33 分；简答 7 题 60 分

Basics

Architecture: 软硬件的抽象接口，或者叫做 ISA (I/O, 寄存器/内存管理, 指令集)，其中 calling convention 服从 ABI.

• E.g.: Intel x86, ARM, RISC-V (now) and IBM 360, SUN Microsystem SPARC, MIPS, DEC (past)

Microarchitecture: 同一 ISA 下的具体实现，ISA 确保不同微架构可运行同一软件. Control and Datapath. Parallel techniques like pipelining, superscalar.

• E.g.: branch predictor, Mem Hierarchy: Local memory and caches, Registers, vector registers, SIMD registers

System Software: 例如 compiler、assembler、linker、OS、file、thread、virtual memory。

ISA

LWU 和 LD/SD 只在 RV64 中有意义，而 LB/SB (8), LH/SH (16), LW/SW (32), LBU/LHU (unsigned 零展开), LUI 对 RV32 和 RV64 都是合法指令。另外，⚠️ LDU 在 RV64 是不存在的，原因与 LWU 在 RV32 不存在类似 (都占满了何谈展开)

Extentions：‘I’ – 整数，‘M’ – 乘除法，‘F’ and ‘D’ – 单双精度浮点数，‘V’ – 向量展开，‘C’ – 压缩展开 (16b)，‘A’ – Atomic operation。

32 GPR 中，X0 固定为 0

六种类型的指令: R, I, S, B, U, J。⚠️ S-type 和 B-type 很像，但 immediate 的解释不同。S-type immediate 是 byte offset；B-type branch immediate 通常按 2-byte 对齐处理。

伪指令: e.g. Li → Lui + Addi，不是硬件真实执行的指令，而是 assembler 帮你展开成真实 ISA instruction。

Branch/jump 指令的范围: Branch: ± 2¹² B, Jal: ±2²⁰ B, Jalr, 2³¹-1 B

数据类型

内存 (计算机架构) 本身不知道一串信息的数据类型，这归编译器管

中文用 Unicode，英语用 ASCII code

RISC-V 的整数 overflow 不要求硬件 trap，使用软件检查并设 flag

对于整数 X / 2ⁿ = X » n，⚠️ 对于负数要用 SRA+除数调整， X / N = (X + (N - 1)) » log2(N)

单精度 (32) / 双精度 (64) 浮点格式在 IEEE 754-1985 被定义；而 Quad-精度 (128) / 半精度 (16) 浮点格式在 IEEE 754-2008 被定义。

• IEEE 754: Quad precision: 1, 15, 112，

  Double precision: 1, 11, 52，x = (-1)^s × (1 + fraction) × 2^{(exponent - 1023"bias")}

  Single precision: 1, 8, 23，x = (-1)^s × (1 + fraction) × 2^{(exponent - 127)}

  Half precision: 1, 5, 10 (fp16), (bfloat16 (1,8,7) has the same range as fp32)；

  exponent	fraction	表示
  all 0	0	0
  all 0	nonzero	denormalized
  all 1	0	±∞
  all 1	nonzero	NaN

  ⚠️ 普通 normalized number 有 hidden 1；denormalized number 没有 hidden 1。

• Others: Mini-float: 1, 4, 3 (fp8)，Nibble-float: 1,2,1 (fp4)。

特殊的数据处理

Subword parallelism：一个 word 或 double word 中放多个小数据，例如 8-bit 或 16-bit 数据，然后一条指令并行处理多个数据。E.g. 64-bit register 可以放：8 个 8-bit data；4 个 16-bit data；2 个 32-bit data。

这适合 media data，比如 image、audio、video。

SIMD = Single Instruction Multiple Data，用于 DLP

PPT 提到 Intel 从 MMX 到 SSE，再到更宽的 SIMD register：

1. MMX 支持 multimedia subword parallelism；
2. SSE 引入 128-bit XMM registers；
3. 后来扩展到 512-bit ZMM registers；
4. Intel AMX 支持 fp16 和 bf16。

Vector architecture 也用于 DLP，的基本流程：

1. load sets of data into vector registers；
2. operate on vector registers；
3. store results back to memory。

注意 RVV (V-Extension) is Vector Length Agnostic (VLA)。SIMD 通常依赖固定宽度，例如 128-bit、256-bit、512-bit。RVV 程序则不必硬编码具体 vector length，更适合跨不同实现移植。

性能

CPI = Inst count X CPI X Clock cycle time: the smaller the better，IPC (ins./cycle): the larger the better，VE: reduce instruction count，Pipeline: reduce cycle time，Superscalar: reduce CPI，Cache: reduce CPI，Branch Prediction: reduce CPI，Code Scheduling: reduce CPI，CISC: reduce instruction count, but increase cycle time，Calling Convention: reduce instruction count，SIMD: reduces instructions, but not CPI and cycle time。

单周期机 CPI=1，最小周期为最慢指令 lw 的总时长 (“long cycle”)；多周期机和流水线机最小周期为最慢阶段时长 (“short cycle”)，比如 MEM/EX。周期 (ps) 的倒数为频率 (GHz)。流水线加速来自 throughput 增加，而不是 latency 减少，事实上单条指令的 latency 反而可能更大 (若不平衡)，阶段不平衡时 CPI 甚至 >1。

Pipeline Hazards：Structural (Von Neumann architecture, long instructions, like div), Data (use forwarding (hard) 或 scheduling (soft)，load-and-use 必定 stall 1), Control (最难预测的控制风险是 “indirect jump for branch JALR”)

Branch Prediction 分为 Whether (BHT，最好用 2-bit saturating counter 四元有限状态机) 和 Where (BTB)

内存结构

Memory wall：高速提升的 processor speed 和落入瓶颈的主存 (DRAM) speed 之间的差距越来越大。

问题的两个维度：

1. latency 解决方案：cache；local memory；NUMA；PIM；multithreading / hyper-threading；warp interleaving；chip multithreading。
2. bandwidth 解决方案：interleaved memory；wider bus；interconnection network；SDRAM；HBM, 3D stacking + wide interface。

HPC (高性能机) 和 LLM 中，主存性能尝是主要瓶颈，GPU 很擅长 parallel processing，但 data transfer 和 bandwidth 可能限制性能。

Memory Hierarchy：离 CPU 近则小、贵、快，远则大、安、慢 —— 创造又大又快的错觉。

层次	Transfer Unit
Registers	instruction operands
Cache	blocks / lines
Virtual Memory	pages
File system	files

缓存

Q1: Where can a block be placed?

Block placement：

1. direct mapped；
2. set associative；
3. fully associative。

Q2: How is a block found?

Block finding：set selection 和 tag comparison。

地址 = 标记位 Tag + 组索引 Set Index + 块内偏移 Block Offset

缓存行总数 = 缓存总容量 / 每个块的大小

组数 = 缓存总容量 / (每个块的大小 × 每组的行数)

Byte offset 块内选址位数 = log₂(每个块的大小)

Set Index 组索引位数 = log₂(组数) = log₂(缓存总容量 / (每个块的大小 × 每组的行数))

tag 位数 = 地址总位数 - 组索引位数 - 块内偏移位数

Q3: Which block should be replaced?

Replacement policy：

1. LRU approximation；
2. MRU；
3. Belady’s algorithm。

Q4: What happens on a write?

Write strategy：

写命中：

1. write-through 同时写：简单，但写流量大。
2. write-back 只写 cache：性能好，但需要 dirty bit，coherence 更复杂。

写不命中：

1. write-allocate 载入 cache，通常搭配 write-back：现在等 load
2. write-no-allocate 载入低一层记忆，搭配 write-through：待会等 load

4C：Compulsory / Cold Miss (无法完全解决)，Conflict / Collision Miss，Capacity Miss (缓存大小不变行变大会导致)，Coherency Miss

AMAT = Hit Time + Miss Rate × Miss Penalty。在 80s–90s 对 blocking cache、in-order processor 很有用。 但现代处理器中，由于：OoO, non-blocking cache, miss-under-miss (MLP), prefetching,split I/D cache 导致 cache miss latency 常常被隐藏，所以 AMAT 不总是准确。

Optimization

优化目标可以从 CPI 公式看：减少 instruction count；降低 CPI；减小 clock cycle time；提高 locality；减少 branch；减少 memory waiting；利用 parallelism。

Compiler Opt.

Level	含义
-O0	不优化，编译快，适合 debugging
-O1 / -O	基本优化
-O2	推荐默认优化，安全稳定，代码大小增加不多
-O3	激进优化，包括 loop unrolling、SIMDization
-O4	旧编译器中常指 LTO；现在可能表示 -O3 + LTO

⚠️ -O3 不一定总是更快。它可能导致 code bloat、更长 compile time、更难 debug，甚至 runtime 更差。

Compiler Flag 通常不能：通常不能：改变 algorithmic complexity；改变 program behavior；随便忽略 edge cases；轻易假设 floating point 满足 associative law；完全知道 runtime input；轻易判断 memory aliasing；跨整个程序分析，除非使用 LTO；预测 malicious input 的 worst case。

Inlining

把 function body 直接复制到 call site。

优点：消除 function call overhead；暴露更多优化机会；constant arguments 可进一步优化；让 compiler 跨函数优化；对小函数、hotspot 函数尤其有用。

缺点：code bloat；instruction cache pressure；compile time 增加；debugging 更难。

Compiler 决定是否 inline 时考虑：function size；execution frequency；call 是否在 loop 内；call sites 数量；是否有 constant arguments；recursion depth limit；是否可以触发更多优化。

Memory Locality Opt.

技术	主要解决什么问题	提升哪种局部性	核心思想
Loop Interchange	按列访问导致 cache miss	空间局部性	调整循环顺序，让内层循环访问连续内存
Loop Fusion	多个循环重复加载同一数据	时间局部性	把多个循环合并，趁数据还在 cache 中马上复用
Array Padding	不同数据映射到同一 cache set	减少 conflict miss	增加无用填充，改变地址映射
Matrix Transpose Blocking	转置中一边按列访问	空间 + 时间局部性	小块转置，让工作集留在 cache
Matrix Multiplication Tiling	大矩阵超过 cache 容量	时间局部性	分块计算，提高 A/B/C 小块复用
Software Prefetching	随机访问硬件预取失败	隐藏内存延迟	提前告诉 CPU 未来要访问哪里
AoS → SoA	结构体字段访问浪费 cache line	空间局部性	把同类字段连续存放

• CSC3060