GATE CSE 2004 | Question: 64

Question

Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$

$$ \begin{array}{|l|l|c|} 
\hline 
\text{Instruction} & \text{Operation} & \text{Instruction size (in Words)} \\
\hline 
\text{MOV } R_1, 5000 & R_1 \leftarrow \text{Memory}[5000] & 2 \\
\hline
\text{MOV } R_2, (R_1) & R_2 \leftarrow \text{Memory}[(R_1)] & 1 \\
\hline 
\text{ADD } R_2, R_3 & R_2 \leftarrow R_2 + R_3 & 1 \\
\hline 
\text{MOV } 6000, R_2 & \text{Memory}[6000] \leftarrow R_2 & 2 \\
\hline 
\text{Halt} & \text{Machine Halts} & 1 \\
\hline 
\end{array} $$

Let the clock cycles required for various operations be as follows:

$$ \begin{array}{|l|l|} \hline \text {Register to/from memory transfer}  &  \text{3 clock cycles } \\\hline  \text {ADD with both operands in register}  &  \text{1 clock cycles } \\\hline \text {Instruction fetch and decode}  &  \text{2 clock cycles }\\\hline \end{array} $$

The total number of clock cycles required to execute the program is

• A. $29$
• B. $24$
• C. $23$
• D. $20$

Comments

@Psy Duck then why are we considering 4 cycles for fetching and decoding the first instruction in the selected answer?

---

@Cormen Because after fetching, we also need to check the opcode to determine if we need to bring one more instruction before we can start decoding. There might be two cases. One being, we already have some extra logic in the fetch unit so that we can examine the opcode in the fetch cycle itself without wasting another cycle (assuming $1$ cycle for fetch and $1$ cycle for decode). If this were the case, then $2$ word instructions would take $3$ cycles for fetch and decode instead of $4$, and the answer would have been $22$ cycles instead of $24$, which is not in the options.

---

in the MOV R2,(R1) // R2 <- M[(R1)] // where (R1) = M[M[R1]] ? which will take like 2 memory access

Answer 1

B.  $24 \text{ cycles}$

$$\begin{array}{|l|c|c|} \hline \text {Instruction}  &  \text{Size }& \text{Fetch and Decode + Execute} \\\hline \text{MOV} & \text{$2$} & \text{$2$} \times \text{$2 + 3 = 7$} \\\hline  \text{MOV} & \text{$1$} & \text{$2$} \times \text{$1 + 3 = 5$} \\\hline  \text{ADD} & \text{$1$} & \text{$2$} \times \text{$1 + 1 = 3$} \\\hline \text{MOV} & \text{$2$} & \text{$2$} \times \text{$2 + 3 = 7$} \\\hline \text{HALT} & \text{$1$} & \text{$2$} \times \text{$1 + 0 = 2$} \\\hline   & \text{Total} & \text{$24 $ Cycles} \\\hline \end{array}$$

Comments

@cormen CPU can fetch one word at a time. So for multiword instructions first word is fetched during instruction fetch cycle then remaining words are fetched during decode of the instruction. Actually thats why it is called fetch-decode cycle.

---

the  statment :"CPU fetches one word at a time"

but that was not given in question, also, there a default thing, that memory is byte addressable, then cpu may fetch one byte at a time.

they should mention in question....

is there any other approach?

---

is the intution: cpu fetches one word at a time is default

just like memory is byte addressable?

Answer 2

Each instructions requires fetch and decode

So total instructions size is 7 words

Number of cycles = 7*2=14 cycles

Now in addition to that

Move     R1,5000 3 cycles for register /to memory transfer

Move     R2,(R1)  3 cycles

Add        R2,R3    1 cycle ALU

Move     6000,R2  3 cycle

Additional 10 cycle

Total = 14+10=24 cycles

Comments

very well explained

---

how instruction 4 will get 3 cycles is it go into instruction decode phase?

---

Memory transfer to register

Answer 3

The clock cycles are per block; if an instruction size is 2 then it requires twice no. of clock cycles.

Instruction no.       size                                              no. of clock cycles

1                                2                                                                       3*2+2

2                                1                                                                       1*3+2

3                                1(add only)                                                      1

4                                2                                                                       3*2+2

5                                1                                                                       2(fetch and decode)

Total                                                                  24

  So answer is (B)

Comments

correct xplaination ..nice

---

@debojit1990, In the second instruction it is register indirect addressing, first read is to register and second read is to memory, since time to register read is not given we are only considering only memory read

---

Instead of register indirect in second instruction if memory indirect will be there then we should take 2 memory ref that means 6 cycles or 3 cycle ?

Answer 4

$3+3+1+3+7(2)=24$

Why the Instruction Fetch and Decode is counted 7 times when the number of instructions are 5?

Because the largest unit of memory that can be transferred to and from it, in a single operation is the word size. Since there are 7 words in total, to fetch them we need to devote 7 separate operations, and each such operation would take 2 clock cycles (given)

Comments

This explanation is not correct.

---

The equation I wrote here is literally equivalent to the one in the best answer, lol.

Still, please come up with the reasoning as to why is it not correct, I'd be happy to rectify myself :)

---

Btw, this is what Hamacher has to say:

---

I feel, Question seems to be misguiding as they asked "The total number of clock cycles required to Execute the program is".  

But the options given are for all phases of the entire program.

---

superb explanation

Answer 5

 

---

Given:

• Instruction fetch + decode = 2 cycles    Register ↔ Memory transfer = 3 cycles      ADD with both operands in registers = 1 cycle

Instructions and sizes:

Instruction	Operation	Size (words)
MOV R1, 5000	R1 ← Memory[5000]	2
MOV R2, (R1)	R2 ← Memory[(R1)]	1
ADD R2, R3	R2 ← R2 + R3	1
MOV 6000, R2	Memory[6000] ← R2	2
Halt	Machine halts	1

---

Step 1: Instruction fetch & decode

• Instruction size matters only for fetch, because CPU fetches each word separately.

• Each word fetch = 2 cycles

Instruction 1: MOV R1, 5000 (2 words)

• Fetch word 1: 2 cycles

• Fetch word 2: 2 cycles

• Memory transfer (R1 ← Memory[5000]): 3 cycles

• 
  Total = 2 + 2 + 3 = 7 cycles

---

Instruction 2: MOV R2, (R1) (1 word)

• Fetch: 2 cycles

• Memory transfer (R2 ← Memory[(R1)]): 3 cycles
  Total = 2 + 3 = 5 cycles

---

Instruction 3: ADD R2, R3 (1 word)

• Fetch: 2 cycles

• ADD (register operands): 1 cycle

• 
  Total = 2 + 1 = 3 cycles

---

Instruction 4: MOV 6000, R2 (2 words)

• Fetch word 1: 2 cycles

• Fetch word 2: 2 cycles

• Memory transfer (Memory[6000] ← R2): 3 cycles

• 
  Total = 2 + 2 + 3 = 7 cycles

---

Instruction 5: Halt (1 word)

• Fetch: 2 cycles

• No other operation

• 
  Total = 2 cycles

---

Step 2: Add all cycles

7 + 5 + 3 + 7 + 2 = 24 

 Answer: B. 24

 

Answer 6

Ans