并行广度优先搜索

Question

我正在比较两种广度优先搜索算法在时间执行上的差异。并行和非并行。但对于我制作的每个图，非并行版本都比并行版本快10倍。

这是并行广度优先搜索。我不知道问题出在哪里，但我想在这个方法中的某个地方：

public static int PBFS(Node start, Node end)
{
    var queue = new ConcurrentQueue<Node>();
    queue.Enqueue(start);

    while (queue.Count != 0)
    {
        bool isFinished = false;
        if (isFinished) break;

        Parallel.ForEach<Node>(queue, CurrentNode =>
        {
            if (queue.TryDequeue(out CurrentNode))
            {
                foreach (Node Child in CurrentNode.Children.Keys)
                {
                    if (Child.IsVisited == false)
                    {
                        Child.IsVisited = true; 
                        if (Child == end) { isFinished = true; return; }
                    }
                    queue.Enqueue(Child);
                }
            }  
            return;
        });
    } return 1;
}

这是非并行BFS：

public static int BFS(Node start, Node end)
{
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(start);

    while (queue.Count != 0)
    {
        Node CurrentNode = queue.Dequeue();
        CurrentNode.IsVisited = true;

        foreach (Node Child in CurrentNode.Children.Keys)
        {
            if (Child.IsVisited == false)
            {
                Child.IsVisited = true;
                //Console.Write(Child.Name+" ");
                if (Child == end) return 1;
            }
            queue.Enqueue(Child);
        }
        // Console.WriteLine();
    }

    // Console.WriteLine();
    return 0;
}

Answer 1

共享数据的并行化和并发性需要同步。同步是很昂贵的--正如您可能看到的那样。ConcurrentQueue有它自己的同步，这可能不是最适合你的情况。

超过CPU数量的并行化(这里可能没有发生，但它是相关的)会导致大量的上下文切换--这是昂贵的，并且降低了并行运行的代码的生产力。也就是说，在一个问题上投入更多线程的前提通常会产生相反的效果。

如果性能是一个问题，我认为您可能希望考虑不同的设计，可能是Actor-based、message-passing或producer/consumer，以避免共享数据和共享数据的同步。

Answer 2

我建议你首先编写一个并行的双向BFS:你创建两个搜索线程，一个从开始节点沿着“箭头”前进，另一个从目标节点反向开始，当它们的搜索边界“相遇”时终止这两个线程。例如，在Java中，它看起来像[this]。