GATE CSE
First time here? Checkout the FAQ!
x
+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?
asked in CO & Architecture by (143 points)   | 31 views

1 Answer

+1 vote
Best answer

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

 

answered by Veteran (77.1k points)  
selected by
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.

Related questions

0 votes
1 answer
1
0 votes
0 answers
2
0 votes
0 answers
3
asked in CO & Architecture by rahul sharma 5 Veteran (11.3k points)   | 27 views


Top Users Sep 2017
  1. Habibkhan

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,726 answers
79,957 comments
31,115 users