我正在编写一个 C++ 程序，该程序对封闭的骑士之旅。代码是here.
我想使用 OpenMP 并行化它。我的问题是以一种创建足够程度的并行性的方式来做到这一点。现在相关部分我的代码看起来像这样
#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
The if (depth==4)我试图确保不会创建太多并行任务，但另一方面会创建足够多的并行任务以使所有处理器保持忙碌。环境depth==2不会改变程序的运行时间。
这似乎行不通。对于 3x12 问题，在我的双核处理器上，OpenMP 版本消耗的总 CPU 时间约为 130 秒，而没有 OpenMP 的单线程版本则需要大约 40 秒的 CPU 时间。
我希望得到有关如何更好地使用 OpenMP 的建议或它不适合解决此问题的原因。
更新：感谢@Zulan，我有一个新版本使用具有更快顺序性能和良好并行化的 OpenMP 任务。
首先，让我们快速了解一下您的应用程序在哪里花费了时间，方法是使用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未完全锁定，它似乎也不能很好地并行化。
不需要做太多进一步的调查就能发现这是由复制引起的visited and 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，如图所示Vampir.
红色是实际工作，蓝色是隐式屏障，意味着线程处于空闲状态。似乎总是有 3 或 1 个活动线程。原因很简单：棋盘上的大多数位置都有 4 或 2 个邻居，但其中一个已经被访问过，因此该循环迭代会立即完成。因此，实际工作是在循环的 3 次或 1 次迭代中进行。对于 2 个线程来说，这是一个特别糟糕的匹配。使用 3 个线程，运行时间降至 1.7 秒
注意：所有时间均在 E5-2690 @ 2.90 GHz 上使用 gcc 5.3，无 Turbo。没有注意补偿运行时间的差异。
考虑到单个循环会导致该问题的并行性非常差，您可能会想要嵌套并行循环。我鼓励你尝试一下，但我认为效果不会很好。我认为任务在这种情况下工作得很好，因为任务可以产生其他任务。因此，您可以将每个递归步骤作为任务生成，并让 OMP 运行时找出良好的调度。但请确保将其限制在一定范围内depth，这样任务就不会太短。
我想强调使用工具的重要性：在没有性能分析工具的情况下尝试找出性能问题就像在没有调试器的情况下找出错误一样。perf它很容易用于 Linux，并且其基本形式非常易于使用。然而它非常强大（尽管高级用法可能有一些陷阱）。
附加说明：对于 OpenMP，尝试不同的编译器通常是值得的。例如，对于（固定）任务代码，gcc 的扩展不再超过 4 个线程，而 intel 编译器/omp 运行时甚至可以提供高达 24 个线程的加速。