5,337
edits
Parallel Algorithms: Difference between revisions
→Speedup
| Line 38: | Line 38: | ||
* A work-optimal parallel algorithm is ''work-time-optimal'' if T(n) cannot be improved by another work-optimal algorithm. | * A work-optimal parallel algorithm is ''work-time-optimal'' if T(n) cannot be improved by another work-optimal algorithm. | ||
* If T(n) is best known and W(n) matches it, this is called ''linear-speedup'' | * If T(n) is best known and W(n) matches it, this is called ''linear-speedup'' | ||
====NC Theory==== | |||
Nick's Class Theory | |||
* Good serial algorithms: Poly time | |||
* Good parallel algorithm: poly-log <math>O(\log ^c n)</math> time, poly processors | |||