How to calculate cache block size from its overhead?

Question

I've being looking for this for a lot of time now (over 3 days) without luck. Maybe one of you guys can tell me how can I solve it.

Consider you have a computer with a 16-bit size address and a byte addressable memory. The cache is 2-way set-associative mapped, write-back policy and a perfect LRU replacement strategy. Cache has an overhead of 4352 bits. What's the size of the block?

Very few resources talk about overhead and the ones I've found only relate it to total cache size. The problem is I only know how to calculate cache size with #blocks or at least with the fields of the address properly defined (which I have not being able to do for this problem since I can't calculate the size of the tag.).

Any help would be appreciated.

Answer 1

So, here's how I read this question:

Overhead bits are the bits that don't count toward the actual data that is being cached.  They are bits that track maintenance state of the cache, and help the cache implement hits, write back, and eviction policy.  To some way of looking at it, if one byte is being cached (8 bits) how many non-data bits are in the cache to help manage that (or at least for all the actual data bits how many non-data/overhead bits are there).

This is mathematical, so I hope I haven't made an error, but even if I have maybe you can see your way through the reasoning.

Let's derive some additional information:

A write-back policy means the cache needs to store "dirty" information for each data block: dirty is 1-bit: yes, dirty -or- no, clean.

For 2-way set associative cache, a "perfect" LRU algorithm is also 1 bit (yes: first block -or- no: second block) but this 1 bit costs per index position (i.e. per line) — not per block as there are two blocks per index.

What we don't know is if there is a valid bit, which would also be per data block, but most caches I see in coursework have the valid bits, so we might assume they have it.

And lastly, there's the tag bits where tag bits are: however many bits are leftover in the address space bits after accounting for index bits and block offset bits.

So, a formula for overhead might be:

overhead in bits = index positions * (1 x LRU bit + block overhead bits)

where block overhead bits = 2 [ways] * (1 x Dirty bit + 1 x Valid bit + tag bits)

We also know that tag bits = address space bits - index bits - block bits

So, we have:

• 4352 [overhead in bits] = index positions * (1 + 2 * (2 + tag bits))

  -and-

• tag bits = address space bits - index bits - block offset bits

  -and-

• index positions = 2^{index bits}

  -and-

• We also know that the number of tag, index, and block offset bits has to be an integer (no fractions of bits).

So, we can begin to reduce those two formulas by substituting:

4352 = index positions * (1 + 2 * (2 + address space bits - index bits - block bits)

by reduction also then:

4352 = 2^{index bits} * (1 + 2 * (2 + 16 - index bits - block bits)

Solving for block bits we have:

-((4352/2^{index bits} - 1)/2 - 18 + index bits) = block bits

I don't know how to solve this directly mathematically, given the constraint that the variables must be integers, so, instead of solving directly, simply try/search different values:

If index bits is 7 then by this formula, block bits is fractional, so that doesn't work.

If index bits is 9 then by this formula, block bits is fractional, so that doesn't work.

No other values between 0 and 16 result in an integer number of bits, except:

If index bits is 8 then by this formula, block bits is 2, so:

16 = tag bits + 8 + 2, meaning tag bits is 6, index bits is 8, and block offset is 2.

Since block offset is 2 then block size is 2².