5,337
edits
Parallel Algorithms: Difference between revisions
→Models
(→Models) |
|||
| Line 33: | Line 33: | ||
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 x=x(n) operations and d=d(n) 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 O(x/p + d) time | ||
===Speedup=== | |||
* work-optimal | |||
* work-time-optimal | |||
* linear-speedup | |||