Turbo Charge CPU Utilization in Fork/Join Using the ManagedBlocker mit Heinz Kabutz

Am 26.1. war Heinz Kabutz zu Gast bei der Java User Group Darmstadt und hat einen Vortrag mit dem Titel „Turbo Charge CPU Utilization in Fork/Join Using the ManagedBlocker.“ gehalten.

HeinzLos ging es mit einer sehr einfachen Implementierung des Fibonacci-Algorithmus.
Das Ziel war, dass alle Kerne des Prozessors gleichmäßig ausgelastet werden und nicht untätig auf etwas warten. Wenn man den Fibonacci-Algorithmus für größere Zahlen ausrechnen möchte und dafür die einfache Implementierung verwendet, dann steigt die Laufzeit verhältnismäßig schnell an, wobei die Prozessorkerne nicht vollständig ausgelastet sind.
Also muss man dafür sorgen, dass die Rechenoperationen gut auf die einzelnen Kerne verteilt werden.
Wobei die Herausforderung bei dem Fibonacci-Algorithmus die Multiplikation von BigInteger-Zahlen ist.
Als erstes hat Heinz versucht, die Algorithmus mit Standard-Mitteln zu optimieren, allerdings stößt man da sehr schnell an die Grenzen. Deshalb haben wir uns den Sourcecode von BigInteger angeschaut und die beiden Algorithmen (Karatsuba und der Toom-Cook), die zum Multiplizieren verwendet werden, herauskopiert und als innere Klassen in unserer einfachen Implementierung ergänzt.
Nun wurde im ersten Schritt an einiger Stellen das fork- und das join-Kommando ergänzt, was schon dafür gesorgt hat, dass die Auslastung des Prozessors und die Laufzeit besser wurde.
Als verschiedene kleine Optimierungen keine Verbesserungen mehr brachten, hat Heinz den ManagedBlocker ergänzt und sehr ausführlich erklärt, was dieser bewirkt. Mit der letzten Version war es möglich Fibonacci für 250 Mio. in 30-45 Sekunden zu berechnen (Wenn ich mich richtig erinnere), wobei die Prozessorkerne verhältnismäßig gleich ausgelastet waren.

HeinzHeinz hat beim Heimflug herausgefunden, dass die Parallelisierung des Karatsuba unsinnig war, aber dass die Parallelisierung von Toom Cook den Ausschlag gegeben hat. Insgesamt hat er nochmal 4 Sekunden herausgeholt. :-)

Vielen Dank an Heinz, dass er den Vortrag nach einem langen Schulungstag abends noch gehalten hat! Auch ein großen Dank an die Telekom in Darmstadt, dass wir deren Räumlichkeiten benutzen durften.
Wen der Talk interessiert, hat die Chance ihn dieses Jahr bei der JFokus zu sehen und hoffentlich im Anschluss auch als Video. :-)
Oder alternativ bei Heinz’s Happy Hour:


Anmerkung: Ich habe an zwei Tagen die Schulung „The Java Specialist Master Course“ bei Heinz besucht und kann das jedem Java-Entwickler empfehlen. Gerade, wenn man mehr als die Standard-Dinge zu Java 8 wissen möchte, lernt man da sehr viel neues, was nicht in den „Hello World“-Tutorials zu finden ist.

Kommentare sind abgeschaltet.