如何確定的fork-join任務的適當分工門檻

望Fork/Join Tutorial後，我創建了一個類來計算大的階乘：如何確定的fork-join任務的適當分工門檻

public class ForkFactorial extends RecursiveTask<BigInteger> { 

    final int end; 
    final int start; 
    private static final int THRESHOLD = 10; 

    public ForkFactorial(int n) { 
     this(1, n + 1); 
    } 

    private ForkFactorial(int start, int end) { 
     this.start = start; 
     this.end = end; 
    } 

    @Override 
    protected BigInteger compute() { 
     if (end - start < THRESHOLD) { 
      return computeDirectly(); 
     } else { 
      int mid = (start + end)/2; 
      ForkFactorial lower = new ForkFactorial(start, mid); 
      lower.fork(); 
      ForkFactorial upper = new ForkFactorial(mid, end); 
      BigInteger upperVal = upper.compute(); 
      return lower.join().multiply(upperVal); 
     } 
    } 

    private BigInteger computeDirectly() { 
     BigInteger val = BigInteger.ONE; 
     BigInteger mult = BigInteger.valueOf(start); 
     for (int iter = start; iter < end; iter++, mult = mult.add(BigInteger.ONE)) { 
      val = val.multiply(mult); 
     } 
     return val; 
    } 
}

這個問題我已經是如何確定哪些門檻我細分任務？我發現了一個page on fork/join parallelism其中規定：

一個主要的東西用叉子實現算法時要考慮/ join並行的艇員選拔，確定任務是否會執行順序計算，而不是分叉並行門檻子任務。

如果閾值過大，那麼程序可能不會創建足夠的任務來充分利用可用的處理器/內核。

如果閾值太小，則任務創建和管理的開銷可能變得很大。

一般來說，一些實驗將是必要的，以找到合適的閾值。

那麼，爲了確定閾值，我需要做哪些實驗？

來源

2013-11-24 vandale

我感興趣的是你在調查中取得的成就。請參閱http://stackoverflow.com/questions/22191369/fork-join-optimization。你能和我分享一個結果嗎？ –

PigeonHole估計：設置一個任意的閾值，計算計算時間。並基於它增加和減少閾值，以查看您的計算時間是否提高，直到您看到通過降低閾值沒有改善爲止。

來源

2013-11-24 17:19:20 user3020494

據我所知，這個實驗是一個優化，所以它只應用在需要的時候。

您可以嘗試不同的拆分策略 - 即可以拆分兩個相等的部分或估計的乘法成本（取決於整數小數長度）。

對於每種策略，您都可以測試儘可能多的閾值以獲取策略的全貌。如果你在CPU資源方面有限，你可以測試，即每5或10次。所以，根據我的經驗，這裏第一個重要的事情就是全面瞭解算法的執行情況。

來源

2013-11-24 17:51:47

請注意，算術不是BigInteger的常量時間，它與輸入的長度成正比。每個操作的實際複雜性不容易在hand，雖然該Q/A部分引用的futureboy實現確實記錄了它在不同情況下（預期）實現的內容。

無論是在決定如何將問題分割成更小的塊和確定某個塊是否值得重新劃分時，獲取工作估算函數都是正確的。

當使用實驗來確定閾值時，您需要注意不要只針對問題空間的一個角落進行基準測試。

來源

2013-11-24 17:52:29 gwaigh

選擇閾值取決於很多因素：

實際計算應採取合理的時間量。如果您正在對一個數組進行求和並且該數組很小，那麼按順序執行它可能會更好。如果陣列長度是16M，那麼將它分成更小的片段和並行處理應該是值得的。試試看看。

處理器的數量應該足夠了。 Doug Lea曾經用數字16+處理器記錄了他的框架，以使其值得。即使將數組分成兩半，並在兩個線程上運行，也會產生大約1.3％的吞吐量增益。現在你必須考慮拆分/連接的開銷。嘗試在許多配置上運行，看看你得到了什麼。

併發請求的數量應該很小。如果您有N個處理器和8個併發請求，那麼每個請求使用一個線程對於吞吐量通常更有效。這裏的邏輯很簡單。如果你有N個可用的處理器，並且你相應地分配了你的工作，但是還有其他幾百個任務在你之前，那麼分裂的目的是什麼？

這是什麼試驗手段。

不幸的是，這個框架沒有提供問責手段。沒有辦法看到每個線程上的負載。 deques中的高水位。處理的請求總數。遇到的錯誤等。

祝你好運。

來源

2013-11-24 18:54:34 edharned

如何確定的fork-join任務的適當分工門檻

回答

相關問題