Search code examples
cachingcpu-architecturecpu-cache

Cache: Find the size of the tag in bits

So I have this problem:

One cache memory is organised in 4 lines of 32bytes. The main memory has the size of 64 KBytes. The RAM access time is 200ns and the CACHE access time is 20ns

and I struggle to find the way to solve this sub-question:

Find the size of the tag in bits.

The given answer by the instructor is 11 bits.

I can't understand how can I find the length of the address, and how to determine if the cache is set-associative or fully associative.

Solution

  • I can't understand how can I find the length of the address

    The following formulas relate the number of Values, V, with the number of bits (binary digits), N, that it takes to represent and differentiate between V number of values.

    V = 2N, and the reverse, which is N = log2 V

    In the above formulas, V is 64k and N is what you're looking for, the number of bits it takes to differentiate between 64k different values (here those values are addresses, but the formula works to relate any N and V).

    So, 1 bit can distinguish between 2 different values; 2 bits between 4 different values, 3 bits: 8 values, ...

    how to determine if the cache is set-associative or fully associative

    The cache is organized in 4 lines of 32 bytes — and they don't say any more, so we should assume it is direct mapped or 1-way set associative (those are the same thing).

    If it were fully associative, there wouldn't be any "lines", just 4 blocks all in the same set (as if only 1 line).  Still, it is a matter of terminology, so YMMV.

    If it were > 1-way set associative, I believe they would have said something to that effect.  An obscure way would have been to give the total cache size as a multiple of 4*32=128.  If the first multiple (e.g. 128), then 1-way set associative (i.e. direct mapped), and if 2nd multiple (e.g. 256) then 2-way set associative.