Initial investigations and experiments of CUB DeviceScan algorithm with device resident problem sizes
- 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
Assessment
This issue has not been assessed yet.