Skip to main content

Cache Basics and Cache Mapping Techniques

Image
By

 

Cache Basics and Cache Mapping Techniques 



Modern processors execute billions of instructions every second. However, processor speed has increased much faster than main memory (RAM) speed. This difference, known as the memory wall, creates a performance bottleneck because the CPU often has to wait for data from slower memory. To solve this problem, computer systems use cache memory—a small, high-speed memory located between the CPU and the main memory.

In this article, we will understand the fundamentals of cache memory, the principle of locality, cache organization, and the three major cache mapping techniques.



What is Cache Memory?

Cache memory is a small, high-speed memory that stores copies of frequently accessed data from the main memory. Since accessing cache is much faster than accessing RAM, the CPU first checks whether the required data is available in the cache.

If the data is found in the cache, it is called a cache hit. Otherwise, the CPU fetches the data from the main memory, resulting in a cache miss.

CPU
 │
 ▼
Cache Memory
 │
 ▼
Main Memory

The primary objective of cache memory is to reduce the Average Memory Access Time (AMAT).

Why Do We Need Cache Memory?

Without cache memory, every memory request would go directly to RAM, causing significant delays.

For example,

  • CPU access time: ~1 ns
  • Main memory access time: ~100 ns

This means the CPU would spend most of its time waiting for data.

Cache memory bridges this speed gap by storing recently and frequently used information.

Principle of Locality

Cache memory works because most programs do not access memory randomly. Instead, they follow predictable patterns known as the Principle of Locality.

There are two important types of locality.

1. Temporal Locality

Temporal locality states that recently accessed data is likely to be accessed again in the near future.

Example

for(int i=0; i<1000; i++)
{
    sum += A[0];
}

The value A[0] is accessed repeatedly.

Keeping it in cache avoids multiple accesses to main memory.

2. Spatial Locality

Spatial locality states that memory locations near a recently accessed location are likely to be accessed soon.

Example

for(int i=0; i<1000; i++)
{
    sum += A[i];
}

After accessing A[0], the processor will likely access A[1], A[2], and so on.

Therefore, cache loads an entire block instead of a single byte.

Cache Line (Cache Block)

The smallest unit transferred between the main memory and the cache is called a cache line or cache block.

Byte0 Byte1 Byte2 Byte3 ... Byte(B−1)

|---- Cache Block ----|

Block Size = B Bytes

Instead of fetching a single byte, the processor fetches an entire block.

Common cache block sizes are:

  • 32 Bytes
  • 64 Bytes
  • 128 Bytes

Important Cache Terminology

Cache Size (C)

The total storage capacity of the cache.

Example:

Cache Size = 32 KB

Block Size (B)

The number of bytes stored in one cache line.

Example:

Block Size = 64 Bytes

Number of Cache Blocks

The number of blocks present in the cache is

Number of Blocks=CB\text{Number of Blocks}=\frac{C}{B}

Example

Cache Size = 32 KB
Block Size = 64 Bytes

Blocks = 32768 / 64 = 512

Memory Address Breakdown

Every memory address is divided into three fields.



Tag

Used to identify whether the requested block is actually stored in the selected cache location.

Index

Selects the cache line or cache set.

Block Offset

Selects the required byte inside the cache block.

Cache Mapping Techniques

A cache cannot store the entire main memory.

Therefore, we need a mapping technique to determine where a memory block should be placed inside the cache.

There are three major cache mapping methods.

  1. Direct Mapping
  2. Set Associative Mapping
  3. Fully Associative Mapping

1. Direct Mapped Cache

In a Direct Mapped Cache, every memory block maps to exactly one cache line.



Notice that multiple memory blocks compete for the same cache line.

Advantages

  • Very simple implementation
  • Fast hardware
  • Low cost
  • Easy indexing

Disadvantages

  • High conflict misses
  • Frequent replacement when multiple blocks map to the same line

2. Set Associative Cache

Set Associative Cache is a compromise between Direct Mapping and Fully Associative Mapping.

The cache is divided into sets.

Each set contains multiple cache lines called ways.



However, it can be stored in any way inside that set.

The mapping equation is

Set Index=(Block Number) mod (Number of Sets)\text{Set Index}=(\text{Block Number}) \bmod (\text{Number of Sets})


Advantages

  • Fewer conflict misses
  • Better cache utilization
  • Good balance between performance and hardware complexity

Disadvantages

  • Slightly slower than Direct Mapping
  • Requires multiple tag comparisons

3. Fully Associative Cache

In a Fully Associative Cache, any memory block can be placed in any cache line.

Memory Block
      │
      ▼
Any Cache Line

There is no fixed mapping.

The hardware searches all cache lines simultaneously.

Advantages

  • Lowest conflict misses
  • Highest flexibility
  • Best cache utilization

Disadvantages

  • Expensive hardware
  • Requires comparison with every cache line
  • High power consumption

Comparison of Cache Mapping Techniques



Cache Hit and Cache Miss

Whenever the CPU requests data, two outcomes are possible.

Cache Hit

The requested data is found in the cache.


Result:

  • Fast access
  • Low latency
  • Better performance


Cache Miss

The requested data is not available in the cache.


Result:

  • Slower access
  • CPU waits for RAM
  • Performance decreases

Goal of Cache Memory

The primary goal of cache memory is to reduce the Average Memory Access Time (AMAT) by increasing the cache hit rate.

A well-designed cache should:

  • Maximize cache hits
  • Minimize cache misses
  • Reduce CPU waiting time
  • Improve overall system performance

Key Takeaways

  • Cache memory is a small, fast memory placed between the CPU and main memory.
  • It stores frequently used data to reduce memory access time.
  • Cache performance relies on Temporal Locality and Spatial Locality.
  • Data is transferred in units called cache blocks (cache lines).
  • Memory addresses are divided into Tag, Index, and Block Offset.
  • Direct Mapped Cache is simple and fast but suffers from conflict misses.
  • Set Associative Cache offers a balance between performance and hardware complexity.
  • Fully Associative Cache provides maximum flexibility with the least conflict misses but requires the most hardware.
  • The effectiveness of a cache is measured by its cache hit rate, which directly impacts processor performance.

Understanding these cache fundamentals is essential before moving on to advanced topics such as cache replacement policies (LRU, FIFO, Random), write-through vs. write-back caches, multi-level cache hierarchies (L1, L2, L3), and Average Memory Access Time (AMAT), which are typically covered in the next stages of computer architecture and cache design.

Labels:

Comments

Post a Comment

Popular posts from this blog

Module 1 — SystemVerilog Basics

By
VLSI Verification  •  SystemVerilog Series Module 1 — SystemVerilog Basics A complete, example-driven walkthrough of SystemVerilog fundamentals: data types, variables vs nets, arrays of every flavor, strings, enums, structs, unions, and typedef — the building blocks every verification engineer needs before UVM. 🧩 Beginner → Intermediate ⏱ ~25 min read 💻 Code Examples Included 📑 Table of Contents Introduction to SystemVerilog Verilog vs SystemVerilog Data Types: 2-State vs 4-State Logic Variables and Nets Arrays: Packed vs Unpacked Dynamic Arrays Queues Associative Arrays Strings Enumerations Structures Unions Typedef 1 Introduction to SystemVerilog SystemVerilog (IEEE 1800) is a unified hardware description and verification language (HDVL). It extends Verilog (IEEE 1364) with powerful constructs for design (interfaces, always_comb/always_ff, enhanced d...
Post a Comment
Read more

GPU Memory System & Interconnect: How Data Travels Inside a Modern GPU

By
GPU Memory System & Interconnect: How Data Travels Inside a Modern GPU Modern GPUs deliver incredible computing power by processing thousands of operations simultaneously. While compute cores often receive the spotlight, the real performance of a GPU depends heavily on how efficiently data moves between memory and compute units. A GPU memory system is designed to provide extremely high bandwidth while keeping latency as low as possible. This is achieved through a collection of specialized hardware components working together, including the Memory Controller, HBM/GDDR memory, Crossbar, Network-on-Chip (NoC), DMA Engine, PCIe Interface, and NVLink. In this article, we'll explore each component in detail and understand how they collectively enable high-performance parallel computing. Why Does GPU Memory Matter? Every GPU application—from gaming and graphics rendering to AI model training and scientific simulations—requires continuous movement of enormous amounts of data. For examp...
Post a Comment
Read more

Clock Domain Crossing (CDC): A Complete Beginner's Guide to Metastability, Synchronizers & Safe Data Transfer

By
Clock Domain Crossing (CDC): A Complete Beginner's Guide to Metastability, Synchronizers & Safe Data Transfer Modern System-on-Chip (SoC) designs rarely operate with a single clock. Instead, different modules such as CPUs, GPUs, memory controllers, communication interfaces, and peripherals often run at different clock frequencies or even use completely independent clock sources . When data moves from one clock domain to another, timing uncertainty can cause serious problems such as metastability , data corruption , and unpredictable system behaviour . This challenge is known as Clock Domain Crossing (CDC) . CDC is one of the most important topics in ASIC Design , RTL Design , ASIC Verification , FPGA Design , and SoC Architecture . Every modern chip—from smartphones to automotive processors—uses CDC techniques to ensure reliable communication between multiple clock domains. In this article, we'll explore CDC fundamentals, metastability, synchronization techniques, asynchro...
Post a Comment
Read more

AXI Verification Interview Questions and Real-World Debugging

By
AMBA Protocol Series · Part 10 of 10 AXI Verification Interview Questions and Real-World Debugging Common protocol violations, how to read them off a waveform, and a curated set of interview questions with concise, correct answers — the capstone of the core 10-day series. AMBA Protocol Series: From APB & AHB to AXI — A Complete Guide for VLSI Engineers This wraps up the core 10-day series. Everything here draws directly on Days 1–9 — if any answer below feels unfamiliar, that's a good signal for which earlier post to revisit. (If you want to go further, see the 20-day extended list at the end of this post.) In This Article Common Protocol Violations Debugging From a Waveform Interview Questions and Answers Series Recap Extending the Series 1. Common Protocol Violations VALID deasserted before handshake — a source drops VALID before READY ever went high (violates the Day 8 stabi...
Post a Comment
Read more

Timing Basics in Static Timing Analysis (STA): Delay Models, Sequential Timing, and Wire Delays

By
Timing Basics in Static Timing Analysis (STA) Static Timing Analysis (STA) is one of the most important verification techniques used in modern VLSI design. Before a chip is manufactured, engineers must verify that every signal reaches its destination within the required clock period. Even if a design passes functional simulation, it may still fail after fabrication because of timing violations. Unlike simulation, Static Timing Analysis mathematically analyzes every timing path without applying input test vectors. This makes STA significantly faster and capable of analyzing millions of timing paths efficiently. Table of Contents What is Static Timing Analysis? Why STA is Required Propagation Delay Contamination Delay Cell Delay Models Combinational Gate Delay Sequential Timing Setup Time Hold Time Wire Delay RC Delay Model PVT Corners Worked Examples Interview Questions Key Takeaways What is Static Timing Analysis? Static Ti...
Post a Comment
Read more

Computer Architecture Interview Question Part 1

By
Skip to content Computer Architecture Interview Series Part 1 · CPU Basics · RISC vs CISC · ISA 50 Most Asked Computer Architecture Interview Questions (Part 1) The foundational round every VLSI, ASIC, and CPU design interview opens with: instruction set architecture, RISC vs CISC trade-offs, Von Neumann vs Harvard design, registers, endianness, and the fetch-decode-execute cycle — explained the way interviewers actually expect you to answer.  40 Questions (Q1–Q40) ⌛ 22 min read  VLSI & Computer Architecture Interviews On this page Foundations of Computer Architecture RISC vs CISC — Core Differences Von Neumann, Harvard & the Semantic Gap Architecture Styles, Endianness & Registers ILP, VLIW, Superscalar & Amdahl's Law Register Files, Microcontrollers & the Fetch Cycle Tip...
Post a Comment
Read more