c - 使用带有 MPI 的 master-worker 时，哪个大小的 block 将产生最佳性能？

Question

我正在使用 MPI 来解析一个试图解决 Metric TSP 问题的程序。我有P个处理器，N个城市要通过。

每个线程都向 master 请求工作，接收一个 block ——这是一个他应该检查并计算其中最小值的排列范围。我通过提前修剪不良路线来优化这一点。

共有 (N-1) 个!计算路径。每个 worker 都会得到一个带有数字的 block ，该数字代表他必须检查的第一条路线，也是最后一条路线。此外，大师向他发送已知的最近最好的结果，因此可以提前很容易出现坏路线，并对其遗骸进行一些下限。

每次工作人员找到比全局更好的结果时，他都会将其异步发送给所有其他工作人员和主服务器。

我不是在寻找更好的解决方案——我只是想确定哪个 block 大小是最好的。

到目前为止，我发现的最佳 block 大小是 (n!)/(n/2)! ，但它并没有产生那么好的结果。

请帮助我了解哪个 block 大小是最好的。我试图在计算量和通信量之间取得平衡
谢谢

Answer 1

这在很大程度上取决于您无法控制的因素:MPI 实现、机器上的总负载等。但是，我敢猜测它也很大程度上取决于有多少工作进程。关于这一点，请了解 MPI 产生进程，而不是线程。

最终，与大多数优化问题的情况一样，答案只是“测试很多不同的设置，看看哪一个最好”。您可能希望手动执行此操作，或者编写一个实现某种启发式(例如遗传算法)的测试应用程序。