NVIDIA / NVIDIA/cccl

[RFE] Add warp-level and block-level primitives for top-k (`WarpTopK` and `BlockTopK`)

Open
#6,389 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

### Help Us Prioritize Top-K Algorithm Variants for `WarpTopK` and `BlockTopK` (i.e., the versions of the top-k algorithm, where each warp and block, respectively, selects the top k items)

We are planning the implementations for `WarpTopK` and `BlockTopK` , and we’d like your input to help prioritize which variants we should focus on.

Please copy & paste the form below into a new comment and fill it out in order to describe **which top-k features or variants are most important to you**. Your responses will help us understand common use cases, preferred behaviors, and performance requirements, so we can prioritize the development of the most relevant versions.

🗒️ Top-K Algorithm Specification Form

````markdown

# 🧮 Top-K Algorithm Specification Form

Please fill out the form below to describe which **Top-K algorithm parameters or variants** you need.
Use the checkboxes (`[x]`) to select the features or behaviors you’d like supported (multiple selections are fine). You can also add clarifying notes inline.

**Use case:**
```
If possible, briefly describe how or where you plan to use the top-K algorithm.
```

---

## 🧩 **WarpTopK or BlockTopK:**
In case you are interested in both but have a different set of requirements, please feel free to submit the form twice, once for `WarpTopK` and once for `BlockTopK`
- [ ] `WarpTopK`
- [ ] `BlockTopK`

## ⚙️ Basic Algorithmic Properties

**Result ordering:**
- [ ] Ordered (top-k items are returned as a sorted sequence)
- [ ] Unordered (top-k items are returned in arbitrary order (i.e., a set of items))

**Stability:**
- [ ] Stable (retain the relative order from the input of selected items)
- [ ] Unstable (no order guarantee)

**Determinism:**
- [ ] Deterministic (bit-wise reproducible results)
- [ ] Non-deterministic (e.g., faster parallel variants)

---

## 🔢 Extended-K Behavior

**Extend `k` by all keys that compare equal?**
- [ ] Yes — include all elements with equal keys beyond `k`
- [ ] No — exactly `k` elements only

---

## 🧮 Algorithm Type

Choose the algorithmic approach:
- [ ] Radix-based
- [ ] Comparison-based

▶️ If Radix-based, please specify:

**Support for custom/arbitrary types?**
- [ ] Yes
- [ ] No

**Bit range to process:**
**Would you like to be able to specify the bit range that top-k will be looking at?**
- [ ] Yes
- [ ] No

---

## 💾 Data Characteristics

**Common data types** (select all that apply):
- [ ] **Built-in / fundamental types**: standard integer and floating-point types (`uint8_t`, `int32_t`, `float`, `double`, etc.)
- [ ] **Extended floating-point types**: fp16, bfloat16, ...
- [ ] **Custom data types**
- [ ] **Specific subset only**: I primarily care about a few specific types: ☐ (please list them)

---

## 📏 Typical Problem Sizes

**Common number of input elements (`N`):**
- [ ] 1 – 9
- [ ] 10 – 99
- [ ] 100 – 999
- [ ] 1 000 – 9 999
- [ ] 10 000 – 99 999
- [ ] ≥ 100 000
- [ ] Custom: ☐ (please specify exact or range values)

**Common `k` values (number of top elements):**
- [ ] 1 – 9
- [ ] 10 – 99
- [ ] 100 – 999
- [ ] 1 000 – 9 999
- [ ] 10 000 – 99 999
- [ ] ≥ 100 000
- [ ] Fraction of `N` (e.g., `k = N / 10`)
- [ ] Variable / depends on workload
- [ ] Custom: ☐ (please specify)
````

_If you're interested in other Top-K algorithm variants such as `DeviceTopK` and/or `DeviceSegmentedTopK`, please refer to the corresponding issue below:_

- [📄 `DeviceTopK`: User requests & feature prioritization](https://github.com/NVIDIA/cccl/issues/6387)
- [📄 `DeviceSegmentedTopK`: User requests & feature prioritization](https://github.com/NVIDIA/cccl/issues/6391)

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.