Mumbai University > Computer Engineering > Sem 8 > Parallel & Distributed System

Consider n inputs fed to a serial processor and to a K-stage linear pipeline. speed up is defined as

Time taken for a given computation by a

$speed \ up = \frac{non \ pipelined \ functional \ unit}{Time \ taken \ for \ the \ same \ computation \ by \ a \ pipelined \ version}$

Assuming K-stage of equal complexity which takes time T per stage, starting empty pipeline, first input takes K to calculate all K stages, In pipeline, the successive (n - 1 ) inputs complete on each successive T time period as shown:

Thus the completion time for all n inputs is $KT + (n-1) T$

i.e.$ [K + (n - 1 ) ] T$

whereas, in non pipelined serial processor each input would have taken time KT. thus total time is $n \times K \times T$

Hence the speed up is :

$ speed up = \frac{nKT}{(K+ n-1)T} = \frac{n K}{k + n - 1}$

For large number of inputs (i.e. when n > > K)

$k + n - 1 = n$

Hence speed up = $\frac{nk}{n} = k$

Hence Proved.