Content deleted Content added
No edit summary |
m →Overview: missing italics |
||
Line 17:
* ''[[Speedup]]'' is the gain in speed made by parallel execution compared to sequential execution: {{math|''S<sub>p</sub>'' {{=}} ''T''<sub>1</sub> ∕ ''T<sub>p</sub>''}}. When the speedup is {{math|Ω(''n'')}} for input size {{mvar|n}} (using [[big O notation]]), the speedup is linear, which is optimal in the PRAM model because the work law implies that {{math|''T''<sub>1</sub> ∕ ''T<sub>p</sub>'' ≤ ''p''}} ([[Speedup#Super-linear speedup|super-linear speedup]] can occur in practice due to [[memory hierarchy]] effects). The situation {{math|''T<sub>p</sub>'' ∕ ''T''<sub>1</sub> {{=}} ''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<sub>p</sub>'' ∕ ''p''}}.<ref name="casanova"/>
* ''Parallelism'' is the ratio {{math|''T''<sub>1</sub> ∕ ''T''<sub>∞</sub>}}. It represents the maximum possible speedup on any number of processors. By the span law, the parallelism bounds the speedup: if {{math|''p'' > ''T''<sub>1</sub> ∕ ''T<sub>∞</sub>''}}, then {{math|''T''<sub>1</sub> ∕ ''T''<sub>p</sub> ≤ ''T''<sub>1</sub> ∕ ''T<sub>∞</sub>'' < ''p''}}.<ref name="clrs"/>
* The ''slackness'' is {{math|''T''<sub>1</sub> ∕ (''pT''<sub>∞</sub>)}}. A slackness less than one implies (by the span law) that perfect linear speedup is impossible on {{mvar|p}} processors.<ref name="clrs"/>
| |||