5,337
edits
Parallel Algorithms: Difference between revisions
→WD-presentation Sufficiency Theorem
No edit summary |
|||
| Line 47: | Line 47: | ||
====WD-presentation Sufficiency Theorem==== | ====WD-presentation Sufficiency Theorem==== | ||
Given an algorithm in WD mode that takes x=x(n) operations and d=d(n) time, | Given an algorithm in WD mode that takes <math>x=x(n)</math> operations and <math>d=d(n)</math> time, | ||
the algorithm can be implemented in any p-processor PRAM with O(x/p + d) time | the algorithm can be implemented in any p-processor PRAM with <math>O(x/p + d)</math> time. | ||
;Notes | |||
* Other resources call this Brent's theorem | |||
* <math>x</math> is the work and <math>d</math> is the depth | |||
===Speedup=== | ===Speedup=== | ||