并行化深度优先搜索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是你的朋友。

最好有一个工作列表样式的算法，它包含要搜索的扩展树的节点。然后，每个处理器可以进入工作列表，获取一个节点，将该节点展开为子节点，并将子节点重新放入工作列表中。这将给出一个随机扩展的边界，而不是深度优先。

首先要深入，寻找工作的节点希望工作队列为其提供最深的扩展节点，因此工作列表应该起到类似优先级队列的作用。通过这种方式，最深的节点首先由处理器进行扩展，给出了深度优先的味道。

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

盗用作品的版本给了你这样的效果。第一处理器生成一组工作；如果它在生成某个节点P的子节点时有大量的工作，它就停止生成P的子节点，留下一点工作来生成P的其他子节点，并将其注意力切换到已经生成的P的一个子节点，这就产生了深度优先效应。其他节点在有工作时以相同的方式执行；当它们没有工作时，它们会从另一个节点窃取一个工作列表条目，这将导致它们开始在子树中搜索。