Analysis of parallel algorithms: Difference between revisions

Revision as of 20:55, 25 January 2015

Revision as of 20:58, 25 January 2015

Line 21:

==Execution on a limited number of processors==

Any computation that can run in parallel on {{mvar|PN}} processors can be executed on {{math|''p'' < P''N''}} processors by letting each processor execute multiple units of work;. aA result called Brent's law states that the performance of such a "simulation" is 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_PT_N + \frac{T_1 - T_PT_N}{p}</math>

==References==