Question

Memory Hierarchy & Caches

Based on the following behavior, which of the following block sizes is NOT possible for our cache?

Consider:

1) Cache starts empty, also known as a cold cache

2) Access (address: hit/miss) stream: (14: miss), (15: hit), (16: miss)

Addresses above are in decimal

a. 4 bytes

b. 8 bytes

c. 16 bytes

d. 32 bytes

Answer 1

Let's evaluate each case one by one :

a. 4 bytes

In this case, following groups of physical addresses will be mapped together in corresponding blocks :

• 0, 1, 2, 3
• 4, 5, 6, 7
• 8, 9, 10, 11
• 12, 13, 14, 15
• 16, 17, 18, 19
• 20, 21, 22, 23
• 24, 25, 26, 27
• 28, 29, 30, 31

So if accesses are :

• 14 => miss
  • Block for (12, 13, 14, 15) is loaded.
• 15 => hit
  • Due to (12, 13, 14, 15) already loaded.
• 16 => miss
  • Block for (16, 17, 18, 19) is loaded.

So, access-sequence possible = YES

b. 8 bytes

In this case, following groups of physical addresses will be mapped together in corresponding blocks :

• 0, 1, 2, 3, 4, 5, 6, 7
• 8, 9, 10, 11, 12, 13, 14, 15
• 16, 17, 18, 19, 20, 21, 22, 23
• 24, 25, 26, 27, 28, 29, 30, 31

So if accesses are :

• 14 => miss
  • Block for (8, 9, 10, 11, 12, 13, 14, 15) is loaded.
• 15 => hit
  • Due to (8, 9, 10, 11, 12, 13, 14, 15) already loaded.
• 16 => miss
  • Block for (16, 17, 18, 19, 20, 21, 22, 23) is loaded.

So, access-sequence possible = YES

c. 16 bytes

In this case, following groups of physical addresses will be mapped together in corresponding blocks :

• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
• 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31

So if accesses are :

• 14 => miss
  • Block for (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) is loaded.
• 15 => hit
  • Due to (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) already loaded.
• 16 => miss
  • Block for (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31) is loaded.

So, access-sequence possible = YES

d. 32 bytes

In this case, following groups of physical addresses will be mapped together in corresponding blocks :

• 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31

So if accesses are :

• 14 => miss
  • Block for (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31) is loaded.
• 15 => hit
  • Due to (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31) already loaded.
• 16 => miss
  • not possible, as address 16 is already present in the cache (in the solitary block).

So, access-sequence possible = NO

So, the correct option is

d. 32 bytes