13,360 views

Consider the following data path of a simple non-pipelined CPU. The registers $A, B$, $A_{1},A_{2}, \textsf{MDR},$ the $\textsf{bus}$ and the $\textsf{ALU}$ are $8$-$bit$ wide. $\textsf{SP}$ and $\textsf{MAR}$ are $16$-$bit$ registers. The $\textsf{MUX}$ is of size $8 \times (2:1)$ and the $\textsf{DEMUX}$ is of size $8 \times (1:2)$. Each memory operation takes $2$ $\textsf{CPU}$ clock cycles and uses $\textsf{MAR}$ (Memory Address Register) and $\textsf{MDR}$ (Memory Date Register). $\textsf{SP}$ can be decremented locally.

The $\textsf{CPU}$ instruction "push r" where, $r =$ $A$ or $B$ has the specification

• $M[SP] ← r$
• $SP ← SP - 1$

How many $\textsf{CPU}$ clock cycles are required to execute the "push r" instruction?

1. $2$
2. $3$
3. $4$
4. $5$

didnt get properly , although my answer by understanding is 3.
1.SPout , MAR in , Sin
2.MAR out , MDR in
SP <= S - 1
3. Rout , MDR in
SP out, MAR in ------ 2 cycles as they are 16 bit and system bus is of 8 bits

A out, MDR in --------- 1 cycle

M[MAR]<----- MDR ------- 2 cycles

So total 5 cycles
edited by
If somebody is thinking -->  why Mux and DeMux is used ?  then  It is used because bus size and memory address size is different.

Now some people(like me) will be thinking why is last micro-operation is taking 2 cycle. So answer is it is mentioned in the question that memory operation takes 2 cycle( If it is not mentioned then it could be done in one clock cycle because our data Bus size is 8 bit)
This comes under which topic in GATE Computer Organization subject? Is this in syllabus?
Is this figure correct? In figure both are MUX.But as per question one is MUX and one is DEMUX
Please provide me with some good resources to study these topics from...
Can anyone share any resource or link to solve such kind of ALU data path question except previous years gate question. It will be very helpful

using sachin Sir explaination on this  Question https://gateoverflow.in/43568/gate2005-80.  .

Explaination;

T0: MAR← SP   (SINCE THERE IS A CONNECTION BETWEEN MUX OF SP AND DEMUX OF MAR I ASSUME THIS TRANSFER DOES NOT USE INTERNAL BUS.)

T0: MDR← R ( THIS USES INTERNAL BUS)

T1: SP<-SP-1 (LOCAL)

T1: M[MAR]<-MDR

Can somebody clarify if this is right?

edited

There is typo in question.

MDR (Memory Date Register)

Shouldn’t it be Memory Data Register?

A microinstruction cannot be further broken down into two or more. It can take more than a cycle if it involves a memory access. The first instruction given here is not a microinstruction. It is an assembly language instruction.

It can be broken down as:

$T1 , T2: MAR \leftarrow SP$

$T3. : MDR\leftarrow r , SP\leftarrow SP-1$ $($It is not mandatory to decrement it in this cycle. Anyway, it can be decremented locally$)$

$T4, T5 : M [MAR] \leftarrow MDR$

The problem says, 8-bit MDR, 8-bit data bus, 8 bit registers.Can't you see that the given CPU is 8-bit? 8 multiplexers transfer 8 bits when selection input is 0 and 1 respectively. During cycle 1, bits in even positions are moved to MAR. During cycle 2, bits in odd positions are transferred to MAR.  We certainly need to move 16-bit SP to 16-bit MAR via a 8-bit bus. So, 2 cycles to get SP to MAR.

The given data path has a single bus, which requires  r to be carried in a separate cycle. For the contents of r to be moved to MDR during the cycles T1 or T2, address and data bus should be separate. Here, it ain't the case.

Memory read takes 2 more cycles. In total, we need 5 of them clock cycles to execute a push.

https://www.cise.ufl.edu/~mssz/CompOrg/CDA-proc.html
Computer organization pal chaudari page 334-335

Computer architecture by behrooz parahmi exercise 7.6

Correct Answer: $D$

How do we know that transferring bits from mux to MAR will take exactly one cycle?
This comes under which topic in GATE Computer Organization subject? Is this in syllabus?
Can you please explain that once MAR and MDR are loaded in 3 clock cycles, how M[MAR] <-- MDR will happen in 2 clock cycles ??

8 multiplexers transfer 8 bits when selection input is 0 and 1 respectively. During cycle 1, bits in even positions are moved to MAR. During cycle 2, bits in odd positions are transferred to MAR.

Can you please explain how this was deduced?

@Arjun sir @rajaneesh16 sir can you kindly explain how the last instruction takes 2 clock cycle since its just 8 bit data transfer and we have the address in MAR. So it's just due to it's mentioned that memory transfer gonna take 2 cycles, otherwise it should take 1 cycle ?

T4,T5:M[MAR]←MDR

Yes correct, because it is mentioned memory operations take 2 cycles.
Can you please explain sp is decremented in which cycle and what does it mean by saying sp is decremented locally does it not require alu for this purpose and if alu is required then although durong the first cycle when sp is moved to mar we can move  of sp to reg A1 A0 and in sub cycle perform sp-1 but in T3- content of r is moved to MBR so new value of sp cant be loaded back to sp reg in this cycle and in cycle T4 ,T5-content of MBR is put to memory pointed by MAR then doesn it require 1 more cycle To load new value of SP to SP reg ???
Sequence of micro operations required

T1:- SP -> MAR, now as SP is 16 bits and data bus is 8 bit so it needs 2 cycles to move data

T2:- r->MBR; Both are 8 bit and no memory operation hence 1 cycle

T3:- M[MAR]<-MBR, move contents of MBR to memory pointed by MAR.AS its a memory operation ,it will take 2 cycles.SP can be decrement locally in same cycle.

So total 5 clock cycles.

well explained, thanks @rahul sharma 5

Can you please explain sp is decremented in which cycle and what does it mean by saying sp is decremented locally does it not require alu for this purpose and if alu is required then although durong the first cycle when sp is moved to mar we can move  of sp to reg A1 A0 and in sub cycle perform sp-1 but in T3- content of r is moved to MBR so new value of sp cant be loaded back to sp reg in this cycle and in cycle T4 ,T5-content of MBR is put to memory pointed by MAR then doesn it require 1 more cycle To load new value of SP to SP reg ??? @rahul sharma 5

3 cycles are required

what about size of input to MUX?

I've never encountered such a representation of Mux before, which is 1:2 here.
Hence, I guessed that it codes 16bits to 8bits and later the Demux decodes those 8bits to 16bits.
That's what 1:2 meant i guess.

one cycle for A to MDR

one cycle for SP to MAR

two cycles for write in memory

within this reference we can decrement SP value

so why not four cycles????
please explain how 3? you have to send sp to mar 2 times,through 8 bit bus,sp is given 16 bit register,then here only 2 cycles,from A/B which is  8 bit you can send to MDR in one more cycle,again for memory read 2 cycles,so total 5 cycles,please say where my approach is wrong?
In the figure you illustrated , there are 2 memory accesses that means 2+2=4 clock cycles requires .

@ arjun sir plz give a proper explanation for this question.
sp to mar takes 2 cycles as we can send only 8 bits at a time

Yes, You are correct,

The same is provided here too.

GATE | GATE-CS-2001 | Question 38 - GeeksforGeeks

A stack pointer is a small register that stores the address of the last program request in a stack

A stack is a specialized buffer which stores data from the top down. As new requests come in, they push down the older ones. The most recently entered request always resides at the top of the stack, and the program always takes requests from the top.

And SP decremented locally doesnt required any extra cycle

therefore memory operation required 2 cycles as mentioned in question. option A

because only MAR is directly connected to memory bus. SP is like a normal register rt?
I am considering  M[sp] <- r  as one memory operation and it is mentioned memory operation requires 2 cycle.

is it right?
Then the sequence of operations should be

MAR <- SP

MDR <- R

Wait for Memory complete.

But I'm not clear about the MUX and DEMUX in figure- guess something is wrong there and guess the actual question is no longer available.
yaah... what mux size of 8 x(2:1) stands for ? and deMux of size 8 x(1:2) too??

and i hv checked every book the question is exactly same evrywhr.

So you can give this ques. another shot...
thank you

Guess this is the original paper- but it is too blurred:

http://www.examrace.com/d/pdf/85fee1a1/GATE-Computer-Science-2001.pdf

MUX and DEMUX must be used for moving data in/out of SP and MAR. Since, they are of 8 bits, it would need 2 cycles to move the data from SP to MAR. Now, as per the diagram, SP can transfer data only via the common data bus. So, in these 2 cycles, we cannot transfer r to MDR which will require another cycle (for memory write operation address must be in MAR and data must be in MDR). So, totally 3 and 2 more for memory read.

reshown
@arjun

A microinstruction can't be further broken down into two or more. It can take more than a cycle if it involves a memory access. The first instruction given here isn't a microinstruction. It is an assembly lang instruction.

It can be broken down as:

T1 , T2: MAR<--SP

T3.      : MDR<-- r , SP<-- SP-1 ( it is not mandatory to decrement it in this cycle. Anyway, it can be decremented locally)

T4, T5     : M [MAR] <-- MDR

The problem says, 8-bit MDR, 8-bit data bus, 8 bit registers.Can't you see that the given CPU is 8-bit? 8 multiplexers transfer 8 bits when selection input is 0 and 1 respectively. We certainly need to move 16-bit SP to 16-bit MAR via a 8-bit bus. So, 2 cycles to get SP to MAR. In total, we need 5 of them clock cycles to execute a push.

Thank me later.
can't the operation of R->MDR and MAR->memory be multiplexed as MAR uses separate address bus.
This comes under which topic in GATE Computer Organization subject? Is this in syllabus?
I think this requires 3 clock cycles :

As Arjun sir said,for write operation, the data must be in MDR and address must be in MAR.

1 cycle required to load the SP into MAR (since SP and MAR are directly connected i,e no bus required) and simultaneously move the data to MDR (we need bus access here)

2 cycles required to load the data of MDR into the address the memory indicated by MAR (since it is given 2 mem cycles are required for each memory operation)

And SP can be decremented locally so no mem cycle required (we can do this during memory operation)

1 comment

3Cycles to load the MAR from SP as the bus is of 8bit but address is of 16bit and it  is non pipelined

To load the data from one of the registers to MDR we dont need additional cycles , can be done within this 3 cycles above .SP can be decremented locally so we dont need additional cycle for it.

2cycles to write the data into memory.

Therefore total 5 cycles.

official answer is given 3 cycles
official answer key for GATE 2001?
Can you plz explain how 3 cycles are needed to load the MAR from SP..

cycle1:

cycle2:

cycle3:

Because SP is store in MAR(it's a register there is no clock cycle needed for this)

M[MAR] <--r(A/B)  store the value in memory only need two clock cycle
by

3 clock cycles are needed

T1: MAR <- SP  // Bits in even positions are moved to MAR

T2: MDR <- r,  MAR <- SP  // Bits in odd positions are transferred to MAR

T3: M[MAR] <- MDR

At T2, Since the MAR and SP are connected directly through MUX/DEMUX and hence Data Bus is free to perform MDR <- r operation which requires 8 bit data bus and hence we can overlap these 2 operations.

by