Analysis of parallel algorithms: Difference between revisions

Revision as of 20:58, 25 January 2015

Revision as of 21:03, 25 January 2015

Line 21:

==Execution on a limited number of processors==

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 theone performancecan ofperform such a "simulation" isin bounded bytime<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>

or, less precisely,<ref name="casanova"/>

:<math>T_p = O \left( T_N + \frac{T_1}{p} \right) .</math>

==References==