Advanced Cache Mapping Problems – Problem 1

In a K-way set associative cache, the cache is divided into multiple sets. Each set contains exactly K cache lines. This design balances the simplicity of direct-mapped caches with the flexibility of fully associative caches.

If the cache contains V sets, the sets are numbered from:

Set 0, Set 1, Set 2, ... , Set (V − 1)

Each set contains K cache lines. For example, if:

• K = 4 lines per set
• V = number of sets

The cache line numbering will look like:

• Set 0 → Lines 0,1,2,3
• Set 1 → Lines 4,5,6,7
• Set 2 → Lines 8,9,10,11
• Set 3 → Lines 12,13,14,15

The lines of each set are stored sequentially in memory, meaning the lines belonging to set S appear before the lines belonging to set S+1.

The Problem

Given a main memory block numbered J, determine which cache lines the block can occupy in a K-way set associative cache.

Unlike direct-mapped caches where a block maps to exactly one line, a set associative cache allows the block to occupy any line within its mapped set.

Step 1 – Determine the Set Number

To determine the set where the block will be placed, we compute:

Set Number = J % V

Where:

• J = Main memory block number
• V = Total number of sets

The remainder determines which set the block maps to.

Step 2 – Find the First Line of the Set

Once the set number is known, the first cache line of that set is calculated as:

First Line = (J % V) * K

Where:

• K = Number of lines per set

Step 3 – Find the Last Line of the Set

The last cache line within that set is:

Last Line = (J % V) * K + (K - 1)

This provides the complete range of cache lines where the block may be placed.

Final Mapping Range

The main memory block J can be placed in any cache line between:

(J % V) * K  ≤  Cache Line  ≤  (J % V) * K + (K - 1)