Analysis of parallel algorithms: Difference between revisions

Revision as of 20:54, 25 January 2015

Revision as of 20:55, 25 January 2015

Line 23:

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 \geqleq T_P + \frac{T_1 - T_P}{p}</math>

==References==