MEMORY HIERARCHY
REG CACHE MAIN SECONDARY
Memory Hierarchy
• Registers
– In CPU
• Primary Memory
– May include one or more levels of cache
– “RAM”
• Secondary memory
– Magnetic/Optical
CACHE:
-High Speed Memory (SRAMs)
-Small in Size
-High cost
Fig. 13.55 A CMOS SRAM memory cell.
MAIN MEMORY
-High density ( DRAMs)
-Low cost
-Slower than Cache.
Cache
• Small amount of fast memory
• Sits between normal main memory and
CPU
Cache operation - overview
• CPU requests contents of memory location
• Check cache for this data
• If present, get from cache (fast)
• If not present, read required block from
main memory to cache
• Then deliver from cache to CPU
• Cache includes tags to identify which block
of main memory is in each cache slot
Typical Cache Organization
Mapping Function
• Cache of 64kByte
• Cache block of 4 bytes
– i.e. cache is 16k (214) lines of 4 bytes
• 16MBytes main memory
• 24 bit address
– (224=16M)
Direct Mapping
• Each block of main memory maps to only one
cache line
– i.e. if a block is in cache, it must be in one specific
place
• Address is in two parts
• Least Significant w bits identify unique word
• Most Significant s bits specify one memory block
• The MSBs are split into a cache line field r and a
tag of s-r (most significant)
Direct Mapping
Address Structure
Tag s-r Line or Slot r Word w
8 14 2
• 24 bit address
• 2 bit word identifier (4 byte block)
• 22 bit block identifier
– 8 bit tag (=22-14)
– 14 bit slot or line
• No two blocks in the same line have the same Tag field
• Check contents of cache by finding line and checking Tag
Direct Mapping Cache
Organization
Direct Mapping pros & cons
• Simple
• Inexpensive
• Fixed location for given block
– If a program accesses 2 blocks that map to the
same line repeatedly, cache misses are very
high
Associative Mapping
• A main memory block can load into any
line of cache
• Memory address is interpreted as tag and
word
• Tag uniquely identifies block of memory
• Every line’s tag is examined for a match
• Cache searching gets expensive
Fully Associative Cache
Organization
Associative Mapping
Address Structure
Word
Tag 22 bit 2 bit
• 22 bit tag stored with each 32 bit block of
data
• Compare tag field with tag entry in cache to
check for hit
Set Associative Mapping
• Cache is divided into a number of sets
• Each set contains a number of lines
• A given block maps to any line in a given set
– e.g. Block B can be in any line of set i
• e.g. 2 lines per set
– 2 way associative mapping
– A given block can be in one of 2 lines in only one set
K- Way Set Associative Cache
Organization
Set Associative Mapping
Address Structure
Word
Tag 9 bit Set 13 bit 2 bit
• Use set field to determine cache set to look
in
• Compare tag field to see if we have a hit
Main Memory 64kB
Block size 8 bytes
Direct Mapped Cache – 32 lines
How is the 16 bit mem add divided
Into what line a byte with add below be stored
0001 0001 0001 1011
1100 0011 0011 0100
