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 Problem – Example 3

This example demonstrates how to analyze a set-associative cache system and determine the following parameters:

  • Number of cache lines
  • Number of sets
  • Main memory size
  • Address field breakdown
  • Number of comparators
  • Comparator size

Given Information

Parameter Value
Cache Size 218 bytes
Block Size 210 bytes
Lines per Set 8 lines
Tag Size 7 bits
Addressing Byte Addressable

Step 1 – Number of Cache Lines

The number of cache lines can be calculated as: 


Number of Lines = Cache Size / Block Size


Cache Size  = 2^18 bytes
Block Size  = 2^10 bytes

Lines = 2^18 / 2^10
Lines = 2^8
Total Cache Lines = 256 lines

Step 2 – Number of Sets

Each set contains 8 lines (8-way set associative). 


Number of Sets = Total Lines / Lines per Set


Sets = 2^8 / 2^3
Sets = 2^5
Total Sets = 32 sets

Step 3 – Frames Mapped to Each Set

The tag size is 7 bits. This means each set can correspond to: 


2^7 frames

Therefore, 128 frames from RAM map to each set.

Step 4 – Number of Frames in RAM

Total frames in RAM: 


Frames = Number of Sets × Frames per Set


Frames = 2^5 × 2^7
Frames = 2^12
Total Frames in RAM = 2^12

Step 5 – Main Memory Size

Each frame has the same size as the block: 


Frame Size = 2^10 bytes

Total RAM size: 


RAM Size = Frames × Frame Size
RAM Size = 2^12 × 2^10
RAM Size = 2^22 bytes
Main Memory Size = 2^22 bytes (4 MB)

Step 6 – Physical Address Size

Since RAM size is: 


2^22 bytes

The physical address must contain:

Physical Address Size = 22 bits

Step 7 – Address Format

A physical address in set-associative cache is divided into: 


| Tag | Set Index | Block Offset |

Field sizes:

  • Block Offset = log₂(2^10) = 10 bits
  • Set Index = log₂(32) = 5 bits
  • Tag = 22 − (10 + 5) = 7 bits

Step 8 – Number of Comparators

In set-associative caches, the number of comparators equals the number of lines per set. 


Comparators = 8
Number of Comparators = 8

All comparators operate in parallel to compare the incoming tag with the tags stored in each line of the selected set.

Step 9 – Comparator Size

Comparator size depends on the number of tag bits. 


Tag Size = 7 bits
Comparator Size = 7-bit comparator

How the CPU Accesses Data

  1. The CPU generates a 22-bit physical address.
  2. The set index selects one of the 32 cache sets.
  3. The tag is compared with the tags of the 8 lines inside that set.
  4. If any comparator matches → Cache Hit.
  5. If none match → Cache Miss, and the block is fetched from RAM.

Final Results

Parameter Result
Total Cache Lines 256
Number of Sets 32
Lines per Set 8
Main Memory Size 4 MB
Physical Address Size 22 bits
Tag Bits 7 bits
Set Bits 5 bits
Offset Bits 10 bits
Comparators 8
Comparator Size 7-bit

Key Concepts

  • Cache lines = Cache Size ÷ Block Size
  • Sets = Total Lines ÷ Lines per Set
  • Tag size determines how many frames map to a set
  • Comparator count = associativity (lines per set)
  • Comparator width = tag size