Analysis of parallel algorithms: Difference between revisions

Revision as of 05:11, 7 February 2022

Revision as of 06:28, 21 January 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|Ω(''n'')}} for input size {{mvar|n}} (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>

<math>\frac{T_1}{T_p} \leq \frac{T_1}{T_\infty} < p</math> .<ref name="clrs" />

* The ''slackness'' is {{math|''T''₁ / (''pT''_∞)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar|p}} processors.<ref name="clrs" />