понимание PLINQ узкое место в поиске дерева

Question

У меня есть некоторые странные результаты с PLINQ, которые я не могу объяснить. Я пытаюсь распараллелить поиск альфа-бета-дерева, чтобы ускорить процесс поиска, но он эффективно замедляет его. Я ожидал бы, когда я повышу степень параллелизма, я бы линейно увеличивал количество узлов в секунду ... и получал удар с дополнительными узлами, обработанными, поскольку обрезка отбрасывается до конца. В то время как счетчик узел соответствует ожиданиям, мое время не:

без 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; 
    } 

И тогда структура данных для совместного использования параметров альфа- и бета на разных уровнях дерева ...

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 (первое совпадение) было найдено. Параллелизм будет лучше работать, если у вас есть известный набор больших базовых нагрузок. Вы можете попробовать, что произойдет, если вы только выполняете параллелизм на своих верхних уровнях (узлах).