liveBook · Manning

Work efficiency

As explained in Grokking GPU Programming

Work efficiency describes an algorithm's computational work relative to that required by an efficient computation of the same problem.

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

How Grokking GPU Programming covers it

How deep it goes
Defines total work and depth, then contrasts sequential scan’s n−1 work with Hillis–Steele’s O(n log n) work.
Examples
Uses Hillis–Steele and two-phase Blelloch scans to contrast extra work with linear work.
What you can do after
Evaluate whether a parallel scan reduces depth without excessive total work.
How it connects
Connects work efficiency to parallel scan, depth, Hillis–Steele, and Blelloch algorithms.

This explainer was generated by Manning's knowledge graph from the text of Grokking GPU Programming. The section links point to the parts of the book it draws on.