In a k-way set associative cache, the cache is divided into v sets, each of…
2013
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
- A.
(j mod v) * k to (j mod v) * k + (k − 1)
- B.
(j mod v) to (j mod v) + (k − 1)
- C.
(j mod k) to (j mod k) + (v − 1)
- D.
(j mod k) * v to (j mod k) * v + (v − 1)
Attempted by 5 students.
Show answer & explanation
Correct answer: A
Concept
In a k-way set-associative cache the lines are grouped into v sets of k lines each. A main-memory block is first assigned to exactly one set by the set-mapping rule set = (block number) mod (number of sets), i.e. s = j mod v. Within that set the block may occupy any of the k lines (that is what “k-way” means).
Because the lines are laid out one set after another — set 0’s k lines first, then set 1’s k lines, and so on — the lines belonging to set s occupy the contiguous line numbers s·k up to s·k + (k − 1).
Applying it to block j
Find the set for block j: s = j mod v (the modulus is the number of sets v, not k).
Find where set s starts in the line array: each earlier set contributes k lines, so set s begins at line s·k = (j mod v)·k.
Set s spans k lines, so block j may map to any line from (j mod v)·k through (j mod v)·k + (k − 1).
Hence the range of cache lines is (j mod v)·k to (j mod v)·k + (k − 1).
Cross-check / why the others fail
The set index must use the number of sets v as the modulus; using j mod k mixes up associativity (k) with the count of sets (v).
The starting line of a set is the set index multiplied by k (the lines-per-set stride). A range that omits this ×k factor cannot reach the later sets’ line numbers.
A set contains k lines, so the span is k − 1 wide, not v − 1.