NVIDIA / NVIDIA/cccl

[FEA]: Implment primitives for distributed sorting

Open
#5,683 0 comments 1 reaction 0 assignees View on GitHub
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.