c++ - 在缓存 C++ 中查找命中/未命中

Question

我正在为我的硬件而苦苦挣扎。它要求读取一个跟踪文件，其中每一行都有引用类型和十六进制地址。例如，文件中的第一行地址为 0x4ef1200231，带有指令类型。它还要求检查缓存中的这个地址是否命中或未命中(在 L1 和 L2 中)。我不太确定如何编写 C++(我是新手)来检查它是否成功。

我想象有一个函数，比如 address(long int)，然后如果我调用 address(0x4ef1200231) 那么控制台可以告诉我这个地址在 L1 上是命中还是未命中，如果是未命中，然后调用另一个函数来检查 L2 中的这个地址。是不是太天真了？请帮忙。谢谢。

---跟踪中的几行---
4ef1200231 整数
2ff1e0122234 写入
82039ef9a3 R

注解:Int表示指令，WR表示写数据，R表示读数据。问题是在读取整个跟踪文件后，总共有多少次命中和未命中。谢谢。

Answer 1

这个问题对于 C++ 初学者来说可能太高级了，但是这里有一些关于如何实现解决方案的解释....

首先，您需要有一个容器来模仿每一级缓存所使用的逻辑:最简单(并且可能足够)的此类容器是最近最少使用 (LRU) 数据结构。它的作用是记录缓存中元素的固定最大数量，当访问元素时，它会在列表中搜索它:如果找到它，它就会移到列表的顶部/前面，取代第一个和后续列表元素直到它留下的空隙再次被填满。如果它不在列表中，那么它也被添加到顶部，所有其他元素向下移动以腾出空间，如果列表达到其最大大小，则最后一个元素被删除。要很好地实现 LRU，您需要能够按值快速查找元素，同时在列表中快速插入和删除元素。这最好结合 unordered_map 和 list 来完成，但作为 C++ 初学者，仅实现它就超出了您的合理预期。您可以从仅使用一个列表开始 - 搜索会很慢(O(n) 或线性/蛮力)，但您可以让它正常工作。

给定这样一个 LRU 类，您可以设置两个实例的大小来表示 L1 和 L2 缓存中的页面，然后对于输入文件中的每个地址，您寻找该页面(比如对于 4k 页面，您可以将其除以 4096 ，或按位-和它与 4095 的按位取反，或按位-或它与 4095，或将它右移 12 次等)在 L1 中，必要时回退到 L2。 “它是否已经在缓存中”代码可以保持命中/未命中计数器。

下面是一些帮助您入门的示例代码:

template <typename T>
class Dumb_LRU
{
    Dumb_LRU(size_t max_size) : n_(max_size) { }
    bool operator()(const T& t)
    {
        std::list<T>::iterator i = std::find(l_.begin(), l_.end(), t);
        if (i == l_.end())
        {
            l_.push_front(t);
            if (l_.size() > n_)
                l_.pop_back();
            return false;
        }
        if (i != l_.begin()) // not already the first element...
        {
            l_.erase(i);
            l_.push_front(t);
        }
        return true;
    }
  private:
    std::list<T> l_;
    size_t n_;
};

然后您可以像这样进行模拟:

static const size_t l1_cache_pages = 256;
static const size_t l2_cache_pages = 2048;
static const size_t page_size = 4096;

Dumb_LRU<size_t> l1(l1_cache_pages);
Dumb_LRU<size_t> l2(l2_cache_pages);

size_t address;
std::string doing_what;
int l1_hits = 0, l1_misses = 0, l2_hits = 0, l2_misses = 0;
while (std::cin >> address >> doing_what)
{
    if (l1(address / page_size))
        ++l1_hits;
    else
    {
        ++l1_misses;
        if (l2(address / page_size))
            ++l2_hits;
        else
            ++l2_misses;
}
// ...print out hits/misses...