liveBook · Manning

Work

As explained in Grokking GPU Programming

Work is the total amount of computation performed by an algorithm, commonly measured by its operation count.

Imagine computing a running total for an array. A sequential scan adds each new element to the previous total. A parallel scan can perform several additions at once, but it may perform more additions overall. Work is the total computation performed: for a parallel algorithm, count the operations across all threads, not just those on one thread. section 6.14 section 6.19

Work differs from depth, which counts sequential rounds. Parallelism can reduce depth while increasing work. Whether that trade pays off depends on having enough threads to run each round in parallel; extra additions also consume time, energy, and GPU resources. section 6.14 section 7.0

Counting additions in a scan

For eight elements, a sequential inclusive scan needs seven additions. Hillis–Steele uses three rounds, with strides 1, 2, and 4. The rounds perform 7, 6, and 4 additions respectively, for 17 additions in total. Copies are not included in this addition count. section 6.14 section 6.19

The difference grows with the array. For 1,024 elements, the sequential scan uses 1,023 additions; Hillis–Steele uses 9,217, roughly nine times as many. Hillis–Steele has O(log n) depth but O(n log n) work, so it is not work-efficient compared with the O(n) sequential scan. section 6.14 section 6.19

A work-efficient alternative is the Blelloch scan. It builds partial sums in an up-sweep, then distributes prefix sums in a down-sweep. Its total work is O(n), while its number of rounds remains logarithmic. In the eight-element up-sweep, only 4 positions add in the first round, 2 in the next, and 1 in the last. section 7.0 section 7.1

Figure 7.1 The Blelloch scan in two phases. The up-sweep builds an implicit reduction tree across 3 rounds; the seed step replaces the root with 0; the down-sweep distributes prefix sums back down across 3 rounds. Dotted boxes are unchanged, dashed boxes are computed by add, and solid boxes are computed by swap-and-add.

Follow the two phases to see how the reduction tree limits work while producing an exclusive scan. section 7.1

How Grokking GPU Programming covers it

How deep it goes
Counts additions per round and compares asymptotic work and depth across scan algorithms.
Examples
Compares addition counts for 1,024 elements and traces active positions in an eight-element up-sweep.
What you can do after
Evaluate scan algorithms by comparing their operation counts and sequential rounds.
How it connects
Connects total work with depth, parallel scan, work efficiency, and reduction.

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.