[EPIC]: Reproducible floating-point reductions

[jrhemstad]

Is this a duplicate?

• [X] I confirmed there appear to be no duplicate issues for this request and that I agree to the Code of Conduct

Area

CUB

Is your feature request related to a problem? Please describe.

I would like reproducible reductions for floating-point values.

Describe the solution you'd like

@maddyscientist has a proof-of-concept implementation here: https://github.com/maddyscientist/reproducible_floating_sums/tree/feature/cuda

MVP:

• Extend DeviceReduce::Sum with requirements API for opt-in reproducibility
• Works only for input iterator value_type of float/double

Future work:

• Support half/bfloat by upconverting to float/double
• Support for custom types containing floating point values by using something similar to the decomposer approach we used for radix sort to decompose a custom type into something like tuple<float, double, ...>.
• Extend BlockReduce with reproducible algorithm
• Extend to Scan
  • For scan, we'd ideally like to fit the aggregate state in 128 bits, which would be tricky because for k=2 (from @maddyscientist's algorithm) we'd need 128 bits trivially, but could potentially reserve 2 of the bits in the aggregator type to use for the decoupled lookback signaling (see https://github.com/NVIDIA/cccl/issues/220)

Describe alternatives you've considered

No response

Additional context

No response

[jrhemstad]

This algorithm is discussed in @maddyscientist's GTC talk here: https://www.nvidia.com/gtc/session-catalog/?search=S62405&tab.allsessions=1700692987788001F1cG#/session/1696035956217001KKhw