[FEA]: Determine the best approach of tuning the Segmented Algorithms with regard to their segment size
- Dominant language
- C++
- Stars
- 2.5k
- Forks
- 486
- Avg merge
- 2d 6h
- Merged PRs (30d)
- 295
Description
### Area
CUB
### Is your feature request related to a problem? Please describe.
The family of segmented algorithms in CCCL (e.g., segmented sort, segmented radix sort) suffers from an inherent tuning problem:
Any new tuning configuration inevitably speeds up one class of segment sizes while causing regressions in others.
This happens because the performance characteristics of small, medium, and large segments differ so much that no single tuning or heuristic applies well to all of them. Because of that:
- small segments prefer low-overhead, fine-grained kernels,
- large segments prefer aggressive caching, large CTAs, and high throughput,
- mid-range segments break when the bucket boundaries shift.
This structural imbalance makes **segmented algorithms extremely sensitive to tuning**, and changes almost always introduce regressions in a class of segment sizes. Any change to tuning(_bucket boundaries, CTA sizes, memory tiling, policies_) inevitably optimizes one segment-size regime and harms another.
Finally, **the heuristic that decides bucket boundaries is critical**. If segmented sizes are known _a priori_ tuning values can be selected accordingly and significantly improve performance, because the algorithm will not have to traverse throughout all segments to figure out which kernel to invoke for each.
---
TL;DR
The core issue with CCCL segmented algorithms is the structural tuning conflict caused by segment size variance.
- Segment size knowledge is the fundamental bottleneck for applying cohesive tunings throughout the segmented algorithm.
- Bucket heuristics amplify the tradeoff.
- User-defined tuning policies (when enabled) will be a reliable solution but will still require effort from the user.
---
TODO
Given that segmented algorithms cannot be tuned globally across the full set of their workloads, find out
- [ ] which workloads are more representative
- [ ] how can we prioritize best within the segmented algorithms workloads (is there a class of segments size that is more important than others?)
_figure incoming_
Contributor guide
Assessment
This issue has not been assessed yet.