병렬 재귀가 "순차적"재귀보다 느립니다. 내가 잘못 했니?

Question

내 프로그램에서 병렬 처리를 사용하면 눈에 띄는 속도 향상을 제공하는지 확인하기 위해 몇 가지 매우 기본적인 테스트를 수행하고 있습니다. 지금까지 결과에 대해 혼란 스럽습니다. 내 테스트에서, 나는 30의 분기 구조를 가진 나무 구조를 만들었습니다. 먼저 병렬 처리를 사용하지 않고 테스트를 수행 한 다음 병렬 for 루프를 사용하여 동일한 작업을 시도합니다. 여기 내 결과는 다음과 같습니다

연속 :

Depth: 2 Time: 0.0013964 (900 nodes) 
Depth: 3 Time: 0.0053703 (27,000 nodes) 
Depth: 4 Time: 0.3994147 (810,000 nodes) 
Depth: 5 Time: 14.8306510 (24,300,000 nodes) 
Depth: 6 Time: 6:54.4050838 (729,000,000 nodes) 

병렬 : 나는 6 미만 칠분을 복용 참조하지 않는

Depth: 2 Time: 0.0389201 (900 nodes) 
Depth: 3 Time: 0.1180270 (27,000 nodes) 
Depth: 4 Time: 6:06.2296531 (810,000 nodes) 

나는 더 테스트를 귀찮게하지 않았다 깊이.

필자는 듀얼 코어 프로세서를 사용하고 있으며 병렬 처리에는 일정량의 오버 헤드가 있음을 알고 있지만 그다지 중요하지는 않습니다. 각 노드에서 적절한 수의 자식 노드 (30)를 사용하여 두 상황에서 생성 된 트리 구조가 지정된 깊이로 올바르게 형성되었는지 확인했습니다. 내가 뭔가를 잘못하고 있어요 바라고

TreeStructure ts = new TreeStructure(4, true);//TreeStructure(int targetDepth, bool runParallel) 

: 당신은 사용하여 테스트 할 수 있습니다

using System; 
using System.Collections.Concurrent; 
using System.Collections.Generic; 
using System.Threading.Tasks; 

namespace ParallelRecursion 
{ 
    class TreeStructure 
    { 
     public TreeStructure(int targetLevel, bool runParallel) 
     { 
      _root = new TreeNode(targetLevel, runParallel); 
     } 

     private TreeNode _root; 
    } 

    class TreeNode 
    { 
     public TreeNode(int targetLevel, bool runParallel) 
     { 
      _runParallel = runParallel; 

      _rnd = new Random(); 
      _score = _rnd.Next(int.MinValue, int.MaxValue); 

      _level = 0; 
      _targetlevel = targetLevel; 

      if (_level < _targetlevel) 
      { 
       if (!_runParallel) 
       { 
        _children = new List<TreeNode>(); 
        GenerateChildren(); 
       } 
       else 
       { 
        _concurrentChildren = new ConcurrentBag<TreeNode>(); 
        GenerateParallelChildren(); 
       } 
      } 
     } 

     public TreeNode(TreeNode treeNode) 
     { 
      _runParallel = treeNode._runParallel; 

      _rnd = treeNode._rnd; 
      _score = _rnd.Next(int.MinValue, int.MaxValue); 
      _parent = treeNode; 

      _level = treeNode._level + 1; 
      _targetlevel = treeNode._targetlevel; 

      if (_level < _targetlevel) 
      { 
       if (!_runParallel) 
       { 
        _children = new List<TreeNode>(); 
        GenerateChildren(); 
       } 
       else 
       { 
        _concurrentChildren = new ConcurrentBag<TreeNode>(); 
        GenerateParallelChildren(); 
       }     
      } 
     } 

     private bool _runParallel; 
     private Random _rnd; 
     private int _score; 
     private int _level; 
     private int _targetlevel; 
     private TreeNode _parent; 
     private List<TreeNode> _children; 
     private ConcurrentBag<TreeNode> _concurrentChildren; 

     private void GenerateChildren() 
     { 
      for (int i = 0; i < 30; i++) 
      { 
       _children.Add(new TreeNode(this)); 
      } 
     }   

     private void GenerateParallelChildren() 
     { 
      Parallel.For(0, 30, i => { GenerateChild(); }); 
     } 

     private void GenerateChild() 
     { 
      _concurrentChildren.Add(new TreeNode(this)); 
     } 
    } 
} 

:

여기 내 코드입니다. 이런 종류의 구조가 병렬성에 대해 비판적인 것이 아니라는 것입니까?

Answer 1

하나의 경우에는 ConcurrentBag<T>, 다른 하나의 경우에는 List<T>을 사용하면 사과 대 사과를 비교하지 않습니다. 비 동시성 어린이의 경우 List<T>을 ConcurrentBag<T>으로 바꾸면 두 버전을 모두 실행하는 속도가 거의 같아집니다.

Answer 2

병렬 처리가 잘못되었습니다. 단일 노드를 만들기 위해 새 작업을 시작합니다. 그 이유는 병렬 버전이 더 느리기 때문입니다. TPL은 각 반복마다 실제로 작업을 생성하지 않지만 작업을 생성하는 작업은 시간이 많이 걸립니다 (스레드가 아닌).

당신이해야 할 일은 분열하고 정복하고, 일을 나누고, 일을 만들어 하나의 TreeNode가 아니라 많은 TreeNode를 만드는 것입니다.