One of the problems asked during the Winter Hackathon revolved around figuring out the number of bits needed for the Tag field for a given configuration of a 2-way set associative cache and the main memory. This blog will try to teach you a method to working around such problems and other similar variations.

Problem Statement:

Calculate the number of bits in the tag for a 2-way set associative cache with the following parameters:
- Cache Size: 16 KB
- Block Size: 256 B
- Main Memory Size: 128 KB

Solution:

The first thing to solve would be to get the total number of bits in the address space. In most of the problems this could be either given straight away (the address space is 32-bits wide) or you would have to calculate it using the information given in the problem. In this problem, the main memory size would give us the number of bits in the address vector. The problem specifies that the main memory is 128KB - this means we need the address vector to be wide enough to access the entire 128KB region of memory.

For a byte addressable memory this would be the number of bits needed to access the entire memory i.e. from address 0x0 to 0x1FFFF. The following equation can be used to get that number:

Number of bits = log2(128K)
=> log2(128 * 1024)
=> log2(128) + log2(1024)
=> 7 + 10 = 17 bits

Once we have this information we know that the following would always be true:

Bits in (Tag + Index + offset) = Number of bits in address space

In order to know the number of bits in Tag field, we would need to figure out the number of bits in Index and Offset fields. Then the above equation can be used to get the number of bits in the Tag field.

Before we get into calculating the number of bits in these fields, here's a quick refresher on how a n-way set associative cache is organised:

Set Associative Cache

The above cache organisation shows that the index bits are used to select the row in the cache. The offset would then be used to get the cache block. This means we definitely need those number of bits to access information from the cache and the remaining bits from the total address space can be used to store the tag information. Hence the address space is divided in the following manner:

Address Bits

Calculating the number of bits for the offset

The offset fields can be calculated using the information about the block size. A cache block is the basic unit of storage for the cache. For these set of problems the offset should be able to index every byte from within the cache block. In this case we know that the block size is 256B hence the number of bits needed for the offset would simply be

offset bits = log2(256)
offset bits = 8

Calculating the number of bits for the cache index

Calculation for the number of index bits is slightly more involved than the calculation for the offset field. The reason being that the calculation needs to take the number of sets, block size and the cache size into account. The index bits are needed to select the cache row but before that we need to figure out the number of rows for a given cache configuration.  
The number of rows would be equal to the cache size divided by the block size for a direct mapped cache (there's just one way). For a n-way set associative cache, the number of rows would be cache size divided by the number of ways and the block size, i.e.

Number of rows =          Cache Size
                 ---------------------------
                 Block Size x Number of Ways

For the given problem, the cache is 2-way set associative with 16KB of space. The block size is 256B. The number of rows in the cache would then be:

Number of rows =   16KB
                ----------
                 256B x 2

Number of rows = 32

Once the number of rows are known, the number of index bits would simply be the log base 2 of the number of rows:

Index bits = log2(32)
Index bits = 5

That's it. We can now work the number of Tag bits using the following relationship:

Tag + Index + Offset = Address bits
Tag + 5 + 8 = 17
Tag = 4

Most of the variations of the problem would provide this information in one way or the other. Remember to always find the address space, offset and index to get the Tag information. Try to workout the following variant of the problem and submit your answer in the comment section.

Calculate the number of bits in the tag for a direct mapped cache for a 32-bit RISC-V CPU with the following parameters:
- Cache Size: 16 KB
- Block Size: 256 B