Question

Draw the memory address blocks (Tag, Index and Offset) for a direct mapped and N-way set associative cache organization for the below cache configurations. Round the cache size to nearest power of 2 (e.g., 1KB = 2^10) and assume 32-bit memory address.
a. 64KB cache, 32-byte block, N = 4
b. 1MB cache, 64-byte block, N=16
c. 32KB cache, 512-byte block, N=64

Answer 1

Tag, Index and offset for a direct mapped and N-way set associative cache.

Memory is 32- bit.

(a) 64 KB cache, 32-byte block,N=4

Direct mapped cache:

Each block size of the cache is 32-byte, to represent these 32 bytes we need 5 bits (because 2⁵ = 32).

Therefore offset = 5 bits.

Total size of the cache is 64 Kb, then total number of blocks in the cache is = 64 Kb / 32 byte = (64 * 1024) byte / 32 bytes = 2 * 1024 blocks = 2 * 2¹⁰ blocks = 2¹¹ blocks.

Therefore to represent these 2¹¹ blocks we need 11 bits. Index = 11 bits.

Tag = total memory length - (index + offset) = 32- (11+5) = 32- 16 = 16 bits.

TAG	INDEX	OFFSET
16	11	5

(N = 4) way set associative:

Offset doesn't change because the block size is same. (i.e, 32 bytes)

Therefore offset = 5 bits.

Total number of blocks in the cache is = 64 Kb / 32 bytes = (64*1024) bytes / 32 bytes = 2048 blocks.

According to N-way set cache we have 4 blocks for each set.

Therefore number of sets = 2048 blocks / 4 blocks = 512 set. To represent these 512 sets we need 9 bits (2⁹ = 512).

Therefore set index = 9 bits.

Tag = total memory length - (index + offset ) = 32 - (9+5) = 32 - 14 = 18 bits.

TAG	INDEX	OFFSET
18	9	5

(b) 1 MB cache, 64-byte block,N=16

Direct mapped cache:

Each block size of the cache is 64-byte, to represent these 64 bytes we need 6 bits (because 2⁶ = 32).

Therefore offset = 6 bits.

Total size of the cache is 1 Mb, then total number of blocks in the cache is = 1 Mb / 64 byte = (1 * 1024 * 1024) byte / 64 bytes = 16 * 1024 blocks = 2⁴ * 2¹⁰ blocks = 2¹⁴ blocks.

Therefore to represent these 2¹⁴ blocks we need 14 bits. Index = 14 bits.

Tag = total memory length - (index + offset) = 32- (14+6) = 32- 20 = 12 bits.

TAG	INDEX	OFFSET
12	14	6

(N = 16) way set associative:

Offset doesn't change because the block size is same. (i.e, 64 bytes)

Therefore offset = 6 bits.

Total number of blocks in the cache is = 1 Mb / 64 bytes = (1024*1024) bytes / 64 bytes = (16 * 1024) blocks = 2¹⁴ blocks.

According to N-way set cache we have 16 blocks for each set.

Therefore number of sets = 2¹⁴ blocks / 16 blocks = 2¹⁴ blocks / 2⁴ blocks = 1024 sets. To represent these 1024 sets we need 10 bits (2¹⁰ = 1024).

Therefore set index = 10 bits.

Tag = total memory length - (index + offset ) = 32 - (10+6) = 32 - 16 = 16 bits.

TAG	INDEX	OFFSET
16	10	6

(c) 32 KB cache, 512-byte block,N=64

Direct mapped cache:

Each block size of the cache is 512-byte, to represent these 512 bytes we need 9 bits (because 2⁹ = 512).

Therefore offset = 9 bits.

Total size of the cache is 32 Kb, then total number of blocks in the cache is = 32 Kb / 512 byte = (32 * 1024) byte / 512 bytes = 32 * 2 blocks = 64 blocks = 2⁶ blocks.

Therefore to represent these 2⁶ blocks we need 6 bits. Index = 6 bits.

Tag = total memory length - (index + offset) = 32- (6+9) = 32- 15 = 17 bits.

TAG	INDEX	OFFSET
17	6	9

(N = 64) way set associative:

Offset doesn't change because the block size is same. (i.e, 512 bytes)

Therefore offset = 9 bits.

Total number of blocks in the cache is = 32 Kb / 512 bytes = (32*1024) bytes / 512 bytes = 64 blocks.

According to N-way set cache we have 64 blocks for each set.

Therefore number of sets = 64 blocks / 64 blocks = 1 set. To represent these 1 set we need 1 bit.

Therefore set index = 1 bit.

Tag = total memory length - (index + offset ) = 32 - (1+9) = 32 - 10 = 22 bits.

TAG	INDEX	OFFSET
22	1	9