4.3 Elements of Cache Design

COS2621 - Computer Organisation · 4. Cache Memory

Elements of Cache Design

Overview of Cache Memory

Cache memory is a small, fast type of volatile memory that provides high-speed data access to the processor. It stores copies of frequently accessed data from main memory, reducing the time it takes to retrieve this data. The design of cache memory is crucial for enhancing system performance.

Types of Cache

There are several types of cache memory, including:

  • Level 1 (L1) Cache: This is the smallest and fastest cache, located inside the CPU. It is typically split into instruction and data caches.
  • Level 2 (L2) Cache: Larger than L1, this cache is slower but still faster than main memory. It may be located on the CPU chip or nearby.
  • Level 3 (L3) Cache: This is even larger and slower than L2 cache and is shared among multiple cores in a multi-core processor.

Cache Memory Principles

Cache memory operates on several principles, including:

  • Locality of Reference: Programs tend to access a relatively small portion of their address space at any given time. This principle is divided into:
    • Temporal Locality: Recently accessed data is likely to be accessed again soon.
    • Spatial Locality: Data located close to recently accessed data is likely to be accessed soon.
  • Hit and Miss: A cache hit occurs when the data requested by the CPU is found in the cache, while a cache miss occurs when it is not. The miss rate is a critical performance metric.

Cache Mapping Techniques

Cache design involves selecting a mapping technique to determine how data is stored in the cache. The three main techniques are:

  • Direct Mapping: Each block of main memory maps to exactly one cache line. For example, if a cache has 16 lines and the main memory has 256 blocks, the mapping can be calculated as follows:
  • Cache Line = (Block Number) mod (Number of Cache Lines)

    If Block 10 is accessed, it maps to Cache Line 10 mod 16 = 10.

    Watch out: Direct mapping can lead to high conflict misses if multiple blocks map to the same line.

  • Associative Mapping: Any block can be placed in any line of the cache, which reduces conflict misses but increases complexity.
  • Set Associative Mapping: The cache is divided into sets, and each block maps to a specific set. For example, in a 2-way set associative cache, each block can go into one of two lines in its set.

Replacement Policies

When a cache miss occurs and the cache is full, a replacement policy determines which block to evict. Common policies include:

  • Least Recently Used (LRU): The block that has not been used for the longest time is replaced.
  • First-In-First-Out (FIFO): The oldest block in the cache is replaced.
  • Random Replacement: A block is chosen at random for replacement.

Example of Cache Design

Consider a cache with 4 lines and a block size of 1 byte. If the following memory addresses are accessed in order: 0, 1, 2, 3, 0, 4, 1, 2, the cache behavior can be analyzed:

Access 0: Cache Miss (Load 0 into line 0)  
Access 1: Cache Miss (Load 1 into line 1)  
Access 2: Cache Miss (Load 2 into line 2)  
Access 3: Cache Miss (Load 3 into line 3)  
Access 0: Cache Hit  
Access 4: Cache Miss (Replace line 0 with 4)  
Access 1: Cache Hit  
Access 2: Cache Hit

This example shows how cache hits and misses affect performance.

Conclusion

Understanding cache design elements is essential for optimizing computer performance. The choice of mapping technique and replacement policy significantly impacts the efficiency of cache memory.

Check your understanding

  1. What are the main types of cache memory?
  2. Explain the concept of locality of reference.
  3. What is the difference between direct mapping and associative mapping?
  4. Describe the LRU replacement policy.

Test yourself

4 quick questions on this lesson. Pick an answer to see if you're right.

  1. 1. Which type of cache is the fastest and located inside the CPU?

  2. 2. What is the primary purpose of cache memory in a computer system?

  3. 3. What does a cache hit indicate?

  4. 4. Which cache mapping technique allows any block to be placed in any line of the cache?