What is Cache?

Cache refers to a component, either hardware or software-based, utilized in computer systems to improve data access speed and overall system performance. By temporarily storing frequently accessed data, instructions, or content, cache enables faster retrieval compared to retrieving them from the original source, such as main memory or disk storage.

Dissecting Cache

Cache was initially introduced in the mid-1960s when computer systems heavily relied on magnetic core memory, which had slower access times. The aim was to overcome this performance limitation by introducing a small and fast memory component located near the CPU. 

This component, known as cache, leveraged the principle of locality of reference to store frequently accessed data or instructions. By storing this data in a smaller and faster memory, cache minimized the need for accessing the slower main memory.

How it Works

Cache functions as an intermediary storage medium positioned between the CPU and the main memory, facilitating efficient data retrieval and enhancing the overall operation of the system. The basic functioning of cache involves:

1. Cache Lookup: When the CPU requests data or instructions, the cache controller first checks if the requested data is present in the cache. It does this by comparing the memory address of the request with the tags associated with each cache line. The tags indicate the memory address range stored in that cache line.
2. Cache Hit: If the requested data is found in the cache, it results in a cache hit. The cache controller retrieves the data from the cache and provides it to the CPU, avoiding the longer latency associated with retrieving it from the main memory. This significantly speeds up the data access process.
3. Cache Miss: If the requested data is not found in the cache, it leads to a cache miss. In this case, the cache controller needs to retrieve the data from the main memory. The cache miss triggers a process called cache coherence, where the cache controller determines which cache line to replace with the newly fetched data.
4. Fetch from Main Memory: Upon a cache miss, the cache controller initiates a memory access to fetch the requested data from the main memory. This process involves retrieving the data from the appropriate memory address location and transferring it to the cache.
5. Store in Cache: After fetching the data from the main memory, the cache controller stores it in the cache. The cache line that previously held the data to be replaced is selected based on the cache replacement policy. The fetched data is then stored in the cache line, along with the corresponding tag.
6. Update Cache State: Once the data is stored in the cache, the cache controller updates the cache state to reflect the presence of the newly stored data. This ensures that subsequent requests for the same data can be served from the cache, avoiding further cache misses.

Cache Policies and Algorithms

Cache policies and cache algorithms work together to optimize cache performance, memory utilization, and overall system efficiency. The choice of a specific policy or algorithm depends on factors such as cache size, access patterns, and trade-offs between performance, complexity, and energy efficiency.

Cache Policies

Cache policies, also known as cache replacement policies, determine the rules and criteria used to decide which cache line should be replaced when a cache miss occurs. The goal of cache policies is to maximize cache utilization and minimize performance impact.

• Least Recently Used (LRU): LRU is a popular cache replacement policy. It evicts the cache line that has not been accessed for the longest period of time, assuming that recently accessed data is more likely to be accessed again in the near future.
• Least Frequently Used (LFU): LFU is a policy that considers the frequency of cache line accesses. It evicts the cache line that has been accessed the fewest number of times. This policy aims to prioritize evicting data that is accessed infrequently.
• Random Replacement: The random replacement policy selects a cache line for eviction randomly. It does not consider any access history or frequency. While simple to implement, this policy may not be optimal in terms of cache utilization or performance.
• First-In, First-Out (FIFO): The FIFO policy evicts the cache line that has been in the cache for the longest period of time. It assumes that the oldest cache lines are the least likely to be accessed again soon.
• Pseudo-LRU (PLRU): Pseudo-LRU is a cache policy that approximates the behavior of the LRU policy while requiring less hardware. It uses a binary tree or other data structure to track the access history of cache lines and determine the least recently used line for eviction.
• Adaptive Replacement Cache (ARC): ARC is a self-tuning cache policy that dynamically adjusts the cache replacement decisions based on recent access patterns. It balances between keeping frequently accessed data and making room for new data.

Cache Algorithms

Cache algorithms, also known as cache management algorithms, govern how data is stored, retrieved, and managed within a cache. These algorithms play a crucial role in cache operations and overall system performance. 

• Direct Mapping: In direct mapping, each block of data from the main memory is mapped to a specific cache line. This mapping is based on a simple arithmetic formula using the memory address. Direct mapping has a one-to-one correspondence between memory blocks and cache lines, but it can lead to conflicts and limited flexibility.
• Set-Associative Mapping: Set-associative mapping divides the cache into multiple sets, each containing multiple cache lines. Each memory block can be mapped to any cache line within a specific set. The choice of the cache line within a set is usually determined by a replacement policy, such as LRU or random replacement.
• Fully Associative Mapping: Fully associative mapping allows each memory block to be placed in any cache line, regardless of the set. This provides maximum flexibility but requires additional hardware, such as content-addressable memory (CAM), to perform the lookup. Replacement policies like LRU or random replacement are typically used to select the cache line for eviction.
• Write-Through: Write-through is a cache write policy where any modifications made to the cache are immediately propagated to the main memory. This ensures that the data in the cache and the main memory are always consistent but can result in increased memory traffic.
• Write-Back: Write-back is a cache write policy where modifications are initially made only in the cache. The updated data is written back to the main memory only when the cache line is evicted. This reduces memory traffic but requires additional complexity in managing dirty cache lines and ensuring data consistency.
• Write-Allocate: Write-allocate is a cache write policy where, on a cache miss for a write operation, the entire cache block is fetched into the cache before the write operation is performed. This ensures that subsequent accesses to nearby memory locations can benefit from the already fetched data.
• No-Write-Allocate: No-write-allocate is a cache write policy where, on a cache miss for a write operation, the modified data is written directly to the main memory without fetching the entire cache block into the cache. This avoids unnecessary data transfers when subsequent accesses are unlikely.