Module 5 Microcontroller
Basic Architecture Of Cache Memory
Cache memory is a small, high-speed memory placed between the processor and main
memory that stores frequently used data to reduce memory access time and improve
system performance.
Components of Cache Architecture
1. Cache Controller : Controls transfer of data between cache and main memory.
• Intercepts CPU memory requests.
• Divides address into:
o Tag field
o Set index
o Data index
• Determines:
o Cache Hit → Data found in cache
o Cache Miss → Data fetched from main memory
2. Cache Memory : Cache is organized into cache lines (blocks). Each cache line has:
a) Directory Store (Tag) : Stores address of the data from main memory.
• Used for comparison with requested address.
b) Data Section : Stores actual instructions/data.
• Accessed using data index.
c) Status Bits : Maintain state of cache line:
o Valid bit → Indicates valid data
o Dirty bit → Indicates modified data
Working of Cache Memory
1. CPU sends memory address to cache controller.
2. Address is divided into tag, set index, data index.
3. Controller checks:
o Valid bit
o Tag comparison
4. If match → Cache Hit (fast access).
5. If not → Cache Miss:
o Data fetched from main memory
o Stored in cache (cache line fill)
How Main Memory Maps to Cache Memory
Mapping is the process of placing blocks of main memory into cache memory locations so
that the processor can access data faster. In the simplest case, this is done using a direct-
mapped cache.
• Main memory is divided into blocks, and cache is divided into cache lines.
• Each block of main memory maps to one specific cache line.
• Mapping is done using the formula:
Cache Line = (Main Memory Block Number)mod (Number of Cache Lines)
Address Structure
The processor address is divided into three parts:
1. Tag → Identifies the block
2. Set Index → Selects cache line
3. Data Index → Selects word inside block
Working
1. CPU generates an address.
2. Set index selects a cache line.
3. Tag is compared with stored cache-tag:
o Match → Cache Hit
o No match → Cache Miss
4. On miss:
o Required block is fetched from main memory
o Stored in that cache line (may replace existing data)
Associative Cache (Set-Associative Cache)
An associative cache is a cache organization in which a block of main memory can be placed
in more than one cache location (set) instead of a single fixed location. It reduces conflict
problems seen in direct-mapped cache.
• Cache is divided into sets.
• Each set contains multiple cache lines (ways).
• A memory block can be placed in any line within a set.
Address Format
• Set Index → Selects a set
• Tag → Compared with all tags in that set
• Data Index → Selects data within cache line
Working
1. CPU sends address to cache controller.
2. Set index selects a set of cache lines.
3. Tags of all lines in that set are compared simultaneously.
4. If match found → Cache Hit
5. If no match → Cache Miss:
o Block fetched from main memory
o Placed in one of the lines in the set (replacement policy used)
Example
• A 4 KB cache may be divided into:
o 4 ways
o 64 lines per way
• Total = 256 cache lines arranged in sets.
Advantages
• Reduces cache thrashing compared to direct mapping
• Flexible placement of data
• Better cache utilization
Disadvantages
• More complex hardware (multiple tag comparisons)
• Slightly slower than direct-mapped cache
Cache Line Replacement Policies
A cache line replacement policy determines which cache line is replaced (victim) when a
cache miss occurs and new data must be loaded into the cache.
• The selected line is called the victim cache line.
• If the victim contains dirty data, it must be written back to main memory before
replacement.
Working Concept
• On a cache miss:
1. Cache controller selects a set using set index.
2. From that set, one cache line is chosen for replacement.
3. Replacement policy decides which line to evict.
Types of Cache Line Replacement Policies
1. Round-Robin (Cyclic) Replacement
• Selects cache lines sequentially in order.
• Uses a counter that increments for each replacement.
• When maximum is reached, it resets to start.
Features:
• Simple and easy to implement
• Predictable behavior
• Performance may vary with access patterns
2. Pseudorandom Replacement
• Selects cache line randomly for replacement.
• Uses a non-sequential counter with random increments.
Features:
• Reduces chances of repeated conflicts
• Less predictable
• Often better performance than round-robin in some cases
3. Least Recently Used (LRU) (General Concept)
• Replaces the cache line that was not used for the longest time.
• Requires tracking usage history.
Write Buffers and Measuring Cache Efficiency
A write buffer is a small, fast FIFO (First-In-First-Out) memory placed between the cache
and main memory to temporarily hold data being written to main memory.
Working
• In systems without write buffer:
o Processor writes directly to slow main memory → delay.
• In systems with write buffer:
1. Data is written quickly to the write buffer.
2. Write buffer transfers data slowly to main memory.
Functions
• Reduces processor waiting time during write operations.
• Improves performance during cache line eviction:
o Dirty cache lines are first written to buffer
o Then transferred to main memory later.
Key Features
• Very small and fast memory
• Works as FIFO queue
• May support write merging (coalescing):
o Combines multiple writes into one cache line
Limitations
• Data in write buffer cannot be read until written to main memory.
• Usually has limited size (few cache lines).
2. Measuring Cache Efficiency
Cache efficiency is evaluated using hit rate, miss rate, hit time, and miss penalty.
1. Hit Rate
• Percentage of memory accesses found in cache.
Cache Hits
Hit Rate = × 100
Total Memory Requests
2. Miss Rate
• Percentage of accesses not found in cache.
Cache Misses
Miss Rate = × 100
Total Memory Requests
• Also:
Miss Rate = 100 − Hit Rate
3. Hit Time
• Time required to access data from cache.
4. Miss Penalty
• Time required to fetch data from main memory into cache.