다중 스레드 재귀 작업

Question

성능을 향상시키려는 작은 프로그램이 있습니다. 이 프로그램은 매우 단순하며 대부분 단일 재귀 함수를 기반으로합니다. 그러나 그 뒤에있는 데이터 세트는 상당히 크기 때문에 6,000,000,000 회 정도의 재귀가 필요하며 컴퓨터에 따라 4 ~ 6 시간 정도 소요됩니다. 데이터를 처리하는 I/O가 없기 때문에 코드를 최적화하는 데 꽤 많은 시간을 투자하여 개선의 60 %를 발견 할 수있었습니다.

지금보고 싶은 것은 코드를 멀티 스레딩하여 호스트 컴퓨터의 모든 코어를 활용하는 것입니다. 그러나 스레드, 작업 및 Parellel 라이브러리의 비트를 사용하여 시도하고 부정적인 방식으로 성능에 충돌하지 않는 아무것도 찾을 수 없었습니다.

내가 찾고 있어요 당신 코드의 종류의 아이디어를 제공하려면, 당신은 함수의 각 실행 실행하는 데 오래 걸리지 않습니다 볼 수 있듯이

class Program 
{ 
    static void Main(string[] args) 
    { 
     RecursiveFunction(0); 
     Console.ReadLine(); 
    } 
    static void RecursiveFunction(int currentLevel) 
    { 
     DoWork(currentLevel); 

     if (currentLevel < 1000) 
      for (int i = 0; i < (currentLevel % 6) + 1; i++) 
       RecursiveFunction(currentLevel + 1); 
    } 
    static void DoWork(int currentLevel) 
    { 
     Thread.Sleep(42); 
    } 
} 

, 그래서를 만드는 비용 각 재귀에 대한 스레드는 그만한 가치가 없습니다. 재귀의 각 분기는 길이가 다를 수 있으므로 각 분기의 길이를 알 수 없으므로 특정 레벨의 스레드가 올바른 방법이 아닙니다.

누구에게 의견이 있습니까?

Answer 1

응용 프로그램을 몰라도 의견을 말하기 어렵습니다.

재귀 함수는 동일한 level 값에 대해 여러 번 호출됩니다. 같은 수준의 레벨에서 이전 실행 결과를 얻을 수 있습니까? ... 아마도, 당신은 아마 실행 결과보다는 부작용에 관심이 있습니다.

.NET 4.5 (VS 2012) TAP을 사용해 보셨나요? async/await, Tasks를 사용하면 Task.ContinueWith를 사용하여 같은 (레벨 % CORE_COUNT) 수준의 재귀 호출을 연결할 수 있습니다. 이것은 모든 작업과 결과적으로 모든 코어의 부하를 분산시키는 데 도움이 될 수 있습니다. MSDN : Chain multiple tasks.

나는 당신에게 어떤 전략이 효과가 있었는지 다시 게시하기를 바랍니다.

Answer 2

트리의 상위 레벨에서 병렬 처리를 사용하십시오. 각 호출에는 몇 분에서 수 시간이 걸리기 때문에 스레딩으로 인한 오버 헤드가 거의 없습니다.

루프를 병렬로 실행하려면 Parallel.For* 메서드를 사용하십시오.

재귀 트리의 하위 계층에는 일반적인 순차 루프를 사용하십시오.

수천 개의 병렬 루프 반복을 발생시키는 방식으로 컷오프 수준을 선택하십시오.

Answer 3

아래 코드를 사용하여 작업을 항상 연결하고 작업 스케줄러에서 작업 일정을 잡을 수 있습니다.

class Program 
    { 
     private static int MaxLevel = 1000; 
     static void Main(string[] args) 
     { 
      Stopwatch stopwatch = new Stopwatch(); 
      stopwatch.Start(); 

      Task mainTask = ParallelRecursiveFunction(0); 
      mainTask.Wait(); 
      stopwatch.Stop(); 
      Console.WriteLine("Total time of parallel execution : {0}", stopwatch.ElapsedMilliseconds); 


      Console.WriteLine("Press Enter to execute the operation sequentially"); 
      Console.WriteLine(); 
      Console.ReadLine(); 
      stopwatch.Reset(); 
      stopwatch.Start(); 

      SequentialRecursiveFunction(0); 

      stopwatch.Stop(); 

      Console.WriteLine("Total time of sequential execution: {0}",stopwatch.ElapsedMilliseconds); 
      Console.ReadLine(); 
     } 

     private static void SequentialRecursiveFunction(int currentLevel) 
     { 
      if (currentLevel >= MaxLevel) 
       return; 
      DoWork(currentLevel); 

      SequentialRecursiveFunction(currentLevel +1); 
     } 

     public static Task ParallelRecursiveFunction(int currentLevel) 
     { 
      if (currentLevel >= MaxLevel) 
       return _completedTask; 
      Task t1 = Task.Factory.StartNew(() => DoWork(currentLevel)); 

      Task<Task> t2 = Task.Factory.StartNew(() => ParallelRecursiveFunction(currentLevel + 1)); 

      return Task.Factory.ContinueWhenAll(new Task[] { t1, t2.Unwrap() }, Task.WaitAll); 

     } 
     private static Task _completedTask = ((Func<Task>)(() => 
     { 
      var tcs = new TaskCompletionSource<object>(); 
      tcs.SetResult(null); 
      return tcs.Task; 
     }))(); 

     static void DoWork(int currentLevel) 
     { 
      Console.WriteLine("Do work at level {0}", currentLevel); 

      Thread.Sleep(42); 

     } 
    } 

필자는 순차 알고리즘보다 약 4 배 빠른 (= 내 컴퓨터의 프로세서 수) 실행중인 병렬 코드를 테스트했습니다.

귀하의 의견을 알려주십시오.

건배.