GATE CSE 2018 | Question: 50

Question

The instruction pipeline of a RISC processor has the following stages: Instruction Fetch $(IF)$, Instruction Decode $(ID)$, Operand Fetch $(OF)$, Perform Operation $(PO)$ and Writeback $(WB)$, The $IF$, $ID$, $OF$ and $WB$ stages take $1$ clock cycle each for every instruction. Consider a sequence of $100$ instructions. In the $PO$ stage, $40$ instructions take $3$ clock cycles each, $35$ instructions take $2$ clock cycles each, and the remaining $25$ instructions take $1$ clock cycle each. Assume that there are no data hazards and no control hazards.

The number of clock cycles required for completion of execution of the sequence of instruction is _____.

Comments

Because the Extra cycle is only for the PO stage, not for all stages.

---

@shashankpal bless u

---

In Exam we can try this approach  to know how exactly extra cc we needed

Suppose n=1 instr then (suppose it is the instr from the 40 instr set )

by pipeline formula = 5 + 1-1 = 5 cc but if

we actually passs this instr from pipline then it will take #cc= 7 cc

suppose n=2 instr then (suppose it is the instr from the 40 instr set )

by pipeline formula = 5 + 2-1 = 5 cc but if

we actually passs this instr from pipline then it will take #cc= 10 cc

if we try to genralise it then 

for every instr from 40 instr set , there is 2 extra cc consumed .

means for this set there is extra cc needed = 40*2 = 80

now solve remaining part same like above.

Answer 1

Total Instruction $= 100$
Number of stages $= 5$
In normal case total cycles $= 100 +5 -1 = 104$ cycles

Now, For PO stage $40$ instructions take $3$ cycles, $35$ take $2$ cycles and rest of the $25$ take $1$ cycle.
That means all other stages are perfectly fine and working with $CPI$ (Clock Cycle Per Instruction)$ = 1$

PO stage:
$40$ instructions take $3$ cycles i.e. these instructions are suffering from $2$ stall cycle,
$35$ instructions take $2$ cycles i.e. these instructions are suffering from $1$ stall cycle,
$25$ instructions take $1$ cycles i.e. these instructions are suffering from $0$ stall cycle,

So, extra cycle would be $40*2 + 35*1 + 25*0 = 80+35 = 115$ cycle.

Total cycles = $104 + 115 = 219$

Comments

Why structural hazards are not taken into consideration here? i;e why are we considering that many PO instructions can be executed in parallel? In the question it has been told that there are no data and control hazards. If we do not make such assumptions, we get number of clock cycles as 227.

 

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# of Cycles

I1

IF

ID

OF

PO

PO

PO

WB

7

I2

IF

ID

OF

PO

PO

PO

WB

10

I3

IF

ID

OF

PO

PO

PO

WB

13

I4

IF

ID

OF

PO

PO

PO

WB

16

I5

IF

ID

OF

PO

PO

PO

WB

19

I6

IF

ID

OF

PO

PO

PO

WB

22

The number of cycles for 40 such instructions = 7 + (39)*3 = 124 cycles

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# of Cycles

I1

IF

ID

OF

PO

PO

WB

6

I2

IF

ID

OF

PO

PO

WB

8

I3

IF

ID

OF

PO

PO

WB

10

I4

IF

ID

OF

PO

PO

WB

12

I5

IF

ID

OF

PO

PO

WB

14

I6

IF

ID

OF

PO

PO

WB

16

The number of cycles for 35 such instructions = 6 + (34)*2 = 74 cycles

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# of Cycles

I1

IF

ID

OF

PO

WB

5

I2

IF

ID

OF

PO

WB

6

I3

IF

ID

OF

PO

WB

7

I4

IF

ID

OF

PO

WB

8

I5

IF

ID

OF

PO

WB

9

I6

IF

ID

OF

PO

WB

10

The number of cycles for 25 such instructions = 5 + (24)*1 = 29 cycles

The total number of cycles for 100 such instructions = 124 + 74 + 29 = 227 cycles

Please let me know if anything is wrong here.

---

I got the mistake I made in my previous comment.

See below image. Hopefully it helps someone. :)

---

@Digvijay Pandey

Why Instruction Fetch (IF) and Operand Fetch (OF) not causing Structural Hazard.

why are we assuming that system has Instruction-cache and Data-cache?

Answer 2

Total Instruction =100
Instruction Fetch (IF). Instruction Decode (ID). Operand Fetch (OF), and Write back (WB) performed in 1 cycle.
PO stage:
40 instructions takes 3 cycle
35 instructions take 2 cycles
25 instructions take 1 cycle
Average number of cycles required is = (40 x 3+35 x 2+25 x 1)/100 = 2.15 cycles.
On an average first instruction completed in 1+1+1+1+2.15 cycles = 6.15;
Remaining 99 instruction will takes 99 × 2.15 = 212.85 cycles
Total number of cycles is 6.15+212.85 = 219 cycles.

Comments

Why can't I do it with (k+(n-1))*tp

for PO stage: 0.4*3 + 0.35*2 + 0.25*1 = 2.15 cycles for PO stage. This is larger than all the 5 stages of the given pipeline.

So applying the above formula it gives (5+99)*2.15 =224 cycles.

---

yes same doubt @Gupta731

---

You are applying the formula wrong..

So according to your solution

First stage will execute in 6.15 cycles

The next 99 instructions will execute in 2.15 cycles..

Therefore time=6.15+99*2.15

                           =219

Answer 3

We have 100 instructions.We only focus on PO stages.Becoz of pipeline,instructions execute like this...

1st instruction takes (1+1+1+3+1)=7 Clock cycles.

2nd to 40th instructions PO stages takes=39*3 clock cycles.

41th to 75th instructions PO stages takes=35*2 clock cycles.

76th to 100th instruction PO stages takes=25*1 clock cycles.

So, total=7+(39*3)+(35*2)+(25*1).

219 clock cycles required.

Comments

Thanks. It really helps.

---

Thanks. Simple and easiest approach.

---

Nice approach

Answer 4

7 + 39×3 + 35×2 +25×1 = 219 clock cycle

Comments

Another way could be 100 + Extra cycles  = $100 + 40*2 + 35 + 4$ (for initial filling of pipeline) = 219