🧠

Cache Mapping Lecture Notes

Jul 13, 2024

Cache Mapping Lecture Notes

Introduction

  • Topic: Mapping accesses to caches
  • Example Cache: 128 bytes of storage, 12-bit addresses
  • Simplification: Uses 12-bit addresses instead of typical 32 or 64-bit addresses

Example: Direct Mapped Cache

Cache Specifications

  • Block Size: 32 bytes
  • Total Cache Capacity: 128 bytes
  • Address Breakdown:
    • Offset bits: Calculated using log2(block size) = 5 bits
    • Index bits: Calculated using log2(number of sets) = 2 bits
    • Tag bits: Remaining bits in address = 5 bits

Calculations

  1. Offset Bits:
    • log2(32) = 5, so 5 bits are used for offset.
  2. Number of Sets:
    • 128 / 32 = 4 sets
    • log2(4 sets) = 2, so 2 bits for set/index.
  3. Tag Bits:
    • Total = 12 bits
    • Offset = 5 bits
    • Index = 2 bits
    • Remaining for tag = 5 bits

Address Example: 0x060

  • Binary: 0000 0110 0000
  • Offset: Last 5 bits (5 LSB)
  • Set/Index: Next 2 bits
  • Tag: Remaining upper 5 bits

Practical Example

  • Set Representation: 4 sets (0-3)
  • Address Accesses: 9 different addresses examined twice to see the hit/miss pattern

First Pass Accesses

  1. Address 0x070: Set 3, Tag 0 → Miss
  2. Address 0x000: Set 0, Tag 1 → Miss
  3. Address 0x060: Set 3, Tag 0 → Hit
  4. Address 0x040: Set 0, Tag 1 → Miss
  5. Address 0x020: Set 0, Tag 1 → Miss
  6. Address 0x0A0: Set 3, Tag 1 → Miss
  7. Address 0x080: Set 0, Tag 1 → Hit
  8. Address 0x0C0: Set 0, Tag 0 → Miss
  9. Address 0x0E0: Set 3, Tag 0 → Miss
  • First Pass Hit Rate: 2 hits out of 9 accesses → ~22%

Second Pass Accesses

  1. Address 0x070: Set 3, Tag 0 → Hit
  2. Address 0x000: Set 0, Tag 1 → Miss
  3. Address 0x060: Set 3, Tag 0 → Hit
  4. Address 0x040: Set 0, Tag 1 → Miss
  5. Address 0x020: Set 0, Tag 1 → Miss
  6. Address 0x0A0: Set 3, Tag 1 → Miss
  7. Address 0x080: Set 0, Tag 1 → Hit
  8. Address 0x0C0: Set 0, Tag 0 → Miss
  9. Address 0x0E0: Set 3, Tag 0 → Miss
  • Second Pass Hit Rate: 3 hits out of 9 accesses → ~33%

Summary

  • Key Concepts: Understanding how to break down an address into offset, index, and tag bits.
  • Hit/Miss Patterns: Analyzing how repeatedly accessing the same addresses can influence hit rate.
  • Practical Insights: Illustrates direct mapped cache behavior and efficiency.

Note: Understanding these concepts is crucial for optimizing cache design and memory management in computer systems.

Full transcript