The main memory of a computer has 2cm blocks while the cache has 2c blocks. If…
2020
The main memory of a computer has 2cm blocks while the cache has 2c blocks. If the cache uses the set-associative mapping scheme with two blocks per set, then block k of the main memory maps to the set:
- A.
(k mod m) of the cache
- B.
(k mod c) of the cache
- C.
(k mod 2c) of the cache
- D.
(k mod 2cm) of the cache
Attempted by 82 students.
Show answer & explanation
Correct answer: B
In set-associative mapping the cache is partitioned into equal-size sets, and every main-memory block is forced into exactly one set. The governing rule is: set index = (block number) mod (number of sets in the cache). The block number is reduced against the number of SETS — not the number of blocks.
Applying it to the given sizes:
Cache size: the cache holds 2c blocks.
Associativity: the scheme places two blocks in every set (2-way set-associative).
Number of sets: S = (total cache blocks) / (blocks per set) = 2c / 2 = c.
Mapping: block k therefore maps to set (k mod c).
So block k of main memory maps to set (k mod c) of the cache.
Why the other values do not fit:
(k mod m): m is only a factor of the main-memory block count 2cm, not a count of cache sets.
(k mod 2c): 2c is the total cache block count; the two-blocks-per-set grouping halves it to c sets.
(k mod 2cm): 2cm is the main-memory block count, and the set index never depends on main-memory size.
Cross-check: the 2cm main-memory blocks spread evenly over the c sets, 2cm / c = 2m blocks competing for each set — internally consistent, and confirming the cache has c sets.