Table of Contents

CSAPP:CacheLab
#

This lab has parts A and B. I will work through them as I go, and will partially quote material and discussion questions written by our TAs. First we need to get familiar with how caches work — you can also look at my ComputerOrgnization notes (not great; better to read the textbook, and I recommend doing the exercises). Part A implements a 3-level cache, which should deepen familiarity with cache mechanics; Part B optimizes a matrix-transpose function and, I think, teaches what cache-friendly code looks like.

Note: the following does not teach caches from scratch, and do not plagiarize, do not plagiarize, do not plagiarize.

Cache: a great idea that appears everywhere in computer systems……

Warm-up:

Cache-Line Organization
#

You can view it as a 2D array whose elements are cache lines.

https://xjtu-ics.github.io/assets/images/cachelab_memory_orgnization.png

E = 1: direct-mapped

S = 1: fully associative

Handling Writes
#

The write path is more complex than reads because writes involve changing data. Once modification is involved, coherence issues arise, so the cache must carefully decide when and how far to propagate updates. Write misses must also be handled. Here is a brief overview of write-related issues and mechanisms.

In general, caches use one of two write policies:

write back: updates happen only in the current cache level. A dirty bit usually marks that this line is inconsistent with the next level (or memory); the line is written back only when it is evicted.
write through: as the name suggests, a write updates both the current cache and the next level (or memory), so the two stay in sync.

Besides those policies, the cache must decide what to do on a write miss. Typically there are two options:

write allocate: on a miss, fetch the needed line from the next level (or memory) into this cache, then modify it
no write allocate: on a miss, do not bring the line into this cache; write directly to the next level (or memory)

The four combinations exist, but the two common pairings are:

write back/write allocate: write-back + write-allocate (figure from Wikipedia)

write through/no write allocate: write-through + no-write-allocate

Q: Why not write-back combined with no-write-allocate?

A: Imagine L1 and L2. On an L1 write miss, if that location is likely to be written again soon, it is more reasonable to bring the line into L1 — otherwise every write misses, which fights temporal locality. You can reason about the other pairing similarly.

Multi-Level Inclusion Policy
#

This is the heart of the lab — understand it carefully.

Inclusion: a higher (faster) cache’s contents are a subset of the lower-level cache.

Modern L1 and L2 may use different inclusion/coherence policies:

Inclusive cache: L2 must contain everything in L1.
Non-inclusive cache: L1 and L2 need not hold the same data; each may cache different lines.
Exclusive cache: L1 and L2 do not share data; a line lives in only one level.

https://xjtu-ics.github.io/assets/images/Inclusive.png

A simulated scenario as in the figure:

I will not belabor the rest — just keep these two points:

On repeated misses walking down the hierarchy, once you find a level that hits (or memory), install the line into every level that missed.
When a lower level evicts a line, invalidate that line in all upper levels. Under Inclusive Policy, failing to do so would break the subset property.

Three-Level Cache Simulator
#

We implement a cache like this:

https://xjtu-ics.github.io/assets/images/three_level_cache.png

L1 is split into L1D (data R/W) and L1I (instruction fetch); L1I is read-only.
L1 and L2 are private per core
L2 is a unified cache — it stores both instructions and data
L3 is unified and shared by all cores

Per-cache configuration for quick reference:
- L1D(I) cache
  - size: 64B
  - set: 4
  - associativity: 2-way
  - cache line size: 8B
  - write policy: write back + write allocate
- L2 cache
  - size: 256B
  - set: 8
  - associativity: 4-way
  - cache line size: 8B
  - write poliy: write back + write allocate
  - inclusion policy: inclusive
- L3 cache
  - size: 2KB
  - set: 16
  - associativity: 8-way
  - cache line size: 16B
  - write policy: write back + write allocate
  - inclusion policy: inclusive

We implement a single-core cache hierarchy — no concurrent access or multi-core coherence.

Mild rant: our TAs basically spoon-feed the lab, turning it into a LeetCode-style “fill in the core code” exercise. That is not ideal, though it lowers the barrier.

(Sorry — I misjudged; it is still quite hard……)

Read the header first:

/*
 * cachelab.h - Prototypes for Cache Lab helper functions
 */

#ifndef CACHE_LAB_H
#define CACHE_LAB_H

#include <stdbool.h>
#include <stdint.h>

#define L1_SET_NUM 4
#define L1_LINE_NUM 2
#define L1_CACHELINE_SIZE 8

#define L2_SET_NUM 8
#define L2_LINE_NUM 4
#define L2_CACHELINE_SIZE 8

#define L3_SET_NUM 16
#define L3_LINE_NUM 8
#define L3_CACHELINE_SIZE 16

#define ADDRESS_LENGTH 64

#define MAX_TRANS_FUNCS 100

//核心的CacheLine是一个结构体
typedef struct {
  bool valid;
  bool dirty;
  uint64_t tag;
  uint64_t latest_used; // for LRU
} CacheLine;

typedef struct trans_func {
  void (*func_ptr)(int M, int N, int[N][M], int[M][N]);
  char *description;
  char correct;
  unsigned int num_hits;
  unsigned int num_misses;
  unsigned int num_evictions;
} trans_func_t;

// defined in csim.c
extern CacheLine l1dcache[L1_SET_NUM][L1_LINE_NUM];
// L1 Instruction Cache
extern CacheLine l1icache[L1_SET_NUM][L1_LINE_NUM];
// L2 Unified Cache
extern CacheLine l2ucache[L2_SET_NUM][L2_LINE_NUM];
// L2 Unified Cache
extern CacheLine l3ucache[L3_SET_NUM][L3_LINE_NUM];

/* Fill the matrix with data */
void initMatrix(int M, int N, int A[N][M], int B[M][N]);

/* The baseline trans function that produces correct results. */
void correctTrans(int M, int N, int A[N][M], int B[M][N]);

/* Add the given function to the function list */
void registerTransFunction(void (*trans)(int M, int N, int[N][M], int[M][N]),
                           char *desc);

#endif

Implementation order (flowchart; assume we are accessing level-i cache):

From the memory address, extract tag and set
Check whether level i hits
On a hit, jump to step 8
Otherwise, continue to the next level (or memory) to obtain the data
In this level’s set, find an invalid line for the fetched line; if several are invalid, pick the smallest index, then jump to step 8
If the set was full in step 5, first evict a line using LRU; if the victim is dirty, write it back to the next level (or memory) first
Because of inclusive policy, you may need to back-invalidate the corresponding line in level i − 1
Set the line’s tag, LRU, and valid fields
If the access is a write, set dirty
Return

They gave an example — let me look……

https://xjtu-ics.github.io/assets/images/cache_sim.png

Cache access trace in order:

Read a
Read b
Read a
Write b
Read c
Write a
Read d
Read c
Write b
Write c
Read e
Read f
Read b
Read d

Draw it out — it is fairly complex; the hardest part is back-invalidation on eviction.

Some notes from the TAs:

Before accessing the cache, correctly initialize every cache line — i.e., zero all fields

You may assume a single access never spans two lines — i.e., you can ignore the third parameter of cacheAccess

An M access may be treated as one read plus one write

Note that L2 and L3 hold both instructions and data

You may assume instructions and data never touch the same memory — i.e., a line in L2 never appears in both L1D and L1I

Is that really true? After I assumed accesses to one block, a bunch of cases passed (or I may be misleading people……)

This lab only simulates cache accesses — you need not care about the actual written data

You may use bit tricks to extract tag, set, and block offset from the address

You may use bit tricks to reconstruct a memory address from tag, set, and block

When installing a line, find a free line in the set — i.e., a line with valid == false. If several are free, pick the smallest index

You must use strict LRU to choose eviction victims

A simple loop-based LRU is fine (ignore asymptotic cost); maintain a global clock and carefully set each line’s latest_used

On eviction, honor dirty: if dirty is true, write the old line back to the next level before installing the new one; if false, you may simply discard it

When evicting, you need not update the victim’s LRU field

Update LRU after every successful access: a hit on read/write, or a read/write after the line has been fetched from a lower level

On a conflict miss, strictly fetch first, then evict: first obtain the needed line from the next level or memory, then choose a victim. This can affect LRU ordering. Example: global clock is 10; L1 conflict-misses and L2 hits — access L2 first; on L2 hit set that line’s LRU to 10 and return the line to L1; if L1’s victim is dirty, write it back to L2 first (this is a 100% hit — why?), so that L2 line’s LRU becomes 11; finally place the needed line in the vacated L1 slot and set its LRU to 12

The lab requires that anything in an upper cache also exists in the lower one — inclusive policy. Maintain and exploit this invariant

Under inclusion, writing back dirty data is effectively a 100% hit; arrange code order accordingly

On a write miss, first fetch the line from the next level (or memory), then write it. Think carefully about what access type to use when touching the next level

If you evict a line from L2 that also exists in L1, you must also evict it from L1 — back invalidation. If the L1 copy is dirty, write it back to L2 first.

If you evict from L3, also evict the corresponding lines from L1 and L2. Think carefully about eviction order to preserve inclusion.

Different levels may have different line sizes — account for that when designing the code

In VS Code: Ctrl+Shift+I to format

Debug is driving me crazy…… (debug diary)

//分析一下错误
Testcase                                     Lines     Result    Random    Score     
---------------------------------------------------------------------------------
traces-data-intensive/long.trace             267988    FAIL      IGNORE    0/3       
  Details for trace <traces-data-intensive/long.trace>
                          Your simulator           Reference simulator
     Level      Hits    Misses    Evicts      Hits    Misses    Evicts
      L1 D    231249     55715     53833    230444     56520     53285
      L1 I         0         0         0         0         0         0
        L2     46998     26645     26424     47391     27797     24629
        L3     32061     10181     10053     33435     11645     11517

hits + misses match, but the delta is exactly 805 — too many hits, too few misses, so evicts drift too. This should be a logic bug, not a counting bug.

races-basic/mixed-2.trace                   90        FAIL      IGNORE    0/5       
  Details for trace <traces-basic/mixed-2.trace>
                          Your simulator           Reference simulator
     Level      Hits    Misses    Evicts      Hits    Misses    Evicts
      L1 D        20        60        52        20        60        52
      L1 I        18        12         7        17        13         6
        L2        71        43        15        71        44        16
        L3        19        28         0        21        28         0

Why do I-side alone and the parts alone look fine, but combining them fails — how do they interfere???

traces-hard/grep.trace                       406467    FAIL      IGNORE    0/1       
  Details for trace <traces-hard/grep.trace>
                          Your simulator           Reference simulator
     Level      Hits    Misses    Evicts      Hits    Misses    Evicts
      L1 D     37304      1068       949     22544     15828       502
      L1 I    184075    184064    184034    184075    184064    184016
        L2    176099      9087      9055    118023     81983     81951
        L3      6693      2413      2285     79669      2416      2288

L3 hit counts diverge badly — L2 data not evicted in time???

Park this for now; rest and come back.

Already at 76 points, but the remaining logic bugs are brutal to find. Agonizing!

OK — finally 93. The last few points I simply cannot find; I will not paste the source. It is six-to-seven hundred lines of runnable junk; I will tidy it later. I gave it everything. By the end it no longer felt like a design problem — I was even second-guessing whether some of the design hints were wrong, which is no fun……

In the end it was likely the different block-offset widths across the three levels; handle that carefully. Zeroing L3’s block bits naively can corrupt L2’s set-index bits.

About posting code:

My code is poor — not worth posting (time was tight; compressed it could be ~300 lines).

Academic integrity.

Some Thoughts on Caches
#

Not especially deep — just digging further. Views below are my own or from asking GPT. If you have a better take, please comment. Here “lower-level cache” means the level closer to memory.

1.
#

This lab stresses Inclusive policy. That design was common in older CPUs, especially Intel, but modern CPUs increasingly move toward NINE. That raises:

What conditions must an Inclusive cache satisfy? Pros and cons?

The lower cache must contain the upper cache; on lower-level eviction, perform back invalidation.

Pros:

Easy to reason about; with multiple cores it is clear whether higher-level contents exist in lower levels.

Cons:

Redundant eviction: when L2 evicts a line, L1 must evict it too even if L1 is still hot — extra L1 misses.

Capacity waste: to maintain inclusion, some L2 space is forced to mirror L1, lowering effective capacity.

Lower performance ceiling: the lower cache is not a true “supplement”; it is constrained by what L1 holds.
NINE does not force the lower cache to contain the upper. Pros/cons vs inclusive?

(NINE: Non-Inclusive, Non-Exclusive)

NINE means the lower cache need not contain the upper, and the two levels need not be mutually exclusive either.

Pros:

Less redundancy, better utilization; lower-level eviction need not disturb the upper cache and cause unnecessary misses.

Cons:

Harder coherence and more complex management (NINE sits between inclusive and exclusive). E.g., after an L2 hit, do you promote into L1 and drop L2? Inclusive forbids dropping; exclusive requires it.
This lab leans hard on inclusion to simplify design. How would you change the code for NINE?

First remove back-invalidation; then, as above, add a promote path for lower-level lines.

2.
#

Modern CPUs almost always split L1 into L1D and L1I, while L2 and below are unified. Why?

GPT’s answer (seems decent; I am not fully sure how accurate it is):

✅ Why split L1 into L1D and L1I?

➕ Benefit 1: bandwidth / parallelism

Each cycle the CPU typically needs both instruction fetch and data access.
A unified L1 contends for one cache port.
Split L1I/L1D lets the CPU fetch instructions and access data concurrently.

➕ Benefit 2: lower latency

L1 is closest to the core — small and fast.
Separate management enables specialized optimizations:
- L1I: prefetch, branch prediction;
- L1D: load/store paths, write buffers, etc.

➕ Benefit 3: less pollution

Instruction and data access patterns differ:
- instructions are more sequential with good locality;
- data may be strided, random, or repeatedly reread.
Separation avoids data polluting the I-cache (or vice versa).

✅ Why are L2/L3 unified?

➕ Reason 1: utilization

L2/L3 are larger (hundreds of KB to tens of MB).
A split I/D L2 might leave one side empty while the other is full — wasted capacity.
Unified cache allocates dynamically by demand.

➕ Reason 2: simpler / cheaper

Farther from the core, latency is higher; concurrent ports are less critical.
One structure is simpler — no separate tags/replacement for I and D.

➕ Reason 3: coherence protocols

A shared L3 is easier to track, snoop, and communicate over when unified.

3.
#

How does the CPU distinguish instruction vs data memory accesses?

1. Internally, modern CPUs have clear units:

Instruction Fetch Unit — fetches instructions
Load/Store Unit — reads/writes data

They use different paths and thus different caches (L1I vs L1D).

2. From software:

The compiler places executable code in one memory region
And variables/data in another

At runtime:

Accesses from the instruction pointer (PC / IP) are fetches
Accesses from ordinary Load/Store instructions are data accesses

So the issuing unit tells you whether the access is I or L/S.

4.
#

The lab requires strict LRU. A brute-force scan of all lines is O(E). Can you design an O(1) approach?

This is the classic LRU Cache problem — you should see why: https://leetcode.cn/problems/lru-cache/description/

Java implementation (I have written a lot of Java before):

//Least Recently Used
//最近最少使用
//HashMap + DoublyLinkedList
class LRUCache {
    //简单的双向链表
    class Node{
        int key;
        int val;
        Node prev;
        Node next;
        public Node(){}
        public Node(int _key, int _val){key = _key; val = _val;}
    }
    private Map<Integer, Node> cache;
    private int size;
    private int capacity;
    private Node head;
    private Node tail;
    //初始化缓存
    public LRUCache(int capacity) {
        cache = new HashMap<>();
        this.size = 0;
        this.capacity = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
    //相当于读取内存，读取成功这个值就返回value,并且放到双向链表的头部，否则返回-1（实际上要从内存中获取）
    public int get(int key) {
        if(cache.containsKey(key)){
            moveToHead(cache.get(key));
            return cache.get(key).val;
        }
        return -1;
    }
    //写值，道理类似
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            Node node = cache.get(key);
            node.val = value;
            moveToHead(node);
        }else{
            ++size;
            if(size > capacity){
                --size;
                Node d = tail.prev;
                remove(d);
                cache.remove(d.key);
            }
            Node node = new Node(key, value);
            cache.put(key, node);
            add(node);
        }
    }
    //一旦get或者put，就放到head之后，作为最新的节点
    private void moveToHead(Node node){
        remove(node);
        add(node);
    }
    //一旦过容量，或者其他场景，删除节点
    private void remove(Node node){
        Node p = node.prev;
        Node n = node.next;
        p.next = n;
        n.prev = p;
    }
    //新put进来的元素，加到头节点之后
    private void add(Node node){
        Node n = head.next;
        head.next = node;
        node.prev = head;
        node.next = n;
        n.prev = node;
    }
}

Basically a doubly linked list + hashmap: given a key, find the cache line / list node in O(1), move that node to the head as MRU; the node before the tail is LRU.

Asymptotically O(1), but constant factors are not tiny.

5.
#

LRU can cause 100% misses in a certain pattern — can you find it?

LRU thrashing

Example: L1 has one set with three lines; cycle through four elements A B C D:

Install A B C

Read D → miss, evict A, place D

Read A → miss, evict B, place A

Read B → miss, evict C, place B

……

That pattern is 100% miss.

6.
#

True LRU is expensive in hardware, so most vendors use approximations. How would you design one?

From GPT — not the clearest; see https://en.wikipedia.org/wiki/Pseudo-LRU

Pseudo-LRU (PLRU)

Implementation:

Most common is binary-tree PLRU:
- Fits 4-, 8-, 16-way set-associative caches.
- Maintain a tree of bits; each node records whether the left or right child was used more recently.
- Only E − 1 bits to choose a victim.

Schematic:

    (b1)
   /   \
(b2)   (b3)
 / \    /  \
A   B  C    D

Each internal node 0/1 indicates which side was accessed more recently
To pick a victim, walk from the root toward the “least recently used” side

Example:

b0, b1, b2 are three bits steering which subtree to take.
Each bit records “which side was used last”.

Interpretation:

If b0 = 0, left subtree (A, B) was used last → prefer replacing right (C, D)
If b1 = 1, within left, B was used last → replace A
If b2 = 0, within right, C was used last → replace D

From the root, follow bits toward the side not recently used until a leaf (the victim line).

Then flip bits along the path to mark the path just taken as recently used.

Suppose currently:

b0 = 0 → last used left (A or B)
b1 = 1 → last used B
b2 = 0 → last used C

On replacement:

b0 is 0 → left was recent → replace right
Enter b2, see 0 → C was recent → replace D

✅ Victim is D

Then set:

b0 = 1 (now right was used)
b2 = 1 (D was used)

Pros:

Simple hardware, low cost
Often close to true LRU in practice

Cons:

Not true LRU — may evict a still-hot block

7.
#

In this lab, on a conflict miss we always fetch from the next level before deciding to evict. Pros/cons? What if the order is swapped? Consider inclusive policy.

With only one cache level plus memory, order barely matters.

Think with two cache levels plus memory:

L1 L2 memory

L1 misses, L1 is full — evict immediately to make room.

Then L2 misses, L2 is full — evict, and back-invalidate L1 if needed. The back-invalidated L1 line might be the same line L1 just evicted — wasted work?

Then fetch from memory into L2 and into the L1 slot just freed.

Scheme	Pros	Cons

Fetch then evict (lab policy)	- Avoids pointless Inclusive invalidates - More stable coherence - Simpler	- Higher latency - Sometimes redundant fetch

Evict then fetch	- Can hide latency - Possible parallelism	- Conflicts with Inclusive - Extra state

8.
#

Cache accesses extract tag/set from addresses, but the CPU produces virtual addresses that must be translated to physical ones (see virtual memory). Caches can be physical-index or virtual-index:

Pros/cons of physical index?

Avoids synonyms/aliases; needs TLB translation → latency.
Pros/cons of virtual index?

Faster access, but aliasing issues.
Can you combine the best of both?

Not sure（?）

Compromise: VIPT (Virtual Index, Physical Tag)
#

Index with the virtual address; compare tags with the physical address

Advantages:
#
- Keeps virtual-index speed (find the set with VA index)
- Physical tags avoid aliasing
- Mainstream modern L1 design (as long as index bits stay within the page offset)
Design constraints:
#
- Page offset is unchanged — index bits must lie in the page offset (otherwise you cannot know the index before translation).
- Example:
  - Page size: 4KB = 12-bit offset
  - Index bits ≤ 12
  - Tag = physical address minus index + block-offset bits

I have done a bit of Java concurrency but not a full OS course yet — enough to appreciate multithreading issues. It gets quite complex here; I will stop hand-waving.

9.
#

This simulator only handles sequential access. How would you extend it for concurrent threads?

Protect each cache set with a mutex so at most one thread touches a set at a time.

Use atomics for LRU-related state, etc.

Better ideas welcome in the comments!

10.
#

This lab ignores multi-core coherence. If L3 is the shared cache and you must handle coherence, how would you change the code?

11.
#

Under multi-core coherence, if you switch from inclusive to NINE, what else must change?

Finished code:

Also on my GitHub. When you implement it yourself you will notice lots of similar logic — think about how to factor it. It should have been a much more elegant structure.

#include "cachelab.h"
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
// 可能要包含的头文件
// 要不要封装功能？具体实现的方式
// 先写的时候可以不急着做功能抽象，先写出来试试看
// Q：当我在l2中访问缓存命中时，我要把这个地址加载回l1,但是由于这个地址已经确定，那么不会出现明明有空但是必须驱逐的现象么
// 相关数据统计量，是我在实现的过程中要进行维护的 容易忘记 一共3 * 4 = 12个数据
// 当一个地址给定的时候，它的所有的SetIndex就已经定下来了
// 注意C语言的{}的风格
int l1d_hits = 0;
int l1d_misses = 0;
int l1d_evictions = 0;
int l1i_hits = 0;
int l1i_misses = 0;
int l1i_evictions = 0;
int l2_hits = 0;
int l2_misses = 0;
int l2_evictions = 0;
int l3_hits = 0;
int l3_misses = 0;
int l3_evictions = 0;

// 定义一些常量
#define L1S 2
#define L1B 3

#define L2S 3
#define L2B 3

#define L3S 4
#define L3B 4

#define INSTRUCTION 0
#define DATA 1

//@params time:要使用LRU算法维护的一个全局时钟
int timeStamp = 0;

// 全局变量加载默认初始化为0
void cacheInit()
{
}

// 拼接地址,假设填充的偏移字节不会产生影响：都用0来做填充
// 这里要好好检查有没有出错
uint64_t addressConcate(uint64_t tag, uint64_t setIndex, int s, int b)
{
    uint64_t addr = ((tag << (s + b)) | (setIndex << b));
    return addr;
}

// 把驱逐一个CacheLine的功能封装一下,要考虑无效回溯的情况，但是我很难封装到一个function里面去，最好写成四个function
// 要驱逐的cacheLine地址
// 并且合理利用包含准则
// 直接把地址作为参数，复用性是不是会更强--->我的目的还是为了少传送几个参数
// 这几个驱逐的函数只是单纯的做驱逐的处理，但是不会加载新的值
// lru找要不要也封装？这样对地址操作有可能出错吗？
// 还要对于统计量进行操作
// 要考察是不是无效回溯导致的驱逐，如果是，那么这里不应该算进去统计的问题
// l1i是一个只读的内存,
void evictCacheLineFroml1i(uint64_t evictAddress, bool isBackInvalidation)
{
    uint64_t tag = (evictAddress >> (L1S + L1B));
    uint64_t setIndex = ((evictAddress >> L1B) & 0b11);

    int evictIndex = -1;

    for (int index = 0; index < L1_LINE_NUM; ++index)
    {
        // 找到了要驱逐的行
        if (l1icache[setIndex][index].valid && l1icache[setIndex][index].tag == tag)
        {
            evictIndex = index;
            break;
        }
    }
    // 没有要驱逐的行,因为要考虑Back Invalidation
    if (evictIndex == -1)
    {
        return;
    }
    // 有要驱逐的行
    if (!isBackInvalidation)
    {
        ++l1i_evictions;
    }
    l1icache[setIndex][evictIndex].valid = false;
}

// L1dcache的驱逐的逻辑和L1icahce的逻辑应该是类似的,其实不是
void evictCacheLineFroml1d(uint64_t evictAddress, bool isBackInvalidation)
{
    uint64_t tag = (evictAddress >> (L1S + L1B));
    uint64_t setIndex = ((evictAddress >> L1B) & 0b11);
    int evictIndex = -1;
    for (int index = 0; index < L1_LINE_NUM; ++index)
    {
        // 找到了要驱逐的行
        if (l1dcache[setIndex][index].valid && l1dcache[setIndex][index].tag == tag)
        {
            evictIndex = index;
            break;
        }
    }
    // 没有要驱逐的行,因为要考虑Back Invalidation
    if (evictIndex == -1)
        return;

    if (!isBackInvalidation)
    {
        ++l1d_evictions;
    }
    // 有要驱逐的行
    l1dcache[setIndex][evictIndex].valid = false;
    if (l1dcache[setIndex][evictIndex].dirty)
    {
        uint64_t tag2 = (evictAddress >> (L2S + L2B));
        uint64_t setIndex2 = ((evictAddress >> L2B) & 0b111);
        for (int index = 0; index < L2_LINE_NUM; ++index)
        {
            if (l2ucache[setIndex2][index].valid && l2ucache[setIndex2][index].tag == tag2)
            {
                // L2的这个Cache被写了，更改timeStamp
                ++l2_hits;
                ++timeStamp;
                l2ucache[setIndex2][index].latest_used = timeStamp;
                l2ucache[setIndex2][index].dirty = true;
                return;
            }
        }
    }
}

// 从l2ucache驱逐,还要考虑你驱逐的是i还是d
void evictCacheLineFroml2(uint64_t evictAddress, int TYPE, bool isBackInvalidation)
{
    if (!isBackInvalidation)
    {
        uint64_t tag = (evictAddress >> (L2S + L2B));
        uint64_t setIndex = ((evictAddress >> L2B) & 0b111);
        int evictIndex = -1;
        for (int index = 0; index < L2_LINE_NUM; ++index)
        {
            if (l2ucache[setIndex][index].valid && l2ucache[setIndex][index].tag == tag)
            {
                evictIndex = index;
            }
        }
        // 没有找到要驱逐的位置
        if (evictIndex == -1)
        {
            return;
        }
        // 这里要进行驱逐
        // 首先从l2ucache驱逐要考虑无效回溯
        // L2 back Invalidation L1的时候不应该给L1算一次evict?
        ++l2_evictions;
        evictCacheLineFroml1d(evictAddress, true);
        evictCacheLineFroml1i(evictAddress, true);
        l2ucache[setIndex][evictIndex].valid = false;

        // 直接驱逐的情况
        if (l2ucache[setIndex][evictIndex].dirty)
        {
            uint64_t tag3 = (evictAddress >> (L3S + L3B));
            uint64_t setIndex3 = ((evictAddress >> L3B) & 0b1111);
            for (int index = 0; index < L3_LINE_NUM; ++index)
            {
                if (l3ucache[setIndex3][index].valid && l3ucache[setIndex3][index].tag == tag3)
                {
                    ++l3_hits;
                    ++timeStamp;
                    l3ucache[setIndex3][index].latest_used = timeStamp;
                    l3ucache[setIndex3][index].dirty = true;
                    return;
                }
            }
        }
    }
    else
    {
        uint64_t tag = (evictAddress >> (L2S + L2B));
        uint64_t setIndex = ((evictAddress >> L2B) & 0b111);
        int evictIndex = -1;
        for (int index = 0; index < L2_LINE_NUM; ++index)
        {
            if (l2ucache[setIndex][index].valid && l2ucache[setIndex][index].tag == tag)
            {
                evictIndex = index;
                evictCacheLineFroml1d(evictAddress, true);
                evictCacheLineFroml1i(evictAddress, true);
                l2ucache[setIndex][evictIndex].valid = false;
                // 直接驱逐的情况
                if (l2ucache[setIndex][evictIndex].dirty)
                {
                    uint64_t tag3 = (evictAddress >> (L3S + L3B));
                    uint64_t setIndex3 = ((evictAddress >> L3B) & 0b1111);
                    for (int i = 0; i < L3_LINE_NUM; ++i)
                    {
                        if (l3ucache[setIndex3][i].valid && l3ucache[setIndex3][i].tag == tag3)
                        {
                            ++l3_hits;
                            ++timeStamp;
                            l3ucache[setIndex3][i].latest_used = timeStamp;
                            l3ucache[setIndex3][i].dirty = true;
                        }
                    }
                }
            }
        }

        if (setIndex % 2 == 0)
        {
            ++setIndex;
            evictIndex = -1;
            for (int index = 0; index < L2_LINE_NUM; ++index)
            {
                if (l2ucache[setIndex][index].valid && l2ucache[setIndex][index].tag == tag)
                {
                    evictIndex = index;
                    evictCacheLineFroml1d(evictAddress, true);
                    evictCacheLineFroml1i(evictAddress, true);
                    l2ucache[setIndex][evictIndex].valid = false;
                    // 直接驱逐的情况
                    if (l2ucache[setIndex][evictIndex].dirty)
                    {
                        uint64_t tag3 = (evictAddress >> (L3S + L3B));
                        uint64_t setIndex3 = ((evictAddress >> L3B) & 0b1111);
                        for (int i = 0; i < L3_LINE_NUM; ++i)
                        {
                            if (l3ucache[setIndex3][i].valid && l3ucache[setIndex3][i].tag == tag3)
                            {
                                ++l3_hits;
                                ++timeStamp;
                                l3ucache[setIndex3][i].latest_used = timeStamp;
                                l3ucache[setIndex3][i].dirty = true;
                            }
                        }
                    }
                }
            }
        }

        if (setIndex % 2 == 1)
        {
            --setIndex;
            evictIndex = -1;
            for (int index = 0; index < L2_LINE_NUM; ++index)
            {
                if (l2ucache[setIndex][index].valid && l2ucache[setIndex][index].tag == tag)
                {
                    evictIndex = index;
                    evictCacheLineFroml1d(evictAddress, true);
                    evictCacheLineFroml1i(evictAddress, true);
                    l2ucache[setIndex][evictIndex].valid = false;
                    // 直接驱逐的情况
                    if (l2ucache[setIndex][evictIndex].dirty)
                    {
                        uint64_t tag3 = (evictAddress >> (L3S + L3B));
                        uint64_t setIndex3 = ((evictAddress >> L3B) & 0b1111);
                        for (int i = 0; i < L3_LINE_NUM; ++i)
                        {
                            if (l3ucache[setIndex3][i].valid && l3ucache[setIndex3][i].tag == tag3)
                            {
                                ++l3_hits;
                                ++timeStamp;
                                l3ucache[setIndex3][i].latest_used = timeStamp;
                                l3ucache[setIndex3][i].dirty = true;
                            }
                        }
                    }
                }
            }
        }
    }
}

// 从l3ucache驱逐，同样要考虑驱逐的类型问题
void evictCacheLineFroml3(uint64_t evictAddress, int TYPE)
{
    uint64_t tag = (evictAddress >> (L3S + L3B));
    uint64_t setIndex = ((evictAddress >> L3B) & 0b1111);
    int evictIndex = -1;
    for (int index = 0; index < L3_LINE_NUM; ++index)
    {
        if (l3ucache[setIndex][index].valid && l3ucache[setIndex][index].tag == tag)
        {
            evictIndex = index;
            break;
        }
    }

    if (evictIndex == -1)
    {
        return;
    }

    // Back Invalidation
    ++l3_evictions;
    evictCacheLineFroml2(evictAddress, INSTRUCTION, true);

    l3ucache[setIndex][evictIndex].valid = false;
}

// TODO：思考fetch函数组的封装有没有问题
// 想把一个line从L2fetch到l1i
void fetchl2tol1i(uint64_t setIndex1, uint64_t tag1)
{
    // 维护l1驱逐的情况
    int evictIndexl1i = -1;
    uint64_t minTimeStampl1i = UINT64_MAX;
    for (int j = 0; j < L1_LINE_NUM; ++j)
    {
        // 能找到L1也存在无效的情况,最好的情况
        if (!l1icache[setIndex1][j].valid)
        {
            ++timeStamp;
            l1icache[setIndex1][j].latest_used = timeStamp;
            l1icache[setIndex1][j].dirty = false;
            l1icache[setIndex1][j].tag = tag1;
            l1icache[setIndex1][j].valid = true;
            return;
        }
        // 要给l1驱逐的情况
        else
        {
            if (l1icache[setIndex1][j].latest_used < minTimeStampl1i)
            {
                minTimeStampl1i = l1icache[setIndex1][j].latest_used;
                evictIndexl1i = j;
            }
        }
    }
    // 先给l1i做驱逐
    uint64_t evictL1iAddress = addressConcate(l1icache[setIndex1][evictIndexl1i].tag, setIndex1, L1S, L1B);
    evictCacheLineFroml1i(evictL1iAddress, false);
    // 此时l1i已经驱逐完毕,驱逐完了之后再fetch进去
    ++timeStamp;
    l1icache[setIndex1][evictIndexl1i].latest_used = timeStamp;
    l1icache[setIndex1][evictIndexl1i].dirty = false;
    l1icache[setIndex1][evictIndexl1i].tag = tag1;
    l1icache[setIndex1][evictIndexl1i].valid = true;
}

// 把一个line从L2fetch到l1d
void fetchl2tol1d(uint64_t setIndex1, uint64_t tag1)
{
    int evictIndexl1d = -1;
    uint64_t minTimeStampl1d = UINT64_MAX;
    for (int j = 0; j < L1_LINE_NUM; ++j)
    {
        if (!l1dcache[setIndex1][j].valid)
        {
            ++timeStamp;
            l1dcache[setIndex1][j].latest_used = timeStamp;
            l1dcache[setIndex1][j].dirty = false;
            l1dcache[setIndex1][j].tag = tag1;
            l1dcache[setIndex1][j].valid = true;
            return;
        }
        else
        {
            if (l1dcache[setIndex1][j].latest_used < minTimeStampl1d)
            {
                minTimeStampl1d = l1dcache[setIndex1][j].latest_used;
                evictIndexl1d = j;
            }
        }
    }
    uint64_t evictL1dAddress = addressConcate(l1dcache[setIndex1][evictIndexl1d].tag, setIndex1, L1S, L1B);
    evictCacheLineFroml1d(evictL1dAddress, false);
    ++timeStamp;
    l1dcache[setIndex1][evictIndexl1d].latest_used = timeStamp;
    l1dcache[setIndex1][evictIndexl1d].dirty = false;
    l1dcache[setIndex1][evictIndexl1d].tag = tag1;
    l1dcache[setIndex1][evictIndexl1d].valid = true;
}

// 把一个line从L3fetch到L2
void fetchl3tol2(uint64_t setIndex2, uint64_t tag2, int TYPE)
{
    uint64_t minTimeStamp = UINT64_MAX;
    // 如果满了，要驱逐的index
    int evictIndex = -1;
    for (int i = 0; i < L2_LINE_NUM; ++i)
    {
        if (!l2ucache[setIndex2][i].valid)
        {
            ++timeStamp;
            l2ucache[setIndex2][i].latest_used = timeStamp;
            l2ucache[setIndex2][i].dirty = false;
            l2ucache[setIndex2][i].tag = tag2;
            l2ucache[setIndex2][i].valid = true;
            return;
        }
        else
        {
            if (l2ucache[setIndex2][i].latest_used < minTimeStamp)
            {
                minTimeStamp = l2ucache[setIndex2][i].latest_used;
                evictIndex = i;
            }
        }
    }
    // 考虑L2的驱逐
    uint64_t evictaddressl2 = addressConcate(l2ucache[setIndex2][evictIndex].tag, setIndex2, L2S, L2B);
    evictCacheLineFroml2(evictaddressl2, TYPE, false);
    ++timeStamp;
    l2ucache[setIndex2][evictIndex].latest_used = timeStamp;
    l2ucache[setIndex2][evictIndex].dirty = false;
    l2ucache[setIndex2][evictIndex].tag = tag2;
    l2ucache[setIndex2][evictIndex].valid = true;
}

// 把一个内存中的值fetch到l3
void fetchMemoryTol3(uint64_t setIndex3, uint64_t tag3, int TYPE)
{
    int evictIndex = -1;
    uint64_t minTimeStamp = UINT64_MAX;
    for (int index = 0; index < L3_LINE_NUM; ++index)
    {
        if (!l3ucache[setIndex3][index].valid)
        {
            ++timeStamp;
            l3ucache[setIndex3][index].latest_used = timeStamp;
            l3ucache[setIndex3][index].dirty = false;
            l3ucache[setIndex3][index].tag = tag3;
            l3ucache[setIndex3][index].valid = true;
            return;
        }
        else
        {
            if (l3ucache[setIndex3][index].latest_used < minTimeStamp)
            {
                minTimeStamp = l3ucache[setIndex3][index].latest_used;
                evictIndex = index;
            }
        }
    }
    uint64_t evictAddress = addressConcate(l3ucache[setIndex3][evictIndex].tag, setIndex3, L3S, L3B);
    evictCacheLineFroml3(evictAddress, TYPE);
    ++timeStamp;
    l3ucache[setIndex3][evictIndex].latest_used = timeStamp;
    l3ucache[setIndex3][evictIndex].dirty = false;
    l3ucache[setIndex3][evictIndex].tag = tag3;
    l3ucache[setIndex3][evictIndex].valid = true;
}

/* 我们先写一个Instruction尝试一下:读取指令
 * @params addr 为访问地址，它是trace文件中的地址的十进制表示的结果,64位16进制内存地址
 * OK：经过纯I指令检测，这个函数实现的没有问题
 */
void instruct(uint64_t addr)
{
    // 先访问第一级Cache,处理addr
    uint64_t tag1 = (addr >> (L1S + L1B));
    uint64_t setIndex1 = ((addr >> L1B) & 0b11);

    uint64_t tag2 = (addr >> (L2S + L2B));
    uint64_t setIndex2 = ((addr >> L2B) & 0b111);

    uint64_t tag3 = (addr >> (L3S + L3B));
    uint64_t setIndex3 = ((addr >> L3B) & 0b1111);

    //  根据拿到的数据看第一级有没有命中
    for (int index = 0; index < L1_LINE_NUM; ++index)
    {
        // 合法并且tag相同，就是命中
        if (l1icache[setIndex1][index].valid && l1icache[setIndex1][index].tag == tag1)
        {
            // 命中之后的处理
            ++timeStamp;
            ++l1i_hits;
            l1icache[setIndex1][index].latest_used = timeStamp;
            return;
        }
    }

    // 到这里证明l1i没有命中,在l2中找
    ++l1i_misses;
    for (int index = 0; index < L2_LINE_NUM; ++index)
    {
        // l2中缓存命中
        if (l2ucache[setIndex2][index].valid && l2ucache[setIndex2][index].tag == tag2)
        {
            ++timeStamp;
            l2ucache[setIndex2][index].latest_used = timeStamp;
            ++l2_hits;
            fetchl2tol1i(setIndex1, tag1);
            return;
        }
    }

    // 到这里证明l2没有命中，在l3中找
    ++l2_misses;
    for (int index = 0; index < L3_LINE_NUM; ++index)
    {
        // l3缓存命中
        if (l3ucache[setIndex3][index].valid && l3ucache[setIndex3][index].tag == tag3)
        {
            ++timeStamp;
            l3ucache[setIndex3][index].latest_used = timeStamp;
            ++l3_hits;
            fetchl3tol2(setIndex2, tag2, INSTRUCTION);
            fetchl2tol1i(setIndex1, tag1);
            return;
        }
    }

    // 到这里证明l3没有命中，要从缓存中取值加载到三层里面去
    ++l3_misses;
    // 找要驱逐的L3的地址
    fetchMemoryTol3(setIndex3, tag3, INSTRUCTION);
    fetchl3tol2(setIndex2, tag2, INSTRUCTION);
    fetchl2tol1i(setIndex1, tag1);
    // 理论上到这里取值令的过程已经结束
}

// 读取数据的问题,读取数据和读取指令是否是类似的
void load(uint64_t addr)
{
    // 先访问第一级Cache,处理addr
    uint64_t tag1 = (addr >> (L1S + L1B));
    uint64_t setIndex1 = ((addr >> L1B) & 0b11);

    uint64_t tag2 = (addr >> (L2S + L2B));
    uint64_t setIndex2 = ((addr >> L2B) & 0b111);

    uint64_t tag3 = (addr >> (L3S + L3B));
    uint64_t setIndex3 = ((addr >> L3B) & 0b1111);

    //  根据拿到的数据看第一级有没有命中
    for (int index = 0; index < L1_LINE_NUM; ++index)
    {
        // 合法并且tag相同，就是命中
        if (l1dcache[setIndex1][index].valid && l1dcache[setIndex1][index].tag == tag1)
        {
            // 命中之后的处理
            ++timeStamp;
            ++l1d_hits;
            l1dcache[setIndex1][index].latest_used = timeStamp;
            return;
        }
    }

    ++l1d_misses;
    for (int index = 0; index < L2_LINE_NUM; ++index)
    {
        // l2中缓存命中
        if (l2ucache[setIndex2][index].valid && l2ucache[setIndex2][index].tag == tag2)
        {
            ++timeStamp;
            l2ucache[setIndex2][index].latest_used = timeStamp;
            ++l2_hits;
            fetchl2tol1d(setIndex1, tag1);
            return;
        }
    }

    // 到这里证明l2没有命中，在l3中找
    ++l2_misses;
    for (int index = 0; index < L3_LINE_NUM; ++index)
    {
        // l3缓存命中
        if (l3ucache[setIndex3][index].valid && l3ucache[setIndex3][index].tag == tag3)
        {
            ++timeStamp;
            l3ucache[setIndex3][index].latest_used = timeStamp;
            ++l3_hits;
            fetchl3tol2(setIndex2, tag2, DATA);
            fetchl2tol1d(setIndex1, tag1);
            return;
        }
    }

    // 到这里证明l3没有命中，要从缓存中取值加载到三层里面去
    ++l3_misses;
    // 找要驱逐的L3的地址
    fetchMemoryTol3(setIndex3, tag3, DATA);
    fetchl3tol2(setIndex2, tag2, DATA);
    fetchl2tol1d(setIndex1, tag1);
}

// 重点逻辑：写入内存的实现
// 先fetch这个cacheline，接着才进行改动，我这里成了先改动，再fecth上去，肯定是不行的
// 简单来说，写入操作是不会影响L2和L3的
void store(uint64_t addr)
{
    // 先列出所有可能要访问的数据
    uint64_t tag1 = (addr >> (L1S + L1B));
    uint64_t setIndex1 = ((addr >> L1B) & 0b11);

    uint64_t tag2 = (addr >> (L2S + L2B));
    uint64_t setIndex2 = ((addr >> L2B) & 0b111);

    uint64_t tag3 = (addr >> (L3S + L3B));
    uint64_t setIndex3 = ((addr >> L3B) & 0b1111);

    // 写l1d
    for (int index = 0; index < L1_LINE_NUM; ++index)
    {
        // l1d write hit
        if (l1dcache[setIndex1][index].valid && l1dcache[setIndex1][index].tag == tag1)
        {
            ++l1d_hits;
            ++timeStamp;
            l1dcache[setIndex1][index].latest_used = timeStamp;
            l1dcache[setIndex1][index].dirty = true;
            return;
        }
    }

    // l1d write misses
    ++l1d_misses;

    // 在L2中写
    for (int index = 0; index < L2_LINE_NUM; ++index)
    {
        // l2 write hit
        if (l2ucache[setIndex2][index].valid && l2ucache[setIndex2][index].tag == tag2)
        {
            // L2写命中，我先把这个位置加载回l1d，接着才进行dirty的修改，写命中时，首先更改一下lru
            ++l2_hits;
            ++timeStamp;
            l2ucache[setIndex2][index].latest_used = timeStamp;
            fetchl2tol1d(setIndex1, tag1);
            for (int i = 0; i < L1_LINE_NUM; ++i)
            {
                // 在fetch了之后，此时这里的lru已经发生了改变，所以是不是不用再进行更改?
                // 应该是的
                if (l1dcache[setIndex1][i].valid && l1dcache[setIndex1][i].tag == tag1)
                {
                    l1dcache[setIndex1][i].dirty = true;
                    return;
                }
            }
        }
    }

    // l2u write misses
    ++l2_misses;
    for (int index = 0; index < L3_LINE_NUM; ++index)
    {
        // l3 write hit
        if (l3ucache[setIndex3][index].valid && l3ucache[setIndex3][index].tag == tag3)
        {
            ++l3_hits;
            ++timeStamp;
            l3ucache[setIndex3][index].latest_used = timeStamp;
            fetchl3tol2(setIndex2, tag2, DATA);
            fetchl2tol1d(setIndex1, tag1);
            for (int i = 0; i < L1_LINE_NUM; ++i)
            {
                if (l1dcache[setIndex1][i].valid && l1dcache[setIndex1][i].tag == tag1)
                {
                    l1dcache[setIndex1][i].dirty = true;
                    return;
                }
            }
        }
    }

    // l3u write miss,在内存中写，然后直接加载上去，是否正确,显然错误
    ++l3_misses;
    fetchMemoryTol3(setIndex3, tag3, DATA);
    fetchl3tol2(setIndex2, tag2, DATA);
    fetchl2tol1d(setIndex1, tag1);
    // 在fetch完了之后，在set1中找要写的值，接着写入即可
    for (int i = 0; i < L1_LINE_NUM; ++i)
    {
        if (l1dcache[setIndex1][i].valid && l1dcache[setIndex1][i].tag == tag1)
        {
            l1dcache[setIndex1][i].dirty = true;
            return;
        }
    }
}

// you are not allowed to modify the declaration of this function
/*cacheAccess函数接受三个参数，参数的定义为：
 * 而且我们不考虑byte的个数，我们这个函数只是模拟访问内存的操作，不实际读写数据
 *@params op 为访问类型，是一个char类型的参数，具体取值和trace文件中的类型相同，为[I, S, L，M]其中的一个。
 *@params addr 为访问地址，它是trace文件中的地址的十进制表示的结果,64位16进制内存地址
 *@params len 为一次访问的长度，也就是字节数量
 *   思考过程：
 *   1.怎么处理地址？要根据不同缓存级别的组数用不同的方式来解读地址么？然后剩下的位都是tag标志
 *   2.I是指令加载的过程，和数据读取类似，但是一级缓存中只能从L1I中来读取指令数据
 *   3.M修改数据，就是一次Load加上一次Store Load：就是读取 Store：就是写入数据
 *   4.代码框架大概是怎样的？一个对应的指令实现一个功能？
 */
void cacheAccess(char op, uint64_t addr, uint32_t len)
{
    switch (op)
    {
    case 'I':
        instruct(addr);
        break;
    case 'M':
        load(addr);
        store(addr);
        break;
    case 'L':
        load(addr);
        break;
    case 'S':
        store(addr);
        break;
    default:
        break;
    }
}

CSAPP:CacheLab #

Cache-Line Organization #

Handling Writes #

Multi-Level Inclusion Policy #

Three-Level Cache Simulator #

Some Thoughts on Caches #

1. #

2. #

3. #

4. #

5. #

6. #

7. #

8. #

Compromise: VIPT (Virtual Index, Physical Tag) #

Advantages: #

Design constraints: #

9. #

10. #

11. #