如何使用CUDA从M个元素中获取N个最大元素，其中N << M？

我只是想知道是否有越来越Ñ最大元件出M个元件，其中N是小于M小得多的任何有效的方式（例如，N = 10，M = 1000）使用GPU。如何使用CUDA从M个元素中获取N个最大元素，其中N << M？

的问题是 - 由于大尺寸的输入数据，我真的不希望将数据从GPU转移到CPU，然后拿回来。然而，由于线程分歧以及我们不关心的排序元素浪费的时间（在上述情况下，DC元素为11〜1000），精确排序似乎并不成功。

我猜一些最大堆是这些问题的典型解决方案。 – halfelf

@halfelf：我不会推荐在CUDA上做最大的二进制堆，如果这就是你所指的？除非你在并行机器上有更具体的方式来做这件事？ – CygnusX1

你举一个例子N = 10，M = 1000，但你谈论的是大量的输入数据。你对N和M有什么现实价值？根据N我建议要么适应减少算法或适应排序算法。即使对于小M，如果它是更大的CUDA算法的一部分，也可以在设备上执行。 – CygnusX1

如果N是足够小的N个最大的值可以保存在共享内存，这将允许快速实现，只有通过你的全局内存M个元素的数组读取一次，然后立即写出这N个最大值。如果N也不超过每个块的最大线程数，则实现变得更简单。

相反串行编程，我不会用堆（或其它更复杂的数据结构），但只是一个排序后的数组。 SM上有很多并行硬件，当遍历一个堆时将不会使用它。整个线程块可用于移动共享内存阵列中小于新传入值的元素。

如果N < = 32，则使用warp shuffle functions可以使用整洁的解决方案来保持寄存器中N个最大数字的排序列表。

2016-08-11 10:13:37 tera

您能否详细说明采用哪种算法？根据你的描述，你提到在第一段中共享内存中保留N个最大值，并使用寄存器来保留第三段中的N个最大值。您帖子中的第二段建议不要使用堆数据结构。我的问题是你用什么算法从M个元素中获取N个最重要的元素。谢谢 – LongY

回答