Cache Organization
Physical address cache
Virtual address cache
Direct mapping
Example: Direct mapping
Full associative or m-way set associative
Full associative or m-way set associative
Set-associative
Example: Set-associative
`Direct mapping questions
Consider a direct mapped cache of size 16 KB with block size 256 bytes.
The size of main memory is 128 KB. Find-
• Number of bits in tag
• Tag directory size
Consider a direct mapped cache of size 512 KB with block size 1 KB.
There are 7 bits in the tag. Find-
• Size of main memory
• Tag directory size
Full associative questions
Consider a fully associative mapped cache of size 16 KB with block size
256 bytes. The size of main memory is 128 KB. Find-
• Number of bits in tag
• Tag directory size
• Consider a fully associative mapped cache of size 512 KB with block
size 1 KB. There are 17 bits in the tag. Find-
• Size of main memory
• Tag directory size
Set-associative questions
A block-set associative cache memory consists of 128 blocks divided into
four block sets . The main memory consists of 16,384 blocks and each
block contains 256 eight bit words.
• How many bits are required for addressing the main memory?
• How many bits are needed to represent the TAG, SET and WORD fields?
• A computer has a 256 KB, 4-way set associative, write back data cache
with block size of 32 bytes. The processor sends 32 bit addresses to the
cache controller. Each cache tag directory entry contains in addition to
address tag, 2 valid bits, 1 modified bit and 1 replacement bit.
• The number of bits in the tag field of an address is-
• The size of the cache tag directory is-
Sector
mapping
Cache Replacement Schemes
• FIFO
• LIFO
• LRU
• MRU
Cache Replacement Schemes
• Consider the cache has 4 blocks. For the memory references-
5, 12, 13, 17, 4, 12, 13, 17, 2, 13, 19, 13, 43, 61, 19
What is the hit ratio for the following cache replacement algorithms-
• FIFO
• LRU
• MRU
• 2-way set associative mapping using LRU
fully Associative Cache with Least Recently
Used
• Consider a fully associative cache with 8 cache blocks (0-7). The
memory block requests are in the order-
4, 3, 25, 8, 19, 6, 25, 8, 16, 35, 45, 22, 8, 3, 16, 25, 7
If LRU replacement policy is used, which cache block will have memory
block 7? Also, calculate the hit ratio and miss ratio.
Set-associative with LRU
• Consider a small 2-way set associative mapping with a total of 4
blocks. LRU replacement policy is used for choosing the block to be
replaced. The number of cache misses for the following sequence of
block addresses 8, 12, 0, 12, 8 is ____.
