NVIDIA / NVIDIA/cccl

Extend and improve `BlockTopK` for unordered `k`

Open
#7,799 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

This issue is a collection of potential further extensions and possible improvements to `BlockTopK`, following https://github.com/NVIDIA/cccl/issues/7092.

- [ ] Add option to extend and include tied keys across the k-th position in the results
- [ ] Evaluate unrolling loop over passes that finds the splitter prefix ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2892281811))
- [ ] Evaluate use of BlockHistogram and BlockAdjacentDifference ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2883889451))
- [ ] Clarify and evaluate use of `cuda::atomic` ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2892220329))
- [ ] Reuse data already in registers from `compute_bin_offsets` in `choose_bucket` ([comment](https://github.com/NVIDIA/cccl/pull/7384#discussion_r2883944056))
- [ ] Add option to enforce not writing more than `k` items
- [ ] Benchmark whether we need to forceinline all the member functions and drop them if they're not beneficial
- [ ] Add support for custom keys
- [ ] Extend interface to pass constraints/guarantees on `k`
- [ ] Add support for passing items via shared memory (and `cuda::std::array`/`span`)
- [ ] Add support for passing items in strided/striped arrangement, returning items in strided/striped arrangement
- [ ] Add variant that materializes reduced candidate set while determining the splitter prefix
- [ ] Add optimized path for shorter-than-4B-key-types, where we pack key and value/index into a 4B word
- [ ] Consider splitting the branch that was unified in https://github.com/NVIDIA/cccl/pull/7384/commits/f96304e79bb0d8ac23c833461245c4655c48e148 again. It gave 2% slowdown in some cases.

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.