5,337
edits
Parallel Algorithms: Difference between revisions
→Speedup
(→Models) |
|||
| Line 35: | Line 35: | ||
===Speedup=== | ===Speedup=== | ||
* work-optimal | * A parallel algorithm is ''work-optimal'' if W(n) grows asymptotically the same as T(n). | ||
* work-time-optimal | * A work-optimal parallel algorithm is ''work-time-optimal'' if T(n) cannot be improved by another work-optimal algorithm. | ||
* linear-speedup | * If T(n) is best known and W(n) matches it, this is called ''linear-speedup'' | ||