Why is work-efficiency desired in GPU programming?

Question

I've been reading the following article on how to do a parallel scan in CUDA:

https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html

In the article, there is an emphasis on making the scan "work efficient". In other words, a GPU algorithm should perform no more additions than a CPU algorithm, O(n). The authors present two algorithms, one "naive" that does O(nlogn) additions, and one that they consider "work efficient". However, the work efficient algorithm does twice as many loop iterations.

From my understanding, GPUs are simply giant SIMD processors and should operate in lock-step. Doing twice as many loops in the "work efficient" algorithm seems to imply that many threads will be idle and decrease performance in the long run. What am I missing?

Answer 1

First of all, re: "GPUs are simply giant SIMD processors and should operate in lock-step", it's a bit more complicated than that. The entire GPU does not run in lockstep. Shader threads are organized into groups of 32 called "warps" (on NVIDIA; on AMD they're groups of 64 called "wavefronts", but same concept). Within a warp, all the threads do run in lockstep as a SIMD array. However, different warps are not in lockstep with each other. In addition, some warps may be actively running while others may be suspended, much like CPU threads. Warps can be suspended either because they're waiting for something (such as memory transactions to return or barriers to clear), or because there isn't a slot available for them (since the GPU can only actively run a certain number of warps at a time).

Now, back to your question. I can see two ways that the "work-efficient" algorithm from that paper looks like it would be more efficient than the "naive" algorithm.

1. The work-efficient version requires half as many threads to begin with. In the naive algorithm, they have one thread per array element; but in the work-efficient version, each thread operates on two adjacent elements of the array and so they need only half as many threads as array elements. Fewer threads means fewer warps, and so a larger fraction of the warps can be actively running.

2. Although the work-efficient version requires more steps, this is offset by the fact that the number of active threads decreases faster, and the total number of active threads over all the iterations is considerably smaller. If a warp has no active threads during an iteration, that warp will just skip to the following barrier and get suspended, allowing other warps to run. So, having fewer active warps can often pay off in execution time. (Implicit in this is that GPU code needs to be designed in such a way that active threads are packed together into as few warps as possible—you don't want them to be sparsely scattered, as even one active thread will force the whole warp to stay active.)

   Consider the number of active threads in the naive algorithm. Looking at Figure 2 in the article, you can see that all the threads are active except for the first 2^k on the k​th iteration. So with N threads, the number of active threads goes like N ​− 2^k. For example, with N = 1024, the number of active threads per iteration is:

   1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512
   

   If I convert this to number of active warps (by dividing by 32 and rounding up), I get:

   32, 32, 32, 32, 32, 31, 30, 28, 24, 16
   

   for a sum of 289. On the other hand, the work-efficient algorithm starts with half as many threads, then it halves the number of active ones on each iteration until it gets down to 1, then starts doubling until it gets back up to half the array size again:

    512, 256, 128, 64, 32, 16, 8, 4, 2, 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
   

   Converting this to active warps:

   16, 8, 4, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 8, 16
   

   The sum is 71, which is only a quarter as many. So you can see that over the course of the entire operation, the number of active warps is much smaller with the work-efficient algorithm. (In fact, for a lengthy run in the middle there are only a handful of active warps, which means most of the chip is not occupied. If there are additional compute tasks running, e.g. from other CUDA streams, they could expand to fill that unoccupied space.)

All that being said, it's unfortunate that the GPU Gems article does not clearly explain any of this, instead focusing on big-O "number of additions" analysis that, while not entirely irrelevant, misses a lot of the details about why this algorithm is faster.