In a $k$-way set associative cache,main memory block mapping in range?

Question

In a $k$-way set associative cache, the cache is divided into $v$ sets, each of which consists of $k$ lines. The lines of a set are placed in sequence one after another. The lines in set $s$ are sequenced before the lines in set $(s+1)$. The main memory blocks are numbered 0 onwards. The main memory block numbered $j$ must be mapped to any one of the cache lines from:

1. $(j\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
2. $(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
3. $(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
4. $(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $

---

My attempt:

Somewhere it explained as : Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from (j mod v) * k to (j mod v) * k + (k-1). (Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence reduces the chances of replacement.)

Can you explain it in a formal way, please?

Answer 1

Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from (j mod v) * k to (j mod v) * k + (k-1). (Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence reduces the chances of replacement.)

This is a simple concept of k-way set associate mapping.

To understand it better I would like to take an example:

Example:

• 2-way set associative

• 4 blocks

• Lines of a set are placed in sequence one after another (as in the
  question)

• The main memory blocks are numbered 0 onwards (as in the question)

Empty 2-way set associative Cache Memory :

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   -   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Memory reference (data asked for processing) in the order:

4, 5, 9, 7

Reference 4:

4 % 4 = 0 (goes to Block 0 Set 1) Cache miss as it doesn't already present in the cache

As it had 4 blocks, we mod it the reference address to know which location of cache should I put it.

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   -   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 5:

4 % 5 = 1 (goes to Block 1 Set 1) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   -   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 9:

4 % 9 = 1 (goes to Block 1 Set 2) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   -   │   -   ║
╚═══╧═══════╧═══════╝

Reference 4:

4 % 7 = 3 (goes to Block 3 Set 1) Cache miss

╔═══╤═══════════════╗
║   │     Cache     ║
╠═══╪═══════╤═══════╣
║   │ Set 1 │ Set 2 ║
╟───┼───────┼───────╢
║ 0 │   4   │   -   ║
╟───┼───────┼───────╢
║ 1 │   5   │   9   ║
╟───┼───────┼───────╢
║ 2 │   -   │   -   ║
╟───┼───────┼───────╢
║ 3 │   7   │   -   ║
╚═══╧═══════╧═══════╝

Visualization of Cache memory for you undersatnding:

╔═════════════════════════════════════════════════════╗
║                    Cache Memory                     ║
╠════════════════╤════════════╤═══════════════════════╣
║ Memory address │ References │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       0        │     4      │                       ║
╟────────────────┼────────────┤ Cache line 0 elements ║
║       1        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       2        │     5      │                       ║
╟────────────────┼────────────┤ Cache line 1 elements ║
║       3        │     9      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       4        │     -      │                       ║
╟────────────────┼────────────┤ Cache line 2 elements ║
║       5        │     -      │                       ║
╟────────────────┼────────────┼───────────────────────╢
║       6        │     7      │                       ║
╟────────────────┼────────────┤ Cache line 3 elements ║
║       7        │     -      │                       ║
╚════════════════╧════════════╧═══════════════════════╝

Both of the two set of cache line 1 is full, therefore calculation the location of first and last element of line gives us the answer.

Lets now check if the answer is option (1) as you mentioned

1. (j mod v) ∗ k to (j mod v) ∗ k + (k − 1)

Given:

v = 4 (four blocks)

k = 2 (two-way)

First element of cache line 1 = (j mod v) ∗ k = (5 mod 4) ∗ 2 = 2 yes, its located at memory location 2.

Last element of cache line 1 = (j mod v) ∗ k + (k − 1) = (9 mod 4) ∗ 2 + (2 - 1) = 3 yes, its located at memory location 3.

Done.

Answer: (j mod v) ∗ k to (j mod v) ∗ k + (k − 1)