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 2

This example demonstrates how to solve a typical set-associative cache problem. Using the given cache and memory parameters, we determine:

  • Number of cache lines
  • Number of sets
  • Tag size
  • Number of comparators
  • Comparator size

Given Information

Parameter Value
Main Memory Size 4 GB (232 bytes)
Cache Size 8 KB
Block Size 128 bytes
Cache Type 4-way Set Associative
Addressing Byte Addressable

Step 1 – Number of Cache Lines

The number of lines in the cache is calculated using: 


Number of Lines = Cache Size / Block Size

Substitute the values: 


Cache Size = 8 KB = 2^13 bytes
Block Size = 128 bytes = 2^7 bytes

Number of Lines = 2^13 / 2^7
Number of Lines = 2^6
Total Cache Lines = 64 lines

Step 2 – Number of Frames in Main Memory

Frames in RAM are calculated as: 


Frames = RAM Size / Block Size


RAM Size = 4 GB = 2^32 bytes
Block Size = 2^7 bytes

Frames = 2^32 / 2^7
Frames = 2^25
Total Frames in RAM = 2^25

Step 3 – Number of Sets

Since the cache is 4-way set associative, each set contains 4 cache lines. 


Number of Sets = Total Cache Lines / Lines per Set


Number of Sets = 2^6 / 4
Number of Sets = 2^6 / 2^2
Number of Sets = 2^4
Total Sets = 16 sets

Step 4 – Frames Mapped to Each Set

Each set receives multiple frames from main memory. 


Frames per Set = Total Frames / Number of Sets


Frames per Set = 2^25 / 2^4
Frames per Set = 2^21
Frames mapped to each set = 2^21

Step 5 – Tag Size

Since each set can store one of 2^21 possible frames, the tag must uniquely identify one frame among them.

Tag Size = 21 bits

Step 6 – Address Format

Since the system is byte-addressable and RAM size is: 


4 GB = 2^32 bytes

The physical address is 32 bits.

Address fields: 


| Tag | Set Number | Block Offset |
  • Block Offset = log₂(128) = 7 bits
  • Set Bits = log₂(16) = 4 bits
  • Tag Bits = 32 − (7 + 4) = 21 bits

Step 7 – Number of Comparators

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


Comparators = 4
Number of Comparators = 4

Each comparator checks the tag of one cache line within the selected set.

Step 8 – Comparator Size

Comparators compare the tag bits.

Since tag size is 21 bits, each comparator must compare two 21-bit values.

Comparator Size = 21-bit comparator

Final Results

Parameter Result
Total Cache Lines 64
Number of Sets 16
Tag Bits 21 bits
Offset Bits 7 bits
Set Bits 4 bits
Comparators 4
Comparator Size 21 bits

Key Concepts

  • Cache lines = Cache Size ÷ Block Size
  • Sets = Total Lines ÷ Lines per Set
  • Comparator count = number of ways in the cache
  • Comparator size = tag size
  • Address fields = Tag + Set Index + Block Offset