Content deleted Content added
→Overview: fix speedup defn, implication from work law, parallelism, slackness |
Brent's law |
||
Line 19:
* ''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"/>
==Execution on a limited number of processors==
Any computation that can run in parallel on {{mvar|P}} processors can be executed on {{math|p < P}} processors by letting each processor execute multiple units of work; a result called Brent's law states that<ref>{{cite encyclopedia |encyclopedia=Encyclopedia of Parallel Computing |year=2011, |pages=182–185 |title=Brent’s Theorem |first=John L. |last=Gustafson |url=http://link.springer.com/referenceworkentry/10.1007/978-0-387-09766-4_80}}</ref>
:<math>T_p \geq T_P + \frac{T_1 - T_P}{p}</math>
==References==
| |||