Work efficiency compares an algorithm’s total operations across threads with the work required by an efficient computation of the same problem. In parallel scan, reducing sequential depth is useful only if total work does not grow too much. section 6.19
Scan algorithms show the tradeoff:
- Hillis–Steele reaches O(log n) depth but uses O(n log n) work, so its extra work grows with the array size. section 6.19
- The two-phase Blelloch algorithm reduces scan’s total work to O(n). section 6.19
