c++ - MPI_Allgather 是我的代码瓶颈吗？如何修复它？

Question

我有一个程序，其目的是将特定数据添加到一个主数组中。随机数测试 passesTest(randomNumber) 每秒执行数百万次，并且极少数情况下测试会通过并且随机数被推送到数组的末尾。因此，大多数时候，当计算正在进行时，数组只是坐在那里。

我决定使用 MPI 并行化此过程，因为我认为执行随机数测试的 1000 个处理器将大大加快速度，并且由于内存写入非常罕见，因此 MPI 应该非常适合这项工作。令我沮丧的是，我的程序使用 mpirun -np 1 速度最快，但随着我添加的每个进程，速度明显变慢。

在包含 passesTest(randomNumber) 的 while 循环末尾，我有 MPI::COMM_WORLD.Allgather() 来收集每个进程的一个标志，指示是否有需要推送到数组的新随机数。如果任何标志为 true，那么我会执行另一个 Allgather() 来实际收集此数据并将其推送到每个进程的数组的本地拷贝。同样，第二个 Allgather() 很少执行，因为测试很少通过。

所以我猜测我的瓶颈是从每个 MPI 进程收集所有标志以查看是否有新数据。每个随机数的测试执行速度很快，因此我假设每秒数十亿个 while 循环现在已显着减少，因为从多个进程收集数据的开销。这是一个好的猜测吗？我是 MPI 新手，所以我不知道 Allgather() 涉及什么样的时间尺度。

如果是这个原因，那么当测试通过时我怎样才能只与其他进程“交互”呢？这确实是我想做的。换句话说，如果随机数通过测试，则向所有其他进程发送一条消息以停止它们正在执行的操作并将该数字添加到它们的数组中。

Answer 1

首先，我强烈支持 Voo 和 Hristo Iliev 的评论。

从 MPI_Allreduce 开始检查传递显然更快 - 它需要传输的数据少得多。然而 Allreduce 仍然需要 > 2 * log2(n) * 延迟。对于 1000 个进程，可能需要大约 100 微秒，具体取决于您的系统。如果您每秒进行数百万次测试，这意味着每个测试只需要 100 纳秒，那么很明显，每次测试后的集体操作确实会降低您的性能 - 无论每个单独的通信步骤设计得多么优化。

现在，如果不了解依赖性，就很难提出根本性的改进建议。您可以考虑假设没有命中，推测性地执行多次迭代，并在发现命中后丢弃无效的迭代。

此外，我建议使用 MPI_Allreduce 和 MAX 来确定需要添加的最高随机数。重复此操作，直到添加完所有内容。显然，只有在通常添加很少的情况下，这才有效。