数组比较(逐个元素)

Question

我正在使用的一种算法花费了大量时间将一个数组与矩阵的一行进行比较。如果任何 ith<​​/em> 元素相同，则算法调用过程 A，如果没有元素相等，则调用过程 B。例如:

[1, 4, 10, 3, 5] 和 [5, 3, 0, 3, 0] 调用 A() 因为对于第 4 个位置，两个数组中的值都是 3。

[1, 4, 10, 3, 5] 和 [5, 3, 0, 1, 0] 调用 B() 因为对于相同的位置，值永远不会相同。

请注意 (1) 数组和矩阵行的大小始终为 N，并且 (2) 算法调用 A() 当至少有一个值匹配时.

在 C 中执行此操作的最简单但非常幼稚的方法是:

for(int i=0; i<N; i++)
   if( A[i] == B[i] ){
      flag = 1;
      break;
   }

这样还是很低效的。在最坏的情况下，我将进行 N 次比较。这里真正的问题是该算法进行了数万亿次此类比较。

N(矩阵中数组/行的大小)从 100 到 1000 不等。我想加快此例程的速度。我查看了矢量化，发现可以使用 cmpeq_pd。但是，矢量化仍然会受到限制，因为我所有的条目都是 longs。有没有人有想法？我可以敷面膜吗？

更多信息/上下文:

• 这是一个迭代算法。在每次迭代中，我在一行中递增矩阵并多次检查整个矩阵。我也可能会更新几行。
• 匹配的可能性不取决于位置。
• 我愿意出现误报和漏报，以大大加快此例程。
• 如果有匹配，则验证匹配的位置不相关(我只需要知道是否有匹配的位置)。
• 最大数量(约 70%)的比较没有导致匹配。
• 并行化是在不同的层次上完成的，即这个内核不能并行化。

Answer 1

我不知道这是否适用于您正在开发的应用程序，但大型数组上的操作通常在 GPU 上得到很好的加速。与 CPU 相比，您可以预期 10-20 倍的吞吐量加速。如果您的应用程序可以在 CUDA 上运行关键部分这将产生巨大的影响。