Cache Memory

Lecture 03

Instructor: Md. Selim Reza, SWE, DIU.

 Performance of Memory
• Based on three performance parameters
• Access time (latency): For random-access memory, this is the time
it takes to perform a read or write operation
– For non-random-access memory, access time is the time it takes
to position the read–write mechanism at the desired location
• Memory cycle time: This concept is primarily applied to random-
access memory and consists of the access time plus any additional
time required before a second access can commence
– This additional time may be required for transients to die out on
signal lines or to regenerate data if they are read destructively
• Transfer rate: This is the rate at which data can be transferred into
or out of a memory unit
– For random-access memory, it is equal to 1/(cycle time)
 Performance of Memory
• For non-random-access memory, the following relationship
holds:
𝑛
𝑇𝑁 = 𝑇𝐴 +
𝑅
• where
TN = Average time to read or write N bits
TA = Average access time
n = Number of bits
R = Transfer rate, in bits per second (bps)
• Several physical characteristics of memory are also important
The Memory Hierarchy
Depends on:
a. Faster access time, greater cost
per bit
b. Greater capacity, smaller cost per
bit
c. Greater capacity, slower access
time
Cache Memory Principles
 Cache Memory Principles
• The cache contains a copy of portions of main memory
• When the processor attempts to read a word of
memory, a check is made to determine if the word is in
the cache. If so, the word is delivered to the processor
• If not, a block of main memory, consisting of some
fixed number of words, is read into the cache and then
the word is delivered to the processor
• When a block of data is fetched into the cache to
satisfy a single memory reference, it is likely that there
will be future references to that same memory location
or to other words in the block
– Locality of reference
Cache Memory Structure
Cache Read Operation
Typical Cache Organization
Elements Of Cache Design
Cache Addresses
 Mapping Technique
Performance of the cache memory mapping
function
is key to the speed
• There are a number of mapping techniques
– Direct mapping
– Associative mapping
– Set associative - mapping
 Direct Mapping
• The mapping is expressed as:
𝑖 = 𝑗 𝑚𝑜𝑑𝑢𝑙𝑜 𝑚
• where
i= cache line number
j = main memory block number
m = number of lines in the cache
Mapping Mechanisms
Mapping Mechanisms
Direct Mapping Technique
Direct Mapping Example
 Direct Mapping Example

• Advantage and Disadvantage?

– Refer to text book

Fully Associative Cache Example
 Fully Associative Cache Example

• Advantage and Disadvantages?

– Refer to textbook
Set-associative Mapping
Set-associative Mapping (2- way set.)
 Replacement Algorithms
• Once the cache has been filled, when a new block
is brought into the cache, one of the existing
blocks must be replaced
• For direct mapping, there is only one possible line
for any particular block, and no choice is possible
• For the associative and set-associative
techniques, a replacement algorithm is needed
– To achieve high speed, such an algorithm must be
implemented in hardware
 Replacement Algorithms
• Least Recently Used (LRU)
– Most effective
• First-in-First-Out (FIFO)
• Least Frequently Used (LFU)

• For details: Find the book and study!

 Write Policy
• When a block that is resident in the cache is to be
replaced, there are two cases to consider
• If the old block in the cache has not been altered,
then it may be overwritten with a new block
without first writing out the old block
• If at least one write operation has been
performed on a word in that line of the cache,
then main memory must be updated by writing
the line of cache out to the block of memory
before bringing in the new block
 Write Policy
• Two potential problems
• More than one device may have access to
main memory
• If multiple processors are attached to the
same bus and each processor has its own local
cache
 Write Policies
• Write through
– Simplest of all
• Write back
– Minimizes memory writes (dirty bit or use bit)
 Write Policies
• In a bus organization in which more than one
device (typically a processor) has a cache and
main memory is shared, a new problem is
introduced
• If data in one cache are altered, this invalidates
not only the corresponding word in main
memory, but also that same word in other caches
• A system that prevents this problem is said to
maintain cache coherency
 Write Policies
• Solutions:
– Bus watching with write through
– Hardware transparency
– Non-cacheable memory
Thanks!