10,076 views

A processor takes $12$ cycles to complete an instruction I. The corresponding pipelined processor uses $6$ stages with the execution times of $3, 2, 5, 4, 6$ and $2$ cycles respectively. What is the asymptotic speedup assuming that a very large number of instructions are to be executed?

1. $1.83$
2. $2$
3. $3$
4. $6$

### 1 comment

A really good question.

For non pipeline processor we have n instruction and each instruction take
$12$ cycle so total $12n$ instruction.

For pipeline processor we have each stage strict to $6ns$ so time to complete
the $n$ instruction is $6\times 6+ (n-1)\times 6$.

$\lim_{n \to \infty }\dfrac{12n}{36 + (n-1)\times 6}=\dfrac{12}{6} =2$.

Correct Answer: $B$

edited
CShub ans makes more sense than best answer.
edited
@HitechGa absolutely correct reasoning. But then in synchronous pipeline, we also assume that CPI =1 , i.e. 1 CPI. So, 1 clock cycle time in pipeline = max. of all stage delays. Correct me if I am wrong
edited

@Arjun Sir the best answer provided is wrong.

 S1 S2 S3 S4 S5 S6 I1 3 5 10 14 20 22 I2 6 8 15 19 26 28 I3 9 11 20 24 32 34

In pipelined for 3 instructions total cycles needed are 34.

For n instructions total cycles needed are 22+[(n-1)*6].

In non pipelined for n instructions total cycles needed are 12n.

Speed up= $\lim_{n \to \infty} \frac{12n}{22+[(n-1)*6]}$ = $\frac{12}{6}$ = 2

Speed Up= Time without Pipeline / Time with Pipeline

Time without Pipeline =12 cycle

Time with Pipeline = 6 cycle    take maximun one

Speed up =12/6=2

Speed Up= Time without Pipeline / Time with Pipeline

=n*tn/[k+(n-1)]tp

where, Time without Pipeline= n*tn

Time with Pipeline= [k+(n-1)]tp

but in the question it is given that "assuming that a very large number of instructions are to be executed" ie. n>>k

therefore ,Time with Pipeline= n*tp   (as n is very large so k becomes zero)

now, speedup= n*tn/n*tp

=tn/tp

=12/6 = 2

Option B