Pipeline Execution time

Question

The instruction pipeline of RISC processor has 200 instructions in which 100 are performing addition, 25 performing division and 75 are performing multiplications, where Excution state for addition take 1 clock cycle, multiplication take 3 clock cycles and division take 5 clock cycles. Assume pipeline has 5 stages IF, ID, EX, MA and WB and their is no data and control hazard. The number of clock cycles required for execution of sequence of instructions are ________.

Ans. 454

Comments

https://gateoverflow.in/227703/pipeline-execution-time

found a link already ques here

---

Same question but the answer is changed by made easy.

They set some weird questions most of them tougher than Gate.

---

Gupta731 yes but  answer is 454 see 

i am mentioning from above Hemanth_13 comment

25*2--> 25 mul instruction takes 2 extra cycles(given 3==> one '1' cycle is considered in the previous step so taken 2

why they will take 4 cycles not 2  and we have 25  DIVISONS NOT MULTIPICATIONS.

so 25 * 4 there and multipication do yourself i think i.e. 75 * 2 

if any doubt then say ......but i thinkHemanth_13 take mul as division and vice versa

Answer 1

Ok let me explain...

Here, we go by sequence...

1. Now let's take 100 instructions, if you have drawn pipeline, then you know, very first instruction take all cycles then all consecutive instruction will be completed in every clock cycle so total cycles required by 100 instruction is =
   
                                          99*1 + 5(no. of pipeline stages)= 104
    
2. Now then take division instructions which are total 25, now as in above point, consecutive instruction will be completed in every clock cycle from now onwards but this instructions take 5 more cycles so
   
                                         25*5=125
    
3. Then take 75 multiplication instructions which take 3 more cycles, so
   
                                          75*3= 225

So total cycles needed is= 104+125+225 = 454

Comments

you can refer https://gateoverflow.in/204125/gate2018-50

---

i think it should be

$\left ( 100+5-1 \right ) + (25 \times (5-1)+75 \times (3-1))=104+100+150=354$

---

@Abbas

Brother Please Clear Some of my doubts here:-

1. If say Tp = 4ns which is the time taken by largest stage, if i say one stage takes 4 cycle it means there is a stall of 3 cycle because ideally every stage should take 1 clock cycle i.e. 1*4 = 4ns should be taken by every stage isn't it ?

2. When i say CPI = 1 it means its on an average per instruction right,because if i have no stalls then every stage will take 1 clock cycle so first instruction will take k*tp time to complete and after that every instruction takes tp time for large number of instruction it on an average instruction will take 1 tp time to complete which is equal to 1 clock cycle so CPI = 1

---

@Na462

Let me take your each point,

1. There shouldn't be stall cycles you should consider here, but yes, after 1st instruction all will be completed in 1 clock cycle.

2. Your 2nd point is correct...that's what I am saying, if no stall cyles, on an average you need only 1 clock cycle per instruction.

P.S.: If you consider stall cycles, then same above procedure you need to consider.

 

Let me know if still your doubt is not clear.

---

One more thing:-

1. Question here says there are no data and control hazards then how does the stalls appear. Is it because maybe condition like say in Fetch phase there was a miss so it resulted in more clock cycles ??

2. These two formula's:-

S = n*Tn/(K+(n-1))Tp                    and                   S = #Instruction * CPI * Tnp / (#Instruction * CPI * Tp)

they both are same right for large value of n only the difference is that in first formula the CPI is considered as 1 isn't it ?

Answer 2

Case 1: Number of the clock Cycle 200 instruction In Normal case

     =  5*1 + 199 * 1 (CPI = 1).

   =  5 + 199 = 204.

Case 2 : For Execution Phase

100 instruction takes 1 cycles i.e. these instructions suffering from 0 stall cycle,
25 instruction takes 3 cycles i.e. these instructions suffering from 2 stall cycle,
75 instruction takes 5 cycles i.e. these instructions suffering from 4 stall cycle,

So, extra cycle would be = 100*0 + 25*2+ 75*4 = 350 Cycles.

 

Total cycles =  204 + 350 = 554 Cycles.

Comments

@kumar.dilip Bro why  haven't u read question data properly.?

25 instruction are of division and 75 instruction are of multiplication.

Pls correct Ur answer.

Answer 3

Addition =100 and 1 clock

Division=25 and 5 clock

Multiplication=75 and 3 clock

 

Total time = 100×1+ 25×5 + 75×3 + 2+2=100+125+225+4=554

Example

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

IF

ID

EX

M

W

IF

ID

EX

M

W

IF

ID

EX

M

W

IF

ID

EX

EX

EX

M

W

IF

ID

EX

EX

EX

M

W

IF

ID

EX

EX

EX

M

W

IF

ID

EX

EX

EX

EX

EX

M

W

 

Total time= 2+ 3×1 + 3×3 + 1×5 + 2

                =2+3+9+5+2

                =21