Java Fork - Join Framework und effizienter Code

In diesem Blog geht es um das in Java 7 enthaltene Fork/Join Framework, auch bekannt als JSR-166 Concurrency Utilities, das zum Ziel hat, effizienten Code zu schreiben.
Es gibt diverse Fachliteratur sowie einige Blogs zu dieser Thematik; ich werde am Beispiel der Fibonacci-Berechnung auf die Vor- und Nachteile von Fork/Join Frameworks eingehen.

In Zeiten steigender Taktraten genossen Entwickler die Tatsache, dass ihre Single-threaded-Software durch Hardwareoptimierungen immer schneller ausgeführt wurde. In den letzten Jahren hat aber ein Paradigmenwechsel auf dem Gebiet der Computer-Prozessoren stattgefunden. Dies betrifft neben PCs, Notebooks und Servern auch Mobiltelefone.
Der Grund dafür ist einfach: Es ist billiger, zusätzliche Kerne hinzuzufügen, als einen einzelnen schnelleren Prozessor zu bauen. Daher müssen wir Entwickler daran arbeiten, dass unser Code die Parallelität unterstützt und wir davon profitieren. Das Ziel muss also sein, sich auf die neuen Hardwaretechnologien einzustellen und die Multi-Core-Chip-Designs durch Multi-threaded-oder Multi-Process-Codierung voll auszuschöpfen. Daraus ergibt sich die Notwendigkeit von Leverage Parallelität, d.h. die Verwendung mehrerer CPU-Kerne für die Abwicklung aller Aufgaben anstatt eines einzigen schnellen Cores.

Das Mooressche Gesetz gilt noch immer, aber in einem anderen Kontext.
Parallel Computing oder Parallelisierung ist eine Form der Berechnung, bei der viele Berechnungen gleichzeitig durchgeführt werden. So wird eine große Aufgabe in mehrere Teilaufgaben unterteilt, die dann gleichzeitig (parallel) gelöst werden können. Diese Teilaufgaben werden zur Optimierung verschiedenen Prozessoren zugeordnet:

if (my portion of the work is small enough)
do the work directly
else
split my work into two pieces
invoke the two pieces and wait for the results

Aus meiner Sicht hat die Fork/Join-Bibliothek ein sehr hohes Potenzial für die praktische Anwendung im Software-Engineering. Fork-Join library bietet ein einfaches Programmier-Modell für Algorithmen, die mit „divide and conquer“-Algorithmen implementiert werden können.
Diese Art von Algorithmen ist perfekt für Probleme, die in zwei oder mehr Teilprobleme der gleichen Art aufgeteilt werden können. Sie zerteilen das Problem in kleinere, einfache Aufgaben bis diese klein genug sind, um direkt gelöst werden zu können. Die Lösungen der Teilprobleme werden dann kombiniert, um eine Lösung des ursprünglichen Problems zu erhalten.
 

Beginnen wir mit einem Code-Beispiel

class Fibonacci extends RecursiveTask<Integer> {

final int n;
    Fibonacci(int n) { this.n = n; }

    Integer compute() {
        if (n <= 1)
            return n;
        // Die erste Phase - der rekursive Abstieg für fib(n-1)
        FibonacciTask fib1 = new FibonacciTask(n - 1);
        // Einen neuen Worker-Thread mit fork() abspalten:
        fibTask1.fork();
        // Rekursiver Abstieg für fib(n-2) und Zusammenführung
der Teilergebnisse mit join ()
        FibonacciTask fib2 = new FibonacciTask(n - 2);
        // Die Berechnungen wieder zusammenführen: join()
        // Abstrakte Methode compute() mit dem Rückgabetypv, in der
        // in eigenen Realisierungen die eigentlichen Berechnungen stattfinden
        return fib2.compute() + fib1.join();
    }

    // Ausführung der Tasks
    public static void main(String[] args)
    {
        // Einen Pool an Worker-Threads in Form der Klasse ForkJoinPool anlegen
        final ForkJoinPool forkJoinPool = new ForkJoinPool(8);
        // Berechnung von fib(60) mit invoke() starten
        System.out.println(forkJoinPool.invoke(new FibonacciTask(60)));
        }
}


Wir haben hier ein Programm, das Fibonacci-Zahlen (ein klassisches pädagogisches Problem) berechnet, und sehen, welche Mechanismen die neue Klasse verwendet, um die Berechnung so schnell wie möglich durchzuführen.

Unsere Klasse Fibonacci (Quelle: http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/RecursiveTask.html) ) erweitert die generische abstrakte Klasse RecursiveTask<V> (class Fibonacci extends RecursiveTask<Integer>), welche die Klasse ForkJoinTask<V> erweitert, die das Interface Future <V> implementiert. Dort finden und überschreiben wir die abstrakte compute()-Methode mit dem Rückgabetyp T, in der die wichtigsten Berechnungen stattfinden sollen. Für alle Werte n <= 1 wird die compute()-Methode den Wert n zurückliefern.


        if (n <= 1)
            return n;
        FibonacciTask fib1 = new FibonacciTask(n – 1);
        fibTask1.fork();
        FibonacciTask fib2 = new FibonacciTask(n - 2);
                 return fib2.compute() + fib1.join();
 

Ansonsten erzeugt die Methode zwei kleinere Tasks und führt jeden einzeln und unabhängig vom anderen aus.
Ein ForkJoinTask<V> kann über den Aufruf der Methode fork() einen neuen Worker-Thread abspalten und mit join() die Berechnungen wieder zusammenführen. Die Ausführung erfolgt in verschiedenen Threads (auf die Technik des Workstealing, die für eine möglichst gleichmäßige Verteilung der Tasks auf die verfügbaren Pool-Threads sorgt, werde ich in diesem Blog nicht näher eingehen), und ihre Ergebnisse werden dann kombiniert.

Zudem überprüfen wir die verfügbare Anzahl von Prozessoren im System und erstellen dann einen neuen ForkJoinPool (new ForkJoinPool(8)) mit dem korrespondierenden Level an Parallelität. Der Default-Konstruktor erzeugt einen Pool, der genau so viel Parallelismus vorsieht wie Prozessoren vorhanden sind. Wir beginnen die Ausführung der Aufgabe mithilfe der invoke()-Methode.

final ForkJoinPool forkJoinPool = new ForkJoinPool(8);
forkJoinPool.invoke(new FibonacciTask(60));
 

Können wir den Code mit dem Einsatz von ForkJoinTasks wirklich beschleunigen?

public static long fib(long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

In der Praxis ist der Ansatz der Berechnung der Fibonacci-Zahl mit dem Einsatz von ForkJoinTasks schlecht. Das eigentliche Problem ist die Komplexität. Der hier vorgestellte Algorithmus (multi-threaded) für die Fibonacci-Zahl ist exponentiell. Das Ausführen von fib(n +1) erfordert ungefähr doppelt so viele Schritte wie das Ausführen von fib(n). Wenn man fib(n) auf einer Maschine mit einem Prozessor (single-threaded) und anschließend auf einer Multi-Prozessor-Maschine ausführt, wird man in der Lage sein, fib(n + 10) in der gleichen Zeit aufzuführen.

Bei Multi-threaded-Berechnungen werden die rechenintensiven Operationen (ab einer gewissen Granularität ist die sequenzielle Berechnungen schneller als die parallele) auf die einzelnen Prozessoren verteilt. Alle Prozessoren tragen dazu bei, die gesamte Berechnung durchzuführen, was die Gesamt-CPU-Auslastung verringert.
Dagegen ist bei Single-threaded-Berechnungen die gesamte CPU-Auslastung während der Ausführung sehr niedrig, und der Single-Thread kämpft alleine auf dem einen für den Thread verfügbaren CPU-Kern, um alle Berechnungen durchzuführen.

Beschleunigung durch Memoization

Als Fazit dieses Blogs bleibt festzustellen, dass die oben beschriebene rekursive Implementierung (mittels Fork/Join Framework) zur Fibonacci-Berechnung keine erhebliche Code-Beschleunigung darstellt.

Beide Implementierungen (single-/multi-threaded) zur Fibonacci-Berechnung sind höchst ineffizient, da die gleichen Berechnungen wiederholt durchgeführt werden. In einem realen Szenario sollten die bereits berechneten Werte zwischengespeichert und in nachfolgenden Ausführungen z.B. aus einem Cache herausgeholt werden.

Ich empfehle Ihnen eine weiterführende Betrachtung dieser Thematik (z.B. „Fork/Join With Fibonacci and Karatsuba“) unter folgender URL: http://www.javaspecialists.eu/archive/Issue201.html.

Es gibt also weitere Features, mit denen sich Entwickler vertraut machen sollten, um effizienten Code zu schreiben. Eine Möglichkeit zur Code-Beschleunigung der Fibonacci-Berechnung ist die Memoization, d.h. das Vermeiden des nochmaligen Aufrufs der Funktion für die bestimmten Argumente sowie die Pufferung (z.B. in einer HashMap) der (Zwischen-)Ergebnisse (Fibonacci-Zahlen), um die Anzahl der rekursiven Aufrufe erheblich zu reduzieren. Diese Methode ist wesentlich effizienter als Threading.

Im meinem nächsten Blog werde ich mich damit beschäftigen, wie man mit InvokeDynamic einfacher und effizienter einen dynamischen Code schreiben kann (siehe https://github.com/waldekkot/Confitura2012_InvokeDynamic/blob/master/DemoFifth/src/pl/confitura2012/speedrecurence/SpeedRecurenceWithIndyUsingBigInteger.java) und wie man damit die Verbesserung der Ausführungsgeschwindigkeit von Fibonacci-Zahlen-Berechnungen erreicht.