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.
Los 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.
Heinz 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. :-)
@JUG_DA managed to shave another 4 seconds off the 250000000 calculation, whilst flying from Frankfurt to Thessaloniki :-)
— Heinz Kabutz (@heinzkabutz) 28. Januar 2017
@hansolo_ @JUG_DA turns out it was pointless parallelising Karatsuba. Toom Cook was sufficient. — Heinz Kabutz (@heinzkabutz) 28. Januar 2017
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:
Join us on https://t.co/4ZVm5rMsvy tomorrow 2nd Feb @ 17:00 for a look at how to add fork/join and ManagedBlocker into existing code @Java
— Heinz Kabutz (@heinzkabutz) 1. Februar 2017
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.