# GATE2014-2-55

8.9k views
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 ________

edited
0
@arjun sir im not able to understand this question what is that 500 ns used for ? is the bus is  1 word or memry is 1 word ?
need explanation to question . :(
4
100ns is used only by control unit...for sequencing and read/write control signals...

In 500ns modules accept and transfer a word into the data bus....

For one word it takes 600ns ...and we have 8 modules and to  initiate one operation takes 100ns in one module so 8 module takes 800ns...

So 600ns can be overlapped .... But if modules are only 5 and less ...than there will be additional delay...
0
pls explain the quesiton ?wht about 500
0

@Habib sir,@ srestha pls explain this

0

What will be the answer if we have only 5(means less then 6) memory modules ?

Could you derive some general formula ? :)
0
in 700ns we can initiate only 5 requests with 5 modules. so in 1ms we can raise request 5*1ms/700ns requests.
1
@chhotu.. I think if we have 5 modules then too  there will be 5 requests initiated in 500 ns... So in 1 ms still 10,000 requests are there...

Basically in every 100 ns 1 request  initiated.
0

Hi @gari ji,

What will happen in less then 5 case ?

0
@Chhotu for less than 5 modules we can initiate 4 req normally but for 5th one we should wait 200ns
1 @Ashwin Yes you are correct. For less than 5 module , it 5th store has to wait for 200ns.

Since we have 8 module here, after every 100ns we can initiate a new store operation due to pipelining

0

So, Generally

Let The time that any resource takes to get back online ( or available for use req.) be $T$  as here, $T = 600ns$,

and

Let Time taken to generate requests for all resources is $X$, as here $X= 800ns$

then

if $(X>T )$ then in every $100ns$ one request could be generated.

and

if $(X<T )$ then in every $Tns$

Request that could be generated. = $NumberOfResources$.

So, if $NumberOfResources = 3$ (say)

then $3$ requests can be generated in $T = 600ns$. So further use Unitary method.

0
@Satyajeet Singh,How could you deduce that the given ques is solely talking about the architecture of a Pipelined Processor whereas it is not mentioned?
@Srestha,@Papesh you all join in as well.
0
@Devshree

what is meaning of this line?

"the main memory system that consists of 8 memory modules attached to the system bus"
0
@Srestha,Okay I see tat. So this line explains that the architecture which is being talked of is pipeline system. Isn't it?Tysm Srestha, If the architecture is Non-Pipeline system,it'll be explicitly mentioned?
1

@devshree

See bus is the interconnection between  CPU,IO and Memory module. So, when bus transfers some signals it must transfer the data for reading or writing(those signal are combination of 0 or 1) .

Now, 1st 100 ns bus is used to do external operation, but rest 500 ns. it is used to do store operation i.e. internal operation and that can overlap

Overlapping means we can do data operation like pipeline. U can think like this the main work is done in EX stage in pipeline and other stages overlapping

0
@Srestha,Okay Srestha. I see that.Since the processor is pipelined therefore, the overlapping takes between read/write operation and in store operation as well. Am I right?If wrong please correct me. Tysm Srestha. :)
1

when operating on clock cycles, it will always be pipelined

But in case of read or write operation there need to some data as valid data and some are invalid data.  When we are writing in processor, some address is generated and then reading or writing is performed . But when memory clock comes into picture, then only data is valid(it may generate some delay after writing) That is how writing performed in memory 1
@Srestha,That's so sweet of you. Indeed a big Thanks. I can see in the image that address has been generated,and the writing is synchronized with the clock. Am I right at this point. If wrong,please correct. A big Thanks to you. :)
1
haha :)

yes it is for synchronous clock
1
@srestha,you cleared a plentiful of doubts. Tonnes Thanks again. :)
0
if there are 4 module, we need to wait for 200 ns., but for 5 module we need to wait for 100 ns
0
@Srestha,How?Can u elaborate it?
0
@Srestha,By logically going, if there are 4 module,since the no of module  is less,therefore it will take more time,but in case of 5 module the time taken will be less.Am I right?
2 See upto 4 module means where work is completed in 400ns, but u need to wait upto 600 ns minimum as it is minimum time to complete 1stage

0
@Srestha,I understand what you are trying to convey. So for min time period of 600 ns,one cycle is completed. Isn't it?
11

Actually it is the from MEMORY INTERLEAVING we are able to parallelize  the request to memory module after identifying the module and when they are working on storing or any operation at that time their is no need to stuck their when first one on 500 ns at that we can make another request to another memory module so no need to wait for 500ns we can make a request to module each and every 100ns that is what we gain from memory interleaving .

100ns = 1 request

so in 1 sec = 1/100*10^-9 request

so in 1 ms = 1*10^-3/100*10^-9 = 10,000 request 11
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.
0

We have to wait for 200ns for 1st module to get freed up 0

@TheDaniel thanku for the explanatation, Your explanation is quite crstyal clear.

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$

edited by
5
10000 stores can be initiated and 9994 stores will be completed in 1msec.am I right?
0
@arjun sir according to me..ans should be 99500 bcs it is also taking additional 500 ns!!!
0

@ 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?

0
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.
39
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
0
0
@Arjun according to your approach, it should  be $3$ writes for $300ns$ (instead of 1ms). But is it so?
0
Amazing question and amazing answer. Thats GATE
1
@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 ?
3
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.
0

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?

1
This is a pipeline concept based question and we can apply the concept solve. Hope this is helpful for better understanding of the question.
0
Please explain what would be the maximum number of stores if the memory module is 4 or 5.
0

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.

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

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.

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$

## Related questions

1
4k views
Three processes $A$, $B$ and $C$ each execute a loop of $100$ iterations. In each iteration of the loop, a process performs a single computation that requires $t_c$ CPU milliseconds and then initiates a single I/O operation that lasts for $t_{io}$ ... uses a time slice of $50$ milliseconds. The time in milliseconds at which process C would complete its first I/O operation is ___________.
A FAT (file allocation table) based file system is being used and the total overhead of each entry in the FAT is $4$ bytes in size. Given a $100 \times 10^6$ bytes disk on which the file system is stored and data block size is $10^3$ bytes, the maximum size of a file that can be stored on this disk in units of $10^6$ bytes is _________.
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.