GATE CSE 2001 | Question: 2.13

Question

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?

• A. $2$
• B. $3$
• C. $4$
• D. $5$

Comments

(292) Datapath GATE 2001-2020 | Lec. - 10 | COA GATE PYQ | GATE 2022 | Vishvadeep Gothi - YouTube

 

---

Important information about related to question

why SP is here ?

==> $SP$ means Stack Pointer. It is a register that stores the 16-bit memory address pointing to the current top of the stack in RAM.It is in datapath because it is needed for instructions like push ,pop operation.

Why MUX and DEMUX are Used

==> The central bus is only 8 bits wide, but $SP$ and $MAR$ are 16-bit registers. A 16-bit value cannot be transferred in a single clock cycle across an 8-bit bus.

==> MUX : Connects $SP$ to the bus. It splits the 16-bit $SP$ value into two 8-bit chunks (the lower byte $SP$ and upper byte $SP$), sending them onto the 8-bit bus one byte per clock cycle.

==> DEMUX : Connects the 8-bit bus to $MAR$ (and $SP$). It receives 8-bit chunks from the bus one at a time and directs them sequentially to either the lower byte or upper byte of $MAR$ to rebuild the full 16-bit address...

---

solution = "https://youtu.be/ZoZx1tc9glE?si=1UUWGB6TOhe_HQ3t"

Answer 1

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$

Comments

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

---

Even though this might seem silly, please help understand this.

Instead of doing $MDR\leftarrow r$ and then $M[MAR]\leftarrow MDR$

Why can't we do it directly like $M[MAR]\leftarrow r$

---

Because with memory we can only  send and recieve data via MDR only so register r  can't directly interact with memory location pointed by MAR.

Answer 2

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.

Comments

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

Answer 3

answer = option B
3 cycles are required

Comments

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

Answer 4

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

Comments

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

Answer 5

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)

Comments

i think your answer is right..now please tell what is the answer i should follow..? please tell if any discussion happened on this

---

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)
 

how SP and MAR are directly connected??

the bus is involved here too.. and at a time only one data can be there in the bus thus moving the content of SP into MAR will take 2 cycle (bcoz size of Bus is 8 bits). 

Now, MDR ← r  (this will take 1 cycle)

and at last  M[MAR] ← MDR will take 2 cycles (bcoz memory operation takes 2 cycles as given in the ques)

thus total 5 cycles.

Answer 6

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.

Comments

please explain this clearly

---

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: