2

我正在使用带有 Java 的单线程 CPLEX（在 Linux 下）对线性程序 (LP) 进行建模和求解。我的目标是在并行线程中解决多个小型 LP，理想情况下每个内核独立解决一个 LP。

问题是并行求解两个或多个 LP 比求解单个 LP 慢得多。在一个非常简单的测试中，我同时启动了多个相同的进程来解决相同的 LP。启动单个进程和启动多个进程之间的运行时差异是巨大的：

  • 1 个过程：180 秒
  • 2 个进程：225 秒
  • 3 个过程：280 秒

同样，从同一进程启动多个线程以同时解决多个 LP 比解决单个 LP 慢得多。

我怀疑内存访问可能是瓶颈，但测试一段经常读写内存的代码会产生类似的运行时：

  • 1 个过程：87 秒
  • 2 个过程：85 秒
  • 3 道工序 88 秒

知道什么可能导致缓慢吗？

我正在运行的机器有 6 个内核和足够的内存以避免任何交换。IBM ILOG Cplex 库是 12.5 版。

4

2 回答 2

2

如果您启用了多个线程，那么 CPLEX 将使用并发优化器。这意味着它在一个线程中运行对偶单纯形，而在其余其他线程中运行屏障算法。CPLEX 报告首先完成的算法的答案。因此，如果您有 6 个内核，那么它​​可能使用 1 个线程用于双单工，5 个线程用于屏障。当您尝试同时解决 3 个 LP 时，它们会互相窃取循环。您可以通过将参数 RootAlg 设置为 2 来仅使用对偶单纯形法（始终只使用 1 个线程）。您还可以设置参数AuxRootThreads限制每个 LP 求解使用的线程数。您应该检查哪种算法（Primal、Dual 或 Barrier）更适合您的问题。如果可以利用多个线程的 Barrier 工作得最好，您最好串行运行每个模型并让 CPLEX 进行并行化。

于 2013-06-13T04:38:57.930 回答
0

首先，让我强调一下TJCrowder的评论是正确的。一般来说，真正的加速在多线程方法中不可能是线性的。事实上，请考虑：1）机器上运行的其他进程，不仅仅是你的；2）CPU架构很重要，还有其他硬件（主板、RAM等），那么这些可能会影响你算法的性能。

我建议使用 CPLEX 中包含的几个选项，例如使用parallel mode switch.

最后，另一个重要的考虑是关于你的问题：你假设你的实现是好的，但没有证据证明这一点。

于 2013-06-12T07:53:19.233 回答