使用乒乓技术在1D数组中搜索值？

Question

假设我想使用GPU来搜索大小为2^L的未排序1D数组中的特定值，其中L是正整数。数组中的所有值都是唯一。 是否可以使用并行缩减（乒乓技术）将搜索结果缩减为单个数字？

我的直觉告诉我，这是可能的，但我不知道如何开始。谁能帮我吗？我坚持了几天！任何建议，欢迎，谢谢！

Answer 1

如果每个线程根据是否找到搜索值，将0或它们的（1D索引+ 1）写入输出缓冲区，则可以稍后运行prefix sum并查找（1D索引+ 1 ），它与O（log n）中的输出缓冲区中的搜索值相对应，而不是O（n），这将是您只需遍历整个事物的替代方法。