Theoretical Speedup Curves

Similar to section 5.2.1, an expression for speedup can be derived for the eigenvalue and perturbation parallel algorithms. For the master-slave algorithm, serial communication takes place, because the master process can only receive one message at a time. We expect the parallelization overhead and synchronization time to be proportional to (N-1). Hence, we express $\Delta\tau$ as;  

$${\Delta\tau} = {\alpha(N-1)}\;\;\;.$$ (124)

The time for a parallel simulation on N processors can be written as;  

$${\tau_N} = a + {{bN_h}\over {N}} + {\alpha(N-1)}\;\;\;.$$ (125)

In the above equation, after evaluating constants a and b from two serial execution time, all the terms are known except $\alpha$. The parameter $\tau_N$ is the actual measured time on N processors of IBM-SP2. Hence, $\alpha$ can be determined from equation (5.22). The observed speedup is expressed as;  

$${S_N} = {{\tau_1}\over{\tau_N}} = {{\tau_1}\over{{a} + {b{{N_h}\over{N}}} + {\alpha(N-1)}}}\;\;\;.$$ (126)

The predicted speedup follows the curve given by;  

$${S_N{(predicted)}} = {{N}\over{{1} + {{\beta}N}}}\;\;\;,$$ (127)

where,  

$${\beta} = {{\alpha}\over{\tau_N}}\;\;\;.$$ (128)

Here $\beta$ represents the fraction of total computation time spent in parallelization overhead, communication, synchronization, etc. between two processors [Mat94].