Set-Associative Cache Problem – Example 5 (Finding Main Memory Size)

In this problem we are given the cache size, tag size, and that the cache is 8-way set associative. The goal is to determine the total size of main memory (RAM).

Given Information

Step 1 – Cache Size Formula

Cache size can be expressed as:

Cache Size = Number of Lines × Line Size

In a set-associative cache:

Number of Lines = Number of Sets × Lines per Set

Therefore:

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

Step 2 – Use Associativity

The cache is 8-way set associative, meaning:

Lines per Set = 8 = 2^3

Thus:

Cache Size = Number of Sets × 8 × Line Size

Step 3 – Address Field Representation

A physical address is divided into three fields:

| Tag | Set Index | Block Offset |

Let:

• t = number of tag bits
• s = number of set index bits
• o = number of offset bits

The total physical address size is:

x = t + s + o

The main memory size will be:

Main Memory Size = 2^x bytes

Step 4 – Relating Sets and Line Size

From the address fields:

• Number of sets = 2^s
• Line size = 2^o bytes

Therefore:

Number of Sets × Line Size = 2^s × 2^o

= 2^(s + o)

But since:

x = t + s + o

Then:

2^(s + o) = 2^(x - t)

Step 5 – Substitute Known Values

Tag size:

t = 11

Therefore:

Number of Sets × Line Size = 2^(x - 11)

Now substitute into the cache size formula:

Cache Size = 8 × 2^(x - 11)

Since:

Cache Size = 1 MB = 2^20 bytes

2^3 × 2^(x - 11) = 2^20

Step 6 – Solve for x

2^(x - 11) = 2^20 / 2^3

2^(x - 11) = 2^17

x - 11 = 17
x = 28

Final Result

Key Concept

Even if the set index bits and offset bits are unknown individually, we can combine them using the relation:

s + o = x - t

This allows us to derive the total physical address size and determine the main memory size.

Important Takeaways

• Cache Size = Number of Sets × Lines per Set × Line Size
• Associativity determines the number of lines per set
• Physical Address = Tag + Set Index + Offset
• Main Memory Size = 2^{Physical Address Bits}