c++ - 并行化深度优先搜索 C++

Question

我当时正在为 HiQ 编写程序，并且正在使用这个深度优先搜索循环。但是我想将它与 MPI 并行进行，但是我该怎么做才能使深度优先搜索并行进行呢？

bool FindSolution(ConfigType PuzzleConfig ) // Depth-First Search for sol to puzzle
{

if (PuzzleConfig == SolutionConfig) return true;    

bool SolutionFound = false;

Mark(PuzzleConfig);

// For all configurations adjacent to current Puzzle Configuration (uses brute-force)
for (short from=1; !SolutionFound && from<=NUMHOLES; from++)
{
    for (short to=1; !SolutionFound && to<=NUMHOLES; to++)
    {
        JumpType jump = {from,to};
        if ( ValidJump(jump, PuzzleConfig) )
        {
            ConfigType NewConfig = FindNewConfig(jump, PuzzleConfig);
            if ( !Marked(NewConfig) )
            {
                SolutionFound = FindSolution( NewConfig );  // Recursive call for Depth-First Search
                if (SolutionFound)
                    JumpStack.push(jump);
            }
        }
    }
}

return SolutionFound;
}

Answer 1

当您可以预先定义并行计算元素的具体拓扑结构时，MPI 很有用，并且可以在执行之前很大程度上跨计算元素划分工作。然后每个元素“知道”其他元素在哪里，以及它们大致在做什么，因此可以决定它应该向哪个元素发送消息以发出 MPI 发送。同样，接收元素必须“知道”它们将要接收消息，以便发出 MPI 接收。

深度优先搜索可以说是树状的，所以你知道抽象的拓扑结构......但你不知道树的实际形状，因此没有处理器事先知道它与哪些节点相关联。所以很难弄清楚哪些处理器应该发送，哪些应该接收。我不认为 MPI 是你的 friend 。

有一个工作列表风格的算法可能会更好，它包含要搜索的扩展树的节点。然后每个处理器可以转到工作列表，获取一个节点，将该节点扩展为子节点，并将子节点放回工作列表中。这将给出一个随机扩展的边界，而不是深度优先。

要深入优先，寻找工作的节点希望工作队列为它提供最深扩展节点，因此工作列表应该像优先级队列一样工作。通过这种方式，最深的节点首先由处理器扩展，具有深度优先的风格。

可能最容易实现这种效果的方法是让一个处理器扩展一个树节点，将扩展的集合推到工作列表的顶部作为集合；然后每个处理器从工作列表顶部的集合中获取工作。当处理器发现工作列表顶部的集合为空时，它可以弹出该集合并重试。

一个窃取 版本给你这种效果。第一个处理器生成一组工作；如果它在生成某个节点 P 的子节点时有很多工作，它会停止生成 P 的子节点，留下一些工作来生成 P 的其余子节点，并将注意力转移到 P 的已经生成的子节点上。这给出了深度优先的效果。其他节点有工作时执行相同；如果他们不这样做，他们就会从另一个节点窃取工作列表条目，这会导致他们开始向下搜索子树。