Direct mapping
Direct mapping is a cache memory mapping technique where each main memory block is
mapped to a specific, single cache line, determined by a modulo operation on the block
address.
How it works:
Mapping: Each main memory block can only be stored in one specific cache line.
Calculation: The cache line number to which a block maps is calculated using:
Cache Line Number = (Block Address of Main Memory) Modulo (Total Number of Lines in
Cache).
Address Decomposition: A memory address is divided into three fields: tag, index, and block
offset.
Index: Identifies the specific cache line.
Tag: Verifies if the data in the indexed cache line corresponds to the requested memory block.
Advantages:
Simplicity: Direct mapping is easy to implement in hardware due to its straightforward nature.
Disadvantages:
Potential for Cache Misses: If multiple frequently accessed memory blocks map to the same
cache line, it can lead to frequent cache misses, a phenomenon known as "cache thrashing".
No Replacement Algorithm: In direct mapping, there is no need for a replacement algorithm
because each main memory block maps to a specific cache line.
Many-to-one mapping: Each main memory block can map to only one cache line.
Associative mapping
Associative mapping is a cache memory organization technique where any main memory block
can be stored in any cache line, offering greater flexibility and reducing cache thrashing
compared to direct mapping, but requiring more complex hardware.
Associative mapping allows a memory block to be stored in any available cache line, rather than
being restricted to a specific location.
How it works:
A tag field is used to identify which memory block is stored in each cache line.
During a cache access, the CPU searches all cache lines in parallel for a matching tag.
If a match is found (a "hit"), the data is retrieved from the cache.
If no match is found (a "miss"), the data is fetched from main memory and loaded into the
cache.
Advantages:
Flexibility: Any memory block can be stored in any cache line, reducing the likelihood of cache
thrashing (where frequently accessed blocks are repeatedly evicted and reloaded).
Reduced conflict misses: With direct mapping, multiple memory blocks can map to the same
cache location, leading to conflict misses. Associative mapping avoids this by allowing blocks to
be placed anywhere.
Disadvantages:
Hardware Complexity: Associative mapping requires more complex hardware to search all
cache lines in parallel for a match, leading to higher costs and power consumption.
Higher Hit Latency: The parallel search across all cache lines can result in a slightly longer time
to find a cache hit compared to direct mapping.
Set-associative mapping
set-associative mapping is a cache memory organization that divides the cache into sets,
allowing a main memory block to map to any line within its assigned set, offering a compromise
between direct and fully associative mapping.
Cache Organization:
The cache memory is organized into sets, where each set contains multiple lines (cache
blocks).
Mapping:
A main memory block can be mapped to any of the lines within its corresponding set.
Sets:
A main memory block is assigned to a specific set based on its address.
Associativity:
The number of lines within each set is called the associativity (e.g., 2-way, 4-way).
Conflict Reduction:
Set-associative mapping reduces cache conflicts compared to direct mapping, as a main
memory block can potentially map to multiple cache lines within its set.
How it Works:
Address Decomposition: A memory address is divided into three parts: tag, index, and offset.
Index Calculation: The index portion of the address is used to determine which set the memory
block belongs to.
Set Selection: The cache controller uses the index to select the corresponding set.
Tag Comparison: Within the selected set, the tag portion of the address is compared with the
tags of the cache lines to find a match.
Line Selection: If a match is found, the data is retrieved from the corresponding cache line.
Replacement: If the cache is full and a new block needs to be loaded, a replacement policy
(e.g., Least Recently Used - LRU) is used to determine which line to replace
Advantages:
Reduced Conflicts: Improves cache hit rates compared to direct mapping by allowing multiple
locations for a given memory block.
Better Performance: Leads to faster access times and improved overall system performance.
Flexibility: Offers a good balance between the speed of direct mapping and the flexibility of fully
associative mapping.
Disadvantages:
Increased Complexity: Requires more complex hardware for set selection and tag comparison.
Higher Cost: Can lead to higher hardware costs compared to direct mapping.
Replacement Overhead: Implementing a replacement policy adds some overhead.
Example:
Imagine a 2-way set-associative cache with 4 sets. Each set has 2 lines. A main memory block
can be mapped to either of the two lines within its designated set.