Content deleted Content added
m Disambiguate Processor to Central processing unit using popups |
Fixed definition of perfect linear speedup, indexes where reversed |
||
Line 15:
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|''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>
* ''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"/>
| |||