directed-map cache简单示例

在这里插入图片描述
这张图的地址映射是基于直接映射缓存的策略进行的，以下是详细解释：

直接映射缓存的映射方式

缓存块号 (Cache Block Number):
- 使用公式 Cache块号 = 主存块号 % 缓存块总数 来决定主存地址在哪个缓存块中存储。
- 比如，这里 Cache块总数 = 4，所以 Cache块号 = 主存块号 % 4。
主存块号 (Memory Block Number):
- 主存地址通过 主存块号 = 地址 / 缓存行大小 转换为主存块号。
映射规则:
- 主存地址经过计算后映射到特定的缓存块。

逐步分析表中地址映射过程

假设：

缓存块总数 = 4。
主存地址直接映射到缓存块 (mod 4)。

1. Address 0

计算缓存块号：0 % 4 = 0。
结果：Address 0 被映射到缓存块 0。
命中状态：缓存块 0 初始为空，发生 miss。
更新缓存：缓存块 0 被填入 Memory[0]。

2. Address 8

计算缓存块号：8 % 4 = 0。
结果：Address 8 也映射到缓存块 0。
命中状态：缓存块 0 的内容为 Memory[0]，标签不匹配，发生 miss。
更新缓存：缓存块 0 被替换为 Memory[8]。

3. Address 0

计算缓存块号：0 % 4 = 0。
结果：Address 0 映射到缓存块 0。
命中状态：缓存块 0 的内容为 Memory[8]，标签不匹配，发生 miss。
更新缓存：缓存块 0 被替换为 Memory[0]。

4. Address 6

计算缓存块号：6 % 4 = 2。
结果：Address 6 映射到缓存块 2。
命中状态：缓存块 2 初始为空，发生 miss。
更新缓存：缓存块 2 被填入 Memory[6]。

5. Address 8

计算缓存块号：8 % 4 = 0。
结果：Address 8 映射到缓存块 0。
命中状态：缓存块 0 的内容为 Memory[0]，标签不匹配，发生 miss。
更新缓存：缓存块 0 被替换为 Memory[8]。

总结

缓存块号的计算方式：主存块号 % 缓存块总数。
冲突缺失：
- Address 0 和 Address 8 多次映射到同一个缓存块（块 0），导致频繁替换。
命中和缺失统计：
- 共发生 5 次缺失 (miss)，每次缺失都需要从主存加载数据。

映射规则的局限性

直接映射缓存由于其固定的映射规则，容易发生冲突缺失。在多次访问不同地址但映射到相同缓存块的情况下，会导致频繁替换，从而降低性能。

为什么mod 4

对地址进行 mod 4 的操作是为了确定地址应该映射到哪一个缓存块。使用二进制可以更直观地理解这个过程。以下是详细的二进制解释：

背景

缓存块数：4（对应二进制为 00, 01, 10, 11 共 2 位）。
mod 4 的含义：将地址的低两位用作缓存块号，因为 2^2 = 4，低两位足以区分 4 个缓存块。

二进制视角

假设地址是 32 位的虚拟地址或物理地址（简化为 8 位进行说明），地址可以分为以下几个部分：

| 高位部分（Tag） | 缓存块号部分（Index） | 缓存行内偏移量（Offset） |

高位部分（Tag）：表示标签，用于判断是否是同一个主存块。
缓存块号（Index）：低两位（因为是 4 个块，对应 2^2）。
偏移量（Offset）：更低的位，用于访问缓存行内的具体字节（假设缓存行大小为 4 字节，则需要 2 位偏移量）。

示例

缓存结构假设

缓存块数：4（需要 2 位 Index）。
缓存行大小：4 字节（需要 2 位 Offset）。
总地址大小：8 位（用于演示）。

地址 (二进制)	标签 (Tag)	Index	Offset
`0000 0000` (0)	`0000`	`00`	`00`
`0000 1000` (8)	`0000`	`00`	`00`
`0000 0110` (6)	`0000`	`10`	`00`

映射过程

地址的 Index 部分 决定了缓存块号。
对于地址 0 (0000 0000)，Index 是 00，映射到缓存块 0。
对于地址 8 (0000 1000)，Index 是 00，同样映射到缓存块 0。
对于地址 6 (0000 0110)，Index 是 10，映射到缓存块 2。

这就解释了为什么地址 0 和 8 会冲突，因为它们的 Index 都是 00，但它们的 Tag 不同（区分主存块的标签）。

为什么使用 `mod 4`

本质上是取低位索引值：
- mod 4 操作相当于取地址的低两位（二进制位数由缓存块数决定：log2(4) = 2）。
- mod 8 会取低 3 位（如果缓存块数是 8）。
- 这是通过位运算快速确定地址对应缓存块号的方式。

低位如何影响映射

假设我们有如下地址：

地址 0 (0000 0000) → 00 (mod 4 = 0)
地址 8 (0000 1000) → 00 (mod 4 = 0)
地址 6 (0000 0110) → 10 (mod 4 = 2)

低位的 Index 决定了映射的块号（而不是高位 Tag）。

总结

mod 4 就是用地址的低 2 位（二进制）来确定缓存块号。
使用二进制可以清楚地看到 Index 的作用，即如何根据低位分配缓存块。
二进制的这种取位操作（Index 部分）通过硬件实现起来非常高效，避免了复杂的数学运算。

代码实现

要实现以上过程，我们可以使用一个简单的直接映射缓存模拟器。此缓存模拟器将使用主存地址的某些位来确定缓存块号，并存储数据到缓存中。以下是如何用C语言代码实现这个缓存访问模拟过程。

实现思路

定义缓存块：每个缓存块包含一个有效位、数据和标签。
计算缓存块号：通过(地址 % 4)来确定地址在哪个缓存块。
检查命中或缺失：检查对应块中标签是否匹配，并判断有效位，如果匹配则是命中，否则是缺失。
更新缓存块：在缺失的情况下，将数据加载到缓存块并更新标签和有效位。

代码说明

结构定义：CacheBlock结构体包含有效位valid、标签tag和数据data。
initializeCache：初始化缓存，将所有有效位设置为false，标签设为-1。
accessCache：模拟访问缓存：
- 计算块号：address % CACHE_SIZE
- 计算标签：address / CACHE_SIZE
- 检查缓存块是否有效并且标签是否匹配，若匹配则命中，否则缺失并更新缓存块。
main：模拟一组地址的访问并统计缺失次数。

输出示例

根据示例地址序列的执行结果，输出可能如下：

Address 0: Miss
Address 8: Miss
Address 0: Miss
Address 6: Miss
Address 8: Miss
Total misses: 5

解释

此代码模拟了一个直接映射缓存，其中每次检查地址的有效性和标签是否匹配，若不匹配则视为缓存缺失并更新缓存块的内容。
为了使用一个内存数组memory[]来模拟内存数据存储，我们可以修改代码，将访问的地址值映射到memory[]中，从而在每次缓存缺失时从memory[]中加载数据到缓存。

修改后的代码示例

我们假设memory[]是一个较大的数组，用于模拟主存储器的内容。每次访问缓存时，如果发生缓存缺失，就从memory[]中加载数据到缓存。

#include <stdio.h>
#include <stdbool.h>#define CACHE_SIZE 4      // 缓存块的数量
#define MEMORY_SIZE 16    // 模拟内存大小（可以调整）// 定义缓存块结构
typedef struct {bool valid;    // 有效位int tag;       // 标签int data;      // 存储的数据
} CacheBlock;// 初始化缓存
void initializeCache(CacheBlock cache[]) {for (int i = 0; i < CACHE_SIZE; i++) {cache[i].valid = false;cache[i].tag = -1;cache[i].data = 0;}
}// 初始化内存
void initializeMemory(int memory[]) {for (int i = 0; i < MEMORY_SIZE; i++) {memory[i] = i * 10;  // 示例数据，可以是任意值}
}// 检查缓存是否命中，若缺失则从 memory[] 加载数据
bool accessCache(CacheBlock cache[], int memory[], int address) {int blockNumber = address % CACHE_SIZE;  // 计算缓存块号int tag = address / CACHE_SIZE;          // 计算标签if (cache[blockNumber].valid && cache[blockNumber].tag == tag) {printf("Address %d: Hit (Data: %d)\n", address, cache[blockNumber].data);return true; // 命中} else {printf("Address %d: Miss, loading from memory...\n", address);// 缺失，从 memory 加载数据到缓存块cache[blockNumber].valid = true;cache[blockNumber].tag = tag;cache[blockNumber].data = memory[address];return false; // 缺失}
}int main() {CacheBlock cache[CACHE_SIZE];int memory[MEMORY_SIZE];initializeCache(cache);initializeMemory(memory);// 模拟一组地址访问int addresses[] = {0, 8, 0, 6, 8};int misses = 0;for (int i = 0; i < 5; i++) {if (!accessCache(cache, memory, addresses[i])) {misses++;}}printf("Total misses: %d\n", misses);return 0;
}

代码说明

initializeMemory: 将memory[]数组初始化为示例数据，例如memory[i] = i * 10。
accessCache: 模拟缓存访问：
- 使用address % CACHE_SIZE计算缓存块号。
- 使用address / CACHE_SIZE计算标签。
- 如果缓存块有效且标签匹配，则为命中，否则为缺失。
- 如果缺失，从memory[address]加载数据到缓存块。