Фибоначчи с помощью Fork Join в Java 7

Question

Это программа для Фибоначчи, использующая Java 7 ForkJoin . Но похоже, что есть мертвый замок.

package ForkJoin;

import java.time.LocalTime;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

import static java.time.temporal.ChronoUnit.MILLIS;

class Fibonacci extends RecursiveTask<Integer>{

    int num;
    Fibonacci(int n){
        num = n;
    }

    @Override
    protected Integer compute() {
        if(num <= 1)
            return num;

        Fibonacci fib1 = new Fibonacci(num-1);
        fib1.fork();
        Fibonacci fib2 = new Fibonacci(num-2);
        fib2.fork();

        return fib1.join()+ fib2.join();
    }
}

public class ForkJoinFibonaaciEx {

    public static void main(String[] arg){
        LocalTime before = LocalTime.now();
        int processors = Runtime.getRuntime().availableProcessors();
        System.out.println("Available core: "+processors);
        ForkJoinPool pool = new ForkJoinPool(processors);
        System.out.println("Inside ForkJoin for number 50:  "+pool.invoke(new Fibonacci(50)));
        LocalTime after = LocalTime.now();
        System.out.println("Total time taken: "+MILLIS.between(before, after));
    }
}

JVisualVM ---- показывает, что есть мертвая блокировка. Не уверен, что реальная проблема.

Кроме того, я заметил коды, где разработчики сделали вызов вилки для одной части и вычислили для другой половины проблемы.

например, здесь, в этом примере, они используют fib1.fork() и fib2, которые они не разветвляют.

Вы можете увидеть полный пример https://github.com/headius/forkjoin.rb/blob/master/examples/recursive/Fibonacci.java

Ваша помощь очень ценится. Спасибо и хорошего С уважением Deenadayal Manikanta

Answer 1

Добавляя fib2.fork(); в методе вычисления вы создаете избыточную подзадачу, которая уже была рассчитана ранее (т.е. при следующем рекурсивном вызове fib1.fork ()). В конечном итоге добавление лишней подзадачи, которая займет дополнительное время. Вместо этого вы можете вызвать fib2.compute(), который в свою очередь вызовет fork в рекурсии.

Хотя это не фактический виновник трудоемкости. Настоящая проблема вызвана операцией fork.join(). Поскольку эта операция ожидает завершения всех дочерних подзадач (которые могут быть выполнены другим потоком). Поэтому, хотя на каждом ядре выполняется несколько потоков, обеспечивающих параллелизм, фактические вычисления на конечном уровне ничтожно малы по сравнению с операцией объединения.

Итог:

Мы должны использовать fork-join, если нижеследующие случаи верны:

1. Проблему можно решить, используя Divide and Conquer, создавая подзадачу и рекурсивно решая ее.

2. Проблема не может быть разделена заранее и является динамичной.

Также для эффективной работы fork-join мы должны разделить проблему только до определенного уровня, где параллельные вычисления приносят больше пользы, чем вреда.

Answer 2

Попробуй это:

      class ComputeFibonacciTask extends RecursiveTask<Long> {

    private int n;

    public ComputeFibonacciTask(int n) {
        this.n = n;
    }

    protected Long compute() {
        if (n <= 1) {
            return Long.valueOf(n);
        }

        else {
            RecursiveTask<Long> otherTask = new ComputeFibonacciTask(n - 1);
            otherTask.fork();
            return new ComputeFibonacciTask(n - 2).compute() + otherTask.join();
        }
    }
}