[FEA]: Implement CUDA backend for parallel `cuda::std::lower_bound`

[miscco]

Is this a duplicate?

• I confirmed there appear to be no duplicate issues for this request and that I agree to the Code of Conduct

Area

libcu++

Is your feature request related to a problem? Please describe.

We want to implement a CUDA backend for the following algorithms:

• std::lower_bound see https://en.cppreference.com/w/cpp/algorithm/lower_bound.html
• std::upper_bound see https://en.cppreference.com/w/cpp/algorithm/upper_bound.html
• std::equal_range see https://en.cppreference.com/w/cpp/algorithm/equal_range.html

Describe the solution you'd like

Should reuse the CUB device_for_each backend

Note that none of those are not standard parallel algorithms but we provide them as an extension

Describe alternatives you've considered

No response

Additional context

No response

[bernhardmgruber]

Should reuse the CUB device_for_each backend

🍿

[jrhemstad]

Unless I'm missing something, the PSTL doesn't have parallel versions of lower/upper_bound,equal_range, do they?

Furthermore, the standard spellings of lower/upper_bound aren't useful in a parallel context because rarely is it appropriate to use the GPU for searching a haystack for a single needle.

The version of lower/upper_bound that is useful in parallel is searching for many needles within the same haystack. This bulk/vectorized version is the version that Thrust/CUB provide today that is tremendously useful.

TL;DR: I am unconvinced about the usefulness of a parallel cuda::std::lower_bound that only searches for a single needle. But would support a cuda::lower_bound that searches for many needles.

[miscco]

I believe lower_bound is an inherently serial algorithm, as in a parallel setting you cannot really benefit from the binary search pattern.

The algorithm you are talking about is actually find_first_of

[jrhemstad]

I believe lower_bound is an inherently serial algorithm, as in a parallel setting you cannot really benefit from the binary search pattern.

A common misconception (and used to be one of my interview questions ;) )

A binary search normally has log2(N) complexity, but with T threads can converge in logT(N) complexity.

Granted, thats theoretical complexity and there'd never be a benefit for using a GPU for searching for a single value. Which is why the version that searches for multiple values is more valuable.

All that to say, whats the goal of this issue if we're not adding a parallel single value lower_bound and friends?

[miscco]

The new lower_boud algorithm has been one of the main asks from the awkward side.

So the question is whether we want this as a non-standard algorithm. My suggestion would be yes but not under the same name, but rather something like cuda::lower_bound_batched or similar

lower_bound is a pretty well defined name in the standard and I would love to have less ambiguity there

[bernhardmgruber]

rather something like cuda::lower_bound_batched or similar

I fully agree that we should highlight the batched nature of the algorithm.