Cache Memory Notes | EduRev

Created by: Gurmeet Kaur

: Cache Memory Notes | EduRev

 Page 1


1
Chapter 4
Cache Memory
Computer Organization and Architecture
Note: Appendix 4A will not be covered in class, but 
the material is interesting reading and may be used in 
some homework problems.
Characteristics of Memory Systems
Location
• CPU 
— Registers and control unit memory
• Internal
— Main memory and cache
• External
— Storage devices (paper tape, cards, tapes, discs, 
flash cards, etc.)
Capacity
• Word size
— The natural unit of organisation
— Typically number of bits used to represent an 
integer in the processor
• Number of words
— Most memory sizes are now expressed in bytes
— Most modern processors have byte-addressable 
memory but some have word addressable memory
— Memory capacity for A address lines is 2
A
addressable units
Unit of Transfer
• Internal
— Usually governed by data bus width
• External
— Usually a block which is much larger than a word 
(typical disk 512 - 4096 bytes)
• Addressable unit
— Smallest location which can be uniquely addressed
— Some systems have only word addressable memory 
while many have byte addressable memory
— A block or even cluster of blocks on most disks
Access Methods (1)
• Sequential
— Start at the beginning and read through in order
— Access time depends on location of data and 
previous location
— e.g. tape
• Direct
— Individual blocks have unique address
— Access is by jumping to vicinity plus sequential 
search
— Access time depends on location and previous 
location
— e.g. disk
Page 2


1
Chapter 4
Cache Memory
Computer Organization and Architecture
Note: Appendix 4A will not be covered in class, but 
the material is interesting reading and may be used in 
some homework problems.
Characteristics of Memory Systems
Location
• CPU 
— Registers and control unit memory
• Internal
— Main memory and cache
• External
— Storage devices (paper tape, cards, tapes, discs, 
flash cards, etc.)
Capacity
• Word size
— The natural unit of organisation
— Typically number of bits used to represent an 
integer in the processor
• Number of words
— Most memory sizes are now expressed in bytes
— Most modern processors have byte-addressable 
memory but some have word addressable memory
— Memory capacity for A address lines is 2
A
addressable units
Unit of Transfer
• Internal
— Usually governed by data bus width
• External
— Usually a block which is much larger than a word 
(typical disk 512 - 4096 bytes)
• Addressable unit
— Smallest location which can be uniquely addressed
— Some systems have only word addressable memory 
while many have byte addressable memory
— A block or even cluster of blocks on most disks
Access Methods (1)
• Sequential
— Start at the beginning and read through in order
— Access time depends on location of data and 
previous location
— e.g. tape
• Direct
— Individual blocks have unique address
— Access is by jumping to vicinity plus sequential 
search
— Access time depends on location and previous 
location
— e.g. disk
2
Access Methods (2)
• Random
— Individual addresses identify locations exactly
— Access time is independent of location or previous 
access
— e.g. RAM
• Associative
— Data is located by a comparison with contents of a 
portion of the store
— Access time is independent of location or previous 
access
— All memory is checked simultaneously; access time 
is constant
— e.g. cache
Performance
• From user’s perspective the most important 
characteristics of memory are capacity and 
performance
• Three performance parameters:
— Access time 
— Cycle Time
— Transfer Rate
• Access time (latency)
— For RAM access time is the time between presenting an 
address to memory and getting the data on the bus
— For other memories the largest component is 
positioning the read/write mechanism
Performance
• Cycle Time
— Primarily applied to RAM; access time + additional 
time before a second access can start
— Function of memory components and system bus, not 
the processor
• Transfer Rate – the rate at which data can be 
transferred into or out of a memory unit
— For RAM   TR = 1 / (cycle time)
Transfer rate for other memories
• T
n
= T
a
+ (n/r)   where
• T
n
=Average time to read or write N bits
• T
a 
=Average access time
• n = number of bits
• r = transfer rate in bits / second
Physical Types of Memory
• Semiconductor
— RAM (volatile or non-volatile)
• Magnetic Surface Memory
— Disk & Tape
• Optical
— CD & DVD
• Others
— Magneto-optical
— Bubble
— Hologram
Physical Characteristics
• Volatility
— Does the memory retain data in the absence of 
electrical power?
• Decay
— Ranges from tiny fractions of a second (volatile 
DRAM) to many years (CDs, DVDs)
• Erasable
— Can the memory be rewritten? If so, how fast? How 
many erase cycles can occur?
• Power consumption
Page 3


1
Chapter 4
Cache Memory
Computer Organization and Architecture
Note: Appendix 4A will not be covered in class, but 
the material is interesting reading and may be used in 
some homework problems.
Characteristics of Memory Systems
Location
• CPU 
— Registers and control unit memory
• Internal
— Main memory and cache
• External
— Storage devices (paper tape, cards, tapes, discs, 
flash cards, etc.)
Capacity
• Word size
— The natural unit of organisation
— Typically number of bits used to represent an 
integer in the processor
• Number of words
— Most memory sizes are now expressed in bytes
— Most modern processors have byte-addressable 
memory but some have word addressable memory
— Memory capacity for A address lines is 2
A
addressable units
Unit of Transfer
• Internal
— Usually governed by data bus width
• External
— Usually a block which is much larger than a word 
(typical disk 512 - 4096 bytes)
• Addressable unit
— Smallest location which can be uniquely addressed
— Some systems have only word addressable memory 
while many have byte addressable memory
— A block or even cluster of blocks on most disks
Access Methods (1)
• Sequential
— Start at the beginning and read through in order
— Access time depends on location of data and 
previous location
— e.g. tape
• Direct
— Individual blocks have unique address
— Access is by jumping to vicinity plus sequential 
search
— Access time depends on location and previous 
location
— e.g. disk
2
Access Methods (2)
• Random
— Individual addresses identify locations exactly
— Access time is independent of location or previous 
access
— e.g. RAM
• Associative
— Data is located by a comparison with contents of a 
portion of the store
— Access time is independent of location or previous 
access
— All memory is checked simultaneously; access time 
is constant
— e.g. cache
Performance
• From user’s perspective the most important 
characteristics of memory are capacity and 
performance
• Three performance parameters:
— Access time 
— Cycle Time
— Transfer Rate
• Access time (latency)
— For RAM access time is the time between presenting an 
address to memory and getting the data on the bus
— For other memories the largest component is 
positioning the read/write mechanism
Performance
• Cycle Time
— Primarily applied to RAM; access time + additional 
time before a second access can start
— Function of memory components and system bus, not 
the processor
• Transfer Rate – the rate at which data can be 
transferred into or out of a memory unit
— For RAM   TR = 1 / (cycle time)
Transfer rate for other memories
• T
n
= T
a
+ (n/r)   where
• T
n
=Average time to read or write N bits
• T
a 
=Average access time
• n = number of bits
• r = transfer rate in bits / second
Physical Types of Memory
• Semiconductor
— RAM (volatile or non-volatile)
• Magnetic Surface Memory
— Disk & Tape
• Optical
— CD & DVD
• Others
— Magneto-optical
— Bubble
— Hologram
Physical Characteristics
• Volatility
— Does the memory retain data in the absence of 
electrical power?
• Decay
— Ranges from tiny fractions of a second (volatile 
DRAM) to many years (CDs, DVDs)
• Erasable
— Can the memory be rewritten? If so, how fast? How 
many erase cycles can occur?
• Power consumption
3
Organization
• Physical arrangement of bits into words
• Not always obvious, e.g., interleaved memory 
(examples later)
Memory Hierarchy
• For any memory: 
— How fast? 
— How much? 
— How expensive?
• Faster memory => greater cost per bit
• Greater capacity => smaller cost / bit
• Greater capacity => slower access
• Going down the hierarchy:
— Decreasing cost / bit
— Increasing capacity
— Increasing access time 
— Decreasing frequency of access by processor
Memory Hierarchy - Diagram Memory Hierarchy
• Registers
— In CPU
• Internal or Main memory
— May include one or more levels of cache
— “RAM”
• External memory
— Backing store
Hierarchy List
• Registers
• L1 Cache
• L2 Cache
• Main memory
• Disk cache
• Magnetic Disk
• Optical
• Tape
• (and we could mention punch cards, etc at the 
very bottom)
Locality of Reference
• Two or more levels of memory can be used to 
produce average access time approaching the 
highest level
• The reason that this works well is called 
“locality of reference”
• In practice memory references (both instructions 
and data) tend to cluster
— Instructions: iterative loops and repetitive subroutine 
calls
— Data: tables, arrays, etc. Memory references cluster 
in short run
Page 4


1
Chapter 4
Cache Memory
Computer Organization and Architecture
Note: Appendix 4A will not be covered in class, but 
the material is interesting reading and may be used in 
some homework problems.
Characteristics of Memory Systems
Location
• CPU 
— Registers and control unit memory
• Internal
— Main memory and cache
• External
— Storage devices (paper tape, cards, tapes, discs, 
flash cards, etc.)
Capacity
• Word size
— The natural unit of organisation
— Typically number of bits used to represent an 
integer in the processor
• Number of words
— Most memory sizes are now expressed in bytes
— Most modern processors have byte-addressable 
memory but some have word addressable memory
— Memory capacity for A address lines is 2
A
addressable units
Unit of Transfer
• Internal
— Usually governed by data bus width
• External
— Usually a block which is much larger than a word 
(typical disk 512 - 4096 bytes)
• Addressable unit
— Smallest location which can be uniquely addressed
— Some systems have only word addressable memory 
while many have byte addressable memory
— A block or even cluster of blocks on most disks
Access Methods (1)
• Sequential
— Start at the beginning and read through in order
— Access time depends on location of data and 
previous location
— e.g. tape
• Direct
— Individual blocks have unique address
— Access is by jumping to vicinity plus sequential 
search
— Access time depends on location and previous 
location
— e.g. disk
2
Access Methods (2)
• Random
— Individual addresses identify locations exactly
— Access time is independent of location or previous 
access
— e.g. RAM
• Associative
— Data is located by a comparison with contents of a 
portion of the store
— Access time is independent of location or previous 
access
— All memory is checked simultaneously; access time 
is constant
— e.g. cache
Performance
• From user’s perspective the most important 
characteristics of memory are capacity and 
performance
• Three performance parameters:
— Access time 
— Cycle Time
— Transfer Rate
• Access time (latency)
— For RAM access time is the time between presenting an 
address to memory and getting the data on the bus
— For other memories the largest component is 
positioning the read/write mechanism
Performance
• Cycle Time
— Primarily applied to RAM; access time + additional 
time before a second access can start
— Function of memory components and system bus, not 
the processor
• Transfer Rate – the rate at which data can be 
transferred into or out of a memory unit
— For RAM   TR = 1 / (cycle time)
Transfer rate for other memories
• T
n
= T
a
+ (n/r)   where
• T
n
=Average time to read or write N bits
• T
a 
=Average access time
• n = number of bits
• r = transfer rate in bits / second
Physical Types of Memory
• Semiconductor
— RAM (volatile or non-volatile)
• Magnetic Surface Memory
— Disk & Tape
• Optical
— CD & DVD
• Others
— Magneto-optical
— Bubble
— Hologram
Physical Characteristics
• Volatility
— Does the memory retain data in the absence of 
electrical power?
• Decay
— Ranges from tiny fractions of a second (volatile 
DRAM) to many years (CDs, DVDs)
• Erasable
— Can the memory be rewritten? If so, how fast? How 
many erase cycles can occur?
• Power consumption
3
Organization
• Physical arrangement of bits into words
• Not always obvious, e.g., interleaved memory 
(examples later)
Memory Hierarchy
• For any memory: 
— How fast? 
— How much? 
— How expensive?
• Faster memory => greater cost per bit
• Greater capacity => smaller cost / bit
• Greater capacity => slower access
• Going down the hierarchy:
— Decreasing cost / bit
— Increasing capacity
— Increasing access time 
— Decreasing frequency of access by processor
Memory Hierarchy - Diagram Memory Hierarchy
• Registers
— In CPU
• Internal or Main memory
— May include one or more levels of cache
— “RAM”
• External memory
— Backing store
Hierarchy List
• Registers
• L1 Cache
• L2 Cache
• Main memory
• Disk cache
• Magnetic Disk
• Optical
• Tape
• (and we could mention punch cards, etc at the 
very bottom)
Locality of Reference
• Two or more levels of memory can be used to 
produce average access time approaching the 
highest level
• The reason that this works well is called 
“locality of reference”
• In practice memory references (both instructions 
and data) tend to cluster
— Instructions: iterative loops and repetitive subroutine 
calls
— Data: tables, arrays, etc. Memory references cluster 
in short run
4
Cache
• A small amount of fast memory that sits 
between normal main memory and CPU
• May be located on CPU chip or module
• Intended to allow access speed approaching 
register speed
• When processor attempts to read a word from 
memory, cache is checked first
Cache Memory Principles
• If data sought is not present in cache, a block 
of memory of fixed size is read into the cache
• Locality of reference makes it likely that other 
words in the same block will be accessed soon
Cache and Main Memory A Simple two-level cache
• Level 1: 1000 words, 0.01 ?s
• Level 2: 100,000 words 0.1 ?s
• If word in L1 processor has direct access else 
word copied from L2 into L1 
• Av Access Time as function of hit ratio H:
H * 0.01 ?s + (1-H)* 0.11 ?s
• With H near 1 access time approaches 0.01 ?s
Two-level cache performance Two-level disk access
• Principles of two-level memories can be 
applied to disk as well as RAM
• A portion of main memory can be used as a disk 
cache
— Allows disk writes to be clustered; largest 
component of disk access time is seek time
— Dirty (modified) datamay be requested by the 
program before it is even written back to disk
Page 5


1
Chapter 4
Cache Memory
Computer Organization and Architecture
Note: Appendix 4A will not be covered in class, but 
the material is interesting reading and may be used in 
some homework problems.
Characteristics of Memory Systems
Location
• CPU 
— Registers and control unit memory
• Internal
— Main memory and cache
• External
— Storage devices (paper tape, cards, tapes, discs, 
flash cards, etc.)
Capacity
• Word size
— The natural unit of organisation
— Typically number of bits used to represent an 
integer in the processor
• Number of words
— Most memory sizes are now expressed in bytes
— Most modern processors have byte-addressable 
memory but some have word addressable memory
— Memory capacity for A address lines is 2
A
addressable units
Unit of Transfer
• Internal
— Usually governed by data bus width
• External
— Usually a block which is much larger than a word 
(typical disk 512 - 4096 bytes)
• Addressable unit
— Smallest location which can be uniquely addressed
— Some systems have only word addressable memory 
while many have byte addressable memory
— A block or even cluster of blocks on most disks
Access Methods (1)
• Sequential
— Start at the beginning and read through in order
— Access time depends on location of data and 
previous location
— e.g. tape
• Direct
— Individual blocks have unique address
— Access is by jumping to vicinity plus sequential 
search
— Access time depends on location and previous 
location
— e.g. disk
2
Access Methods (2)
• Random
— Individual addresses identify locations exactly
— Access time is independent of location or previous 
access
— e.g. RAM
• Associative
— Data is located by a comparison with contents of a 
portion of the store
— Access time is independent of location or previous 
access
— All memory is checked simultaneously; access time 
is constant
— e.g. cache
Performance
• From user’s perspective the most important 
characteristics of memory are capacity and 
performance
• Three performance parameters:
— Access time 
— Cycle Time
— Transfer Rate
• Access time (latency)
— For RAM access time is the time between presenting an 
address to memory and getting the data on the bus
— For other memories the largest component is 
positioning the read/write mechanism
Performance
• Cycle Time
— Primarily applied to RAM; access time + additional 
time before a second access can start
— Function of memory components and system bus, not 
the processor
• Transfer Rate – the rate at which data can be 
transferred into or out of a memory unit
— For RAM   TR = 1 / (cycle time)
Transfer rate for other memories
• T
n
= T
a
+ (n/r)   where
• T
n
=Average time to read or write N bits
• T
a 
=Average access time
• n = number of bits
• r = transfer rate in bits / second
Physical Types of Memory
• Semiconductor
— RAM (volatile or non-volatile)
• Magnetic Surface Memory
— Disk & Tape
• Optical
— CD & DVD
• Others
— Magneto-optical
— Bubble
— Hologram
Physical Characteristics
• Volatility
— Does the memory retain data in the absence of 
electrical power?
• Decay
— Ranges from tiny fractions of a second (volatile 
DRAM) to many years (CDs, DVDs)
• Erasable
— Can the memory be rewritten? If so, how fast? How 
many erase cycles can occur?
• Power consumption
3
Organization
• Physical arrangement of bits into words
• Not always obvious, e.g., interleaved memory 
(examples later)
Memory Hierarchy
• For any memory: 
— How fast? 
— How much? 
— How expensive?
• Faster memory => greater cost per bit
• Greater capacity => smaller cost / bit
• Greater capacity => slower access
• Going down the hierarchy:
— Decreasing cost / bit
— Increasing capacity
— Increasing access time 
— Decreasing frequency of access by processor
Memory Hierarchy - Diagram Memory Hierarchy
• Registers
— In CPU
• Internal or Main memory
— May include one or more levels of cache
— “RAM”
• External memory
— Backing store
Hierarchy List
• Registers
• L1 Cache
• L2 Cache
• Main memory
• Disk cache
• Magnetic Disk
• Optical
• Tape
• (and we could mention punch cards, etc at the 
very bottom)
Locality of Reference
• Two or more levels of memory can be used to 
produce average access time approaching the 
highest level
• The reason that this works well is called 
“locality of reference”
• In practice memory references (both instructions 
and data) tend to cluster
— Instructions: iterative loops and repetitive subroutine 
calls
— Data: tables, arrays, etc. Memory references cluster 
in short run
4
Cache
• A small amount of fast memory that sits 
between normal main memory and CPU
• May be located on CPU chip or module
• Intended to allow access speed approaching 
register speed
• When processor attempts to read a word from 
memory, cache is checked first
Cache Memory Principles
• If data sought is not present in cache, a block 
of memory of fixed size is read into the cache
• Locality of reference makes it likely that other 
words in the same block will be accessed soon
Cache and Main Memory A Simple two-level cache
• Level 1: 1000 words, 0.01 ?s
• Level 2: 100,000 words 0.1 ?s
• If word in L1 processor has direct access else 
word copied from L2 into L1 
• Av Access Time as function of hit ratio H:
H * 0.01 ?s + (1-H)* 0.11 ?s
• With H near 1 access time approaches 0.01 ?s
Two-level cache performance Two-level disk access
• Principles of two-level memories can be 
applied to disk as well as RAM
• A portion of main memory can be used as a disk 
cache
— Allows disk writes to be clustered; largest 
component of disk access time is seek time
— Dirty (modified) datamay be requested by the 
program before it is even written back to disk
5
Cache/Main Memory Structure Cache view of memory
• N address lines => 2
n
words of memory
• Cache stores fixed length blocks of K words 
• Cache views memory as an array of M blocks 
where M = 2
n
/K
• A block of memory in cache is referred to as a 
line. K is the line size
• Cache size of C blocks where C < M 
(considerably)
• Each line includes a tag that identifies the 
block being stored
• Tag is usually upper portion of memory address
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
Cache Read Operation - Flowchart
Typical Cache Organization Cache organization
• The preceding diagram illustrates a shared 
connection between the processor, the cache 
and the system bus (look-aside cache)
• Another way to organize this system is to 
interpose the cache between the processor and 
the system bus for all lines (look-through 
cache)
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!