CODEWITHSUNDEEP
cachingcpu-architecturecpu-cache
Chris Wang
Chris Wang

Reputation: 19

With the given information about a direct-mapped cache (including a trace and hit/miss status), how do I find the number of tag bits and offset bits?

I am doing I problem set on direct mapped cache, I need help with finding the number of offset bits and tag bits. I don't know how to calculate the number of tags and offset bits. The solution key says that the the tag bits is 5 and offset bits is 3 without showing any work. The following is the problem:

Problem 4: Cache

For all the questions in this problem, assume that we are using a 12-bit machine with a byte-addressable memory and a direct-mapped cache. The cache can hold up to 16 cache lines.

Part a) How many bits do you need for the set index?

A: I know this part which is just log(# of cachelines)=log(16)=4

Part b) The following sequence of 9 memory accesses generates the hits/misses shown. Some miss/hit entries are intentionally left blank. The cache is initially empty. Note that the addresses are written in binary with spaces added between each 4 bits for readability. These are not necessarily the tag/index/offset boundaries.

# Address        Hit/Miss
1 1101 1111 0000 Miss
2 0000 1101 1111 Miss
3 1101 0111 0101 Miss
4 0000 1101 1100 Hit
5 1101 1111 0011 Miss
6 1111 0111 0010 Miss
7 1101 1111 0000 Miss
8 0000 1101 1101 Hit
9 1111 0111 0100 Miss

What is the number of tag bits? A:

What is the number of offset bits? A:

Upvotes: 1

Views: 41

Answers (1)

Peter Cordes
Peter Cordes

Reputation: 365507

They give you a trace and hit/miss status, and the fact the cache was initially cold. So the first hit must have the same index and tag as one of the three previous misses.

Some of the offset bits might also be the same; we can't be sure from that, but we can look at the other hits to find the highest bit-position where the addresses differ while still hitting in cache. That's a lower bound on the offset width. Here there are two hits, each with the same leading 10 bits as access #2, so definitely the same index+tag. The offset is at least the low 2 bits, but probably more.

We can also look for the lowest bit-position where addresses are the same but it's a miss. That's an upper bound on offset bits. But we need to be careful that it's not a conflict miss, that another access with the same index didn't evict the line we're looking at.

So when you come up with a candidate for the offset, go through the trace and check for matching index, and matching index+tag, to check that this candidate explains all the hits and misses. Probably the best way is to annotate each with a set number so you can look separately at accesses that index different sets (cache lines), for that candidate index position.

Some traces could be ambiguous (e.g. if they have a lot of similar address bits), but hopefully an exam or homework assignment will have a unique solution if they're asking for it.

This seems like a lot of work, but I don't see a simpler way for this problem.

In real life, if you had an unknown machine and were trying to determine its cache geometry, you'd write a program that accessed in simple patterns to start with, like repeatedly loading the same line alternating with loads at increasing power-of-2 distances away, to find when you create a conflict-miss. Rather than trying to infer it from a random trace of addresses without easy-to-see patterns.

Upvotes: 2

Related Questions