Cache Memory
Charles Saah
Memory Hierarchy - Diagram
Characteristics of Cache Memory
• It is a very fast memory
• Has a high access time (program sort for are found in there)
• Very expensive
• It is very small in size
• Can store only KB of instruction
• Programs and instructions are executed from cache memory
• If a program to be executed by the processor is found in the cache, it
called a hit otherwise it’s called a miss
• Hit ratio = hits / (hits + misses) (always less than 1)
• High hit ratio means very good processing
Cache Memory
• This is smaller compared to the main memory
• Faster compared to main memory
• It is sandwiched between the main memory and the CPU
Main
CPU Cache
Word Block / Page Memory
• It’s word addressable while main memory is page addressable
• Locality reference: instruction is executed frequently (more than
once )
• If frequently used instructions are place in the cache, execution
time is reduced
Cache Memory Continuation
• If program to be executed is not found in the cache, it has to be
transferred from the main memory into the cache
• The process of transferring data from main memory to the cache
is referred to as mapping
• Three types of mapping exist
1. Associative mapping
2. Direct mapping and
3. Set Associative mapping
Associative Mapping Argument Register (15bits)
Address (15 bit) Data (12 bits)
• The address of the argument register is compared
with cache memory 01000 3450
• If there is a match in the address the corresponding 02777 6720
data is delivered to the cache. 23345 1217
• E.g. if address 02777 matches with the register
address
• Of main memory, the data 6720 will be sent to the
cache
Associative Mapping
• CPU generated address of 15 bits while the size of RAM is 32KB X12bit word
• 32=25 KB=210 12 bits word size is = 212
• Cache memory can store 512x12 bits out of the 32KB
• CPU generates 15 bit address to be stored in the argument register
• Each character position is 3 bits. So 15 and 12 bits must have 5 and 4
characters respectively
Associative Mapping - Continuation
• The address of the argument register is compared with cache memory
• If there is a match in the address the corresponding
• Is delivered to the cache.
• E.g. if address 02777 matches with the register address
• Of main memory, the data 6720 will be sent to the cache
Argument Register (15bits)
Address (15 bit) Data (12 bits)
01000 3450
02777 6720
23345 1217
Associative Mapping Cont.
• What if the CPU generated address does not match the address of the
cache or the cache memory is full
• We have to replace one of the words in the cache memory with that coming
from the main memory
• Challenge: which one is to be replaced?
• We can use various replacement algorithms
1. FIFO
2. LIFO
3. LRU
Direct Addressing
• Direct addressing is designed to solve the associative mapping problem
• Under direct addressing the CPU generated address is divided into two
parts.
1. Tag (6 bits)
2. Index (9 bits)
• Given a CPU generated address, you have to check the index and tag to be
able to move the data to the cache.
• The challenge is that there could be two or more indices with different tags.
• This slows down the movement of data
Main Memory Cache Memory
15 bits 12 bits 9bits 6 bits 12 bits
Address Data Index Tag Data
00000 1220 811 45 2145
01078 1456 854 96 2589
45811 2145
65478 3215
96854 2589 811 87 6578
Same index, different tags
87811 6578
Black tag Red = index
Direct Mapping Problems
• Same indices with different tags cause a lot of misses and CPU frequently
visits the main memory for data
• This generates lower access time
• To correct this the set associative memory is used
Set Associative Mapping
• Just like direct mapping but multiple data can be stored using
different tags in the same index
Main Memory Cache Memory
15 bits 12 bits 9bits 6 bits 12 bits
Address Data Index Tag Data Tag Data
00000 1220 811 45 2145 87 6578
01078 1456 854 96 2589
45811 2145
65478 3215
96854 2589
87811 6578
Summary Table
•.
Feature Direct Mapping Associative Mapping Set Associative Mapping
Flexibility Low High Medium
Speed Fast Slow (due to parallel search) Moderate
Hardware Complexity Low High Medium
Conflict on Misses High Low Lower than Direct Mapping
Tag Comparison One All lines All lines in a set
Example 3
• A computer has a byte addressable main memory of size 16GB and a
block size of 16 KB. If the number of tag bit is 10, determine the cache
size.
• We first need to convert the various units into bytes
34
• Main memory size = 16B = 2 x2 B =2 B
4 30 34
• No. of physical address bits = log2234 = 34 10 10 14
• Block size = 16KB = 24x210B =214B Tag Block
Line no
given offset
• Block offset = log2214 = 14
• No. of lines = Phy. Address – (Tag + offset) = 34 – (10+14) = 10
• The line no and block offset give the cache size
• Cache size = No of cache line x no of offset = 210 x 214 = 224B = 24x220
• = 16MB
Associative Memory
• A computer has a byte addressable memory of size 256 MB, a cache memory
of size 1MB and a block size of 128B. If it uses a 2-way associative mapping.
Determine the physical address split and the tag directory size
• Solution 28 bits
• 2 – way set associative means each set has 2 lines 21bits
• Physical address split = 256MB = 28x220 B = 228B 9 12 bits 7
• Block size = 128B = 27B. Offset = log227 = 7 Tag Set no.
Block
offset
• No of blocks in main memory = 2 /2 = 2
28 7 21
• Cache size = 1MB = 1x220B
Tag = 28 – (12 + 7) = 9
• No. lines in cache = 220/27 = 213
• No of sets 213/21 = 212 (2 – associative)
• Tag directory size = 212x9 bits
Example 2
• A computer has a byte addressable memory of size 128B, a cache memory of
size 32B and a block size of 4B. If it uses a 2-way associative mapping.
Determine the physical address split and the tag directory size
• Solution
• 2 – way set associative means each set has 2 lines 7
• Physical address = 128B = 27B = log227=7bits 5
• Block size = 22B. Offset = 2 3 2 2
Block
• No. of memory blocks = 2 /2 = 2
7 2 5 Tag Set no
offset
• Cache size =32B = 25B
• No. of cache lines = 25/22 = 23
• No of set 23/21 = 22
• 22 x 3
Class Exercise 1 (Write your name and index
number on your paper
• A computer has a byte addressable memory of size 256 MB, a cache
memory of size 1MB and a block size of 128B. If it uses a 4-way
associative mapping. Determine the physical address split and the tag
directory size
Associative Memory
• A computer has a byte addressable memory of size 256 MB, a cache memory of
size 1MB and a block size of 128B. If it uses a 4-way associative mapping.
Determine the physical address split and the tag directory size
• Solution 28 bits
• 4 – way set associative means each set has 4 lines 21bits
• Physical address split = 256MB = 28x220 B = 228B 10 11 bits 7
• Block size = 128B = 27B. Offset = log227 = 7 Tag Set no.
Block
offset
• No of blocks in main memory = 2 /2 = 2
28 7 21
• Cache size = 1MB = 1x220B
Tag = 28 – (11 + 7) = 9
• No. lines in cache = 220/27 = 213
• No of sets 213/22 = 211 (4 – associative)
• Tag directory size = 211x10 bits
Example
• A computer has a byte-addressable physical memory of size 512 MB,
a cache memory of size 2 MB, and a block size of 64 bytes. The cache
uses a 4-way set-associative mapping.
• Determine:
a) The number of bits in the physical address
b) The address format: number of bits for tag, set index, and block
offset
c) The total number of sets
• Number of bits in physical address = 512MB =29X220 =229
• Physical address = 29
• Addressable format (Tag – Set index - Offset) = 29
• Block size = 64bytes = 26 = offset = 6
• Cache size =2MB =2x220 =221
• No of blocks in cache = 221/26 = 215
• 4-way set-associative cache = 215/22 = 213
• Index = 13 when you use log2
• Tag =physical address – index – offset = 29 – 13 – 6 =10