CODEWITHSUNDEEP
c++performancecachingmemory
ychen
ychen

Reputation: 229

Find hit/miss in cache c++

I'm struggling with my hw. It asks read a trace file, where each line has reference type, and address in hex. For example, 1st line in the file has address 0x4ef1200231, with type of instruction. It also asks to check if this address in cache is a hit or miss(in L1 and L2). I'm not quite sure how to write c++(i'm very new) to check if it is a hit or miss.

I'm picturing there is a function, say address(long int), then if I call address(0x4ef1200231) then the console can tell me if this address is a hit or miss at L1, and if it is a miss, then call another function to check this address at L2. Is this too naive? Please help. Thanks.

---few lines in the trace---
4ef1200231 Int
2ff1e0122234 WR
82039ef9a3 R

comment: Int means instruction, WR means data write, R means data read. Question is after reading the whole trace file, how many hits, and misses total. Thanks.

Upvotes: 1

Views: 3736

Answers (1)

Tony Delroy
Tony Delroy

Reputation: 106068

This question is probably too advanced for a C++ beginner, but here's some explanation of how to implement a solution....

First, you need to have a container that mimicks the logic used by each level of cache: the simplest (and likely adequate) such container is an Least Recently Used (LRU) data structure. What that does is record a fixed maximum number of in-cache elements, and when an element is accessed it searches for it in the list: if it's found it's moved to the top/front of the list, displacing the 1st and subsequent list elements until the gap it left behind is again filled. If it's not in the list, then it's also added at the top, with all other elements shifted down to make room, and the last element removed if the list is at its maximum size. To implement an LRU nicely, you need to be able to find elements quickly by value, while inserting and removing elements quickly mid-list. This is best done with a combination of an unordered_map and a list, but implementation of that alone is more than you can reasonably be expected to do as a C++ beginner. You could start by using only a list - the searching will be slow (O(n) or linear / brute force), but you can get it working functionally.

Given such an LRU class, you can set the sizes of two instances to represent pages in L1 and L2 cache, then for each address in the input file, you seek that page (say for 4k pages you could divide it by 4096, or bitwise-and it with the bitwise negation of 4095, or bitwise-or it with 4095, or bitshift it right 12 times etc.) in L1, falling back on L2 if necessary. The "is it already in the cache" code can keep hit/miss counters.

Here's some example code to get you started:

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_;
};

You can then do your simulation like this:

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...

Upvotes: 3

Related Questions