Remove extra fence in radix sort
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 486
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 295
Description
The following [fence](https://github.com/NVIDIA/cub/blob/416a5c1f6b4d87d59a6763f8a2fe071326e1ff98/cub/agent/agent_radix_sort_onesweep.cuh#L264) should not be needed in the onesweep implementation of radix sort. The loads in the loop are volatile and are not allowed to be hoisted anyways. If we remove the fence and also reorder the following [code](https://github.com/NVIDIA/cub/blob/416a5c1f6b4d87d59a6763f8a2fe071326e1ff98/cub/agent/agent_radix_sort_onesweep.cuh#L617-L622) to be:
```cpp
LoadBinsToOffsetsGlobal(exclusive_digit_prefix);
LookbackGlobal(bins);
UpdateBinsGlobal(bins, exclusive_digit_prefix);
ScatterKeysShared(keys, ranks);
```
we can get the following speedups:
| GPU | I32 | I64 | I128 | FP32/OffsetT=U32 | FP32/OffsetT=U64 | FP64 |
|----------|-------------|-------------|--------------|---------------------------|---------------------------|--------------|
| H100 | -7% | -13% | -10% | +11% | -7% | -8% |
| A100 | -3% | -2% | -1% | +3% | +1.5% | -1.5% |
There's an average slowdown of 5% (max 11%) for FP32 on H100 and no speedup for GeForce:
```
| T{ct} | OffsetT{ct} | Elements{io} | Entropy | Ref Time | Ref Noise | Cmp Time | Cmp Noise | Diff | %Diff | Status |
|---------|---------------|----------------|-----------|------------|-------------|------------|-------------|---------------|---------|----------|
| F32 | I32 | 2^28 | 1 | 33.174 ms | 0.12% | 34.771 ms | 0.07% | 1.598 ms | 4.82% | FAIL |
| F32 | I32 | 2^28 | 0.811 | 33.848 ms | 0.10% | 35.664 ms | 0.09% | 1.816 ms | 5.36% | FAIL |
| F32 | I32 | 2^28 | 0.544 | 33.323 ms | 0.10% | 35.152 ms | 0.06% | 1.829 ms | 5.49% | FAIL |
| F32 | I32 | 2^28 | 0.337 | 32.570 ms | 0.10% | 34.353 ms | 0.06% | 1.783 ms | 5.47% | FAIL |
| F32 | I32 | 2^28 | 0.201 | 31.945 ms | 0.09% | 33.787 ms | 0.05% | 1.842 ms | 5.77% | FAIL |
| F32 | I32 | 2^28 | 0 | 17.811 ms | 0.12% | 19.879 ms | 0.13% | 2.068 ms | 11.61% | FAIL |
| F32 | I64 | 2^28 | 1 | 34.557 ms | 0.11% | 33.298 ms | 0.16% | -1259.697 us | -3.65% | FAIL |
| F32 | I64 | 2^28 | 0.811 | 35.028 ms | 0.08% | 34.004 ms | 0.15% | -1023.638 us | -2.92% | FAIL |
| F32 | I64 | 2^28 | 0.544 | 34.494 ms | 0.08% | 33.528 ms | 0.14% | -965.479 us | -2.80% | FAIL |
| F32 | I64 | 2^28 | 0.337 | 33.729 ms | 0.07% | 32.823 ms | 0.08% | -905.527 us | -2.68% | FAIL |
| F32 | I64 | 2^28 | 0.201 | 33.143 ms | 0.07% | 32.298 ms | 0.11% | -844.920 us | -2.55% | FAIL |
| F32 | I64 | 2^28 | 0 | 18.741 ms | 0.32% | 17.445 ms | 0.08% | -1295.732 us | -6.91% | FAIL |
```
The fence must be acting as a small delay, reducing contention on L2, so more careful examination is needed before removing it.
In case there's no way to preserve H100 speedups, we should at least update the comment.
Contributor guide
Assessment
This issue has not been assessed yet.