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

10000 stores can be initiated and 9994 stores will be completed in 1msec.am I right?

---

@arjun sir according to me..ans should be 99500 bcs it is also taking additional 500 ns!!!

---

@ arjun, total stores completed coming as 99500 last 500 will be completed at 10^6 +100,10^6 +200,10^6 +300

is he asking only for number of  requests sent in that time?

---

the maximum number of stores of one word would mean storing in 8 modules which would require 800ns as we will have a gap of 100ns between 2 consecutive memory modules. i am confused why you have not taken the time for one word storage @arjun sir please clear the doubt.

---

Number of modules (8), and word length have no role in the answer. It is like pipelining. Assume consecutive modules addressed are distinct in run lengths of 5 = (500/100), so that there is no waiting at any particular module. Then, the time scenario is:

100|500

****100|500

********100|500

....

-----------------------------------------------------

For requests completed in 1 ms,

total time = 100 k  + 500 = 1000,000

k = 999,500 / 100  =  9995

-------------------------------------------------------

For requests initiated in 1 ms,

total time = 100 k = 1000,000

k = 10,000

---

Agree with @madan's solution

---

@Arjun according to your approach, it should  be $3$ writes for $300ns$ (instead of 1ms). But is it so?

---

Amazing question and amazing answer. Thats GATE

---

@Arjun Sir , What if the number of modules is 4 and we have to wait for modules for a request , then how to solve it ?

---

The question tells about the memory design in which we have interleaved memory modules(in this question they are 8).

Note: if you dont know interleaved memory design, please take a look at it.

now going back to the solution:

The scenario is:   8 memory modules are parallelly  connected to BUS.

when the request of “store” operation arrives through bus for any one particular memory module (lets suppose module 1), then it requires 100 nsec to initialize the requests of “store” operation for module 1.

After that, the BUS can move to next module to initialize  the store operation, so now BUS will initialize module 2 and it will require 100 nsec..

in the same fashion this process continues.

also note: once a module is initiated it will take 500 nsec on its own to do the rest of the store operation process, which has got nothing to do with bus.

The only job that BUS is doing here is that : it is initializing modules one after another for which it requires 100 nsec for each module.

so basically we have 1milli-second of time,

so number of initialization that BUS can do in the provided time will be =

provided time/ time required to initiate one module

= 1 milliseconds/ 100 nsec

= 10,000 times the store operation can be initiated.

 

thank you.

---

I have a doubt here

Consider the main memory system that consists of 8 memory modules attached to the system bus, which is one word wide

I understand the interleaved memory design, but in this question do they mean that 1 word of memory system=8*1Word of each Memory Module?

---

This is a pipeline concept based question and we can apply the concept solve. Hope this is helpful for better understanding of the question.

---

Please explain what would be the maximum number of stores if the memory module is 4 or 5.

---

when a request is made to a particular module, the bus is occupied for 100 ns. And thereafter the bus is free and that addressed memory module performs its internal operations for storing that data (for 500 ns). Also note that each module is independent i.e their operations can be interleaved.

This means that,

1 request is made per 100 ns.

i.e The number of requests in 1 ms = (1x10^-3) / (100 x 10^-9) = 10^4 requests.

---

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!