+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.

edited | 368 views

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)