MultiThreaded Fibonacci

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) { 
    } 
} 

}

Je lis actuellement 'multithread algorithmes' de 'Introduction aux algorithmes'. J'ai essayé d'implémenter un programme multithread de base pour calculer le n-ème nombre de fibonacci. Pour n = 30, le programme a donné le résultat suivant:

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

Pourquoi la version parallèle, plus lent que la version non-parallèle. Est-ce que le thread-switching ou 'too-many-number-of-threads' l'a ralenti?

Quelle approche faut-il suivre pour accélérer la version parallèle?

Answer 1

Est-ce que le thread-switching ou «trop-nombre-nombre-de-threads» l'a ralenti?

Oui bien sûr. Dans un certain nombre de
façons-Comme cela a déjà été souligné dans les commentaires

1. Vous créez un nouveau thread par appel soit
   PFibo t = new PFibo(x - 1); t.start();

En effet, vous avez créé environ 28 fils pour PFibo(30) qui signifie un commutateur de contexte pour l'évaluation de chaque terme

2. Deuxièmement, comme l'évaluation de PFibo (x) dépend de PFibo (x - 1) qui vous obligeait à appeler la méthode join(), chaque fois que vous créez/démarrez un nouveau thread, il devient éventuellement un serial.
   

Ainsi, le coût final = coût de la méthode série réelle RFibo(n) + autour de n commutateurs de contexte + temps de synchronisation (temps pris par join())

Quelle approche doit suivre pour accélérer la version parallèle?

Eh bien, je dirais, ne le faites pas. Le modèle de solution de la série Fibonacci ne convient pas pour être optimisé par le parallélisme. Comptez simplement sur la version sérielle (vous pouvez implémenter une version itérative pour plus d'efficacité).