Consider a cache consisting of 256 blocks of 16 words each for a total of 4096 words and assume that the main memory is addressable by a 16 bits address and it consists of 4K blocks. How many bits are there in each of TAG, SET, WORD field for 2-way set associative technique?

The cache has 256 blocks of 16 words each, so it holds $256 \times 16 = 4096$ words. Main memory is addressed by 16 bits, so it has $2^{16} = 65536$ words. With 16 words per block, main memory has $65536/16 = 4096$ blocks, which matches the 4K blocks given.

In set-associative mapping, the cache blocks are grouped into sets. A memory block maps to one set, and it can sit in any block of that set. The address is divided into tag, set and word fields.

Word field

A block has 16 words, so the word field must select one of 16 words:

$$\text{word} = \log_2 16 = 4 \text{ bits}$$

Set field

The cache is 2-way, so each set has 2 blocks. The number of sets is

$$\text{sets} = \frac{256}{2} = 128$$

so the set field has

$$\log_2 128 = 7 \text{ bits}$$

Tag field

The tag is what remains of the 16-bit address:

$$\text{tag} = 16 - 7 - 4 = 5 \text{ bits}$$

The address format is

Therefore the fields are TAG = 5 bits, SET = 7 bits and WORD = 4 bits.

Check

The tag and set bits together give the block number of main memory: $5 + 7 = 12$ bits, and $2^{12} = 4096$ blocks, which agrees with the given size. Each set receives $4096/128 = 32$ memory blocks, and the 5-bit tag tells which of those 32 blocks sits in a cache block. The set has only 2 places, so at most 2 of those 32 blocks can be present at one time.

Working

When the CPU gives an address, the set field picks one set. The tags of both blocks of that set are compared with the tag of the address at the same time. If one of them matches and its valid bit is 1, it is a hit, and the word field selects the word. If neither matches, it is a miss. The block is fetched from main memory into the set, replacing one of the two blocks by the LRU or FIFO rule.

Comparison with other mappings

For the same cache, direct mapping would use 256 lines, giving tag $= 16 - 8 - 4 = 4$ bits, line 8 bits and word 4 bits. Fully associative mapping would use a tag of $16 - 4 = 12$ bits and no set field. The 2-way scheme lies between the two. Going from direct to 2-way, the tag grows by one bit and the set field shrinks by one bit, because the number of sets halves.

A short example shows the use of the fields. Take a memory block whose 12-bit block number has tag 10110 and set field 0000101 (which is 5). This block can go only to set 5 of the cache, in either of its two blocks. Any block with the same last 7 bits, such as one with tag $00001$, also competes for set 5. The two together can stay in the cache, which would be impossible in direct mapping.

The 2-way scheme needs only two comparators, and it still removes many conflicts.