Parallel Algorithms: Difference between revisions
No edit summary |
|||
| Line 155: | Line 155: | ||
==Technique: Informal Work-Depth (IWD) and Accelerating Cascades== | ==Technique: Informal Work-Depth (IWD) and Accelerating Cascades== | ||
===Technique: Accelerating Cascades=== | ===Technique: Accelerating Cascades=== | ||
Consider: for problem of size n, there are two parallel algorithms.<br> | |||
* Algo A: <math>W_1(n)</math> work, <math>T_1(n)</math> time | |||
* Algo B: Work <math>W_2(n) > W_1(n)</math>. Time <math>T_2(n) < T_1(n)</math>. Faster but less efficient. | |||
Assume Algo A is a "reducing algorithm"<br> | |||
Then we start with Algo A until the size is below some threshold. Then switch to Algo B. | |||
==Resources== | ==Resources== | ||