Использование техники пинг-понга для поиска значения в массиве 1D?

Question

Предположим, я хочу использовать графический процессор для поиска определенного значения в несортированном 1D массиве размером 2^L, где L - положительное четное целое число. Все значения в массиве уникальные. Можно ли использовать параллельное сокращение (метод пинг-понга), чтобы уменьшить результат поиска до одного номера?

Моя интуиция говорит мне, что это возможно, но я понятия не имею, как начать. Может кто-нибудь мне помочь? Я застрял на нем целыми днями! Любое предложение приветствуется, спасибо!

Answer 1

Если каждый из ваших потоков записывает 0 или их (1D индекс + 1) в выходной буфер в зависимости от того, нашли ли они искомое значение, вы можете запустить prefix sum позже и найти (1D index + 1), который соответствует искомому значению в выходном буфере в O (log n) вместо O (n), что было бы альтернативой, когда вы просто перебираете всю вещь.