edited by
1,029 views
2 votes
2 votes

Consider the direct mapped cache organization which consists of m-lines with a line size of 2w words/ bytes. Main memory address can be viewed as consisting of three fields. The least significant w-bits identify a unique word within the block of main memory. The remaining ‘S’ bits specify one of the 2S block of main memory. Assume that cache is initially empty. Main memory blocks are referenced by the CPU in a sequential order. Which one of the following sequence of the blocks are mapped on the cache lines in sequential order from the initial line respectively.

  • 2m + 1, 2m + 2,..., 3m – 1
  • 2S – m, 2S – m+1,..., 2S – 1
  • 1, 2, 3,..., m – 1
  • 0, 2, 4,..., (m – 1)

i thought answer would be 1,2,3, ... (m-1)

but now i am confused what is asked in this ques.

edited by

2 Answers

2 votes
2 votes
Offset bits = $w$ and $2^w$ is the cache line size. So, this much size is exactly fitting on cache line.

Now, cache is always organized such that consecutive memory blocks go to consecutive cache sets (to make use of spacial locality) and this is the reason tag bits are the left most.  

Now, answer is easy here but options are not. Answer must be option B. In option A, it should start from $2m$ and not $2m+1$ and similarly in C, it must start from $0$.
1 votes
1 votes

As we know that this is a Direct mapping cache

given :  offset bits  = w

              No of cache lines = m

           direct mapping   | TAG FIELD | LINE NUMBER | LINE OFFSET|

          TAG FIELD + LINE NUMBER  = BLOCK NUMBER

          now as we know that it's a Direct Mapped cache ,

    Xth block of Main Memory is present in the  =( X mod 2^m)  cache block in the cache memory.

 

here it's given that . Main memory blocks are referenced by the CPU in a sequential order

Now let's take an example

No of lines in a cache  = 4

No of blocks in the memory = 16

as Main memory block are referred by CPU in sequential order ,

=== > MM block 0 is refer

                         where it's present in the cache = 2S – m =  16 - 4 mod 4  = 0  

====> MM block 1 is refer

                          where it's present in the cache = 2S – m+1 = 16 - (4+1) mod 4  = 1

====> MM block 2 is refer

                       where it's present in the cache = 2S – m+2 = 16 - (4+2) mod 4  = 2                    

..........

        MM block 15  is refer

            where it's present in the cache = 2S – 1 = 16 -1 mod 4  = 3

Option C and A is not correct because if

No of lines in cache  = 4

then it should be Mapped as  as ( 0 , 1 ,2, 3)

but if you use the formula A and C you can't insert any block into the cache line 0  and it's clearly given in the question that

sequence of the blocks are mapped on the cache lines in sequential order from the initial line

And Option D doesn't mapped on the cache lines in sequential order that's its also wrong

 

Hope you understand the concept  khushtak  smartmeet  Shubhanshu

     

 

             

Related questions

3 votes
3 votes
1 answer
2
ashish pal asked Dec 31, 2017
1,801 views
The statement " Direct mapped cache, may produce more misses if programs refers to memory words that occupy a same tag value." is true or false ?