并行广度优先搜索

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 、消息传递或生产者/消费者，以避免共享数据并避免共享数据的同步。