GATE CSE 2005 | Question: 80

Question

Consider the following data path of a $\text{CPU}.$

The $\text{ALU},$ the bus and all the registers in the data path are of identical size. All operations including incrementation of the $\text{PC}$ and the $\text{GPRs}$ are to be carried out in the $\text{ALU}.$ Two clock cycles are needed for memory read operation – the first one for loading address in the $\text{MAR}$ and the next one for loading data from the memory bus into the $\text{MDR}.$

The instruction "call Rn, sub” is a two word instruction. Assuming that $\text{PC}$ is incremented during the fetch cycle of the first word of the instruction, its register transfer interpretation is

$\text{Rn} \leftarrow \text{PC} + 1$;

$\text{PC} \leftarrow \text{M[PC]}$;

The minimum number of CPU clock cycles needed during the execution cycle of this instruction is:

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

Comments

What is S and T here?

---

Can u explain how 3 cycles??

---

Before looking at explanation first think --->

• First check given architecture carefully.(means check various component and their functionality )
• What are all micro-instruction required.
• How many of them could be done in parallel. 

Execution cycle means OF + EX + WB together. I think keeping these things in mind proper answer could be obtained. 

---

Can someone tell me what GPRs is?

---

General Purpose Registers

---

Yes, general purpose register.

---

$"call\ Rn,sub"$

$Rn\Leftarrow PC+1$

$PC\Leftarrow M[PC]$

---

$T1: PC_{out},S_{in},MAR_{in}$

$T2: Inc,ALU_{out},Rn_{in}|Local\ Bus$

        $M[MAR_{out}]\Rightarrow MDR_{in}|System\ Bus$

$T3: MDR_{out},PC_{in}$

---

$Ans:B$

---

@Kushagra गुप्ता

Can you tell , what is meaning of "call Rn,sub"?

It is a subroutine call instruction, right? And what is it doing?

We have asked here , for only execution cycle. So, we need to eliminate instruction from fetch cycle. right?

 

---

@srestha

Can you tell , what is meaning of "call Rn,sub"?

If RTL is not been given for this instruction i would not be able to interpret. 

We have asked here , for only execution cycle. So, we need to eliminate instruction from fetch cycle. right?

Yes.

It is a subroutine call instruction, right? And what is it doing?

No idea.

 

---

@Kushagra गुप्ता

If we couldnot understand , what the statement actually mean, then how can we determine about the number of cycles it require?

Moreover

PC is incremented during the fetch cycle

And question asking about execution cycle.So, in PC increment doesnot require any extra cycle. right? 

---

@srestha

If we couldnot understand , what the statement actually mean, then how can we determine about the number of cycles it require?

We could understand because of Register transfer interpretation given for this instruction.

$Rn\Leftarrow PC+1$

$PC\Leftarrow M[PC]$

And question asking about execution cycle.So, in PC increment doesnot require any extra cycle. right? 

I don't think it should require any extra cycle because it can be done in the local bus along with other instruction. And yes the question is specifically asking about Execution cycle so we are least interested in Fetching.

---

@Kushagra गुप्ता 

We could understand because of Register transfer interpretation given for this instruction

What do you mean by it?  

See here in answer given, it is telling

MAR ← PC takes 1 cycle. Then why this step is required if "PC is incremented during the fetch cycle"? We should do this question within 2 cycles. right?

---

@srestha

What do you mean by it?  

https://en.wikipedia.org/wiki/Register_transfer_language

See here in answer given, it is telling

MAR ← PC takes 1 cycle. Then why this step is required if "PC is incremented during the fetch cycle"? We should do this question within 2 cycles. right?

We have put the value of PC in S in order to do this operation : $Rn\leftarrow PC+1$ and we have to put the value of PC in MAR too, so that when we can perform this $M[MAR]\rightarrow MDR$ operation with the old value of PC which is there before the increment.  

---

@Kushagra गुप्ता

We have put the value of PC in S in order to do this operation : Rn←PC+1 

why? In which line it is asked in question?

Another thing

why these two line is written in ans

RN ← S+1     (ALU Is free and the two actions are independent.) (Internal BUS) 
PC ← MDR→3rd cycle 
 

 I mean why S value again need to load in $R_{N}$ and MDR value need to load in PC?

---

@srestha

why? In which line it is asked in question?

All operations including incrementation of the PC and the GPRs are to be carried out in the ALU.

I mean why S value again need to load in RN and MDR value need to load in PC?

Why did you used the word again? We are loading in Rn because that's what we need to do as specifically mentioned in RTL.

And because of this : $M[PC]\rightarrow PC$ we have to perform these two operations :

$M[MAR]\rightarrow MDR$

$MDR\rightarrow PC$

And this is the only possible way to get the content of memory by putting it in $MDR$ and to load it somewhere using $MDR$

---

@Kushagra गुप्ता

 

M[MAR]→MDR

MDR→PC

And this is the only possible way to get the content of memory by putting it in MDR and to load it somewhere using MDR

Does they asked for it?

They asked to show the execute cycle of "call Rn, sub”.

And that maynot even require PC,GPR,S or T(as shown in diagram) , those thing when this subroutine is calling.

register transfer interpretation

Rn←PC+1;

PC←M[PC];

These lines may be also require in Fetch cycle, but not Execute cycle.right? 

---

@srestha

Does they asked for it?

Even if they didn't ask then how are you planning to do it ?

They asked to show the execute cycle of "call Rn, sub”.

And that maynot even require PC,GPR,S or T(as shown in diagram) , those thing when this subroutine is calling.

Please, can you write down the steps for $"call\ Rn,sub"$ which you think is valid.

---

@Kushagra गुप्ता

I think like this.

Though the question is asking for execution cycle, but in this subroutine call instruction, there is nothing to execute. Like add, subtract or branching like operation. 

So, what is need to be perform here, nothing but Fetch cycle.

Steps are

1) First Fetch address of the subroutine. Put MAR value in PC.

2)Increment PC value. As it is a memory read operation, wait for Memory Function Complete Signal(WMFC).

3) Fetch data By MDR and put it in IR.

Let me know, if it is correct.

---

someone please provide video lecture link related to this concept

Answer 1

• $\text{MAR} \leftarrow  \text{PC}\qquad \to1$ cycle
• $S \leftarrow \text{PC}$ (Since these two actions are independent they can be done in same cycle)
• $\text{MDR} \leftarrow \text{M[MAR]}\qquad \to 2^{nd}$ cycle (System BUS)
• $\text{Rn} \leftarrow S +1$ $(\text{ALU}$ Is free and the two actions are independent.) (Internal BUS)
• $\text{PC} \leftarrow \text{MDR}\qquad \to 3$rd cycle

Therefore $3$ cycles needed.

A rough sketch:

Correct Answer: B

Comments

during the 2^nd cycle , we are using the bus to transfer the result of (PC+1) into Rn.
That’s why we can’t use it to transfer PC← MDR  @Abhrajyoti00

---

No, @Alekhyo Banerjee. That's not the reason. I got it now. 

We could have done $PC <- MDR$ in the same 2nd cycle only, because reg-reg transfer opn takes 1 cycle and we can do many reg-reg transfer opn in 1 cycle. The problem is that in the 2nd cycle there is a operation of $MDR <- M[MAR]$. Till the value comes into $MDR$, how can we store the value of $MDR$ in $PC$? That's the reason why we need to wait more cycle.

---

But the question says that the Instruction is of 2 words, so 1st word is fetched during Fetch cycle, and the 2nd word of the instruction is fetched in the Execution cycle (Instruction Decode cycle) isn't it? Then 1 more cycle should be added to 3 cycles (4 cycles in total). Correct me if I am wrong.

Answer 2

_{Rn <= Pc+1}

_{Pc<= M[Pc]}

The sequence of instruction take place 

 

I Cycle : PC _out  , S_{in ,} MAR_in (MAR can be loaded with PCout

II Cycle: S _out  , ALUincrement  , R_{n in}

III Cycle: MDR_{out  ,}   PC_in  (MDRout can be performed once MARin has been performed)   therefore 3 cycle required

 

Comments

why we need to store PC value in MAR and Sin??and can we transfer PC content to Sin and MAR in same clock cycle?

Thanks

---

Obviously we can store in same clock because once the content of PC is on bus both the registers MAR and S can activate their load input to take the data on the bus.

Answer 3

Hi Guys,

Although many people have provided correct answer but It seems people want to see complete picture so just adding this answer.

So Answer is B part.

In above explanation $S$ is a temporary ALU register. Notice data to and from memory comes and goes via MDR that too via separate BUS.

If provided information is not correct then please notify.

Comments

@Chhotu ji

can u share the source, from where u given ans?

---

can u share the source, from where u given ans?

@srestha ji,

This answer is not available anywhere. I derived it based on whatever is mentioned in question and standard text book.

---

very nice explanation...but i have one doubt

the pc will increment to 2 in instruction fetch phase  or it will increment to 2 after instruction decode phase?

---

Great solution considering the book Hamacher et al.

A correction by the way, the register Rn_in takes input from MAR_in

Answer 4

1)PCout ,MARin,Rin

2)MDRout ,PCin

2 cycles to read

so total 3  cycles

Comments

can you explain your answer somewhat..as i am not able to understand any of the answers.

---

@Arjun Sir.

I am getting this. Question says, ”PC is incremented during the fetch cycle of the first word of the instruction”. So increment not needed during execution phase.

Please tell if this is correct or not.

T1: $PC_{OUT}, MAR_{IN}, Rn_{IN}, READ$

T2: $WMFC (i.e. MBR\leftarrow MEMORY)$

T3: $MBR_{OUT}, PC_{IN}$