트리 검색에서 PLINQ 병목 현상을 이해합니다.

Question

설명 할 수없는 PLINQ로 인해 이상한 결과가 나타납니다. 나는 알파 베타 트리 검색을 병렬 처리하여 검색 프로세스의 속도를 높이려고 노력했지만 효과적으로 감속하고있다. 병렬 처리 정도를 높이면 초당 노드를 선형 적으로 늘릴 수있을 것이라고 기대할 수 있습니다. 그리고 프 루닝이 처리 될 때까지 처리 된 추가 노드를 사용하여 적중률을 높일 수 있습니다. 노드 수가 예상과 일치하는 동안, 내 시간은하지 않습니다 :

비 PLINQ는, 노드가 방문

: 61418이, 런타임 : 0 : 병렬 00.67

정도 : 1, 노드가 방문 : 61418, 런타임 : 0 : 병렬 01.48

도 : 2, 노드 방문 : 75,504이 런타임 : 0 : 병렬 10.08

도 : 4, 노드가 방문 : 95,664, 01 23,516,런타임 : 1 : 병렬 51.98

도 : 8, 노드 방문 : 108,148, 런타임 : 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 노드 (첫 번째 일치 항목)가 발견되기 전에 일부 노드가 처리를 시작했습니다. 대용량 기본 작업 부하 집합이있는 경우 병렬 처리가 더 잘 작동합니다. 최상위 레벨 노드에서만 병렬 처리를 수행하면 어떤 일이 일어나는지 시험해 볼 수 있습니다.