GATE CSE 2014 | Set 3 | Question: 43

Question

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies $1$ ns, $2.2 $ ns, $2$ ns, $1$ ns, and $0.75$ ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency $2.2/3$ ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency $1$ ns. The new design has a total of eight pipeline stages. A program has $20\%$ branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are $P$ and $Q$ nanoseconds, respectively. The value of $P/Q$ is __________.

Comments

 in case of new pipeline  it is :-  max(1, 0.73, 0.73, 0.73,  1, 1,  1, 0.75) = 1

---

 

 

---

Alternative Approach: Assuming 100 Instructions

We can solve this by calculating the exact execution time for a sample program of $N = 100$ instructions.

 

The general formula for the total number of clock cycles in a pipeline is:

Total Cycles = (Pipeline Fill Time) + (Remaining Instructions) + (Stall Cycles)

Total Cycles = k + (n - 1) + (Number of Branch Instructions × Branch Penalty)

 

Here, $n = 100$. Since 20% of the instructions are branches, we have 20 branch instructions.

 

I) Old Design (P)

 

• Stages (k): 5

• Clock Cycle Time: max(1, 2.2, 2, 1, 0.75) = 2.2 ns

• Branch Penalty: The target is known at the end of the EX stage (3rd stage), so the penalty is $3 - 1 = 2$ stall cycles.

Total Time (P) = (Cycles for 1st instruction + Cycles for remaining 99 + Total Stalls) × Cycle Time

Total Time (P) = (5 + 99 + 20 × 2) × 2.2

Total Time (P) = (104 + 40) × 2.2 = 144 × 2.2 = 316.8 ns

 

II) New Design (Q)

 

• Stages (k): 8

• Clock Cycle Time: max(1, 0.73, 0.73, 0.73, 1, 1, 1, 0.75) = 1 ns

• Branch Penalty: The target is known at the end of the EX2 stage (6th stage), so the penalty is $6 - 1 = 5$ stall cycles.

Total Time (Q) = (Cycles for 1st instruction + Cycles for remaining 99 + Total Stalls) × Cycle Time

Total Time (Q) = (8 + 99 + 20 × 5) × 1

Total Time (Q) = (107 + 100) × 1 = 207 × 1 = 207 ns

 

Result:

The ratio $P / Q$ for 100 instructions is 316.8 / 207 ≈ 1.53.

 

(Note: The exact official answer is 1.54. The slight difference is because this method accounts for the initial pipeline fill time of $k$ cycles. If you assume a very large program where $N \to \infty$, the pipeline fill time becomes negligible, and the ratio perfectly approaches 1.54).

---

Reference : Carl Hamacher 

if the target address and outcome of a branch instruction are determined in stage $k$ of a pipeline, and the instruction fetch stage is held until this determination is complete, the branch instruction incurs $k - 1$ stall cycles

Don't get confuse between b/w two formula both are same 

1) $\text{CPI}_{\text{avg}} = (1 - f_{\text{branch}}) \times \text{CPI}_{\text{normal}} + f_{\text{branch}} \times (1 + \text{Stall Cycles})$

2) $\mathbf{\text{CPI}_{\text{avg}} = 1 + f_{\text{branch}} \times \text{stall cycles}}$

Answer 1

Five stages:

(IF), instruction decode and register fetch (ID/RF),

instruction execution (EX),

memory access (MEM), and register writeback (WB)

---

P old  design:

with stage latencies $\text{1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns}$

$\text{MAX( 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns) = 2.2nsec}$

AVG instruction execution time is 

$\text{Tavg=(1+no of stalls$\times $branch penality)$\times $cycle time}$

$=(1+0.20\times 2)2.2$  { branch peanlity is $2$ because the next instruction
     pointer at the end of the EX stage in the old design.}

 $=3.08 \text{ nsec}$

---

Q :new DESIGN:

the designers decided to split the ID/RF stage into three stages $\text{(ID, RF1, RF2)}$
each of latency $\dfrac{2.2}{3}\text{ ns}$. Also, the $EX$ stage is split into two stages
$\text{(EX1, EX2)}$ each of latency $1\text{ ns}$.
The new design has a total of eight pipeline stages.

Time of stages in new design $=\text{{1 ns, 0.73ns, 0.73ns, 0.73ns , 1ns,1ns, 1 ns, and 0.75 ns}}$

(IF), instruction decode

register fetch (ID/RF) $\rightarrow$ further divided into $3$ ie with latency $0.73$ of each 

instruction execution (EX) $\rightarrow$ further divided int $1\text{ nsec}$ of each)

memory access (MEM)

 register writeback (WB)

$\text{MAX( 1 ns, 0.73ns, 0.73ns, 0.73ns , 1ns,1ns, 1 ns, and 0.75 ns) =1 nsec}$

AVG instruction execution time is 

$\text{Tavg=(1+no of stalls$\times $branch penality)$\times $cycle time}$

$=(1+0.20\times 5)1$ { branch penalty is $5$ because the next instruction pointer
    at the end of the $EX2$ stage in the new design.}

$=2 \text{nsec}$

---

final result 

$\dfrac{P}{Q}=\dfrac{3.08}{2}=1.54$

Comments

I am also having the same doubt….can someone clear this doubt

---

@JAINchiNMay .The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed.

...

This means next instruction fetch stage 

[after the branch instruction] 

halts until the execution stage of branch instruction completes... 

---

The question means to say that NO other instruction can enter the IF stage of execution after the branch instruction, until the branch instruction passes through the EX stage.

Answer 2

cpi for first case $=2.2(1+2\times .2)$ as the stall required is $2$ and $2.2$
is the maximum stage delay.

cpi for second state $=1\times (1+5\times .2)$ as now stall increase to $5$ as
there are five stages before the address is calculated and the maximum stage
delay now is $1.$

$\dfrac{\text{cpu_time1}}{\text{cpu_time2}}=\dfrac{3.08}{2}=1.54$

Comments

How  to find s tall cycle ?? Im getting stall cycles as 3 and 6

---

Video Solution:

(Explained very nicely!)

and he calculated 3 and 6 CPI for Branch instead of 2 and 5 CPI

---

@arpit

Hey i guess you have mentioned wrong formula for CPI

CPI= 1+stall frequency*no of stall cycle

avg execution time= CPI*cycle time   where cycle time =max(stage delay)+register delay

what you have calculated is average execution time.

I know this does not affect the solution but using wrong notation or formula causes confusion.

Answer 3

OLD DESIGN :

phase time = 2 ns branch penalty= 2 (since execution is 3rd stage penalty will be of 2 cycles) ,                                                 other than all branch instrucions CPI = 1

branch instrucion = 20% , other instruction = 80%

total execution time = CPI*Phase time

                            = (1+2*.2)*2ns

                          P = 3.08ns

NEW DESIGN :

phase time = 1ns branch penalty = 5 (since EX2 is 6th stage penalty will be of 5 cycles)

total execution time = (1+.2*5)*1ns

                           Q= 2 ns

therefor P/Q = 3.08/2 = 1.54ns

Answer 4

Old design:

Two bubbles appear in the pipeline when a branch is taken. So clock cycles needed to complete the instruction after a branch is 3. Two cycles wasted by bubbles and one more to actually execute the instruction.

P = (0.8 * 1 + 0.2 * 3) * 2.2 = 3.08 ns

In new design, by the same reasoning, clock cycles for a branch instruction becomes 6. (5 bubbles + 1 )

Q = (0.8 * 1 + 0.2 * 6) * 1 = 2 ns

P/Q = 1.5

Answer 5

Old case :

stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns .

take MAX( 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns) = 2.2 ns

P= Tavg(old) = (0.2*3*2.2)+(0.8*1*2.2)= 3.08 ns.  // here 0.2(for brach instn..) , 3(CPI) , 2.2(MAX time delay) , 0.8(non branch) ,   1(CPI),2.2(MAX time delay)

 

New Case :

Time taken in stages ={1 ns, 0.73ns, 0.73ns, 0.73ns , 1ns,1ns, 1 ns, and 0.75 ns}

MAX( 1 ns, 0.73ns, 0.73ns, 0.73ns , 1ns,1ns, 1 ns, and 0.75 ns) =1 ns

Q= Tavg(New) = (0.2*6*1)+(0.8*1*1) = 2 ns   // here 0.2(for brach instn..) , 6(CPI) , 1(MAX time delay) , 0.8(non branch) , 1(CPI), 1(MAX time delay)

P/Q=3.08/2 = 1.54 

 

 

Answer 6

$T_{avg}$ for old design,

$\text{P = (cycles for unbranched inst + cycles for branched inst ) ×cycle time = (0.8*1+0.2*3)*2.2 ns = 3.08 ns}$

and

$T_{avg}$ for new design,

$\text{Q = (cycles for unbranched inst + cycles for branched inst ) ×cycle time = (0.8*1+0.2*6)*1 ns = 2 ns}$

 

$\therefore \ \frac{P}{Q} = \frac{3.08}{2} = 1.54$