Question about set-associative cache mapping

Question

I found a question:

Let a two-way set-associative cache of 4 memory blocks, each block containing one word.

What is the number of misses and hits considering the following sequence of block addresses: 0, 8, 0, 6, 8 ?

a) 4 misses and 1 hit
b) 3 misses and 2 hits
c) 1 miss and 4 hits
d) 2 misses and 3 hits

Although I understand how set-associative cache mapping works, I don't understand how can you tell if it will be a hit or a miss if you don't know the tags and what is stored on the cache memory.

Can you please point me in the right direction? How should I think about this problem?

Answer 1

You're absolutely right: the question is unanswerable as stated because you don't know what's in the cache at the start of the sequence of memory accesses. You're probably expected to assume that the cache is initially empty but, if this is an exercise you've been set, you should ask your instructor to clarify.

Answer 2

Even I have faced this kind of question in some comparative exams and can be solved with some assumptions.

Assume: Cache is empty

Solution:

2-way set associative with 4 blocks (empty cache) gives

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

Input : 0, 8, 0, 6, 8

Inserting one by one

Inserting : 0 (cache miss)

0 % 4 = 0 (goes to Block 0 Set 1)

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

Inserting : 8 (cache miss)

8 % 4 = 0 (goes to Block 0 Set 2)

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

Inserting : 0 (cache hit)

0 % 4 = 0

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

Inserting : 6 (cache miss)

6 % 4 = 2 (goes to Block 2 Set 1)

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

Inserting : 8 (cache hit)

8 % 4 = 0

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

Answer : 3 misses and 2 hits (option B)