OpenMP:深度优先搜索的良好策略

Question

我正在编写一个C++程序,对闭合的Knight巡演进行蛮力搜索.代码在这里.

我想使用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

这if (depth==4)是我尝试确保没有创建太多并行任务,但另一方面创建了足以保持所有处理器繁忙的任务.设置depth==2不会更改程序的运行时.

这似乎没有成功.对于3x12问题,在我的双核处理器上,OpenMP版本消耗的总CPU时间约为130秒,而没有OpenMP的单线程版本需要大约40秒的CPU时间.

我将很感激有关如何更好地使用OpenMP的建议或者不适合此问题的原因.

更新:感谢@Zulan我有一个使用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没有完全锁定,但它似乎也没有很好地并行化.

不需要进一步调查就可以发现这是由复制每次迭代的向量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记录的应用程序执行情况,如Vampir所示.

红色是实际工作,蓝色是隐含的障碍,意味着线程是空闲的.似乎总是有3个或1个活动线程.原因很简单:板上的大多数位置都有4个或2个邻居,但其中一个已经被访问过,所以这个循环迭代立即完成.所以实际的工作是在循环的3或1次迭代中.对于2个线程来说这是一个特别糟糕的匹配.使用3个线程,运行时间降至1.7秒

注意:E5-2690 @ 2.90 GHz上没有turbo的gcc 5.3的所有时间.没有注意补偿运行时的变化.

考虑到单个循环暴露了该问题的非常糟糕的并行性,您可能想要嵌套并行循环.我鼓励你尝试一下,但我认为这样做不会很好.我认为任务在这种情况下运作良好,因为任务可以产生其他任务.因此,您可以将每个递归步骤生成为任务,并让OMP运行时找出一个良好的调度.但请确保将其限制在一定程度depth,以便任务不会太短.

我想强调使用工具的重要性:在没有性能分析工具的情况下试图找出性能问题就像在没有调试器的情况下搞清楚bug一样.perfLinux随时可用,它的基本形式非常简单易用.然而它非常强大(尽管高级用法可能会有一些陷阱).

另外一点:使用OpenMP,尝试使用不同的编译器通常是值得的.例如,使用(固定)任务代码,gcc不再扩展到超过4个线程,而intel编译器/ omp运行时提供甚至多达24个线程的加速.