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

}

我目前正在阅读“演算法入门”中的“多线程演算法”。我试着实现一个基本的多线程程序来计算n个斐波那契数.对于n=30，程序提供了以下输出：

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

为什么并行版本比非并行版本慢.是线程切换还是“太多线程”减慢了它的速度？

要加快并行版本的速度，必须遵循什么方法？

Answer 1

是线程切换还是“太多线程”减慢了它的速度？

当然可以。在很多方面-

正如在评论中已经指出的

1. 您正在每个调用创建一个新线程，即 PFibo t = new PFibo(x - 1); t.start();

有效地为PFibo(30)创建了大约28个线程，这意味着一个上下文切换用于计算每个术语

1. 其次，由于PFibo(x)的计算依赖于PFibo(x-1)，这要求您在那里调用join()方法，因此每次创建/启动一个新线程时，它最终都变成了串行线程。

因此，最终成本=实际串行方法的成本RFibo(n) +围绕n个上下文开关+同步时间(由join()占用的时间)

要加快并行版本的速度，必须遵循什么方法？

我想说的是，别这么做。Fibonacci级数的求解模式不适合并行优化。只需依赖串行版本(为了更高的效率，您可以实现迭代版本)。

Answer 2

您的输入太小，无法从并行性中获得任何好处。然而，将这个版本的Fibonacci算法并行化是有意义的。你的算法是指数级的。通过创建新线程，可以在线程之间拆分指数工作。但是，请注意，确实有一个计算斐波那契数的线性时间算法，正如这里的人已经说过的，最好是按顺序运行。因此，在您的实现中使用更大的输入，我在Intel 2.3GHz上得到：

$ java Fib 30
Parallel-Fib:832040     Time:0.026805616
Sequential-Fib:832040   Time:0.002786453

$ java Fib 33
Parallel-Fib:3524578    Time:0.012451416
Sequential-Fib:3524578  Time:0.012420652

$ java Fib 36
Parallel-Fib:14930352   Time:0.035997556
Sequential-Fib:14930352 Time:0.056066557

$ java Fib 44
Parallel-Fib:701408733   Time:2.037292083
Sequential-Fib:701408733 Time:3.050315551