An alternative strategy is to allocate a histogram per block and have the block’s threads use shared memory atomics—native hardware operations on Maxwell and later GPUs—to increment the histogram elements.
Even in hardware, atomics that target the same location must serialize, so this approach still exhibits the same type of data-dependent behavior as global memory atomics; the effect is somewhat muted, however, because the contention is spread across the many blocks resident on each SM (each block needs only 1024 bytes of shared memory).
Table 16-4 summarizes how this algorithm degrades due to contention, as the number of possible inputs goes from 256 (a fully random sampling) to 1 (all zeros). The histogram-per-block implementation turns out to suffer from contention even more than the histogram-per-grid implementation of Listings 16-2 and 16-3, which fire atomics directly into the output histogram.
| Values | Tesla | Fermi | Kepler | Ampere |
|---|---|---|---|---|
| 256 | 7165 | 15570 | 13070 | 108100 |
| 128 | 5894 | 12957 | 11345 | 108000 |
| 64 | 4790 | 9457 | 9906 | 107900 |
| 32 | 4185 | 6613 | 6642 | 107900 |
| 16 | 3939 | 4067 | 4104 | 107900 |
| 8 | 2406 | 2471 | 2386 | 107900 |
| 4 | 1392 | 1409 | 1274 | 107900 |
| 2 | 870 | 777 | 654 | 108100 |
| 1 | 579 | 419 | 331 | 107900 |
Table 16-4. Per-Block Performance v. # of Values (Mpix/s; Ampere column is a GeForce RTX 3060)
The Ampere column tells a very different story: the per-block kernel holds essentially flat at about 108,000 Mpix/s no matter how many distinct values the input contains. The native shared-memory atomic units introduced with Maxwell (Section 16.2) absorb the contention that made the older parts degrade by more than an order of magnitude, so the data-dependent cliff that motivates the per-thread work in the next section has largely disappeared on modern hardware.
One optimization that benefited SM 1.x-class hardware but does not help on more recent hardware (because global memory atomics are so slow on SM 1.x) is to perform a reduction on the per-block histograms after writing them to global memory. The benefits of this optimization are summarized below in the Performance section.