NVIDIA / NVIDIA/cccl

Initial investigations and experiments of CUB DeviceScan algorithm with device resident problem sizes

Open
#10,015 1 comment 0 reactions 1 assignee Claimed by @srinivasyadav18 View on GitHub
Dominant language
C++
Stars
2.5k
Forks
486
Avg merge
2d 6h
Merged PRs (30d)
295

Description

The current CUB DeviceScan mainly has two algorithms in the implementation detail, the classic decoupled lookback algorithm ; and the new warpspeed look-ahead algorithm. While, the latest look-ahead algorithm uses occupancy for the `grid size` which works well with device resided problem sizes, whereas, the old lookback algorithm uses `num_tiles` as `grid size`, and it is a dependent on the num_items/ input size, so it changes with the invocation and caluclating temp storage can be complicated. So, one of the ways to mitigate this problem is to chunk the input size (known at run-time on device) into multiple max-capped fixed size chunks (like `INT_MAX`) and do multiple kernel invocations. We can also optimize this by passing bounds to deferred problem size. Additionally, device scan also works with `run-to-run` determinism, Investigate if any extra work is needed to support it directly.

This issue can be closed with an algorithm design description which resolves major bottlenecks like `grid_size` and `temp_storage` requirements which can keep performance closer to host provided problem size, along with minial testing and performance numbers.

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.