Analysis of parallel algorithms: Difference between revisions

Revision as of 06:28, 21 January 2023

Revision as of 03:57, 19 August 2023

Line 66:

Using these definitions and laws, the following measures of performance can be given:

* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math|1=''S_p'' = ''T''₁ / ''T_p''}}. When the speedup is {{math|Ω(''np'')}} for input size {{mvar|np}} processors (using [[big O notation]]), the speedup is linear, which is optimal in simple models of computation because the work law implies that {{math|''T''₁ / ''T_p'' ≤ ''p''}} ([[Speedup#Super-linear speedup|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math|1=''T''₁ / ''T_p'' = ''p''}} is called perfect linear speedup.<ref name="clrs"/> An algorithm that exhibits linear speedup is said to be [[scalability|scalable]].<ref name="casanova"/>

* ''Efficiency'' is the speedup per processor, {{math|''S_p'' / ''p''}}.<ref name="casanova"/>

* ''Parallelism'' is the ratio {{math|''T''₁ / ''T''_∞}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math|''p'' > ''T''₁ / ''T''_∞}}, then:<ref name="clrs" /> <math display="block">\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p.</math>