Direct Mapping

Concept of Direct Mapping

Direct mapping is a cache mapping technique where each block of main memory is mapped to exactly one location in the cache using a simple modulo operation. The address of a memory block is divided into three fields: the tag, index, and block offset. The index field identifies the specific cache line, while the tag field helps to verify if the data in the indexed cache line corresponds to the requested memory block.

This mapping method is straightforward to implement due to its simplicity, making it suitable for hardware implementations that prioritize speed. However, direct mapping may lead to frequent cache misses in cases where multiple memory blocks map to the same cache line, a situation known as cache thrashing.

Implementation of Direct Mapping

In direct mapping, each memory block is placed in a cache line determined by the formula:

Cache Line Number = (Memory Block Address) % (Number of Cache Lines)

For example, if there are 16 cache lines, and the memory block address is 18, the block will be stored in the cache line number 18 % 16 = 2. The tag field is then used to ensure that the data in cache line 2 corresponds to the requested memory block during access.

Associative Mapping

Concept of Associative Mapping

Associative mapping is a more flexible cache mapping technique where a memory block can be stored in any cache line rather than being restricted to a specific one. This is achieved by using a tag field that identifies which memory block is currently stored in each cache line. During access, the cache searches all lines in parallel for the tag that matches the requested memory address.

While this technique offers more flexibility and reduces the risk of cache thrashing, it requires more complex hardware to compare tags across all cache lines simultaneously. The increased hardware complexity can lead to higher costs and power consumption, making associative mapping more suitable for smaller caches.

Implementation of Associative Mapping

In fully associative mapping, any memory block can be placed in any cache line. During data retrieval, the cache checks each line for a matching tag, which indicates that the desired data is present. The implementation relies on a process called *tag comparison*, where all cache lines are searched in parallel for a match.

For example, if a memory block with address 25 is requested, the cache will search through all lines to see if any contain a tag that matches the address. If a match is found, the corresponding data is retrieved; otherwise, the memory block is loaded into an available cache line, possibly replacing an existing one based on the cache replacement policy.

Comparison Between Direct and Associative Mapping

Aspect	Direct Mapping	Associative Mapping
Simplicity	Simpler to implement with a straightforward mapping function. Requires less hardware.	More complex due to the need for tag comparison across all cache lines.
Flexibility	Each memory block is mapped to a specific cache line, increasing chances of conflicts.	Offers greater flexibility since any memory block can be stored in any cache line.
Performance	Prone to cache thrashing, which can lead to lower hit rates in some scenarios.	Typically higher hit rates due to reduced conflict misses, leading to better performance.
Cost and Complexity	Lower cost and power consumption due to simpler hardware requirements.	Higher cost and power consumption due to complex comparison logic.

Hybrid Mapping Techniques

Hybrid mapping techniques combine elements of both direct and associative mapping to balance performance and hardware complexity. The most common hybrid technique is the *set-associative cache*, where the cache is divided into multiple sets, and each memory block maps to a specific set, but can be placed in any line within that set.

Set-associative mapping is typically implemented as n-way set-associative, where n refers to the number of lines in each set. For example, in a 4-way set-associative cache, each memory block maps to a specific set and can occupy any of the 4 cache lines within that set.

This approach offers a middle ground between direct and fully associative caches, reducing the likelihood of conflicts compared to direct mapping while avoiding the high hardware complexity of fully associative caches. Set-associative caches are widely used in modern CPU designs due to their balanced approach.