[FEA]: Implment primitives for distributed sorting
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 486
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 295
Description
### Is this a duplicate?
- [x] I confirmed there appear to be no [duplicate issues](https://github.com/NVIDIA/cccl/issues) for this request and that I agree to the [Code of Conduct](CODE_OF_CONDUCT.md)
### Area
CUB
### Is your feature request related to a problem? Please describe.
CCCL currently provides many options for single GPU sorting, but less so when implementing distributed sort on multi-gpu systems. There are common patterns here in which optimised primitives could be useful. Note that CCCL should only provide primitives for computations on a single gpu, and leave communication up to the user.
### Describe the solution you'd like
Take as an example the sample sort algorithm:
https://en.wikipedia.org/wiki/Samplesort
Samples are taken from each local partition and then shared with other workers to attempt to choose p pivot elements, equally dividing the input across p GPUs.
The local sampling process and merging of samples received from other workers could be CUB primitives (leaving the process of communicating to the user via e.g. nccl).
Allocating local elements to a partition can also be a primitive.
In such a way we can provide a fast path to distributed sorting that could be implemented on top of many distributed computing frameworks.
### Describe alternatives you've considered
_No response_
### Additional context
_No response_
Contributor guide
Assessment
This issue has not been assessed yet.