CS:APP Cache_lab实验报告

发表于 分类于 ， ，

CS:APP Cache Lab 实验报告

学号： 24300240128

姓名： 潘孝圆

提交日期： 2025/12/18

一、 实验概述

本实验旨在深入理解高速缓存存储器（Cache Memory）的工作原理。实验分为两部分：Part A 编写一个缓存模拟器（csim）以模拟 LRU 替换策略；Part B 优化矩阵转置函数（trans.c），在给定的 $s=5, E=1, b=5$（即 32 组，直接映射，块大小 32 字节）缓存参数下，最小化 Cache Miss 次数。

二、 实验思路 (Part A: Cache Simulator)

Part A 要求实现一个通用的缓存模拟器，核心在于正确解析内存地址并实现最近最少使用（LRU）替换算法。

  1. 数据结构设计
    • 定义缓存行（Cache Line）结构体，包含 valid（有效位）、tag（标记位）和 time_stamp（LRU 计数器）。
    • 根据命令行参数 $s, E, b$，动态分配一个二维结构体数组 cache[S][E] 来模拟整个缓存空间，其中 $S = 2^s$。
  2. 地址解析与索引
    • 对于输入的 64 位内存地址，通过位运算提取组索引（Set Index）和标记（Tag）：
      • Set Index = (address >> b) & ((1 << s) - 1)
      • Tag = address >> (s + b)
  3. LRU 策略与状态机
    • Hit（命中）：当组内存在 valid == 1 且 tag 匹配的行时，判定为命中。更新该行的 time_stamp 为当前操作时间。由于数不多，暴力遍历即可。
    • Miss（未命中）：
      • Cold Miss：若组内有空行（valid == 0），直接填入数据。
      • Eviction：若组已满，遍历该组寻找 time_stamp 最小的行（即最久未访问的行）进行驱逐和替换。
    • 操作处理：L（Load）和 S（Store）记为一次访问；M（Modify）记为先 Load 后 Store，即两次访问（Hit 次数可能 +1 或 +2）。

三、 实验思路 (Part B: Matrix Transpose)

针对不同的矩阵维度，由于缓存映射机制的特性，采取了不同的分块（Blocking）策略以利用空间局部性（Spatial Locality）并减少冲突不命中（Conflict Misses）。

  1. $32 \times 32$ 矩阵
    • 问题分析：Cache Block 为 32 字节（8 个 int）。矩阵一行 32 个 int，占 4 个 Block。由于是直接映射，A[k][i] 和 B[i][k] 在对角线附近极易映射到同一个 Cache Set，导致严重的抖动。
    • 优化策略：
      • 采用 $8 \times 8$ 分块。8 个 int 正好填满一个 Cache Line，最大化利用加载进来的数据。
      • 利用 8 个局部变量作为寄存器缓冲。在内层循环中，先将 A 的一行 8 个元素读入局部变量，再写入 B 的对应列。这消除了读取 A 和写入 B 之间可能发生的 Set 冲突，确保缓存行不会被过早逐出。
  2. $64 \times 64$ 矩阵
    • 问题分析：每隔 4 行（$4 \times 64 \times 4$ bytes = 1024 bytes）就会映射到同一个 Cache Set。标准的 $8 \times 8$ 分块会导致块内部产生严重的 Set 冲突（即第 1 行和第 5 行互相驱逐）。
    • 优化策略：
      • 继续使用 $8 \times 8$ 的大循环框架，但在块内部进行精细操作。
      • 利用局部变量，将 $8 \times 8$ 块分为四个 $4 \times 4$ 子块处理。
      • 在处理过程中，先移动上方 $4 \times 8$ 的数据，利用 B 矩阵不发生冲突的区域暂存数据，再将其移动到正确位置。这种方法虽然代码逻辑复杂，但有效避免了同一个 Set 内的反复颠簸。
  3. $61 \times 67$ 矩阵
    • 问题分析：这两个维度互质且不为 2 的幂。内存地址到 Cache Set 的映射比较随机，不易发生规律性的 Set 冲突。
    • 优化策略：
      • 简单分块策略：由于没有特殊的对角线冲突问题，不需要复杂的变量暂存逻辑。
      • 分块大小：经测试，选用 $16 \times 16$ 的分块大小即可满足 Miss < 2000 的要求。
      • 边界处理：由于 61 和 67 无法被 16 整除，代码中增加了边界检查条件（i < N 和 j < M），防止数组越界访问。

四、 测试结果截图

下图为 driver-py3.py 的完整运行结果，包含 Part A 的正确性测试与 Part B 的性能测试。

(注：以下为运行日志，实际提交建议直接使用截图)

Plaintext

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ICS/cache/cachelab-handout via C v13.3.0-gcc via 🐍 v3.12.3 
❯ python3 ./driver-py3.py 
Part A: Testing cache simulator
Running ./test-csim
                        Your simulator     Reference simulator
Points (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
     3 (1,1,1)       9       8       6       9       8       6  traces/yi2.trace
     3 (4,2,4)       4       5       2       4       5       2  traces/yi.trace
     3 (2,1,4)       2       3       1       2       3       1  traces/dave.trace
     3 (2,1,3)     167      71      67     167      71      67  traces/trans.trace
     3 (2,2,3)     201      37      29     201      37      29  traces/trans.trace
     3 (2,4,3)     212      26      10     212      26      10  traces/trans.trace
     3 (5,1,5)     231       7       0     231       7       0  traces/trans.trace
     6 (5,1,5)  265189   21775   21743  265189   21775   21743  traces/long.trace
    27


Part B: Testing transpose function
Running ./test-trans -M 32 -N 32
Running ./test-trans -M 64 -N 64
Running ./test-trans -M 61 -N 67

Cache Lab summary:
                        Points   Max pts      Misses
Csim correctness          27.0        27
Trans perf 32x32           8.0         8         288
Trans perf 64x64           8.0         8        1228
Trans perf 61x67          10.0        10        1993
          Total points    53.0        53

实验总结：

本次实验 Part A 与 Part B 均已通过测试。

  • Part A 模拟器准确复现了参考程序的行为。
  • Part B 通过针对性的分块策略，三个测试矩阵的 Miss 数分别为 288、1228、1993，均达到满分标准。
  • Total Points: 53/53