1
\$\begingroup\$

If the 5th Fibonacci number has to be computed, I'm trying to split the 2 recursive trees into 2 threads:

                       5

         4                           3

   3           2                2        1

2     1     1     0         1       0  

       Thread 1                 Thread 2

My attempt:

public class ParallelFibbonaci
{

static ExecutorService executor = Executors.newFixedThreadPool(2);
// Memoized map.
private static Map<Integer, Long> mem = new ConcurrentHashMap<>();

public static void main(String[] args) throws ExecutionException, InterruptedException{
    final long then = System.nanoTime();    

    System.out.println(fib_wrapper(Integer.parseInt(args[0])));

    final long millis = TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - then);
    System.out.println("Time(ms): " + millis);
    executor.shutdown();
}

public static int fib_wrapper(int n) throws ExecutionException, InterruptedException {
    Future<Integer> future = executor.submit(() -> fib(n-1));
    Future<Integer> future2 = executor.submit(() -> fib(n-2));

    return future2.get() + future.get();
}

public static int fib(int n) throws ExecutionException, InterruptedException {  
    if (n == 1)
        return 1;
    if (n == 0)
        return 0;

    if (mem.containsKey(n)) {
        return mem.get(n);
    }

    long x = fib(n-1) + fib(n-2);
    mem.put(n, x);
    return x;
  }
}

I couldn't prove the parallel version to run faster than the simple version, in fact, all my profiling (done with System.nanoTime() which I believe is not the most reliable) revealed it to be 20-30 times slower:

Sid:Programs siddhartha$ java -Xms2G -Xmx4G parallelfibbonaci 1000
817770325994397771
Time(ms): 60

Sid:Programs siddhartha$ java -Xms2G -Xmx4G simplefibbonaci 1000
817770325994397771
Time(ms): 4

Sid:Programs siddhartha$ java -Xms2G -Xmx4G parallelfibbonaci 500
2171430676560690477
Time(ms): 59

Sid:Programs siddhartha$ java -Xms2G -Xmx4G simplefibbonaci 500
2171430676560690477
Time(ms): 2

Any higher n's crashed my program with a stackoverflow error.

In theory, I'd expect using 2 threads on a tree-recursive algorithm to work faster than a single-threaded implementation, however it seems this is clearly not the case. What am I missing here?

\$\endgroup\$
1
\$\begingroup\$

Don't parallelize serial problems

In theory, I'd expect using 2 threads on a tree-recursive algorithm to work faster than a single-threaded implementation, however it seems this is clearly not the case. What am I missing here?

You are duplicating work. The problem is that generating the Fibonacci sequence is not a tree. It's a vector. This is because you don't actually care what the children are. All you care about is what the current node's two children are. But you need one of those children to generate the other. I.e. the n - 2 subtree is actually part of the n - 1 subtree.

So you take an essentially serial operation and you try to split it over two processes. Unsurprisingly, it takes longer as it tries to synchronize the processes.

Turning it into parallel problems

Is all hope lost? No. If you look at solutions to Project Euler #2: Even Fibonacci Numbers, you will find that

$$F_n = 4 \cdot F_{n-3} + F_{n-6}$$

For example, the 7th Fibonacci number:

$$F_7 = 4 \cdot F_4 + F_1$$ $$F_7 = 4 \cdot 2 + 0 = 8$$

How does that help us? Think about the 8th, 9th, and 10th Fibonacci numbers:

$$F_8 = 4 \cdot F_5 + F_2$$ $$F_9 = 4 \cdot F_6 + F_3$$ $$F_{10} = 4 \cdot F_7 + F_4$$

Notice anything? No overlap. The 7th and 10th overlap, but 7-9 don't and 8-10 don't. This will continue. In general, now you have three serial sequences. So you can parallel process into three threads.

You may also be able to come up with similar equations for two threads or more than three threads. But I knew about this problem and there's already the mathematical derivation available inside the link.

Another issue is that you are searching from n down. You might find it easier to generate the sequences from 1, 2, and 3 up with n as an upper bound. You can do that iteratively rather than recursively, which should avoid the heavy stack usage.

This will only be faster if the system can really parallelize work. If you were limited to a single core and can now use three, you gain. If you're just switching between the three threads on the same processor, it will probably still be slower than the serial solution.

Calculate just one element

If all you want to do is generate the nth Fibonacci number, there is a formula to do that directly:

static int fib(int n) {
    double sqrt_5 = Math.sqrt(5);
    double phi = (1 + sqrt_5) / 2;

    double fib_n = Math.pow(phi, n) / sqrt_5;
    return (int) (fib_n + 0.5);
}

That would be the fastest solution for a single value without precalculating the numbers. Of course, that won't parallel well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.