NVIDIA / NVIDIA/cccl

Performance Improvement Possibilities for Reduce_by_key on B200s

Open
#10,680 1 comment 1 reaction 1 assignee Claimed by @nanan-nvidia View on GitHub
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

Image

The implementation: https://github.com/nanan-nvidia/cccl/tree/reduce-by-key-lookahead

The core idea of the implementation is that the `reduce_by_key` problem can be seen as two problems: (1) getting the unique runs and determine global index (and this is the part where we should use lookahead, like RLE); (2) given the global index and head_flags computed from (1), we just need to reduce the values and this sub problem is now fully parallel. Therefore, we launch 2 kernels, one for each sub problem.

For (2), we notice that the optimal strategy is different for different expected run lengths. Therefore, the implementation is density-adaptive: for each warptile runcount, we change the items_per_thread with corresponding optimizations.

Limitations: only works for 4 byte types as of now, and we need more tempstorage now that we needed to store head flags between (1) and (2).

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.