Question

Consider a cache consisting of 128 blocks of 16 words each, for a total of 2048 (2K) words, and assume that the main memory is addressable by a 16-bit address. The main memory has 64K words, which we will view as 4K blocks of 16 words each. Calculate the tag size for Associate mapping, direct mapping and two-way set associative mapping. Write all the steps very clearly

Answer 1

Answer:

Tag size for:

Associate mapping-12 bit

Direct mapping-5 bit

Two-way set associative mapping-6 bit

Explanation:

1)Associate mapping:-

• This is more flexible mapping method, in which main memory block can be placed into any cache block position.

• In this, 12 tag bits are required to identify a memory block when it is resident in the cache.

• The tag bits of an address recevied from the processor are compared to the tag bits of each block of the cache to see, if the desired block is present. This is known as Associative Mapping technique.

2)Direct Mapping:-

• The simplest way to determine cache locations in which store Memory blocks is direct Mapping technique.

• In this block J of the main memory maps on to block J modulo 128 of the cache. Thus main memory blocks 0,128,256,….is loaded into cache is stored at block 0. Block 1,129,257,….are stored at block 1 and so on.

• Placement of a block in the cache is determined from memory address. Memory address is divided into 3 fields, the lower 4-bits selects one of the 16 words in a block.

• When new block enters the cache, the 7-bit cache block field determines the cache positions in which this block must be stored.

• The higher order 5-bits of the memory address of the block are stored in 5 tag bits associated with its location in cache. They identify which of the 32 blocks that are mapped into this cache position are currently resident in the cache.

3)Set associative mapping:-

• 1) It is the combination of direct and associative mapping technique.

• 2) Cache blocks are grouped into sets and mapping allow block of main memory reside into any block of a specific set. Hence contention problem of direct mapping is eased , at the same time , hardware cost is reduced by decreasing the size of associative search.

• 3) For a cache with two blocks per set. In this case, memory block 0, 64, 128,…..,4032 map into cache set 0 and they can occupy any two block within this set.

• 4) Having 64 sets means that the 6 bit set field of the address determines which set of the cache might contain the desired block. The tag bits of address must be associatively compared to the tags of the two blocks of the set to check if desired block is present.

#SPJ2