MODULE 4 COA

MEMORY INTERLEAVING
Memory Interleaving is a technique used to increase the speed of memory access by splitting
memory into multiple modules (banks) and accessing them in parallel.
 Instead of storing the entire block of data in a single module, memory addresses are
distributed across multiple modules in a round-robin fashion.
 This allows the CPU to fetch the next instruction/data while the previous one is still being
accessed, improving throughput.
Need for Memory Interleaving
 CPU executes instructions much faster than memory can supply data (memory bottleneck
problem).
 Without interleaving, CPU must wait for each memory access to complete.
 Interleaving ensures that while one module is busy, the CPU can access another, reducing
wait time.
Benefits of Memory Interleaving
 Higher Bandwidth: Multiple memory banks work in parallel, so more data can be
transferred at once.y.
 Lower Latency: While one bank is busy, others get ready, reducing wait time.
 Better Performance: Together, higher bandwidth and lower latency make the system faster
and more efficient, especially for heavy tasks and multitasking

CONCEPT OF HIERARCHICAL MEMORY ORGANIZATION
In the Computer System Design, Memory Hierarchy is an enhancement to organize the memory
such that it can minimize the access time. The Memory Hierarchy was developed based on a
program behavior known as locality of references (same data or nearby data is likely to be
accessed again and again). The figure below clearly demonstrates the different levels of the
memory hierarchy.
Why Memory Hierarchy is Required in the System?
Memory Hierarchy helps in optimizing the memory available in the computer. There are
multiple levels present in the memory, each one having a different size, different cost, etc.
Some types of memory like cache, and main memory are faster as compared to other types of
memory but they are having a little less size and are also costly whereas some memory has a
little higher storage value, but they are a little slower. Accessing of data is not similar in all types
of memory, some have faster access whereas some have slower access.
Types of Memory Hierarchy
This Memory Hierarchy Design is divided into 2 main types:
 External Memory or Secondary Memory: Comprising of Magnetic Disk, Optical Disk, and
Magnetic Tape i.e. peripheral storage devices which are accessible by the processor via an
I/O Module.
 Internal Memory or Primary Memory: Comprising of Main Memory, Cache Memory & CPU
registers. This is directly accessible by the processor.
 Memory Hierarchy Design
1. Registers
Registers are small, high-speed memory units located in the CPU. They are used to store the
most frequently used data and instructions. Registers have the fastest access time and the
smallest storage capacity, typically ranging from 16 to 64 bits.
2. Cache Memory
Cache memory is a small, fast memory unit located close to the CPU. It stores frequently used
data and instructions that have been recently accessed from the main memory. Cache
memory is designed to minimize the time it takes to access data by providing the CPU with
quick access to frequently used data.
3. Main Memory
Main memory, also known as RAM (Random Access Memory), is the primary memory of a
computer system. It has a larger storage capacity than cache memory, but it is slower. Main
memory is used to store data and instructions that are currently in use by the CPU.
Types of Main Memory
 Static RAM: Static RAM stores the binary information in flip flops and information remains
valid until power is supplied. Static RAM has a faster access time and is used in implementing
cache memory.
 Dynamic RAM: It stores the binary information as a charge on the capacitor. It requires
refreshing circuitry to maintain the charge on the capacitors after a few milliseconds. It
contains more memory cells per unit area as compared to SRAM.
read more about - Different Types of RAM (Random Access Memory)
4. Secondary Storage
Secondary storage, such as hard disk drives (HDD) and solid-state drives (SSD) , is a non-volatile
memory unit that has a larger storage capacity than main memory. It is used to store data and
instructions that are not currently in use by the CPU. Secondary storage has the slowest access
time and is typically the least expensive type of memory in the memory hierarchy.
5. Magnetic Disk
Magnetic Disks are simply circular plates that are fabricated with either a metal or a plastic or a
magnetized material. The Magnetic disks work at a high speed inside the computer and these
are frequently used.
6. Magnetic Tape
Magnetic Tape is simply a magnetic recording device that is covered with a plastic
film. Magnetic Tape is generally used for the backup of data. In the case of a magnetic tape, the
access time for a computer is a little slower and therefore, it requires some amount of time for
accessing the strip.
Characteristics of Memory Hierarchy
 Capacity: It is the global volume of information the memory can store. As we move from top
to bottom in the Hierarchy, the capacity increases.
 Access Time: It is the time interval between the read/write request and the availability of
the data. As we move from top to bottom in the Hierarchy, the access time increases.
 Performance: The Memory Hierarch design ensures that frequently accessed data is stored
in faster memory to improve system performance.
 Cost Per Bit: As we move from bottom to top in the Hierarchy, the cost per bit increases i.e.
Internal Memory is costlier than External Memory.
System-Supported Memory Standards
According to the memory Hierarchy, the system-supported memory standards are defined
below:

Advantages of Memory Hierarchy

 Performance: Frequently used data is stored in faster memory (like cache), reducing access
time and improving overall system performance.
 Cost Efficiency: By combining small, fast memory (like registers and cache) with larger,
slower memory (like RAM and HDD), the system achieves a balance between cost and
performance. It saves the consumer's price and time.
 Optimized Resource Utilization: Combines the benefits of small, fast memory and large,
cost-effective storage to maximize system performance.
 Efficient Data Management: Frequently accessed data is kept closer to the CPU, while less
frequently used data is stored in larger, slower memory, ensuring efficient data handling.
Disadvantages of Memory Hierarchy
 Complex Design: Managing and coordinating data across different levels of the hierarchy
adds complexity to the system's design and operation.
 Cost: Faster memory components like registers and cache are expensive, limiting their size
and increasing the overall cost of the system.
 Latency: Accessing data stored in slower memory (like secondary or tertiary storage)
increases the latency and reduces system performance.
 Maintenance Overhead: Managing and maintaining different types of memory adds
overhead in terms of hardware and software.

CACHE MEMORY
Cache memory is a small, high-speed storage area in a computer. It stores copies of the data
from frequently used main memory locations. There are various independent caches in a CPU,
which store instructions and data.
 The most important use of cache memory is that it is used to reduce the average time to
access data from the main memory.
 The concept of cache works because there exists locality of reference (the same items or
nearby items are more likely to be accessed next) in processes.
By storing this information closer to the CPU, cache memory helps speed up the overall
processing time. Cache memory is much faster than the main memory (RAM). When the CPU
needs data, it first checks the cache. If the data is there, the CPU can access it quickly. If not, it
must fetch the data from the slower main memory.
Characteristics of Cache Memory
 Extremely fast memory type that acts as a buffer between RAM and the CPU.
 Holds frequently requested data and instructions, ensuring that they are immediately
available to the CPU when needed.
 Costlier than main memory or disk memory but more economical than CPU registers.
 Used to speed up processing and synchronize with the high-speed CPU.
Levels of Memory
 Level 1 or Register: It is a type of memory in which data is stored and accepted that are
immediately stored in the CPU. The most commonly used register is Accumulator, Program
counter, Address Register, etc.
 Level 2 or Cache memory: It is the fastest memory that has faster access time where data is
temporarily stored for faster access.
 Level 3 or Main Memory: It is the memory on which the computer works currently. It is
small in size and once power is off data no longer stays in this memory.
 Level 4 or Secondary Memory: It is external memory that is not as fast as the main memory
but data stays permanently in this memory.
Cache Performance
When the processor needs to read or write a location in the main memory, it first checks for a
corresponding entry in the cache.
 If the processor finds that the memory location is in the cache, a Cache Hit has occurred and
data is read from the cache.
 If the processor does not find the memory location in the cache, a cache miss has occurred.
For a cache miss, the cache allocates a new entry and copies in data from the main memory,
then the request is fulfilled from the contents of the cache.
The performance of cache memory is frequently measured in terms of a quantity called Hit
ratio.
Hit Ratio(H) = hit / (hit + miss) = no. of hits/total accesses
Miss Ratio = miss / (hit + miss) = no. of miss/total accesses = 1 - hit ratio(H)
We can improve Cache performance using higher cache block size, and higher associativity,
reduce miss rate, reduce miss penalty, and reduce the time to hit in the cache.
Cache Mapping
Cache mapping refers to the method used to store data from main memory into the cache. It
determines how data from memory is mapped to specific locations in the cache.
There are three different types of mapping used for the purpose of cache memory which is as
follows:
 Direct Mapping
 Fully Associative Mapping
 Set-Associative Mapping
1. Direct Mapping
Direct mapping is a simple and commonly used cache mapping technique where each block of
main memory is mapped to exactly one location in the cache called cache line. If two memory
blocks map to the same cache line, one will overwrite the other, leading to potential cache
misses. Direct mapping's performance is directly proportional to the Hit ratio.
Memory block is assigned to cache line using the formula below:
 i = j modulo m = j % m
where,
i = cache line number
j = main memory block number
m = number of lines in the cache
For example, consider a memory with 8 blocks(j) and a cache with 4 lines(m). Using direct
mapping, block 0 of memory might be stored in cache line 0, block 1 in line 1, block 2 in line 2,
and block 3 in line 3. If block 4 of memory is accessed, it would be mapped to cache line 0 (as i =
j modulo m i.e. i = 4 % 4 = 0), replacing memory block 0.
The Main Memory consists of memory blocks and these blocks are made up of fixed number of
words. A typical address in main memory is split into two parts:
1. Index Field: It represent the block number. Index Field bits tells us the location of block
where a word can be.
2. Block Offset: It represent words in a memory block. These bits determines the location of
word in a memory block.
The Cache Memory consists of cache lines. These cache lines has same size as memory blocks.
The address in cache memory consists of:
1. Block Offset: This is the same block offset we use in Main Memory.
2. Index: It represent cache line number. This part of the memory address determines which
cache line (or slot) the data will be placed in.
3. Tag: The Tag is the remaining part of the address that uniquely identifies which block is
currently occupying the cache line.
CACHE SIZE VS BLOCK SIZE
No. Cache Size Block Size (Cache Line Size)
1 Total storage capacity of the cache Size of one cache line transferred at a time
Measured in KB or MB (e.g., 32KB,
2 Measured in bytes (e.g., 32B, 64B)
1MB)
Determines how much data can be Determines how much data is fetched per memory
3
stored overall access
4 Affects capacity misses Affects compulsory and conflict misses
Larger cache → generally higher hit
5 Larger block → better spatial locality (up to a limit)
rate
Increasing it increases hardware cost
6 Increasing it increases memory bandwidth usage
significantly
7 Larger size may increase access latency Larger block size increases miss penalty
Does not directly affect data transfer
8 Directly determines memory-to-cache transfer size
unit size
Number of blocks = Cache Size ÷ Block Larger block size reduces total number of blocks (if
9
Size cache size fixed)
Impacts overall system performance
10 Impacts data locality efficiency
capacity
 MAPPING FUNCTIONS
In modern computer systems, the speed difference between the processor and main memory
(RAM) can significantly affect system performance. To bridge this gap, computers use a small,
high-speed memory known as cache memory. But since cache is limited in size, the system
needs a smart way to decide where to place data from main memory — and that’s where cache
mapping comes in.
 Cache mapping is a technique used to determine where a particular block of main memory
will be stored in the cache.
 It defines how and where that new data block from main memory will be placed inside the
cache.
Cache-RAM Mapping
Key Terminologies in Cache Mapping
Before diving into mapping techniques, let’s understand some important terms:
1. Main Memory Blocks: The main memory is divided into equal-sized sections called blocks.
2. Cache Lines (or Cache Blocks): The cache memory is also divided into equal partitions called
cache lines.
3. Block Size: The number of bytes or words stored in one block or line.
4. Tag Bits: A small portion of the address used to identify which block of main memory is
stored in a particular cache line.
5. Number of Cache Lines: Determined by the ratio of Cache Size ÷ Block Size.
6. Number of Cache Sets: Determined by Number of Cache Lines ÷ Associativity (used in set-
associative mapping).
Types of Cache Mapping
There are three main cache mapping techniques used in computer systems:
1. Direct Mapping
In Direct mapping, each block of main memory maps to exactly one specific cache line. The
main memory address is divided into three parts:
1. Tag Bits: Identify which block of memory is stored.
2. Line Number: Indicates which cache line it belongs to.
3. Byte Offset: Specifies the exact byte within the block.
Direct Mapping
The formula for finding the cache line is:
Cache Line Number=(Block Number) MOD (Number of Cache Lines)
2. Fully Associative Mapping
In fully associative mapping, a memory block can be stored in any line of the cache. The address
is divided into:
1. Tag Bits: Identify the memory block.
2. Byte Offset: Specifies the byte within that block.
Fully Associative Mapping
There is no line number here because placement is flexible — any block can go into any cache
line.
 3. Set-Associative Mapping
Set-associative mapping combines the benefits of both direct and fully associative mapping.
 The cache is divided into a number of sets, each containing a few lines (e.g., 2-way, 4-way
set associative).
 A memory block maps to exactly one set, but can be placed in any line within that set.
2-way Set Associative Mapping
The address is divided into:
1. Tag Bits: Identify which memory block is stored.
2. Set Number: Determines which cache set it belongs to.
3. Byte Offset: Specifies the byte position.
The mapping formula is:
Set Number = (Block Number) MOD (Number of Sets)
Need for Cache Mapping
Cache mapping is essential for two main reasons:
1. Locate Data Efficiently: It helps the processor quickly determine whether the required data
is in the cache (cache hit) or must be fetched from main memory (cache miss).
2. Manage Data Placement: When a cache miss occurs, mapping tells the system where in the
cache to place the new memory block.
Essentially, it’s like assigning a “home address” in the cache for every block of main memory.
Comparison Table
Here is a simple comparison among cache mapping types:
Direct
Feature Mapping Fully Associative MappingSet-Associative Mapping

Placement Rule Fixed location Any location Limited (within a set)

Hardware Cost Low High Moderate

Access Time Fast Slow Moderate

Conflict Misses High None Low

Flexibility Low High Medium

Real-Life Analogy
Imagine a parking lot:
 Direct Mapping: Each car has a fixed parking spot number.
 Fully Associative: Any car can park in any spot.
 Set-Associative: Cars are assigned to a specific section, but can park in any space within that
section.
REPLACEMENT ALGORITHMS
A replacement algorithm determines which cache block to remove when a new block must be
loaded into a full cache.
When a cache miss occurs and no empty block is available, the replacement policy decides the
victim block.
🔟 Major Cache Replacement Algorithms
1️⃣ FIFO (First-In First-Out)
 Replaces the block that was inserted first.
 Simple to implement.
 Does not consider usage frequency.
Advantage: Easy hardware design
Disadvantage: May remove frequently used block
2️⃣ LRU (Least Recently Used)
 Replaces the block that has not been used for the longest time.
 Based on temporal locality.
Advantage: Good performance
Disadvantage: Complex hardware implementation
3️⃣ MRU (Most Recently Used)
 Replaces the most recently accessed block.
 Useful in some looping patterns.
4️⃣ LFU (Least Frequently Used)
 Replaces the block with the smallest access count.
Disadvantage: Needs counters → more hardware cost
5️⃣ Random Replacement
 Replaces a randomly selected block.
Advantage: Very simple
Used in: Some processors due to low overhead
6️⃣ Optimal Replacement (Belady’s Algorithm)
 Replaces the block that will not be used for the longest time in the future.
 Theoretical model.
Note: Not implementable in real systems (needs future knowledge).
7️⃣ Second Chance (Clock Algorithm)
 Modification of FIFO.
 Gives a block a second chance if recently used.
8️⃣ Pseudo-LRU
 Approximation of LRU.
 Used in modern processors to reduce complexity.
📊 Where Replacement Is Used
 Direct-Mapped Cache → No replacement choice (only 1 block per set)
 Set-Associative Cache → Replacement needed within a set
 Fully Associative Cache → Replacement needed among all blocks
 WRITE POLICIES
Cache write policies play a crucial role in determining how data is written to the cache and main
memory in computing systems. These policies are essential for improving system performance
and ensuring data consistency. This article explains what cache write policies are, explains
various cache write policies in detail, and discusses how to choose and apply the right write
policy for your needs.
Cache Write Policies
Important Topics for Cache Write Policies
 What are Cache Write Policies?
 Types of Caches
 Cache Write Policies
 Write-Allocate vs. No-Write-Allocate
 Combining Write Policies
 Choosing the Right Cache Write Policy
 Applications of Cache Write Policies
 Challenges in Implementing Cache Write Policies
 FAQs for Cache Write Policies
What are Cache Write Policies?
Cache write policies dictate how data modifications in the cache are propagated to the main
memory. The primary goal of these policies is to balance performance and data consistency.
They determine when and how the changes made to the cached data are written back to the
main memory.
Types of Caches
Caches can be broadly categorized into several types based on their position in the memory
hierarchy and their functionality:
 L1 Cache: The first level of cache, closest to the CPU, offering the fastest access times.
 L2 Cache: A larger, slightly slower cache that sits between the L1 cache and main memory.
 L3 Cache: An even larger cache that serves multiple CPU cores.
 Disk Cache: Used to speed up access to data stored on disk drives.
 Web Cache: Stores frequently accessed web content to reduce latency and bandwidth
usage.
Cache Write Policies
1. Write-Through
In the write-through policy, data is written to both the cache and the main memory
simultaneously. This ensures data consistency between the cache and main memory at the cost
of higher write latency.
Write-Through Cache
Advantages
 Ensures data consistency.
 Simplifies the process of maintaining coherency between cache and memory.
Disadvantages
 Slower write operations due to simultaneous writes.
 Increased memory bandwidth usage.
2. Write-Back
The write-back policy, also known as write-behind, allows data to be written only to the cache
initially. The modified data is written to the main memory at a later time, either when the cache
block is evicted or at specific intervals.
Write-Back Cache
Advantages
 Faster write operations as writes are initially only to the cache.
 Reduced memory bandwidth usage.
Disadvantages
 Requires mechanisms to ensure data consistency.
 Complexity in handling cache coherency.
3. Write-Around
In the write-around policy, data is written directly to the main memory, bypassing the cache.
The cache is only updated if the same data is read again.
Write-Around Cache
Advantages
 Reduces cache pollution with infrequently accessed data.
 Suitable for workloads with low write locality.
Disadvantages
 May lead to slower write operations.
 Potential for cache misses on subsequent reads.
Write-Allocate vs. No-Write-Allocate
Below are the differences between Write-Allocate and No-Write Alllocate:
No-Write-Allocate (Write-No-
Feature Write-Allocate (Fetch-on-Write) Allocate)

On a write miss, the block is loaded On a write miss, data is written

into the cache, then the write is directly to memory, bypassing the
Definition performed. cache.

Cache Miss Loads the block into the cache before Does not load the block into the
Handling writing. cache.

Subsequent reads do not benefit

Subsequent reads benefit from the
Subsequent from cache; may result in more
cached data.
Reads cache misses.

Write Can be slower initially due to fetching Can be faster for initial writes as no
Performance block into cache. block fetching is involved.
 No-Write-Allocate (Write-No-
Feature Write-Allocate (Fetch-on-Write) Allocate)

Higher likelihood of cache pollution Reduced cache pollution as blocks

Cache Pollution due to loading on writes. are not loaded on write misses.

Suitable for workloads with

Useful for workloads with frequent
infrequent read-after-write
read-after-write scenarios.
Use Cases scenarios.

Combining Write Policies

Combining write policies involves using different strategies to balance the advantages and
disadvantages of each. This can be tailored to specific use cases and workload characteristics to
optimize performance, consistency, and resource utilization.
1. Write-Through with Write-Allocate
This combination involves writing data to both the cache and main memory simultaneously
(write-through) and loading the block into the cache on a write miss (write-allocate).
Advantages of combining these policies
 Ensures data consistency between cache and memory.
 Benefits subsequent reads by having the data in the cache.
Disadvantages of combining these policies
 Slower write performance due to simultaneous writing to cache and memory.
 Increased memory traffic due to block fetching on write misses.
Example of combining these policies
 Use Case: Database systems where data consistency is crucial, and there are frequent read-
after-write operations.
 Scenario: An online transaction processing system where updates to user account balances
need to be immediately reflected in both cache and main memory for consistency, and
subsequent queries benefit from having the updated balance in the cache.
2. Write-Back with Write-Allocate
This combination involves writing data only to the cache initially (write-back) and updating main
memory later when the cache block is evicted. On a write miss, the block is loaded into the
cache (write-allocate).
Advantages of combining these policies
 Faster write performance due to delayed writing to main memory.
 Benefits from subsequent reads as the data is loaded into the cache.
Disadvantages of combining these policies
 Risk of data loss or inconsistency if the cache fails before writing to memory.
 Increased complexity in tracking dirty cache blocks.
Example of combining these policies
 Use Case: High-performance computing applications where write performance is critical,
and there are frequent read-after-write operations.
 Scenario: A scientific simulation that frequently updates large data sets, benefiting from fast
write performance and subsequent read operations from the cache.
3. Write-Through with No-Write-Allocate
This combination involves writing data to both the cache and main memory simultaneously
(write-through) but not loading the block into the cache on a write miss (no-write-allocate).
Advantages of combining these policies
 Ensures data consistency between cache and memory.
 Reduces cache pollution by not loading blocks on write misses.
Disadvantages of combining these policies
 Slower write performance due to simultaneous writing to cache and memory.
 Subsequent reads may result in more cache misses if the data is not in the cache.
Example of combining these policies
 Use Case: Systems where data consistency is crucial, and write operations are not followed
by immediate reads.
 Scenario: Logging systems where logs are written to both cache and disk for consistency but
are rarely read back immediately, reducing cache pollution.
4. Write-Back with No-Write-Allocate
This combination involves writing data only to the cache initially (write-back) and updating main
memory later when the cache block is evicted. On a write miss, the data is written directly to
memory, bypassing the cache (no-write-allocate).
Advantages of combining these policies
 Faster write performance due to delayed writing to main memory.
 Reduces cache pollution by not loading blocks on write misses.
Disadvantages of combining these policies
 Risk of data loss or inconsistency if the cache fails before writing to memory.
 Subsequent reads may result in more cache misses if the data is not in the cache.
Example of combining these policies
 Use Case: Write-intensive applications where write performance is critical, and write
operations are not followed by immediate reads.
 Scenario: Batch processing systems where data is written in bulk and processed later,
benefiting from fast write performance and reduced cache pollution.
Choosing the Right Cache Write Policy
1. Factors to consider
1. Write Frequency: How often data is written to the cache.
2. Read Frequency: How often data is read from the cache.
3. Data Consistency Requirements: The importance of keeping cache and main memory data
consistent.
4. System Performance Goals: The balance between read/write performance and overall
system efficiency.
5. Workload Characteristics: The nature of the workload, such as high locality or random
access patterns.
 2. Important scenarios
1. High Consistency Requirements: Use write-through or write-back with write-allocate.
2. High Write Throughput: Use write-back with no-write-allocate.
3. Reduced Memory Bandwidth Usage: Use write-back policies.
Applications of Cache Write Policies
 Database Systems
o Application: Ensures data consistency and optimizes read and write performance
in transactional databases.
o Policy: Write-Through with Write-Allocate for consistency; Write-Back with Write-
Allocate for high-performance analytics.
 Web Servers and Caching Systems
o Application: Improves web content delivery speed and ensures the consistency of
frequently accessed content.
o Policy: Write-Through with No-Write-Allocate to avoid cache pollution for static
content; Write-Back with No-Write-Allocate for dynamic content updates.
 High-Performance Computing (HPC)
o Application: Enhances performance in scientific simulations and data-intensive
computations.
o Policy: Write-Back with Write-Allocate to provide high throughput for frequent
read/write cycles.
 Embedded Systems and IoT Devices
o Application: Ensures data reliability and optimizes power consumption in
resource-constrained environments.
o Policy: Write-Through with Write-Allocate for real-time data consistency; Write-
Back with No-Write-Allocate for efficient power usage.
 Virtualization and Cloud Computing
o Application: Improves virtual machine disk performance and ensures efficient
data management in cloud environments.
o Policy: Write-Back with Write-Allocate for caching VM disk writes and reads to
enhance performance.
Challenges in Implementing Cache Write Policies
 Maintaining Data Consistency: Ensuring that the cache and main memory are synchronized.
 Managing Cache Coherency: Handling coherency in multi-core systems.
 Performance Overheads: Balancing performance trade-offs in different write policies.
 Complexity: Implementing and managing complex cache control mechanisms.
Conclusion
Understanding and implementing the right cache write policy is essential for optimizing system
performance and ensuring data consistency. Each write policy has its own set of advantages
and challenges, and the choice depends on the specific requirements of the application and
workload. By carefully considering the factors and scenarios discussed in this article, you can
select the most suitable cache write policy for your needs.