+1 vote
31 views
A computer system contains a main memory of 32 K size with 16-bit words. It also has a 4 K word cache divided into 4 slot sets with 64 words per slot. Assume that the cache is initially empty. The processor fetches words from 0, 1, 2,...4351 in that order repeatedly 10 times. Assume a LRU policy for block replacement. How many miss operations will occur?

+1 vote

No of main memory blocks required to be accessed  =   No of words / Block size

=   4352 / 64

=   68                           .............(1)

Now number of sets in the cache                             =  Total number of cache words / (No of cache words in each set)

=   4 K  /   (64 * 4)

=   16

Total no of cache blocks available                            =  No of sets * associaitivity

=   64

Hence  when a main memory block having block no  "x" is needed to be accessed , it will be brought into set no :  x mod 16

Now the words (0 - 63) belongs to block no 0 , (64 - 127) belongs to block no 1 ..........., so on and finally (4288 - 4351) belongs to block no 67 ..

Now we try to see the access pattern..

Block no 0 goes to :   0 mod 16  =  0

Block no 1 goes to :   1 mod 16  =  1

and so on till block no 63 goes to :  63 mod 16  =  15

Now block no 64 - 67 need to be allocated but cache is full.Hence need of replacement using LRU policy as given in the question..

Block no 64 goes to :  64 mod 16  =  0..

Now in the set no 0 , the least recently used block was block no 0 and hence it will be replaced..

So we have now in set 0 : Block numbers  64 , 16 , 32 , 48

Similarly in set  1 : Block numbers  65 , 17 , 33 , 49

in set   2 : Block numbers  66 , 18 , 34 , 50

in set   3 : Block numbers  67 , 19 , 35 , 51

Hence number of misses in first iteration   =   68 misses (and all of them being compulsory miss as they are the first appearances in cache)..

As we can see replacement takes place in the first 4 sets only hence from now on we will observe first 4 sets..

Now we come to iteration no.  2 :

When block no 0 is accessed , it is not in cache so block no 16 is replaced hence contents of set 0 : 64 , 0  , 32 , 48

block no 16 is accessed , it is not in cache so block no 32 is replaced hence contents of set 0 :  64 , 0  , 16 , 48

block no 32 is accessed , it is not in cache so block no 48 is replaced hence contents of set 0 :  64 , 0 , 16 , 32

block no 48 is accessed , it is not in cache so block no 64 is replaced hence contents of set 0 :  48 , 0 , 16 , 32

block no 64 is accessed , it is not in cache so block no 0 is replaced hence contents of set 0 : 48 , 64 , 16 , 32

So in total as far as the set no 0 is concerned , no of misses   =    5

Same goes for other 3 sets i.e.  set no 1 , set no 2 and set 3..

Hence no of misses in iteration no 2     =    5 * 4     =    20

As we return to same state of cache as in the end of iteration no 1 , hence we can conclude the misses in the subsequent iterations will also be same as that of the iteration number 2..

Hence number of misses    =   68(for first iteration)  +  20 * 9

=   68   +   180

=   248

Specifically number of compulsory misses  =   68

number of conflict misses(also known as interference miss)    =   180

selected
thank you, Sir!
U r most welcome.. As an exercise plz  try the same problem using MRU page replacement policy.. :)
okay, I will try to solve it.