我有一个程序，目的是将特定数据添加到一个主数组中。每秒执行一次随机数测试passesTest(randomNumber)百万次，偶尔会通过测试，并将随机数推到数组的末尾。因此，在大多数情况下，数组只是在计算进行时坐在那里。
我决定将此过程与MPI并行化，因为我发现执行随机数测试的1000个处理器将大大提高速度，并且由于很少进行内存写入，因此MPI应该非常适合这项工作。令我非常沮丧的是，使用mpirun -np 1时，我的程序运行最快，而添加的每个进程的运行速度却明显变慢。
在包含while的passesTest(randomNumber)循环的最后，我需要MPI::COMM_WORLD.Allgather()从每个进程中收集一个标志，该标志指示是否存在需要推入数组的新随机数。如果任何标志是true，那么我将执行另一个Allgather()来实际收集此数据并将其推入数组的每个进程的本地副本中。同样，由于很少通过测试，因此很少执行第二个Allgather()。
所以我猜我的瓶颈是从每个MPI进程收集所有标志，以查看是否有新数据。对每个随机数的测试都可以快速执行，因此我认为每秒的数十亿次while循环现在已大大减少，因为从多个进程收集数据的开销很大。这是一个很好的猜测吗？我是MPI的新手，所以我不知道Allgather()涉及哪种时间表。
如果这是原因，那么通过测试后，我如何才能仅与其他进程“交互”？这真的是我要做的。换句话说，如果一个随机数通过了测试，则向所有其他进程发送一条消息，以停止它们正在执行的操作并将该数字添加到其数组中。
最佳答案
首先，我强烈支持Voo和Hristo Iliev的评论。
从MPI_Allreduce开始检查通过显然更快-它需要传输少得多的数据。但是，Allreduce仍需要> 2 * log2(n) * latency。对于1000个进程，取决于您的系统，可能约为100微秒。如果您每秒进行数百万次测试，这意味着每个测试仅花费100纳秒，那么很明显，每次测试之后的集体操作确实会损害您的性能-无论每个通信步骤的设计多么理想。
现在，在不了解依赖性的情况下，很难提出基本的改进建议。您可以考虑在假设没有命中的情况下以推测方式执行多个迭代，并在发现有命中之后丢弃无效的迭代。
除此之外，我建议使用MPI_Allreduce和MAX来确定需要添加的最高随机数。重复该过程，直到全部添加。显然，只有通常很少添加时，这才行得通。