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 1

In this example we solve a typical set-associative cache problem. The goal is to determine:

  • Physical address structure
  • Number of sets
  • Total number of cache lines
  • Total cache size
  • Number of comparators
  • Size of comparators

Given Information

Parameter Value
Main Memory Size 233 bytes
Block Size 211 bytes
Cache Type 2-way Set Associative
Tag Size 10 bits
Addressing Byte Addressable

Step 1 – Physical Address Size

Since the system is byte addressable and the main memory size is: 


Main Memory = 2^33 bytes

We need 33 bits to address all bytes in memory.

Physical Address Size = 33 bits

Step 2 – Address Format in Set Associative Cache

A physical address is divided into three parts:

  • Tag
  • Set Number
  • Block Offset

| Tag | Set Number | Block Offset |

Step 3 – Block Offset Size

Block size is: 


Block Size = 2^11 bytes

Therefore:

Block Offset = 11 bits

Step 4 – Tag Size

The problem states that the tag field is:

Tag Size = 10 bits

Step 5 – Set Number Size

Total physical address bits: 


33 bits

Already used:

  • Tag = 10 bits
  • Offset = 11 bits

So the remaining bits are used for the set number. 


Set bits = 33 - (10 + 11)
Set bits = 12
Set Number Size = 12 bits

Step 6 – Number of Sets

If the set number uses 12 bits: 


Number of Sets = 2^12
Total Sets = 4096 sets

Step 7 – Number of Cache Lines

The cache is 2-way set associative, meaning:

  • Each set contains 2 lines

Therefore: 


Total Lines = Number of Sets × Lines per Set
Total Lines = 2^12 × 2
Total Lines = 2^13
Total Cache Lines = 2^13 lines

Step 8 – Cache Size

Cache size can be calculated using: 


Cache Size = Number of Lines × Line Size

Substitute values: 


Cache Size = 2^13 × 2^11
Cache Size = 2^24 bytes
Total Cache Size = 2^24 bytes (16 MB)

Step 9 – Number of Comparators

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

Since this cache is 2-way set associative: 


Comparators = 2
Number of Comparators = 2

Both comparators check the tag of each line in the selected set simultaneously.

Step 10 – Comparator Size

Comparators compare the tag bits.

Since tag size is: 


Tag = 10 bits

The comparator must compare two 10-bit values.

Comparator Size = 10-bit comparator

Final Results

Parameter Result
Physical Address Size 33 bits
Tag Bits 10 bits
Set Bits 12 bits
Offset Bits 11 bits
Number of Sets 2^12
Total Cache Lines 2^13
Cache Size 2^24 bytes (16 MB)
Number of Comparators 2
Comparator Size 10-bit

Key Concept

  • In direct mapping → 1 comparator.
  • In k-way set associative → k comparators.
  • Comparator size always equals the tag size.