多線程遞歸任務

我有一個小程序，我試圖提高性能。該程序非常簡單，主要基於一個遞歸函數。然而，它背後的數據集非常大 - 需要大約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); 
    } 
}

正如你可以看到函數的每次運行並不需要很長時間來運行，所以創建的成本每個遞歸的線程都不值得。遞歸的每一個分支都可以有不同的長度，不知道每個分支將會有多長時間，所以在特定級別的線程化並不是正確的方法。

有沒有人有任何建議？

來源

2013-01-04 Jason Robbins

使用'Parallel.For *' – SLaks

如果不知道應用程序，很難評論。

遞歸函數多次調用相同的級別值。你可以收穫以前的運行結果的相同的價值水平？ ......我想不是，你可能對副作用感興趣，而不是跑步的結果。

您是否嘗試過使用.NET 4.5（VS 2012）TAP？使用async/await，Tasks，你可以嘗試Task.ContinueWith來將遞歸調用與相同的（級別爲％CORE_COUNT）進行鏈接。這可以幫助平衡所有任務以及所有內核的負載。 MSDN : Chain multiple tasks.

我希望你回覆一下什麼策略適合你。

來源

2013-01-04 18:44:08 shr

爲什麼需要.Net 4.5使用'ContinueWith（）'？那該如何幫助呢？ – svick

在樹的上層使用並行性。每次調用都需要幾分鐘到幾小時，因此線程的開銷很小。使用Parallel.For*方法並行執行循環。

在遞歸樹的低層使用正常的順序循環。

選擇截止水平的方式導致幾千個並行循環迭代。

來源

2013-01-04 19:54:04 usr

您可以使用下面的代碼始終鏈接您的任務，並讓任務計劃程序安排您的工作。

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倍（=我機器上的處理器數量）。

請讓我知道你在想什麼。

乾杯。

來源

2013-01-05 12:17:37

多線程遞歸任務

回答

相關問題