1.8k views

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

The CPU instruction "push r" where, r = A or B has the specification

M[SP] ← r

SP ← SP - 1

How many CPU clock cycles are required to execute the "push r" instruction?

1. 2
2. 3
3. 4
4. 5
retagged | 1.8k views
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
If somebody is thinking -->  why Mux and DeMux is used ?  then  It is used because bus size and memory address size is different.

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. 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
Thank me later.
selected by

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.

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

3 cycles are required

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

@amarVashishth First of all thanks for giving nice explanation.

>Each memory operation takes 2 CPU clock cycles

Given Diagram does not support above statement. We have only one common data Bus so from diagram all memory related operation can not be performed in 2 Cycles. It seems question or diagram needs some correction.

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 vote
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:
+1 vote
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.

1
2