Tutorial on Caches
1
• (a) For address 0xABCDEF78, find the set-index in a cache with
16B block and 1024 sets.
• 10 1111 0111 = 759
• (b) Find the block size of a 4KB 8-way cache, which is fully-
associative.
• 512B
• Consider a fully-associative cache which has 8B block size and a
capacity of 4MB. In a 32-bit address, how many bits of tags will
be there?
• 29 bits (=32-3)
• For a cache block size of 7B, which other addresses will be part
of the block that has the address 55.
• Counting starts from 0.
• 49,50,51,52,53,54,55.
• Consider a direct-mapped cache with 4 sets and a cache block size of 4B. Thus,
its total size is 16B.
• It sees the following addresses (in decimal):
• 10, 14, 456, 18, 11, 50, 458, 15, 8, 16
• Same sequence in binary:
• 1010, 1110, 111001000, 10010, 1011, 110010, 111001010, 1111, 1000, 10000
• Find whether each access leads to a hit or miss. For each miss, show its breakup
in compulsory/capacity/conflict. Show solution steps (i.e., cache state after each
access).
Solution: Direct-mapped cache
• After 10: [], [], [8,9,10,11], [] ==== compulsory miss
• After 14: [], [], [8,9,10,11], [12,13,14,15] ==== compulsory miss
• Aft. 456: [], [], [456,457,458,459], [12,13,14,15] ==== compulsory miss
• After 18: [16,17,18,19], [], [456,457,458,459], [12,13,14,15] ==== compulsory
miss
• After 11: [16,17,18,19], [], [8,9,10,11], [12,13,14,15] ==== ? miss
• After 50: [48,49,50,51], [], [8,9,10,11], [12,13,14,15] ==== compulsory miss
• Aft. 458: [48,49,50,51], [], [456,457,458,459], [12,13,14,15] ==== ? miss
• After 15: Hit, cache status not changed.
• After 8: [48,49,50,51], [], [8,9,10,11], [12,13,14,15] ==== ? miss
• After 16: [16,17,18,19], [], [8,9,10,11], [12,13,14,15] ==== ? miss
Solution: Fully-associative cache
• After 10: [8,9,10,11], ==== compulsory miss
• After 14: [8,9,10,11], [12,13,14,15] ==== compulsory miss
• Aft. 456: [8,9,10,11], [12,13,14,15], [456,457,458,459] ==== compulsory miss
• After 18: [8,9,10,11], [12,13,14,15], [456,457,458,459], [16,17,18,19] ====
compulsory miss
• After 11: [12,13,14,15], [456,457,458,459], [16,17,18,19], [8,9,10,11] ==== Hit
• After 50: [456,457,458,459], [16,17,18,19], [8,9,10,11], [48,49,50,51] ====
compulsory miss
• Aft. 458: [16,17,18,19], [8,9,10,11], [48,49,50,51], [456,457,458,459] ==== Hit
• After 15: [8,9,10,11], [48,49,50,51], [456,457,458,459], [12,13,14,15] ====
Capacity Miss
• After 8: [48,49,50,51], [456,457,458,459], [12,13,14,15], [8,9,10,11] ==== Hit
• After 16: [456,457,458,459], [12,13,14,15], [8,9,10,11], [16,17,18,19] ====
Capacity miss
• In the original direct-mapped cache, 11, 458 and 8 were
conflict misses and 16 was a capacity miss.