Content deleted Content added
m →Overview: gr |
|||
Line 21:
==Execution on a limited number of processors==
Analysis of parallel algorithms is usually carried out under the assumption that an unbounded number of processors is available. This is unrealistic, but not a problem, since any computation that can run in parallel on {{mvar|N}} processors can be executed on {{math|''p'' < ''N''}} processors by letting each processor execute multiple units of work. A result called ''Brent's law'' states that one can perform such a "simulation" in time {{mvar|T<sub>p</sub>}}, bounded by<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 \leq T_N + \frac{T_1 - T_N}{p},</math>
| |||