The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+6 votes

Consider a small two-way set-associative cache memory, consisting of four blocks. For choosing the block to be replaced, use the least recently used (LRU) scheme. The number of cache misses for the following sequence of block addresses is

8, 12, 0, 12, 8

  1. 2
  2. 3
  3. 4
  4. 5
asked in CO & Architecture by Veteran (69k points)
retagged by | 1.9k views
what will be the number of conflict cache miss ? is it 2?

2 Answers

+13 votes
Best answer

We have 4 blocks and 2 blocks in a set

=> there are 2 sets. So blocks will go

to sets as follows:

Set Number Block Number
0 0, 8, 12

since the lowest bit of block address is used for indexing into the set. 

So, 8, 12 and 0 first miss in cache with 0 replacing 8 (there are two slots in each set due to 2-way set) and then 12 hits in cache and 8 again misses. So totally 4 misses. 

answered by Veteran (346k points)
selected by
How can tag bits be the lowest most bits ? Tag bits are the upper most bits. Lower most bits is the index. Here as there are only 2 sets, index bit = 1. isn't it ?
Yes. You are right. I have corrected it. It's index or set bits and not tag bits. Tag bits are the upper bits and relevant to identify which block is currently present in a cache block. In this question this part is not asked and we just need to identify the 1 index bit.
Very Nice explanation...
Sir, did you use LRU into it?
+1 vote
2 way set associative

4 blocks

Set size = # of blocks / # of sets

            = 4/2 = 2

So Block addresses will be divided by 2 ... On the basis of their remainder we will place those blocks in the sets .. applying LRU approach ... answer will be 4 ..
answered by Veteran (23.9k points)

This one ....


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

33,646 questions
40,193 answers
38,664 users