了解PLINQ在树搜索中的瓶颈

Question

我用PLINQ得到了一些奇怪的结果，我似乎无法解释。我一直在尝试并行化Alpha - Beta树搜索来加快搜索过程，但它实际上减慢了搜索速度。我希望随着并行度的提高，每秒的节点数会线性增加……当修剪被推迟到以后处理时，额外的节点也会受到影响。虽然节点计数符合预期，但我的时间却不符合:

non-plinq,访问节点:61418;运行时:0:00.67

平行度:1，访问节点:61418;运行时:0:01.48

平行度:2，访问节点:75504;运行时:0:10.08

平行度:4，访问节点:95664;运行时:1:51.98

平行度:8，访问节点:108148;运行时:1:48.94

---

谁能帮我找出可能的罪魁祸首?相关代码:

    public int AlphaBeta(IPosition position, AlphaBetaCutoff parent, int depthleft)
    {
        if (parent.Cutoff) 
            return parent.Beta;
        if (depthleft == 0) 
            return Quiesce(position, parent);
        var moves = position.Mover.GetMoves().ToList();
        if (!moves.Any(m => true))
            return position.Scorer.Score();
        //Young Brothers Wait Concept...
        var first = ProcessScore(moves.First(), parent, depthleft);
        if(first >= parent.Beta)
        {
            parent.Cutoff = true;
            return parent.BestScore;
        }
        //Now parallelize the rest...
        if (moves.Skip(1)
            .AsParallel()
            .WithDegreeOfParallelism(1)
            .WithMergeOptions(ParallelMergeOptions.NotBuffered)
            .Select(m => ProcessScore(m, parent, depthleft))
            .Any(score => parent.BestScore >= parent.Beta))
        {
            parent.Cutoff = true;
            return parent.BestScore;
        }
        return parent.BestScore;
    }
    private int ProcessScore(IMove move, AlphaBetaCutoff parent, int depthleft)
    {
        var child = ABFactory.Create(parent);
        if (parent.Cutoff)
        {
            return parent.BestScore;
        }
        var score = -AlphaBeta(move.MakeMove(), child, depthleft - 1);
        parent.Alpha = score;
        parent.BestScore = score;
        if (score >= parent.Beta)
        {
            parent.Cutoff = true;
        }
        return score;
    }

然后是用于跨树层共享Alpha Beta参数的数据结构…

public class AlphaBetaCutoff
{
    public AlphaBetaCutoff Parent { get; set; }
    private bool _cutoff;
    public bool Cutoff
    {
        get
        {
            return _cutoff || (Parent != null && Parent.Cutoff);
        }
        set
        {
            _cutoff = value;
        }
    }
    private readonly object _alphaLock = new object();
    private int _alpha = -10000;
    public int Alpha
    {
        get
        {
            if (Parent == null) return _alpha;
            return Math.Max(-Parent.Beta, _alpha);
        }
        set
        {
            lock (_alphaLock)
            {
                _alpha = Math.Max(_alpha, value);
            }
        }
    }
    private int _beta = 10000;
    public int Beta
    {
        get
        {
            if (Parent == null) return _beta;
            return -Parent.Alpha;
        }
        set
        {
            _beta = value;
        }
    }
    private readonly object _bestScoreLock = new object();
    private int _bestScore = -10000;
    public int BestScore
    {
        get
        {
            return _bestScore;
        }
        set
        {
            lock (_bestScoreLock)
            {
                _bestScore = Math.Max(_bestScore, value);
            }
        }
    }
}

Answer 1

当您只做很少的工作并为所有底层节点设置新线程时，您将在线程上创建巨大的开销。由于Any，您可能正在处理更多的节点，通常处理将停止，但有些节点在找到Any(第一个匹配)之前已经开始处理。当您拥有一组已知的大型底层工作负载时，并行性将更好地发挥作用。您可以尝试只在顶级节点上执行并行会发生什么。