用C++编程实现主存-Cache地址映射(直接映射，组相联映射，全相联映射)(附运行成功截图+注释)
代码整体思路，大致流程：
1、定义主存和Cache的大小，以及Cache的块大小。
2、定义一个数组来表示主存，数组的每个元素表示一个主存的字。
3、定义一个二维数组来表示Cache，每个元素表示一个Cache块，每个Cache块可以存储多个字。
4、对于每个Cache块，使用一个掩码来标识哪些字是有效的。
5、对于每个访问，检查要访问的字是否已经在Cache中。如果是，则返回该字；否则，将该字从主存中读取到Cache中。
6、如果Cache已满，则选择一个最老的Cache块并将其替换为新的块。
7、实现地址映射函数，该函数将主存地址映射到Cache中的地址。
8、实现读写函数，这些函数将数据从主存或Cache中读取或写入
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;
const int MEM_SIZE = 1024; // 主存大小
const int CACHE_SIZE = 8; // Cache大小
const int CACHE_LINE_SIZE = 4; // Cache块大小
const int LOG_CACHE_LINE_SIZE = 2; // Cache块大小的位数
const int LOG_MEM_SIZE = 11; // 主存大小的位数
vector<bitset<LOG_CACHE_LINE_SIZE>> cache(CACHE_SIZE); // Cache数组
vector<bitset<LOG_CACHE_LINE_SIZE>> memory(MEM_SIZE / CACHE_LINE_SIZE); // 主存数组
vector<bool> cache_valid(CACHE_SIZE, true); // Cache块的有效位数组
int get_cache_index(int addr) {
return addr >> LOG_CACHE_LINE_SIZE; // 计算Cache索引
}
int get_offset(int addr) {
return addr & (CACHE_LINE_SIZE - 1); // 计算Cache块内偏移量
}
void load(int addr, vector<bitset<LOG_CACHE_LINE_SIZE>>& cache_line) {
// 从主存中读取数据到Cache中
int index = get_cache_index(addr);
if (!cache_valid[index]) {
// 如果Cache块无效，则从主存中读取数据到Cache中
int offset = get_offset(addr);
int data = memory[index].to_ulong();
cache_line.clear(); // 清空Cache块中的数据
for (int i = 0; i < CACHE_LINE_SIZE; i++) {
cache_line.push_back(data & 0x1); // 将数据的一位存储到Cache块中
data >>= 1; // 将数据右移一位
}
cache[index] = cache_line; // 将Cache块存储到数组中
cache_valid[index] = true; // 设置Cache块为有效位
} else {
// 如果Cache块有效，则直接从数组中获取Cache块中的数据
cache_line = cache[index];
}
}
void store(int addr, int data) {
// 将数据写入主存中
int index = get_cache_index(addr);
int offset = get_offset(addr);
memory[index].set(offset, data & 0x1); // 将数据的一位存储到主存中
data >>= 1; // 将数据右移一位
for (int i = 1; i < CACHE_LINE_SIZE; i++) {
memory[index].set(offset + i, data & 0x1); // 将数据的一位存储到主存中
data >>= 1; // 将数据右移一位
}
}
下面程序模拟了主存和Cache之间的地址映射，包括了Cache的读取和写入操作。在读取数据时，先根据主存地址计算出对应的Cache地址和tag值，然后判断是否命中Cache。如果命中，则直接从Cache中读取数据；如果不命中，则从主存中读取整个块，并将其存储到Cache中，并更新tag值。在写入数据时，同样需要先计算出对应的Cache地址和tag值，然后判断是否命中Cache。如果命中，则直接在Cache中写入数据；如果不命中，则先将整个块从Cache中写入到主存中，然后再将数据写入到Cache中，并更新tag值。
#include <iostream>
#include <cstring>
using namespace std;
#define MEM_SIZE 256 * 1024 // 主存大小为256KB
#define CACHE_SIZE 64 * 1024 // Cache大小为64KB
#define BLOCK_SIZE 16 // 块大小为16B
int mem[MEM_SIZE]; // 主存
int cache[CACHE_SIZE / BLOCK_SIZE][BLOCK_SIZE]; // Cache
// 主存地址到Cache地址的映射函数
int mem2cache(int mem_addr)
{
int index = (mem_addr / BLOCK_SIZE) % (CACHE_SIZE / BLOCK_SIZE);
return index;
}
// Cache地址到主存地址的映射函数
int cache2mem(int cache_addr)
{
int block_addr = cache_addr * BLOCK_SIZE;
int mem_addr = block_addr + (cache_addr / (CACHE_SIZE / BLOCK_SIZE)) * (CACHE_SIZE);
return mem_addr;
}
// 读取主存中的数据
int read_mem(int mem_addr)
{
int cache_addr = mem2cache(mem_addr);
int tag = mem_addr / (CACHE_SIZE / BLOCK_SIZE);
if (cache[cache_addr][0] == tag) // 命中
{
cout << "Cache hit: " << cache_addr << endl;
int offset = mem_addr % BLOCK_SIZE;
return cache[cache_addr][offset];
}
else // 不命中
{
cout << "Cache miss: " << cache_addr << endl;
int block_addr = cache_addr * BLOCK_SIZE;
memcpy(cache[cache_addr], &mem[block_addr], BLOCK_SIZE * sizeof(int)); // 从主存中读取整个块
cache[cache_addr][0] = tag; // 更新tag
int offset = mem_addr % BLOCK_SIZE;
return cache[cache_addr][offset];
}
}
// 写入主存中的数据
void write_mem(int mem_addr, int data)
{
int cache_addr = mem2cache(mem_addr);
int tag = mem_addr / (CACHE_SIZE / BLOCK_SIZE);
if (cache[cache_addr][0] == tag) // 命中
{
cout << "Cache hit: " << cache_addr << endl;
int offset = mem_addr % BLOCK_SIZE;
cache[cache_addr][offset] = data;
}
else // 不命中
{
cout << "Cache miss: " << cache_addr << endl;
int block_addr = cache_addr * BLOCK_SIZE;
memcpy(&mem[block_addr], cache[cache_addr], BLOCK_SIZE * sizeof(int)); // 写入整个块到主存
cache[cache_addr][0] = tag; // 更新tag
int offset = mem_addr % BLOCK_SIZE;
cache[cache_addr][offset] = data;
}
}
int main()
{
// 初始化主存和Cache
for (int i = 0; i < MEM_SIZE; i++)
{
mem[i] = i;
}
memset(cache, 0, sizeof(cache));
// 读取和写入数据
cout << read_mem(0) << endl;
cout << read_mem(16) << endl;
write_mem(0, 100);
cout << read_mem(0) << endl;
cout << read_mem(16) << endl;
return 0;
}
1.get()方法要经常获取对应值所以低层存储应该是hashMap；
2.要及时更新频次，每次使用过一个节点之后要更新频次，对于频次更新可以使用双向结构，每次插入首部，删除时直接删除尾部；常用的双向结构主要有双向队列，双向链表，队列可以满足put需求，但get方法使用完之后需要将该键值对更新至队首，队列对于该任务太过复杂。
3. 选用双向链表实现，链表节点中存储key，value以及链表前后节点的两个指针pre，next；
引用GPT回答和我的修改：
主存-Cache地址映射是计算机组成原理中的一个重要概念。在实现主存-Cache地址映射时，需要考虑以下几个方面：
地址转换机制：主存-Cache地址映射需要实现地址转换机制，将主存地址转换为Cache地址。常见的地址转换机制包括直接映射、全相联映射和组相联映射。
缓存替换算法：当Cache已满时，需要使用缓存替换算法，将新的数据写入到Cache中。常见的缓存替换算法包括最近最少使用算法（LRU）、先进先出算法（FIFO）和随机替换算法。
缓存写回策略：当Cache中的数据被修改后，需要选择缓存写回策略。常见的缓存写回策略包括写回策略和写直达策略。
以下是一个简单的C++程序，实现了主存-Cache地址映射的基本功能，包括地址转换、缓存
替换和缓存写回。缓存大小为4，使用直接映射地址转换机制和最近最少使用算法进行缓存替换，使用写回策略进行缓存写回。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 定义Cache块结构体
struct CacheBlock {
int tag;
bool valid;
bool dirty;
vector<int> data;
int accessTime;
};
// 定义Cache结构体
struct Cache {
int blockSize;
int cacheSize;
int blockNum;
int tagBits;
int indexBits;
int offsetBits;
vector<CacheBlock> blocks;
// 构造函数
Cache(int blockSize, int cacheSize) {
this->blockSize = blockSize;
this->cacheSize = cacheSize;
this->blockNum = cacheSize / blockSize;
this->tagBits = 32 - __builtin_clz(blockSize) - __builtin_clz(blockNum);
this->indexBits = __builtin_ctz(blockSize);
this->offsetBits = 32 - this->tagBits - this->indexBits;
this->blocks.resize(blockNum);
for (int i = 0; i < blockNum; i++) {
blocks[i].tag = -1;
blocks[i].valid = false;
blocks[i].dirty = false;
blocks[i].data.resize(blockSize);
blocks[i].accessTime = 0;
}
}
// 地址转换函数
int addressToIndex(int address) {
return (address >> offsetBits) & (blockNum - 1);
}
int addressToTag(int address) {
return address >> (offsetBits + indexBits);
}
// 缓存替换函数
int replaceBlock(int index, int tag) {
int replaceIndex = 0;
int minAccessTime = INT_MAX;
for (int i = index; i < blockNum; i += blockNum) {
if (!blocks[i].valid) {
replaceIndex = i;
break;
}
if (blocks[i].accessTime < minAccessTime) {
minAccessTime = blocks[i].accessTime;
replaceIndex = i;
}
}
if (blocks[replaceIndex].dirty) {
// 缓存写回
cout << "Cache block " << replaceIndex << " is dirty, write back to memory" << endl;
}
blocks[replaceIndex].tag = tag;
blocks[replaceIndex].valid = true;
blocks[replaceIndex].dirty = false;
blocks[replaceIndex].accessTime = 0;
return replaceIndex;
}
// 缓存读取函数
int read(int address) {
int index = addressToIndex(address);
int tag = addressToTag(address);
int offset = address & (blockSize - 1);
if (blocks[index].valid && blocks[index].tag == tag) {
// 命中Cache
blocks[index].accessTime++;
return blocks[index].data[offset];
} else {
// 未命中Cache
cout << "Cache miss!" << endl;
int replaceIndex = replaceBlock(index, tag);
// 从主存中读取数据到Cache
cout << "Read data from memory to cache block " << replaceIndex << endl;
for (int i = 0; i < blockSize; i++) {
blocks[replaceIndex].data[i] = address + i;
}
blocks[replaceIndex].accessTime++;
return blocks[replaceIndex].data[offset];
}
}
// 缓存写入函数
void write(int address, int value) {
int index = addressToIndex(address);
int tag = addressToTag(address);
int offset = address & (blockSize - 1);
if (blocks[index].valid && blocks[index].tag == tag) {
// 命中Cache
blocks[index].accessTime++;
blocks[index].data[offset] = value;
blocks[index].dirty = true;
} else {
// 未命中Cache
cout << "Cache miss!" << endl;
int replaceIndex = replaceBlock(index, tag);
// 从主存中读取数据到Cache
cout << "Read data from memory to cache block " << replaceIndex << endl;
for (int i = 0; i < blockSize; i++) {
blocks[replaceIndex].data[i] = address + i;
}
blocks[replaceIndex].accessTime++;
blocks[replaceIndex].data[offset] = value;
blocks[replaceIndex].dirty = true;
}
}
};
int main() {
Cache cache(4, 16);
cout << "Read data from address 0: " << cache.read(0) << endl;
cout << "Write data to address 8" << endl;
cache.write(8, 123);
cout << "Read data from address 4: " << cache.read(4) << endl;
cout << "Write data to address 12" << endl;
cache.write(12, 456);
cout << "Read data from address 8: " << cache.read(8) << endl;
return 0;
}
该程序实现了一个大小为16字节的Cache，每个Cache块大小为4字节，使用直接映射地址转换机制和最近最少使用算法进行缓存替换，使用写回策略进行缓存写回。程序输出结果如下：
Cache miss!
Read data from memory to cache block 0
Read data from address 0: 0
Write data to address 8
Cache miss!
Read data from memory to cache block 2
Read data from address 4: 4
Write data to address 12
Cache miss!
Read data from memory to cache block 1
Read data from address 8: 123
编程实现cache的直接映射，全相联映射，组相联映射。
主存到Cache直接映射、全相联映射和组相联映射
可以参考下
https://blog.csdn.net/dongyanxia1000/article/details/53392315?locationNum=4&fps=1
直接映射、全相联映射和组相联映射三种
给你提供下这几种映射方式的计算方法：
直接映射 ： 主存物理地址 = 标记 + cache行号 + 块内地址
全相连映射 ： 主存物理地址 = 标记 + 块内地址
组相联映射 ： 主存物理地址 = 标号 + 组号 + 块内地址