logo
ZhangKeyaoo
banner
NEWS LETTER

4-cache

Scroll down

cache

一、通用映射策略

1.fetch

  1. 由已有函数计算块号
  2. 用map函数查看是否命中
  3. 如果命中则返回行号rowNO
  4. 未命中则将数据从内存读到cache,再返回更新的rowNO：
    1. 用Memory读出数据data[]
      • 注意read()读的是二进制字符串
      • 模拟从0开始，因此读的起始位置是块号乘一行（一个块）的大小，转成二进制
      • 读出的数据大小也是块的大小（块大小=行大小）
      1
      2
      String beginAddr = Transformer.intToBinary(String.valueOf(blockNO*LINE_SIZE_B));
      byte[] data=Memory.getMemory().read(beginAddr,LINE_SIZE_B);
    2. 计算tag（该组内分配给这个块的次序）
    • 注意tag为26位的二进制！！
    • blockNO/SETS,块号/组数
    1
    2
    3
    4
    private char[] calculateTag(int blockNO){
        int tag=blockNO/SETS;
        return Transformer.intToBinary("" + tag).substring(6, 32).toCharArray();
    }
    1. 根据映射策略
      1. 为直接映射：行数=组数：(CACHE_SIZE_B / LINE_SIZE_B)==SETS
        • 调用cache的update函数
        • 行号=块号%行数（组数）
        • return rowNO
      2. 为组关联映射，调用替换策略的replace函数
        • 组号=块号mod组数。int groupNO=blockNO%SETS;
        • 起始行=组号每组行数.``int start= groupNOsetSize;``
        • 结束行*（闭区间）*.int end = (groupNO+1)*setSize-1;
        • return this.replacementStrategy.replace(start,end,tag,data);

2. map

  • 参量：块号blockNO
  1. 计算组号:blockNO%SETS
  2. 计算tag: char[] tag=calculateTag(blockNO);
  3. 在组范围内查找是否命中：三个条件：非空，有效，tag相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int map(int blockNO) {
    // TODO
    int groupNO = blockNO % SETS;           // 获得内存地址blockNO所对应的组号setNO
    char[] addrTag = calculateTag(blockNO);   // 获得内存地址blockNO所对应的tag
    //在组范围内查找是否命中
    int start = groupNO * setSize;
    int end = (groupNO + 1) * setSize - 1;
    //非空+有效+tag相同
    for (int i = start; i <= end; i++) {
        if (cacheInstance.isMatch(i, addrTag)) {   // 命中该行
            replacementStrategy.hit(i);
            return i; // 返回该行
        }
    }
    return -1;
}
  1. 命中后，调用替换策略hit函数，返回行号
  • replacementStrategy.hit(i);
  1. 否则，返回-1
1
2
3
4
5
6
7
8
9
public boolean isMatch(int rowNO, char[] tag) {
    if (this.cache[rowNO] == null) {//空,false
        return false;
    }
    if (!this.cache[rowNO].validBit) {//不有效,false
        return false;
    }
    return Arrays.equals(this.cache[rowNO].tag, tag);
}

3.update

  • 用于更新cache
  1. 更新当前cache行有效位true，visit初始化为1，时间戳设置成当前时间，更新tag和data
1
2
3
4
5
6
7
8
public void update(int rowNO, char[] tag, byte[] input) {
    // TODO
    cache[rowNO].validBit=true;
    cache[rowNO].visited = 1;
    cache[rowNO].timeStamp = System.currentTimeMillis();
    cache[rowNO].tag=tag;
    cache[rowNO].data=input;
}

二、替换策略的实现

  • 对于FIFO策略，你应该需要用到CacheLine中的timeStamp字段，记录每一行进入Cache的时间。
  • 对于LFU策略，你应该需要用到CacheLine中的visited字段，记录每一行被使用的次数。
  • 对于LRU策略，你应该需要用到CacheLine中的timeStamp字段，记录每一行最后被访问时间。
  • 替换后先判断是否要写回，再更新cache，再返回行号

1.先入先出FIFO

  • 不用写hit。
  • replace替换最小时间戳timeStamp
  1. 初始化
    • 把最早时间戳设为long的最大值：long oldestTimestamp = Long.MAX_VALUE;
    • 把最早行号设为-1： int oldestRow = -1;
  2. 找最早时间和对应行号
1
2
3
4
5
6
7
for (int i = start; i <= end; i++) {
    long timestamp = Cache.getCache().getTimeStamp(i);// 获取时间戳
    if (timestamp < oldestTimestamp) {// 如果[时间戳]<[最早时间戳]
        oldestTimestamp = timestamp;// 更新[最早时间戳]
            oldestRow = i;// 更新[最早行号]
    }
}
  1. 在Cache中添加getTimeStamp()
    • 注意，必须是有效行的时间戳才有意义！
1
2
3
4
5
6
7
public long getTimeStamp(int rowNO){
    CacheLine cacheLine = cache[rowNO];
    if (cacheLine.validBit) {//必须有效
        return cacheLine.timeStamp;
    }
    return -1;
}
  1. 判断是否要写回——脏位是否为true+是否有效valid
    • getDirty方法
    • calculatePAddr方法
    • Memory的write方法
  • calculatePAddr
    1. 标签（Tag）：用于唯一标识一个数据块。
    2. 组号（Set Index）：用于确定数据块在缓存中的哪一组。
      • 转换为二进制字符串，并截取其最后 offset 位：因为offset=组号位数
    3. 块内偏移（Block Offset）：用于确定数据在缓存行中的具体位置。
      • SETS（组数）的二进制位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 由行号获取内存实际地址
// 内存实际地址=tag位+组号+block offset块内偏移
public String calculatePAddr(int rowNO) {
    //计算偏移量 (offset)： （计算 SETS 的二进制位数）
    int offset = 0;
    for (int i = 1; i < SETS; i *= 2) {
        offset++;
    }
    //计算组号 (setNo)：
    //将组号转换为二进制字符串，并截取其最后 offset 位。
    String setNo = Transformer.intToBinary("" + rowNO / setSize).substring(32 - offset, 32);
    //获取标签 (tag)：
    char[] tag = cache[rowNO].tag;
    return new String(tag).substring(offset, tag.length) + setNo + "000000";
}
  1. 更新cache
    • Cache.getCache().update(oldestRow, addrTag, input);
    • Cache.getCache().setTimeStamp(oldestRow);
    • 现在时间戳：System.currentTimeMillis()
1
2
3
public void setTimeStamp(int rowNO) {
    cache[rowNO].timeStamp = System.currentTimeMillis();
}
  1. 返回行号

2. 最近不经常使用LFU

  • hit中将visit+1。replace替换最少使用次数
    1.hit: Cache.getCache().addVisited(rowNO);
1
2
3
4
 // LFU算法增加访问次数
public void addVisited(int rowNO){
    cache[rowNO].visited++;
}
  1. replace：
    1. 遍历找最小访问次数行
    2. 检查写回
    3. update
    4. 返回行数
  • 获取访问次数,也必须是有效的！！
1
2
3
4
5
6
public int getVisited(int rowNO){
    if(cache[rowNO].validBit){
        return cache[rowNO].visited;
    }
    return 0;
}

3. 最近最少用算法 LRU

  • hit更新时间戳。replace替换最小时间戳
  1. hit:每次被访问，都更新时间戳
    • Cache.getCache().setTimeStamp(rowNO);
  2. replace:
    1. 遍历找该组中最小时间戳
    2. 检查写回
    3. update
    4. 返回行数

三、写策略的实现

  • 涉及到cache往主存写数据的只有两个地方：
    • write函数直接向cache写数据时
    • replace函数需要替换掉一行数据时
  • 在write函数和replace函数的相应地方对isWriteBack字段判断，然后根据具体策略来做不同的事情
  • 写直达策略就是在write函数完成写cache后直接修改主存；
  • 写回策略就是在write函数完成写cache后设置好脏位，并在replace函数将要替换掉该行的时候将该行写回内存
  • 在Cache类中编写一个根据行号计算物理地址的方法

1. 写直达策略

  • isWriteBack为false。
  • 在write里如果为写直达，直接修改主存,参数为当前rowNO对应的pAddr，行大小，上面所得的cache_data

2.写回策略

  • isWriteBack为true。
  • 在write里如果为写回，设置好dirty位
  • 在三个替换策略里，如果
    1. 为写回,
    2. 如果替换行脏位为true
    3. 如果替换行有效
    • 则写入内存。参数：替换行所对应的pAddr，行大小，替换行的data
    • （在update之前完成）
1
2
3
4
5
6
//write
if (isWriteBack) {//写回，设置好dirty位
    cache[rowNO].dirty = true;
} else {//写直达，直接修改主存
    Memory.getMemory().write(calculatePAddr(rowNO), Cache.LINE_SIZE_B, cache_data);
}
1
2
3
4
5
6
7
//替换策略中
if (Cache.isWriteBack) {
    if (Cache.getCache().getDirty(minIndex) && Cache.getCache().isValid(minIndex)) {
        String addr = Cache.getCache().calculatePAddr(minIndex);
        Memory.getMemory().write(addr, Cache.LINE_SIZE_B, Cache.getCache().getData(minIndex));
    }
}

3. 一个根据行号计算物理地址的方法

  1. 标签（Tag）：用于唯一标识一个数据块。
  2. 组号（Set Index）：用于确定数据块在缓存中的哪一组。
    • setNo = 行号/每组行数
    • 转换为二进制字符串，并截取其最后 offset 位：因为offset=组号位数
  3. 块内偏移（Block Offset）：用于确定数据在缓存行中的具体位置。
    • 等于SETS（组数）的二进制位数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 由行号获取内存实际地址
// 内存实际地址=tag位+组号+block offset块内偏移
public String calculatePAddr(int rowNO) {
    //计算偏移量 (offset)： （计算 SETS 的二进制位数）
    int offset = 0;
    for (int i = 1; i < SETS; i *= 2) {
        offset++;
    }
    //计算组号 (setNo)：
    //将组号转换为二进制字符串，并截取其最后 offset 位。
    String setNo = Transformer.intToBinary("" + rowNO / setSize).substring(32 - offset, 32);
    //获取标签 (tag)：
    char[] tag = cache[rowNO].tag;
    return new String(tag).substring(offset, tag.length) + setNo + "000000";
}

注意

1. 获取时间戳/访问次数

  • 先判断有不有效！无效返回-1，否则返回时间戳/次数

2.时间戳更新：System.currentTimeMillis();

If you like my blog, you can approve me by scanning the QR code below.

Other Articles
cover
计算机组织与结构
5-磁盘
  • 25/02/22
  • 15:45
  • 2.7k
  • 11
cover
计算机组织与结构
3-浮点数加减乘除
  • 25/02/22
  • 15:43
  • 5.5k
  • 24
你走过的弯路，都是通向正轨的必经之路。
Article table of contents TOP
  1. 1. cache
    1. 1.1. 一、通用映射策略
      1. 1.1.1. 1.fetch
      2. 1.1.2. 2. map
      3. 1.1.3. 3.update
    2. 1.2. 二、替换策略的实现
      1. 1.2.1. 1.先入先出FIFO
      2. 1.2.2. 2. 最近不经常使用LFU
      3. 1.2.3. 3. 最近最少用算法 LRU
    3. 1.3. 三、写策略的实现
      1. 1.3.1. 1. 写直达策略
      2. 1.3.2. 2.写回策略
      3. 1.3.3. 3. 一个根据行号计算物理地址的方法
    4. 1.4. 注意
      1. 1.4.1. 1. 获取时间戳/访问次数
      2. 1.4.2. 2.时间戳更新：System.currentTimeMillis();
Please enter keywords to search
  • to close