CODEWITHSUNDEEP
javamultithreadingalgorithm
user1218191
user1218191

Reputation:

MultiThreaded Fibonacci

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

}

I am currently reading 'Multithreaded Algorithms' from 'Introduction to Algorithms'. I tried implementing a basic multithreaded program for calculating the n-th fibonacci number. For n=30 the program gave the following output :

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

Why is the parallel version slower that the non-parallel version. Has thread-switching or 'too-many-number-of-threads' slowed it down ?

What approach has to followed to speed-up the parallel version ?

Upvotes: 0

Views: 5651

Answers (2)

Fernando Magno Quintao Pereira
Fernando Magno Quintao Pereira

Reputation: 89

your input is too small to gain any benefit from parallelism. Nevertheless, it makes sense to parallelize this version of the Fibonacci algorithm. Your algorithm is exponential. By creating new threads, you split exponential work among the threads. Notice, however, that there is, indeed, a linear-time algorithm to compute the Fibonacci numbers, which, as people here have already said, it is better to run sequentially. So, using larger inputs with your implementation, I get, on an 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

Upvotes: 0

Shubham Chaurasia
Shubham Chaurasia

Reputation: 2632

Has thread-switching or 'too-many-number-of-threads' slowed it down ?

Yes of course. In a number of ways-
As already been pointed out in comments

  1. You are creating a new thread per call i.e.
    PFibo t = new PFibo(x - 1); t.start();

Effectively you have created around 28 threads for PFibo(30) which means one context switch for evaluating each term

  1. Secondly, as the evaluation of PFibo(x) depends on PFibo(x - 1) which required you to put a call to join() method there, each time you are creating/starting a new thread i.e. eventually it has become serial.

So the final cost = cost of actual serial method RFibo(n) + around n context switches + sync time (time taken by join())

What approach has to followed to speed-up the parallel version ?

Well I would say, don't do it. Fibonacci series' solution pattern does not suit to be optimized by parallelism. Just rely on serial version(you can implement an iterative version for more efficiency).

Upvotes: 1

Related Questions