如何修改缓存模拟器的 FIFO 实现中的读取函数

Question

我有一个缓存模拟器，它实现了缓存的FIFO方法，这里是我的结构变量供参考：

#include<stdlib.h>
#include<stdio.h>
#define DRAM_SIZE 1048576

typedef struct cb_struct {
    unsigned char data[16]; // One cache block is 16 bytes.
    u_int32_t tag;
    u_int32_t timeStamp;   /// This is used to determine what to evict. You can update the timestamp using cycles.
}cacheBlock;


typedef struct access {
    int readWrite; // 0 for read, 1 for write
    u_int32_t address;
    u_int32_t data; // If this is a read access, value here is 0
}cacheAccess;

// This is our dummy DRAM. You can initialize this in anyway you want to test.
unsigned char * DRAM; 

cacheBlock L1_cache[2][2]; // Our 2-way, 64 byte cache
cacheBlock L2_cache[4][4]; // Our 4-way, 256 byte cache

// Trace points to a series of cache accesses.
FILE *trace;

long cycles;

void init_DRAM();


// This function print the content of the cache in the following format for an N-way cache with M Sets
// Set 0   : CB1 | CB2 | CB 3 | ... | CB N
// Set 1   : CB1 | CB2 | CB 3 | ... | CB N
// ...
// Set M-1 : CB1 | CB2 | CB 3 | ... | CB N

这里是我实现的

read

函数，意思是用FIFO方法读取缓存：

//Here is the read function I'm talking about. 
u_int32_t read_fifo(u_int32_t address)
{
    u_int32_t setID = getL1SetID(address);
    u_int32_t tag = getL1Tag(address);
    int index = -1; 
    for (int i = 0; i < 6; i++) { 
        cacheBlock* cache;
        int cacheSize;
        if (i < 2) { 
            cache = L1_cache[setID];
            cacheSize = 2;
        } else {
            u_int32_t l2SetID = getL2SetID(address);
            cache = L2_cache[l2SetID];
            cacheSize = 4;
            tag = getL2Tag(address); 
        }
        for (int j = 0; j < cacheSize; j++) {
            if (cache[j].tag == tag) {
                index = j; 
                break; 
            }
        }
        if (index != -1) {
            break; 
        }
    }
    
    if (index != -1) { 
        return L1_cache[setID][index].data[address & 0xF];
    }
    
    u_int32_t l2SetID = getL2SetID(address);
    cacheBlock newBlock;
    newBlock.tag = tag;
    memcpy(newBlock.data, DRAM + (address & 0xFFFFFFF0), 16);
    cacheBlock temp = L2_cache[l2SetID][0];
    L2_cache[l2SetID][0] = newBlock;
    newBlock = temp;
    temp = L1_cache[setID][0];
    L1_cache[setID][0] = L2_cache[l2SetID][0];
    L2_cache[l2SetID][0] = temp;
    
    return L1_cache[setID][0].data[address & 0xF];

}


unsigned int getL1SetID(u_int32_t address)
{
    unsigned int setID = (address >> 4) & 1;
    return setID;
}

unsigned int getL1Tag(u_int32_t address)
{
    unsigned int tag = address >> 5;
    return tag;
}

unsigned int getL2SetID(u_int32_t address)
{
    unsigned int setID = ((address >> 4) & 3);
    return setID;
}

unsigned int getL2Tag(u_int32_t address)
{
    unsigned int output = (address >> 5) & ((1 << 26) - 1);
    return output;
}

int L1lookup(u_int32_t address)
{
    unsigned int setID = getL1SetID(address);
    unsigned int tag = getL1Tag(address);

    for(int i=0; i<2; i++)
    {
        if(L1_cache[setID][i].tag == getL1Tag(address)){
            return 1;
        }
    }

    return 0;
}

int L2lookup(u_int32_t address)
{
    unsigned int setID = getL2SetID(address);
    unsigned int tag = getL2Tag(address);

    for(int i=0; i<4; i++)
    {
        if(L2_cache[setID][i].tag == getL2Tag(address))
            return 1;
    }

    return 0;
}

我的问题是，有没有更好的方法来实现这个，鉴于此

 The cache has two levels
• A cache block is 16 bytes.
• Each address is accessing 1 bytes of data.
• The L1 cache is a 64 Bytes, 2-way set associative cache.
• The L2 cache is a 256 Bytes, 4-way set associative cache.
• The cache is inclusive, which mean that data in L1 cache will also remain in the L2 cache. In other words, the data in L1 is a subset of the data in L2 (This assumption simplify your design)

我是缓存的新手，我基于我对缓存的有限知识形成了这个，所以如果你的设计看起来很荒谬或不寻常，我的推理很清楚。任何清理代码的建议都会对我有很大帮助。请提供带有解释的代码，以帮助我和其他人理解您的回复，谢谢。

Answer 1

对于双向集关联缓存，1 位状态将告诉我们哪个条目是最近的（如果这是你正在做的，则首先是），因此也告诉我们哪个条目是最近的。这个单一的状态位属于整个缓存行集的级别，而不是两种方式中任何一种的一部分。

四路组相联缓存也是如此，但占用多于1位。我认为这需要 2 或 3 位（可以查找）并且有简单的算法可以在命中时推进方式指示器。

---

如果是我，我会将 L1 和 L2 缓存的搜索分开，因为在每个缓存中命中/未命中应该有不同的行为。

搜索L1；如果找到，返回数据。

搜索L2；如果找到，我们知道它在 L2 而不是 L1；因此，从 L1 中逐出该行的一种方式并从 L2 复制到 L1，现在它在 L1 中，因此按照在 L1 中找到的数据返回数据。

如果在任何一个中都没有找到，则执行 L2 缓存未命中：逐出 L2 中该行的一种方式并从内存中读取，然后按照在 L2 中找到的方式进行（从 L1 中逐出一种方式并从 L2 复制到 L1 并按照找到的方式返回在 L1).

---

就 FIFO 而言，这似乎是一个奇怪的选择。最近最少使用的更常见，几乎肯定更有效。

此外，你总是选择方式 0 来驱逐而不是使用你的时间戳——结果，其他方式将永远无法使用！

如果 L1 和 L2 都未命中，您将执行

u_int32_t l2SetID = getL2SetID(address);

两次。

---

这段代码真的有效吗？

// this code runs whether found in L1 or L2,
// but is written as if positively found in L1
if (index != -1) { 
    return L1_cache[setID][index].data[address & 0xF];
}

在我看来 return 语句应该使用

cache

变量，因为 L1 和 L2 搜索的合并，它可以在 L1 或 L2 中找到——但如果在 L2 中找到，则不会将数据从 L2 提升到L1 正如我们所期望的那样。

---

没有脏位，也没有有效位。