NVIDIA / NVIDIA/cccl

[RFE] Add `DeviceSegmentedTopK`

Open
#6,391 9 comments 2 reactions 1 assignee Claimed by @elstehle View on GitHub
Dominant language
C++
Stars
2.5k
Forks
487
Avg merge
2d 7h
Merged PRs (30d)
296

Description

### Help Us Prioritize Top-K Algorithm Variants for `DeviceSegmentedTopK` (i.e., the segmented-problem, device-wide top-k algorithm)

We are planning the implementations for `DeviceSegmentedTopK`, 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.

🗒️ Segmented Top-K Algorithm Specification Form

````markdown

# 🧮 Segmented 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.
```

---

## ⚙️ 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)

---

## 📏 Segment-specific parameters versus global parameters

Which of the following parameters vary across segments (e.g., for the first segment, I need the top-5 for the second segment I need the top-10 items) and which of these parameters are the same for each segment (e.g., "I want the top-5 items for each segment)

Please check the parameters that vary across different segments:
- [ ] Segment size
- [ ] `k`
- [ ] Result ordering
- [ ] Stability
- [ ] Determinism
- [ ] Radix-based versus comparison-bassed
- [ ] Bit range to process

## 📏 Typical Problem Sizes

**Common number of total input elements (i.e., the sum of segment sizes over all segments) (`N`):**
- [ ] 1 – 99 999
- [ ] 100 000 – 999 999
- [ ] 1 000 000 – 9 999 999
- [ ] 10 000 000 – 99 999 999
- [ ] 100 000 000 – 999 999 999
- [ ] ≥ 1 000 000 000
- [ ] Variable / depends on workload
- [ ] Custom: ☐ (please specify exact or range values)

**Common upper bound of segment size (i.e., the larges segment size across all segments):**
- [ ] 1 – 9
- [ ] 10 – 99
- [ ] 100 – 999
- [ ] 1 000 – 9 999
- [ ] 10 000 – 99 999
- [ ] 100 000 – 999 999
- [ ] 1 000 000 – 9 999 999
- [ ] 10 000 000 – 99 999 999
- [ ] 100 000 000 – 999 999 999
- [ ] ≥ 1 000 000 000
- [ ] Variable / depends on workload
- [ ] Custom: ☐ (please specify exact or range values)

**Common upper bound of the `k` values (i.e., the larges value of `k` across all segments)::**
- [ ] 1 – 9
- [ ] 10 – 99
- [ ] 100 – 999
- [ ] 1 000 – 9 999
- [ ] 10 000 – 99 999
- [ ] 100 000 – 999 999
- [ ] 1 000 000 – 9 999 999
- [ ] 10 000 000 – 99 999 999
- [ ] 100 000 000 – 999 999 999
- [ ] ≥ 1 000 000 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`, `BlockTopK`, or `WarpTopK`, please refer to the corresponding issue below:_

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

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.