GATE IT 2007 | Question: 41

Question

Following table indicates the latencies of operations between the instruction producing the result and instruction using the result.
$$\begin{array}{|l|l|c|} \hline \textbf {Instruction producing the result} &  \textbf{Instruction using the result }& \textbf{Latency} \\\hline \text{ALU Operation} & \text{ALU Operation} & 2 \\\hline \text{ALU Operation} & \text{Store} & \text{2}\\\hline \text{Load} & \text{ALU Operation} & \text{1}\\\hline \text{Load} & \text{Store} & \text{0} \\\hline \end{array}$$

Consider the following code segment:

 Load R1, Loc 1; Load R1 from memory location Loc1
 Load R2, Loc 2; Load R2 from memory location Loc 2
 Add R1, R2, R1; Add R1 and R2 and save result in R1
 Dec R2;         Decrement R2
 Dec R1;         Decrement R1
 Mpy R1, R2, R3; Multiply R1 and R2 and save result in R3
 Store R3, Loc 3; Store R3 in memory location Loc 3

What is the number of cycles needed to execute the above code segment assuming each instruction takes one cycle to execute?

• A. $7$
• B. $10$
• C. $13$
• D. $14$

Comments

What is the answer ? 13 or 14?

---

instruction i4 is decrementing i.e arithmatic operation it is betn LOAD and ALU operation so latency is 1

you havnt included that ...

---

No.The explanation given above is correct and answer is 13 only.

See-->

I3 is ALU operation which uses result of LOAD in I2 , so latency is of 1 cycle (after I2)

I4 is ALU operation which uses result of LOAD in I2 , so latency is of 1 cycle (after I2) but I3 is executing at cycle 4. Therefore. I4 will execute at cycle no. 5.

I5 is ALU operation using result of ALU in I3 therefore has to wait for 2 cycles after I3

I6 is ALU and uses result of ALU in I5 ,therefore waits 2 cycles

---

https://youtu.be/lUcMdRwdlOw?si=HUbLUolv-kfJLV75

Answer 1

In the given question there are $7$ instructions each of which takes $1$ clock cycle to complete. (Pipelining may be used)
If an instruction is in execution phase and any other instructions can not be in the execution phase. So, at least $7$ clock cycles will be taken.
Now, it is given that between two instructions latency or delay should be there based on their operation. Ex- $1^{st}$ line of the table says that between two operations in which first is producing the result of an ALU operation and the $2^{nd}$ is using the result there should be a delay of $2$ clock cycles.

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c||} \hline \text {Clock cycle} & \text{T1} & \text{T2}&  \text{T3 }& \text{T4} & \text{T5} & \text{T6} & \text{T7}&  \text{T8 }& \text{T9} & \text{T10} & \text{T11} & \text{T12}&  \text{T13 }\\\hline & \text{I1} & \text{I2} &  & \text{I3}&  \text{I4 } & & \text{I5} & & & \text{I6} & & & \text{I7}\\\hline \end{array}$$

 

1. Load R1, Loc 1; Load R1 from memory location Loc1
   Takes 1 clock cycle, simply loading R1 on loc1.
    
2. Load R2, Loc 2; Load R2 from memory location Loc2
   Takes 1 clock cycle, simply loading r2 on loc2.
    
3. (Add R1, R2, R1; Add R1 and R2 and save result in R1
   R1=R1+R2;
   Hence, this instruction is using the result of R1 and R2, i.e. result of Instruction 1 and Instruction 2.
   As instruction 1 is load operation and instruction 3 is ALU operation. So, there should be a delay of 1 clock cycle between instruction 1 and instruction 3, which is already there due to I2.
   As instruction 2 is load operation and instruction 3 is ALU operation. So, there should be a delay of 1 clock cycle between instruction 2 and instruction 3.
    
4. Dec R2; Decrement R2
   This instruction is dependent on instruction 2 and there should be a delay of one clock cycle between Instruction 2 and
   Instruction 4. As instruction 2 is load and 4 is ALU, which is already there due to Instruction 3.
    
5. Dec R1 Decrement R1
   This instruction is dependent on Instruction 3
   As Instruction I3 is ALU and I5 is also ALU so a delay of 2 clock cycles should be there between them of which 1 clock cycle delay is already there due to I4 so one clock cycle delay between I4 and I5.
    
6. MPY R1, R2, R3; Multiply R1 and R2 and save result in R3
   R3=R1*R2;
   This instruction uses the result of Instruction 5, as both instruction 5 and 6 are ALU so there should be a delay of 2 clock cycles.
7. Store R3, Loc 3 Store R3 in memory location Loc3
   This instruction is dependent on instruction 6 which is ALU and instruction 7 is store so there should be a delay of 2 clock cycles between them.

Hence, a total of 13 clock cycles will be there.

Correct Answer: $C$

Comments

well explained!!

---

best explaination !!

---

I just have one doubt why the Decrement instructions are considered as ALU instructions?

Increment and Decrement can also be done using counter circuits without the need of using the ALU for the same.

---

Wonderful explanation

---

Greatly explained! Thank you

---

If DEC was not considered to be an ALU operation then the answer would be 10 because there would be no time dependency between DEC and MPY which would reduce the answer by 2 and the additional delay that was added between DEC and DEC can be reduced.

---

what a lovely explanation

---

why aren't we considering dependencies here!? as there is WAR dependency between I3 and I4! @madhab

---

the first two instructions are using store and load which takes a latency of 0 according to given table in the question.but in your explanation you have taken it as latency 1.why?

please reply.

---

plz help   ,The difference between Ints4 and Inst2 is 1 right I got it but if you look in the diagram there  is a difference of 2 cycles that is T3 and T4  between I4 and I2.plz tell where i get it wrong

---

@sudharshan

Already mentioned in question that each instruction takes one cycle to execute.

So,for those instructions, you must add one more clock cycle with whatever you got from instruction operation. 

---

@Mostafize Mondal so what are you saying  is that T4 is not counted as latency for Instrn.4 if that is the case then how would you define the the  number of cycles between Inst5 and Inst3 is it 1 or 2  .

Pictorially the difference in no. of cycles between  instr2 and Inst4 is similiar to Instr.3 and Instr5 but it is not it is 1 and 2 respectively .

plz help

thanks

---

@suraj777

Instruction 4 is dependent on instruction 2.As instruction 2 is load and instruction 4 is ALU.So,there should be delay of one clock cycle between those instructions,which is already there due to instruction 3.

We know that CPU executes instructions one by one.Becoz of pipeline,we can do parallel works at a time.So, instruction 4 will complete  after completing of instruction 3.

---

Amazing Explanation :)

---

Very good & Detailed answer

---

beautiful explanation loved it.

---

Why do we consider DEC as an ALU operation?

---

@gmrishikumar I think unless specifically mentioned we should consider it as an ALU Operation only...
http://www.learnabout-electronics.org/Digital/dig58.php#:~:targetText=The%20ALU%20can%20also%20perform,decrement%2C%20subtract%201%20from%20it.&targetText=Putting%20the%20correct%20pattern%20of,input%20at%20A%20and%20B.

---

For I3 why we are not considering 2 more cycle delay as we are performing Alu opn and then storing it... According to table we need 2 cycle delay in between them

---

6. MPY R1, R2, R3; Multiply R1 and R2 and save result in R3
R3=R1*R2;
This instruction uses the result of Instruction 5, as both instruction 5 and 6 are ALU so there should be a delay of 2 clock cycles.

i have a doubt that for MPY instruction uses the result of both DEC R2 and DEC R1, so why did we consider only instruction 5 for delay. shouldn't it be 3 cycles. 

2 for instr 4 and 6 and 2 cycle for instr 5 and 6. as instruction 5 is in between so it will take 1 clock so (2-1)+2 = 3. ?

---

@Shivam Kasat

Because in title/heading of the table it is written that latency is to be considered when an “instruction is using the result” from “instruction producing the result” 

In I4, R2 is being used by I4, which is also used by I3, but it is not a result produced by I3. 

 

---

I4 MUST be taking 2 cycles right (1 execution cycle  + 1 cycle for operation between load and ALU instruction), then why you have allotted only 1 cycle? I am totally fine with other operation. But confused about I4 taking only 1 cycle.

NOTE : It’s mentioned that each instruction takes 1 execution cycle.

For me it’s :

(execution time + time consumed between 2 instructions) :

Total time : ((1+[0])[load(I1) + store(I1)] + (1+[0])[load(I1) + store(I1)] + (1+[1])[load(1) + ALU(I3)] + (1+[0])[load(I2) + store(I4)] + (1+[2])[store(I5) + ALU(I3)] + (1+[2])[store(I4, I5) + ALU(I6)] +(1+[2])[store(I7) + ALU(I6)]) = 14 cycles.

Decrement operation can be done using hardware of which executed value can be then stored directly.

Option (D)

Please help where I am going wrong.

---

I am having the same doubt ....we don't consider it because of parallel execution ?? Means both the operands are fetched parallely so the maximum is 2 cc ?? @Arjun Sir please clarify ...

---

Simply superb

---

Very well explained ! Thanks @Madhab.

---

Bohot pyara likha hai Bhai.

---

This is the best answer ! I wasted my 1 hour time by ignoring this answer and searching in some other sources😵

---

great explanation bro

---

bhai literally you turned that complex logic into simple logic

---

As I6 is using result of I5 so there should be delay of 2 cycles , at the same time I6 is also using result of I4 , as both are ALU operations there should be 2 delay , out of 1 delay is already ther due to I5  so there should be extra one delay i.e at I6 there should be 2+1 = 3 extra dely ???

---

N210479_GEDELA_LEELA

No, it's the overall delay that needs to be counted...Just think R2 needs to wait only 1 cycle and R2 needs to wait for 2 cycles....Since 1 delay is already there due to I5, after another delay(clock cycle) R2 is available for us to use independently...So we only have to wait for one more clock cycle so that R1 is also available

Answer 2

Answer is (C)

Here each instruction takes $1$ cycle but apart from that we have to consider latencies b/w
instruction: If there are two ALU operations by $I1$ and $I2$ such that $I2$ uses the value
produced by $I1$ in some register then $I2$ will be executed ONLY after waiting TWO more
cycles after $I1$ has executed because latency b/w two ALU operations is $2$

See here:

Clock	1	2	3	4	5	6	7	8	9	10	11	12	13
Instruction	I1	I2	-	I3	I4	-	I5	-	-	I6	-	-	I7

 

$I3$ is ALU operation which uses the result of LOAD in $I2,$ so latency is of $1$ cycle.

$I5$ is ALU operation using result of ALU in I3, therefore, has to wait for $2$ cycles after $I3$

$I6$ is ALU and uses result of ALU in I5, therefore waits for $2$ cycles

Comments

I3 is ALU operation which uses result of load in I2 hence latency should be two cycles

I4 is also ALU opn which uses result of load in I2 hence latency 2

I5 is ALU - ALU hence 2

I6 latency 2

I7 latency 1

In this way answer comes to be 16.

Can you please clear my doubt sir?

---

instruction i4 is decrementing i.e arithmatic operation it is betn LOAD and ALU operation so latency is 1

you havnt included that .

---

Short and Crisp answer

Answer 3

cool answer...>>

Comments

totally not cool. For such a good answer to be at bottom!

---

beautifully explained :)

Answer 4

As per the given table and the assumption that 
The instruction of Type R1 <- R1 + R2 requires 
2 x (load - alu op) type
1 x (alu op - store) type

Then the answer should be 14

Analysis:
Instr | Cost
==== ====
1. 0
2. 0
3. 1+1+2 = 4
4. 1+2 = 3
5. 1+2 = 3
6. 1+1+2 = 4
7. 0

AND 
if, R1 <- R1+R2 
is only an (alu-store) type.. then intrs. 3 and 6 take 2 time units each
resulting in the answer as 10..

Unless, somebody presents a different interpretation.. 

Comments

I m not sure between (A) and (B).. If go with table.. it will come out to be 10 clocks, assuming 1 latency is 1 clock.

Next it is clearly given that "Assuming each instruction takes one cycle to execute".. here there are 7 instructions.. So 7 cycle.. isn't it?.. So which should we follow the table or the statement that given..?

---

made easy soluion

Answer 5

explanation using clock cycle graph

Answer 6

Video Analysis (Good Analysis)

https://youtu.be/lUcMdRwdlOw?si=jZsmWFuXRFiB_HTc