16,926 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$

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$

@rajaneesh16 Good explanation. One thing: It is said that $SP$ can be decremented locally. So we assume it to be done in the local bus. Now when in $T3 : MDR\leftarrow r$ is being done how can we do $SP\leftarrow SP-1$ in the same cycle? $SP\leftarrow SP-1$ must be decremented in $T4$ where only System Bus is being used and Internal Local Bus is free.

@Abhrajyoti00

Why not?  in T3 while performing $MDR ← r$ only system bus is in use, and internal bus is free here.

anything wrong in this?

Yes @Pranavpurkar. Previously I was unaware of how internal bus and system bus work independently in the same cycle.

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

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

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?