使用乒乓技術在1D數組中搜索值？

Question

假設我想使用GPU來搜索大小爲2^L的未排序1D數組中的特定值，其中L是正整數。數組中的所有值都是唯一。 是否可以使用並行縮減（乒乓技術）將搜索結果縮減爲單個數字？

我的直覺告訴我，這是可能的，但我不知道如何開始。誰能幫我嗎？我堅持了幾天！任何建議，歡迎，謝謝！

Answer 1

如果每個線程根據是否找到搜索值，將0或它們的（1D索引+ 1）寫入輸出緩衝區，則可以稍後運行prefix sum並查找（1D索引+ 1 ），它與O（log n）中的輸出緩衝區中的搜索值相對應，而不是O（n），這將是您只需遍歷整個事物的替代方法。