From the experiment, it was verified that 70%of execution time was spent on parallel execution. What is the maximum speed up that can be obtained by 16 processors?

Mumbai University > Computer Engineering > Sem 8 > parallel and distributed systems

Amdal's Law: A program requiring time 'T' has sequential execution shall have some part Sequential Frequency Computing (SFC) which is in healthy sequential. In terms of total time taken for solving problem, this fraction called SFC.

• Let f = Sequential frequency of the program
• 1-f = Parallel computing fraction of the program
• n = No. of process in parallel computing then speedup 'S' of parallel computing is given as-

$$ S \le \frac{1}{f + (1-f)/n} $$ Proof: Assume that the time is T then,

• Sequential component of time will be f*T
• Parallel component of time will be (1-f)*T

The Time (1-f)T can be reduced by exploring 'n' processes to generate in parallel to give a time (1-f)T/n

$\therefore$ Total time taken by parallel computing is T+(1-f)T/n, while sequential processes taken time T. Then speedup is $$ S \le \frac{T}{f.T + (1-f).T/n} = \frac{1}{f+ (1-f)/n} $$ For a given example,

n = 16 (No. of processes)

(1-f) i.e parallel computing fraction is 70% i.e. 0.7 $\therefore$ f is 0.3 i.e. sequential computing fraction

$\therefore$ Speed up should be-

$$\begin{aligned} S \le \frac{1}{f+ (1-f)/n} &\le \frac{1}{0.3 + 0.7/16} \\ &\le \frac{1}{0.34375} \\ SC &= 2.9090 \end{aligned}$$