NVIDIA / NVIDIA/cccl

Identify `DeviceBatchedTopK` algorithm composition, fusion, compilation, and dispatching heuristic

Open
#9,807 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

The family of algorithms and implementations behind `DeviceBatchedTopK` is plentiful and complex, comprising various warp-, block-, and cluster-level implementations along with a multi-cta kernel.

A few open questions that come to mind:
- which algorithm specializations are considered for a certain problem (given static ranges of k and segment sizes)
- which algorithm specializations are fused into the same kernel (resource usage versus latency versus throughput):
- fusing another specialization into the same kernel may raise the high-watermark of resource usage and therefore degrade occupancy and throughput (potentially also latency)

The issue can be closed when we have an initial heuristic and tuning that will achieve at least as good as RAFT's current implementation across relevant workloads.

Contributor guide

Open the contributing guide

Research direction

Start by tracing the DeviceBatchedTopK algorithm family and its warp-, block-, cluster-level, and multi-CTA implementations, then compare the specializations considered for static k and segment-size ranges. Study RAFT's current implementation and relevant workloads. Done means an initial fusion, compilation, dispatch, and tuning heuristic performs at least as well as RAFT across the relevant workloads.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
performance
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.