我正在使用MPI解析试图解决Metric TSP问题的程序。我有P个处理器,还有N个城市要通过。
每个线程向主服务器请求工作,接收一个块-这是他应检查并计算其中最小的排列范围。我正在通过预先修剪不良路线来优化此效果。
总共有(N-1)个!计算路线。每个工人都会得到一个带有编号的数据块,该编号代表了他必须检查的第一条路线以及最后一条路线。此外,船长还向他发送了最新的已知最佳结果,因此可以提前轻松地做出一些路线,并在其残骸上设置一些下限。
每当工人发现比全局更好的结果时,他都会异步地将其发送给所有其他工人和主管。
我不是在寻找更好的解决方案-我只是在尝试确定哪个块大小最佳。
到目前为止,我发现的最佳块大小是(n!)/(n / 2)! ,但效果不佳。
请帮助我了解哪种块大小是最好的。我试图在计算量和通讯量之间取得平衡
谢谢
最佳答案
这在很大程度上取决于您无法控制的因素:MPI的实现,计算机上的总负载等。但是,我冒昧地猜测这也很大程度上取决于有多少个工人进程。关于这一点,请理解MPI生成进程,而不是线程。
最终,就像大多数优化问题一样,答案仅仅是“测试许多不同的设置,看看哪个是最好的”。您可能想要手动执行此操作,或者编写一个实现某种启发式(例如遗传算法)的测试器应用。