Test Series: ACE

Question

How to approach this one?

 

In a pipelined processor, all stages are perfectly balanced and there is no hazard when an application is executing on this five stage pipelined CPU, the speed up achieved with respect to the non pipelined CPU execution if $20 \%$ of the instructions incur one pipeline stall cycle is $\qquad$

Answer 1

Theory :

Let,

$n$ be number of instructions,

$k$ is number of stages in pipeline,

$T_P$ is one cycle time of pipelined processor

In pipelined processor only  $1^{st}$ instruction takes $k\times T_P$ time,

all other $(n-1)$ instructions take $1$ cycle time $=(n-1)\ T_P$

Total execution time on pipelined processor assuming no stalls $T_{EP}=k\space T_P+(n-1)T_P=(n-1+k)T_P$

Execution time of each instruction on non-pipelined processor  $T_n=  k\times T_P$

Total execution time on non-pipelined processor  $T_E=n\space k\space T_P$

$Speed Up = \frac {\text{total execution time without pipeline}}{\text{total execution time with pipeline}}=\frac {T_E} {T_{EP}}=\frac{(n\space k\space )T_P}{(n-1+k)T_P}\approx k$

Approximation based on $n>>k,\therefore (n-1+k)\approx n$ 

Now, let $I$ is stalls per instruction in pipelined processor that is $I \times T_P$ time extra per instruction,

Total execution time in pipelined processor,

$T_{EP}=(n-1+k)T_P + (n\times I) T_P =(n+I.n-1+k)T_P=((1+I)n-1+k)T_P$

$Speed Up = \frac {(n\space k)T_P}{((1+I)n-1+k)T_P}\approx \frac k {1+I}... (n>>k)$

Solution :

$k=5$ , $ 20$% instruction cause one stall,

$n$ instruction cause $n\times20$% stall $=0.2n$ stalls.

Stalls per instruction $I=\frac {0.2n}{n}=0.2$

$SpeedUp = \frac {5} {1+0.2} = \frac {5} {1.2} \approx 4.17 $

 

Comments

Thanks a ton!