Parallelverarbeitung mit Java-Threads
Parallelverarbeitung mit Java-Threads
In diesem Beitrag wird die Parallelverarbeitung am Beispiel von Java-Threads vorgestellt. Viele der diskutierten Herausforderungen gelten aber auch in anderen Programmiersprachen wie C++ oder C#.
Zwei Threads summieren Werte eines Arrays. (Bild: Volkswagen)
Auf einen Blick
Um Mehrkernsysteme (Multicore-Prozessoren, Grafikkarten oder HPC-Cluster) effizient auszulasten, sind Techniken der parallelen Programmierung notwendig.
Um parallele Anwendungen zu entwickeln, sind Kenntnisse über das Speichermodell entscheidend.
Nicht synchronisierte, parallele Speicherzugriffe können zu fehlerhaften Ergebnissen und Programmabbrüchen führen.
Ein Thread (oder auf das im ersten Teil des Beitrags bezogene Beispiel, dem Koch) ist ein sequenzieller Ausführungsstrang innerhalb eines Anwendungsprogramms (Prozess). Dabei kann eine Anwendung aus mehreren Threads bestehen, die parallel ausgeführt werden. Die Threads innerhalb einer Anwendung teilen sich den Speicher des Prozesses, in dem sie gestartet wurden (Shared Memory).
Um einen Thread anzulegen, stellt Java, wie viele andere Sprachen auch, die Klasse Thread zur Verfügung. Wollen Entwickler eigene Threads erstellen, erzeugen sie eine vom Thread abgeleitete Klasse, die die Run-Methode überschreibt. Diese beinhaltet den Programmcode, der durch den Thread zur Laufzeit ausgeführt werden soll. Wird ein Thread gestartet, ist zunächst eine Instanz der Klasse zu erstellen und dann die Start-Methode aufzurufen. Alternativ lassen sich Threads auch erstellen, indem die Schnittstelle Runnable implementiert wird. So muss die Klasse nicht vom Thread abgeleitet sein, was Vorteile bei komplexeren Programmstrukturen bietet, weil Java keine Mehrfachvererbung unterstützt. Um diese Vorgehensweise in Java zu veranschaulichen, wird als Beispiel die Summenberechnung über die Werte innerhalb eines Arrays verwendet (Bild 1). Dieses Beispiel lässt sich aufgrund der Datenparallelität effizient über mehrere Threads ausführen. Zwei Threads teilen sich die Berechnung der Summe auf. Während Thread 1 die erste Hälfte des Arrays berechnet, übernimmt Thread 2 dies für die zweite Hälfte. Anschließend werden Teilergebnisse addiert.
Listing 1 (Bild 2) stellt die Klasse Summation (abgeleitet von Thread) dar. Die Run-Methode implementiert die Logik zur Berechnung der Summe. Hierbei wird eine Schleife über dem Array verwendet, die variabel von einem Start-Index bis zu einem End-Index läuft. So lässt sich der gleiche Programmcode für jeden Thread verwenden. Die Klasse Summation erhält über ihren Konstruktor Start und End sowie die in der Klasse Data gekapselten Berechnungsdaten. Data besteht aus einem eindimensionalen Array von Double-Werten und einer Variablen sum zum Speichern der berechneten Summe.
Bild 2: Eine einfache Thread-Implementierung zur Aufsummierung von Werten. (Bild: Volkswagen)
Listing 2 (Bild 3) zeigt die Main-Methode des Programms, in der das Array initialisiert und die Threads zur Summenberechnung gestartet werden. Wird das Programm für ein Array mit 100 Mio. Einträgen auf einem aktuellen Mehrkernrechner ausgeführt, ergibt sich für einen Thread eine Laufzeit von circa 400 ms, bei zwei Threads halbiert sich die Laufzeit auf etwa 200 ms. Die Anwendung skaliert also optimal über zwei Threads.
Bild 3: Starten von Threads. (Bild: Volkswagen)
Vermeidung eines Data Race
Führt der Entwickler das Programm wiederholt aus, treten gelegentlich Programmabbrüche auf. Auslöser ist ein sogenannter Data Race, das heißt, eine Konstellation, bei der mehrere Threads auf dieselben Daten (in diesem Fall die Variable sum) zugreifen und versuchen, diese zu verändern. Die Variable sum ist als 64-Bit-Datentyp (double) implementiert. Das Speichermodell von Java realisiert 64-Bit-Datentypen als nicht atomar, das heißt, nicht Thread-sicher, weil eine Schreiboperation des Werts in zwei Schritten erfolgt, eine für jede 32-Bit-Hälfte. Dadurch kann ein Zustand entstehen, bei dem ein Thread einen 64-Bit-Wert liest, bei dem die erste 32-Bit-Hälfte durch einen anderen Thread bereits verändert wurde, die zweite Hälfte jedoch noch nicht (siehe hierzu auch Java Language Specification [1]). Abhilfe kann dort unter anderem die Kennzeichnung der Variable als volatile schaffen. Für die mit volatile gekennzeichneten 64-Bit-Variablen (wie double und long) wird durch die Java-Laufzeitumgebung sichergestellt, dass Schreibvorgänge stets Thread-sicher sind und andere Threads immer nur vollständig (über beide 32-Bit-Hälften) geschriebene Werte sehen. Werden volatile für das Beispiel (Listing 3, Bild 4) eingeführt, läuft die Anwendung stabil ohne Programmabbrüche durch, was jedoch mit einer deutlich längeren Laufzeit einhergeht.
Bild 4: Vermeidung von Data Race durch Kennzeichnung der Variablen als volatile. (Bild: Volkswagen)
Die Ergebnisausgabe des Programms zeigt jedoch nach jeder Programmausführung unterschiedliche Ergebnisse an. Das korrekte Ergebnis von 100 Mio. wird jedoch nicht aufgeführt. Grund ist die Berechnung der Summe: Dabei kommt es zu einer sogenannten Race Condition, das heißt, das Ergebnis ist abhängig von der zeitlichen Reihenfolge, in der die Threads die Einzeloperationen ausführen. Die Summenberechnung besteht aus drei Einzeloperationen: Einlesen der alten Summe, Addieren der Summe mit dem jeweiligen Wert aus dem Array und schließlich dem Speichern der neuen Summe. Die zeitliche Abfolge, um diese Operationen über mehrere Threads abzuarbeiten, ist zufällig und nicht deterministisch. Entsprechend kann es zu Fehlern bei der Berechnung kommen, wie Bild 5 zeigt.
Bild 5: Race Condition bei Summenberechnung. (Bild: Volkswagen)
Synchronisation des kritischen Abschnitts
Um das Race-Condition-Problem bei der Summenberechnung zu lösen, gibt es in Java die Möglichkeit, Methoden als synchronized zu kennzeichnen. Dabei wird sichergestellt, dass sie immer nur von einem Thread gleichzeitig ausgeführt werden. Alle anderen Threads müssen warten, bis ein ausführender Thread die Methode wieder verlassen hat. Für die Umsetzung wird die Summenberechnung in die synchronisierte Methode increaseSum der Klasse Data verschoben (Listing 4, Bild 6). So wird das Data-Race-Problem aus dem vorhergehenden Abschnitt gleich mitgelöst, das heißt, auf das Schlüsselwort volatile lässt sich in diesem Fall verzichten.
Bild 6: Synchronisierter Zugriff gemeinsam genutzter veränderlicher Daten. (Bild: Volkswagen)
Wird das Programm erneut ausgeführt, wird das korrekte Ergebnis reproduzierbar ausgegeben. Allerdings liegt die Laufzeit für zwei Threads bei etwa 5000 ms und damit um mehr als eine Größenordnung höher als bei der nicht synchronisierten Variante in Listing 1. Das Beispiel verdeutlicht, dass die Synchronisation große Einbußen bei der Performance mitbringt, weil die benötigte Logik bei der Summenberechnung um ein Vielfaches komplexer wird. Beim Aufruf einer synchronisierten Methode wird eine Sperre auf dem Objekt gesetzt beziehungsweise beim Verlassen der Methode zurückgesetzt. Ist die Methode bereits gesperrt, wird der aufrufende Thread blockiert. Neben der eigentlichen Berechnung der Summe wird im Beispiel somit auch dieser Synchronisationsmechanismus 100 Mio. mal aufgerufen.
Zugriff auf gemeinsam genutzte Daten reduzieren
Der zweite Lösungsansatz vereint die Vorteile aus Listing 1 (hohe parallele Effizienz) und Listing 4 (Vermeidung von Race Conditions). Dazu wird der Zugriff auf gemeinsam durch beide Threads genutzte Daten deutlich reduziert. Listing 5 (Bild 7) führt innerhalb der Summenberechnung eine lokale Variable sum ein, die nur vom jeweiligen Thread verwendet wird. Das heißt, die Threads arbeiten zur Berechnung auf eigenen Daten und erst nach Abschluss der Iteration werden die beiden Teilsummen addiert. Nur dieser letzte Schritt erfordert eine Synchronisation. Bei einer erneuten Ausführung des Programmcode für ein Array mit 100 Mio. Einträgen und zwei Threads, wird jetzt reproduzierbar das korrekte Ergebnis bei einer Laufzeit von circa 200 ms erreicht.
Bild 7: Reduktion der gemeinsam genutzten veränderlichen Datenzugriffe. (Bild: Volkswagen)
Unter diesen Voraussetzungen performt Parallel Computing
Um Mehrkernsysteme (Multicore-Prozessoren, Grafikkarten oder HPC-Cluster) effizient auszulasten, sind Techniken der parallelen Programmierung notwendig. Dadurch lässt sich die Leistung erheblich verbessern und die Laufzeit komplexer Anwendungen verkürzen. Das Beispiel auf Basis von Java-Threads zeigt die grundlegenden Herausforderungen paralleler Applikationsentwicklung und lässt sich auf andere Sprachen wie C++ sowie C# und Techniken wie Parallelverarbeitung auf Grafikkarten übertragen. Die Grundfragestellungen sind dabei immer dieselben:
Die Problemstellung muss gut parallelisierbar sein und einen möglichst geringen sequenziellen (nicht parallelisierbaren) Anteil aufweisen. Gut geeignet sind numerische Simulationsverfahren, das Training neuronaler Netze sowie mathematische Verfahren wie Matrizen-, Tensor- und Vektorberechnungen.
Um parallele Anwendungen zu entwickeln, sind Kenntnisse über das Speichermodell entscheidend, wie beispielsweise bezüglich der Atomarität von Datentypen oder Sichtbarkeit (sind Änderungen von Variablen über mehrere Threads hinweg sichtbar).
Nicht synchronisierte, parallele Speicherzugriffe können zu fehlerhaften Ergebnissen und Programmabbrüchen führen. Aber jede Form der Synchronisation (atomare Variablen, synchronized) ist teuer und reduziert die Effizienz des Parallel Computings. Außerdem lässt sich die Entstehung des Programmcodes deutlich schlechter nachvollziehen.
Gemeinsam genutzte veränderliche Daten sind auf ein Minimum zu reduzieren. Optimal sind separate Speicherzugriffe pro Thread oder ein Read-only-Zugriff auf Daten von mehreren Threads.
Dieser Beitrag stammt von unserem Partnerportal Maschinenmarkt.de.
Literatur
[1] Java Language Specification, Non-Atomic Treatment of double and long, am 20. 2. 2020
* Dr. Sebastian Bindick ist IT-Architekt bei der Volkswagen Group IT in 38440 Wolfsburg
(ID:46604934)
