The Gateway to Computer Science Excellence
+1 vote
368 views

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.

in CO and Architecture by Loyal (7k points)
edited by | 368 views

2 Answers

+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$.
by Veteran (424k points)
0
plz explain the solution!
0
@Arjun Sir, plz explain why b is the answer
0
arjun sir m and 2^s will always be the multiple of each other am i right sir?
+1 vote

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

     

 

             

by Boss (13.8k points)

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
50,647 questions
56,459 answers
195,376 comments
100,268 users