我有一个500 x 500的2D浮点数组。我希望从阵列的中间开始在垂直和水平方向上搜索两个方向上的第一个零元素。输出应为北、南、东和西方向上第一个零元素的4个索引。有没有一种方法可以在CUDA上并行化这个搜索操作。
谢谢。
(这个答案假设你不是在搜索整个象限,而是只搜索每个方向上的直线(
1.如果阵列在CPU内存中
事实上,您的搜索空间只有1000个元素。复制数据、启动内核和等待结果的开销是如此之大,以至于不值得你为此烦恼。
在CPU上执行。您的一个轴已经连续地很好地布置了数据;可能最好先在那个轴上工作。另一个轴心在内存访问方面是个婊子,但这就是生活。你可以在这里使用多线程,但我不确定这是否值得你为这么少的工作而烦恼。如果您这样做了,那么每个线程都会在自己的元素上等待。
就算法而言,由于数据没有排序,因此基本上是线性搜索(直到矢量化(。如果你是多线程的——也许可以使用一个共享变量,线程偶尔会轮询这个变量;更靠近中心";线程已找到一个零;当一个线程发现一个零时,它会更新该变量,让其他线程知道停止工作。
2.如果阵列在GPU全局内存中
现在你得到了很多(CUDA("线程"。因此,使用原子变量或轮询等是没有意义的
我们分别处理四个方向中的每一个(尽管不必是4个单独的内核(。
正如@RobertCrovella所指出的,你可以将这个问题视为一个并行归约,每个线程都分配一个输入元素:最初,每个线程保持一个无穷大的值(如果其对应的元素为非零(,或者如果其对应数组值为0,则保持其与中心的距离。现在,归约算子是";最小值";。
这并不完全是最优的,因为当收集扭曲或块结果时(作为并行归约的一部分(,当位于最低的非无穷大值时,这个问题允许短路。你可以阅读并行归约是如何实现的,但我真的不介意,因为你在这里只需要少量的计算工作。
注意:您的阵列也可能在GPU阵列内存中。在这种情况下,你会在两个维度上获得更好的位置
如何定义"在北、南、东和西方向上的第一个零元素";但我可以想象一个矩形数据集沿着对角线分成4个象限。
我们可以将顶部区域标记为";北部地区";我们可以给其他地区贴上类似的标签。
根据这个假设,在最坏的情况下,您必须检查数组的每个元素。
因此,一种可能的方法是并行减少。
然后,考虑到区域中的零元素,您可以对每个区域进行平行归约,以使与中心的距离(使用标准距离公式(最小化。
如果你实际上只对与穿过图像中心的垂直轴和水平轴相关的元素感兴趣,那么另一种方法可能会更好。
即使在这种情况下,我认为平行归约也是一种典型的方法,每个轴两个,只考虑半轴上的零元素。