Set-Associative Cache Problem – Example 4 (Finding Cache Size)

This example demonstrates how to determine the cache size when only partial information about the cache and memory system is given. The system uses a 4-way set associative cache.

Given Information

Cache Size Formula

The total cache size can be calculated as:

Cache Size = Number of Lines × Line Size

In set-associative caches:

Number of Lines = Number of Sets × Lines per Set

Therefore:

Cache Size = (Number of Sets × Lines per Set) × Line Size

Step 1 – Lines per Set

Since the cache is 4-way set associative:

Lines per Set = 4 = 2^2

Step 2 – Assume Address Fields

A physical address in a cache system is divided into three fields:

| Tag | Set Index | Block Offset |

We know:

• Tag size = 10 bits
• Main memory size = 2^27 bytes

Since the system is byte-addressable, the physical address size is:

Physical Address = 27 bits

Step 3 – Remaining Address Bits

The remaining bits correspond to:

• Set index bits = a
• Block offset bits = b

a + b = 27 - 10
a + b = 17 bits

Step 4 – Express Cache Components

Using the variables:

• Number of sets = 2^a
• Line size = 2^b bytes
• Lines per set = 4 = 2^2

Cache size becomes:

Cache Size = (2^a × 2^2) × 2^b

Cache Size = 2^(a + b + 2)

Step 5 – Substitute Known Value

We previously found:

a + b = 17

Therefore:

Cache Size = 2^(17 + 2)
Cache Size = 2^19 bytes

Final Result

Key Insight

When the number of sets and block size are not given, we can represent them using variables. By using the physical address size and the tag size, we can determine the combined number of bits for the set index and block offset.

This allows us to derive the cache size without knowing the exact values of the set index or block offset individually.

Important Concepts

• Cache Size = Number of Lines × Line Size
• Number of Lines = Number of Sets × Lines per Set
• 4-way associative → 4 lines per set
• Physical Address = log₂(Main Memory Size)
• Tag + Set Index + Offset = Physical Address bits