GATE CSE 2014 Set 2 | Question: 55

Question

Consider the main memory system that consists of $8$ memory modules attached to the system bus, which is one word wide. When a write request is made, the bus is occupied for $100$ nanoseconds (ns) by the data, address, and control signals. During the same $100$ ns, and for $500$ ns thereafter, the addressed memory module executes one cycle accepting and storing the data. The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time. The maximum number of stores (of one word each) that can be initiated in $1$ millisecond is ________

Comments

I had one small doubt but I got it ...maybe it will help someone 

What is the use of 8 memory modules? What if there were just (lets say) 2 memory modules?

   1^st memory module [ 100 | 100 |100 |100|100 | 100 ]

   2^nd memory module [ ----- | 100 | 100 | 100 | 100 | 100 | 100 ]

Now as our both modules are busy we can not initiate the next request , we can start 3^rd request only at end of 1^st memory module. i.e at 600 we can initialize storage request for 3^rd and so on…

So hence here, the number of memory modules available makes sense !

PS : if there is any edit needed please do correct me!

---

@jiminpark I am understanding no. of memory modules available = no. of requests in 600 ns interval(max 6 requests).

But my doubt is, lets say 4 memory modules are available.

Then 0 – 100 –> request for 1^st module ( 100 -600 is busy)

100 – 200 → req for 2^nd ( 200 – 700 busy)

200 – 300 → req for 3^rd ( 300 – 800 busy)

300 – 400 → req for 4^th ( 400 – 900 busy)

Now all the memory modules are busy, We have to wait for memory modules to free up.

400 – 500 → wait

Now for 500 → 600 why not generate new request as this 100 ns request will consume bus time and as after 600 ns 1^st memory module will get free and can get on servicing request.

So total 5 request can be in 600 ns interval for 4 modules.

OR

Should we generate request only when module is free. We cannot generate new request if it affects write operation in module. But how it affects being WR signal activated after 100 bus time?

When a write request is made, the bus is occupied for 100 nanoseconds (ns) by the data, address, and control signals. During the same 100 ns, and for 500 ns thereafter, the addressed memory module executes one cycle accepting and storing the data.

Is question suggesting in 100 ns memory module accepts the data and for 500 ns stores the data?If thats the case then, last request cannot be generated.

---

Answer in  Easy language

https://gateoverflow.in/2022/gate-cse-2014-set-2-question-55?show=413830#a413830

Answer 1

When a write request is made, the bus is occupied for $100$ ns. So, between $2$ writes at least $100$ ns interval must be there.

Now, after a write request, for $100 + 500 = 600$ ns, the corresponding memory module is busy storing the data. But, assuming the next stores are to a different memory module (we have totally $8$ modules in question), we can have consecutive stores at intervals of $100$ ns. So, maximum number of stores in $1$ ms

$=  10^{-3} \times 1/(100 \times 10^{ -9}) = 10,000$

Comments

Agreed 👍

---

We can have a maximum of 4 memory modules overlapping, which is definitely okay as we have 8 memory modules to work with.

Every $100\ ns$ we can initiate $1$ request so in $1\ ms\ (= 10^6 \ ns)$ we can have a maximum of $\frac{10^6}{100}=10^{4}$ request initiation.

If they would have asked maximum number of request completion then it will be $\lfloor \frac{10^6-500}{100} \rfloor = 9995$ request completion.

---

@DebRC, we can have 5 mem modules overlapping ,not 4

Answer 2

The (internal) operation of different memory modules may overlap in time

Whenever operations can be overlapped, we can do them simultaneously. Whenever operations can be interleaved, we can use the pipelining concept. This is elementary stuff.

Now, read this line further.

The (internal) operation of different memory modules may overlap in time, but only one request can be on the bus at any time.

This is basically just interleaving. We can use the pipelining concepts here.

---

 

Now, see carefully what the question asks for.

The maximum number of stores (of one word each) that can be initiated in 1 millisecond is

Each initiation takes $100ns$. We can't overlap initiations, so they must be done separately.

In 1ms, we can perform $\frac{1ms}{100ns}=10^4=10000$ initiations. Answer.

---

If the question asked the number of stores that can be completed  in $1ms$

We could write it as

$(100ns+500ns)+x(100ns)=1ms$

ie, the first job would take 100ns + 500ns time. The rest of the jobs would take just 100ns time, because only initiation is to be kept separate, internal operations can be overlapped. This equation is pretty much identical to what we use in pipelining.

 

Upon solving, $x=9994$

Since $x$ denotes "rest of the jobs", we need to add $1$ to $x$ to obtain total jobs.

 

So, total stores completed would be $9994+1=9995$

Comments

Can you explain it for 4 memory modules !!! In four memory modules no memory module will be free ..then how we will solve the question

---

@akshita.gour12 If there are 4 modules then in every 600ns 4 requests can be made because after 400ns there are no free modules left and after 600ns the first module will be free.

1000000/600ns = 1666.66

1666 intervals can be made in 999600ns and in each interval 4 requests are made

1666*4=6664

And in last 400ns 4 requests can be made as modules will be free.

So in 1ms no of requests =6664+4 requests.

 

---

@JashanArora,

Good Explaination.One small correction in your solution is The question is asking for  The maximum number of stores (of one word each) that can be initiated in 1 millisecond so we need to add only initiation time for first request.If the question is asked for number of request completed in 1 ms then we have to also add 500 ns for last write. 

Answer 3

We have 8 total memory modules, and by the time we've completed memory write initiation to 6th memory module, 1st memory module will have completed its (100 + 500 nsec) memory write cycle. Similarly, the 2nd memory module will be ready by the end of 7th memory write initiation. Therefore, at least one memory module will always be ready for write initiation. So it's just a matter of finding how many 100 nsec are there in 1 msec: $\frac{100 \times 10^{-9}}{10^{-3}} = 10000.$

Comments

Can you explain it for 4 memory modules !!! In four memory modules no memory module will be free ..then how we will solve the question

---

It’s funny that in spite of the error is present in the solution, there are 18 upvotes on this solution.

It should be 1ms/100ns = 10000 initiations, and not 100ns/1ms.

Answer 4

Answer in easy language 

1. When a write request is made to the memory, the system bus is occupied for 100 nanoseconds (ns). This means that once a write operation starts, no other operation can start for the next 100 ns.

 

2. After a write request, the corresponding memory module is busy storing the data for a duration between 100 ns and 500 ns. 

 

3. However, if the next write operation is to a different memory module (and there are 8 modules in total), we can start another write operation after 100 ns, even if the previous module is still busy.

 

4. So, in this system, we can initiate a new write operation every 100 ns. As there are 10^6 (1 million) nanoseconds in a millisecond, we can initiate up to 10^6 / 100 = 10,000 write operations in 1 millisecond.

I hope this makes it clearer!