OpenMP：深度优先搜索的好策略

Question

我正在编写一个 C++ 程序，对已关闭的 Knight's tours. The code is here 进行暴力搜索。

我想使用 OpenMP 将其并行化。我的问题是以创建足够程度的并行性的方式来执行此操作。目前 the relevant portion 我的代码看起来像这样

#pragma omp parallel for reduction(+:count) if (depth==4)
  for (size_t i=0;i<g.neighbours[last].size();i++){
    auto n = g.neighbours[last][i];
    // See if n can be used to extend or complete the tour

if (depth==4) 是我尝试确保不会创建太多并行任务，但另一方面创建的并行任务足以让所有处理器保持忙碌。设置 depth==2 不会改变程序的运行时间。

这似乎行不通。对于一个 3x12 问题，在我的双核处理器上，OpenMP 版本消耗的总 CPU 时间约为 130 秒，而没有 OpenMP 的单线程版本需要大约 40 秒 CPU 时间。

对于如何更好地使用 OpenMP 或它不适合解决此问题的原因，我将不胜感激。

更新：感谢@Zulan，我有一个 newer version 使用 OpenMP 任务，具有更快的顺序性能和良好的并行化。

Answer 1

首先，让我们通过使用 perf:

快速查看您的应用程序将时间花在哪里

perf record ./knights_tour_omp 3 12
perf report

# Overhead  Command          Shared Object        Symbol                                                                                         
# ........  ...............  ...................  .................................................................................................
#
    53.29%  knights_tour_om  libc-2.19.so         [.] malloc                                                                                       
    23.16%  knights_tour_om  libc-2.19.so         [.] _int_free                                                                                    
    10.31%  knights_tour_om  libc-2.19.so         [.] _int_malloc                                                                                  
     4.78%  knights_tour_om  knights_tour_omp     [.] _Z13continue_tourIZ4mainEUlRKSt6vectorIiSaIiEEE_EmRK5GraphS4_RKS0_IcSaIcEEiiRT_.constprop.119
     2.64%  knights_tour_om  libc-2.19.so         [.] __memmove_ssse3_back                                                                         
     1.48%  knights_tour_om  libc-2.19.so         [.] malloc_consolidate

您的应用程序将所有时间都花在了分配和释放内存上。虽然有一些报告 malloc is is not fully locked，但它似乎也不能很好地并行化。

无需进一步调查即可发现这是由每次迭代复制 visited 和 path 向量引起的。幸运的是 DFS 有很好的属性，你不一定需要这样做，你可以重用状态并恢复它：

visited[n] = 1;
path.emplace_back(n);
count += continue_tour(g, path, visited, depth+1,remain-1, cb);
visited[n] = 0;
path.pop_back();

但是，对于并行循环，您需要为每个线程制作工作副本，因此您需要为这种情况使用原始行为制作单独的路径。

这个小改动已经将串行运行时间从 22 秒降低到 2.65 秒。进一步使用 2 个线程，它下降到 2.0 秒。有加速，但不是很好——为什么？为了说明这一点，我使用了 4 个线程（在一个足够大的系统上）。下面是用 score-p, shown in Vampir.

记录的应用程序随时间的执行情况

红色是实际工作，蓝色是隐式屏障，表示线程处于空闲状态。似乎总是有 3 个或 1 个活动线程。原因很简单：棋盘上的大多数位置都有 4 个或 2 个邻居，但其中一个已经被访问过，因此此循环迭代立即完成。所以实际工作在循环的 3 次或 1 次迭代中。对于 2 个线程来说，这是一个特别糟糕的匹配。使用 3 个线程，运行时间下降到 1.7 秒

注意：所有时间在 E5-2690 @ 2.90 GHz 上使用 gcc 5.3 无涡轮增压。没有注意补偿运行时的差异。

考虑到对于该问题，单个循环暴露出非常糟糕的并行性，您可能想嵌套并行循环。我鼓励您尝试一下，但我认为效果不会很好。我认为任务在这种情况下工作得很好，因为任务可以产生其他任务。因此，您可以将每个递归步骤生成为一个任务，并让 OMP 运行时计算出良好的调度。但一定要将它限制在某个 depth，这样任务就不会太短。

我想强调使用工具的重要性：在没有性能分析工具的情况下试图找出性能问题就像在没有调试器的情况下找出错误一样。 perf 可随时用于 Linux，并且其基本形式非常易于使用。然而它非常强大（尽管高级用法可能有一些缺陷）。

补充说明：对于 OpenMP，尝试不同的编译器通常是值得的。例如，对于（固定的）任务代码，gcc 不再扩展到超过 4 个线程，而英特尔编译器/omp 运行时提供了甚至高达 24 个线程的加速。

OpenMP：深度优先搜索的好策略

OpenMP: good strategies for depth-first search

c++

parallel-processing

openmp