如何使用 OpenMP 从 0-1 数组中提取所有非零元素的索引？

Question

我是 OpenMP 初学者。我就遇到这样的问题。

我有一个M长度为 的掩码数组N，其元素为either 0 or 1。我希望提取所有i满足的索引M[i]=1并将它们存储到一个新数组中T。

OpenMP 可以加速这个问题吗？

我尝试过以下代码。但它的性能并不有效。

int count = 0;
#pragma omp parallel for
for(int i = 0; i < N; ++i) {
    if(M[i] == hashtag) {
        int pos = 0;
        #pragma omp critical (c1)
        pos = count++;
        T[pos] = i;
}

Answer 1

我不能 100% 确定这会好得多，但您可以尝试以下操作：

int count = 0;
#pragma omp parallel for
for(int i = 0; i < N; ++i) {
    if(M[i]) {
        #pragma omp atomic
        T[count++] = i;
    }
}

如果数组非常稀疏，线程将能够快速遍历许多零，而无需等待其他零。但一次只能更新一个索引。问题实际上是不同的线程正在写入相同的内存块（T），这意味着您将遇到缓存问题：每次一个线程写入时T，所有其他核心的缓存都是“脏的” - 所以当它们尝试修改它，大量的洗牌在幕后进行。所有这些对您来说都是透明的（您不需要编写代码来处理它），但它会显着减慢速度 - 我怀疑这是您真正的瓶颈。如果您的矩阵足够大，值得您花时间，您可以尝试执行以下操作：

1. 创建与线程一样多的数组 T
2. 让每个线程更新自己的T版本
3. 循环完成后将所有 T 数组合并为一个

它可能会更快（因为不同的线程不会写入相同的内存） - 但由于循环内的语句很少，我怀疑它不会。

编辑我创建了一个完整的测试程序，发现了两件事。首先，该atomic指令并非在 的所有版本中都有效omp，您可能必须使用T[count++] += i;它才能编译（这是可以的，因为 T 最初可以设置为全零）；更麻烦的是，如果这样做，您将不会两次获得相同的答案（count从一次传递到下一次传递的最终值会发生变化）；如果您使用critical，则不会发生这种情况。

第二个观察结果是，当增加线程数量时，程序的速度确实会变慢，这证实了我对共享内存的怀疑（处理 10M 元素的时间：

threads  elapsed
  1        0.09s
  2        0.73s
  3        1.21s
  4        1.62s
  5        2.34s

你可以通过改变稀疏矩阵的方式看到这是真的M- 当我创建M一个随机数组并测试M[i] < 0.01 * RAND_MAX（0.1% 密集矩阵）时，事情运行得比我将其设置为 10% 密集时要快得多 - 显示内部的部分这critical部分确实减慢了我们的速度。

既然如此，我认为没有办法在 OMP 中加速这项任务 - 最后将所有线程的输出合并到一个列表中的工作只会耗尽您可能的任何速度优势考虑到内循环内部发生的事情很少，已经发生过。因此，我建议您尽可能高效地重写循环，而不是使用多个线程 - 例如：

for( i = 0; i < N; i++) {
  T[count] = i;
  count += M[i];
}

在我的快速基准测试中，这比 OMP 解决方案更快 - 与threads = 1解决方案相当。再次强调 - 这是因为这里访问内存的方式。请注意，我避免使用if语句 - 这使代码尽可能快。M[i]相反，我利用了总是零或一的事实。在循环结束时，您必须丢弃该元素，T[count]因为它将无效......“好元素”是T[0] ... T[count-1]。M在我的机器上，这个循环处理一个包含 10M 元素的数组大约需要 0.02 秒。对于大多数用途来说应该足够了？