5,350
edits
Parallel Algorithms: Difference between revisions
→Work Depth
(→PRAM) |
|||
| Line 29: | Line 29: | ||
===Work Depth=== | ===Work Depth=== | ||
You provide a sequence of instructions. At each time step, you specify the number of parallel operations. | You provide a sequence of instructions. At each time step, you specify the number of parallel operations. | ||
====WD-presentation Sufficiency Theorem==== | |||
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 | |||