Introduction
Cache Basics Direct Mapped Cache Direct Mapped Example 1 Direct Mapped Example 2 Direct Mapped Problem 1 Direct Mapped Problem 2 Direct Mapped Problem 3 Direct Mapped Problem 4 Direct Mapped Comparators Direct Mapped Disadvantages Direct Mapped Locality Direct Mapped UVM Example Associative Mapped Cache Associative Mapped Problem 1 Associative Mapped Problem 2 Associative Mapped Problem 3 Associative Mapped Problem 4 Set Associative Mapped Cache Set Associative Mapped Comparators Set Associative Mapped Problem 1 Set Associative Mapped Problem 2 Set Associative Mapped Problem 3 Set Associative Mapped Problem 4 Set Associative Mapped Problem 5 Other Mapping Problem - Example 1 Cache Replacement Algorithms LRU Cache Replacement Algorithm FIFO Cache Replacement Algorithm MRU Cache Replacement Algorithm PLRU Cache Replacement Algorithm Round Robin Cache Replacement Algorithm
UVMArena

Set Associative Cache Memory

Set Associative Cache is the most commonly used cache organization in modern CPUs. It combines the advantages of Direct Mapped Cache and Fully Associative Cache while reducing their disadvantages.

Motivation

Before understanding set associative mapping, it is useful to recall the two basic cache mapping techniques.

Mapping Technique Advantages Disadvantages
Direct Mapping Simple hardware, very fast lookup High number of conflict misses
Fully Associative Very flexible, almost no conflict misses Requires many comparators and expensive hardware

Set Associative Mapping combines both approaches to create a balanced solution.

Concept of Set Associative Cache

In a set associative cache, the cache is divided into multiple sets. Each set contains multiple cache lines.

The number of lines in each set is called the associativity.

Examples:
  • 2-way set associative → 2 lines per set
  • 4-way set associative → 4 lines per set
  • 8-way set associative → 8 lines per set

Within a set, blocks can be placed in any line of the set.

Example Cache Organization

Assume a cache with 16 cache lines. If the cache is organized as a 4-way set associative cache, each set contains 4 lines. 


Total Cache Lines = 16
Associativity = 4

Number of Sets = 16 / 4
               = 4 sets
The sets would look like this:
Set Number Cache Lines
Set 0 Lines 0 – 3
Set 1 Lines 4 – 7
Set 2 Lines 8 – 11
Set 3 Lines 12 – 15

Address Structure

In set associative mapping, the physical address is divided into three fields. 


Physical Address

+------------+-----------+-----------+
|    TAG     | SET INDEX |  OFFSET   |
+------------+-----------+-----------+
  • Offset → selects a byte inside a block
  • Set Index → selects which set to access
  • Tag → identifies which memory block is stored in the cache line

Mapping Process

When a memory block is loaded into the cache, the system must determine which set the block belongs to.

This is done using a modulo operation: 


Set Number = Frame Number mod Number of Sets
Examples: 

Frame 8  mod 4 = 0 → Set 0
Frame 78 mod 4 = 2 → Set 2
Frame 87 mod 4 = 3 → Set 3
Once the set is determined, the block can be placed in any line within that set.

Cache Access Process

When the CPU generates a physical address, the cache performs the following steps:

  1. Use the set index to locate the correct set.
  2. Compare the tag with the tags stored in all lines of that set.
  3. If a match is found → Cache Hit.
  4. If no match is found → Cache Miss.

Comparators Required

Unlike fully associative caches (which compare against all lines), set associative caches only compare tags