マルチスレッドフィボナッチ

Question

public class Fibonacci { 

public static class PFibo extends Thread { 
    private int x; 
    public long answer; 

    public PFibo(int x) { 
     this.x = x; 
    } 

    public void run() { 
     if (x <= 2) 
      answer = 1; 
     else { 
      try { 
       PFibo t = new PFibo(x - 1); 
       t.start(); 

       long y = RFibo(x - 2); 

       t.join(); 
       answer = t.answer + y; 

      } catch (InterruptedException ex) { 
      } 
     } 
    } 
} 

public static long RFibo(int no) { 
    if (no == 1 || no == 2) { 
     return 1; 
    } 
    return RFibo(no - 1) + RFibo(no - 2); 
} 

public static void main(String[] args) throws Exception { 
    try { 
     long start = System.currentTimeMillis(); 
     PFibo f = new PFibo(30); 
     f.start(); 
     f.join(); 
     long end = System.currentTimeMillis(); 
     System.out.println("Parallel-Fibonacci:" + f.answer + "\tTime:" + (end - start)); 

     start = System.currentTimeMillis(); 
     long result = RFibo(30); 
     end = System.currentTimeMillis(); 
     System.out.println("Normal-Fibonacci:" + result + "\tTime:" + (end - start)); 


    } catch (Exception e) { 
    } 
} 

}私は現在、「アルゴリズム入門」から「マルチスレッドアルゴリズム」を読んでいます

。私は、n番目のフィボナッチ数を計算するための基本的なマルチスレッドプログラムを実装しようとしました。 n = 30の場合、プログラムは次の出力を出しました。

Parallel-Fibonacci:832040 Time:10 
Normal-Fibonacci:832040  Time:3 

なぜパラレルバージョンが非パラレルバージョンより遅いのですか？スレッド切り替えや「スレッド数が多すぎます」が遅くなっていますか？

パラレルバージョンのスピードアップには、どのようなアプローチが必要ですか？

Answer 1

スレッド切り替えまたは「スレッド数が多すぎます」で速度が低下しましたか？

もちろんです。 PFibo(30)ためways-
すでにコメントで指摘されて

1. あなたは、コールごとに新しいスレッドを作成している
   PFibo t = new PFibo(x - 1); t.start();

すなわち事実上あなたの周りに作成した28件のスレッドの数にはどの各用語を評価する1つのコンテキストスイッチを意味する。

2. 第2に、PFibo（x）の評価は、join()メソッドを呼び出す必要があるPFibo（x - 1）に依存するため、新しいスレッドを作成/開始するたびに、最終的にはシリアルになります。
   

スピードアップに続いているかのアプローチn個のコンテキストスイッチの周りに実際のシリアル方式RFibo(n) + +同期時間（join()に要する時間）

のだから最終コスト =コストパラレル版？

まあ、私はそれをしないと言います。フィボナッチ級数の解法は並列処理では最適化されていません。シリアルバージョンに頼るだけです（効率を上げるために反復バージョンを実装できます）。