Blogpost vom 26. Juni 2018
Parallele Programmierung: Hintergründe und Gesetzmäßigkeiten
Wenn wir in der Softwareentwicklung parallele Programmierung sagen, meinen wir damit ein Entwicklungsmuster, nach dem Softwareprozesse parallel, also gleichzeitig, ablaufen. Durch die gleichzeitige Abarbeitung mehrerer Rechenoperationen erhoffen wir uns einen spürbaren Zugewinn an Effizienz im Workflow einer Applikation. Frommer Wunsch oder berechtigte Hoffnung?
Hintergrund
Im Zeitalter exponentiell ansteigenden Datenverkehrs wird der Bedarf an harten und weichen Rechenkapazitäten immer größer. Auch die Rechenprozesse selbst werden deutlich komplexer und erfordern mehr Ressourcen. Eine Antwort darauf ist die Cloud, die der Nachfrage nach Serverleistung mit virtuellen Hostingdiensten nachkommt und so erheblichen Druck von Rechenzentren und Serverlandschaften nimmt.
Eine andere Antwort darauf sind Computer, die statt mit nur einem gleich mit mehreren Prozessorkernen ausgestattet werden. Damit schaffen sie ideale Bedingungen für die parallele Programmierung, weil sie eine nebenläufige, sprich parallele Abwicklung mehrerer Rechenprozesse ermöglichen – so genannte Threads. Dabei spielt es keine Rolle, ob die Teilprozesse auf die Sekunde genau parallel verlaufen – vielmehr geht es darum, dass die Software dadurch verschiedene Dinge gleichzeitig erledigen kann, also die Fähigkeit zum Multitasking besitzt.
Jule Witte
Presse & Kommunikation
presse@micromata.de
Unterschied zur sequentiellen Programmierung
Die sequentielle oder serielle Programmierung führt Befehle nacheinander aus. Dabei leitet sie die Reihenfolge der nötigen Rechenoperationen aus einer Kausalkette von inhaltlichen und zeitlichen Abhängigkeiten ab. Ziel ist eine Chronologie von Ereignissen, in der jede Aktion, die das Ergebnis einer vorangegangenen Aktion voraussetzt, erst dann ausgeführt wird, wenn dieses Ergebnis vorliegt.
Die Sequentialisierung macht es deutlich einfacher, eine klassische Deadlock-Situation zu verhindern, ein Zustand, in dem eine zyklische Wartesituation zwischen mehreren Prozessen auftritt, weil jeder beteiligte Prozess auf die Freigabe von Ressourcen wartet, die ein anderer beteiligter Prozess bereits exklusiv belegt hat. Eine solche Blockade kann dann nur noch durch ein Time-out oder einen externen Eingriff aufgelöst werden.
Das Amdahl’sche Gesetz
Das Amdahl’sche Gesetz bezeichnet in der Informatik ein Modell zur Beschleunigung von Programmen durch Parallelisierung, deren Voraussetzung bekanntlich die Verwendung mehrerer Prozessoren ist. Verwendet man zum Beispiel doppelt so viele Prozessoren, benötigt man nach Amdahl im besten Fall die halbe Zeit zur Durchführung des Programms aka zur Lösung des Problems. Dabei wird die Temposteigerung allerdings dadurch ausgebremst, dass Programme niemals vollständig parallel operieren können und dass es immer einen gewissen Anteil an sequentiellen Programmteilen geben muss – etwa bei der Initialisierung oder in der Speicherverwaltung, weil diese Dinge entweder auf nur einem Prozessor ablaufen oder in Abhängigkeit zu anderen Ereignissen stehen. Deshalb sieht Amdahl vor, den Programmcode in sortenreine Abschnitte aufzuteilen – solche, die rein sequentiell (zs) und solche, die rein parallel (zp) operieren. Die komplette Dauer eines Programmes ergibt sich dann aus der Formel Z =zs +zp.
Wenn also ein Task zehn Sekunden braucht, um vollständig durchzulaufen, und eine Sekunde davon sequenziell abgewickelt werden muss, entfallen die restlichen neun Sekunden (90 % der Gesamtlaufzeit) auf parallele Prozesse. Diese können zwar auf beliebig viele Prozessoren (ηp) verteilt werden, die gesamte Rechenzeit kann aber niemals unter eine Sekunde sinken. Der Beschleunigungsfaktor liegt damit maximal bei 10.
Amdahl beobachtet, dass bei steigender Anzahl der Prozessoren dieser Beschleunigungsfaktor (Speed-up) immer stärker von den sequenziellen Anteilen des Prozesses gehemmt wird, da mit der Inbetriebnahme weiterer Prozessoren auch weitere Aufwände anfallen, für die Initialisierung etwa oder für die Synchronisierung, sprich z0(ηp).
Kritiker von Amdahl werfen dem Gesetz vor, bestimmte positive Effekte außer Acht zu lassen. Seine rein lineare Beschleunigungsberechnung (zehnfache Anzahl von Prozessoren = zehnfache Beschleunigung) ließe etwa die Funktion des Caches unberücksichtigt, der die Speicherschnelligkeit ebenfalls verzehnfachen und damit ein super-lineares Speed-up ermöglichen könne.
Konflikte und Konfliktmanagement
Konflikte durch Parallelisierung, wie z. B. die zeitgleiche Änderung desselben Datensatzes, können auftreten, lassen sich aber durch Maßnahmen zur Synchronisierung gut verhindern:
Mutex: Das zeitliche Zusammenspiel von Programmteilen kann so koordiniert werden, dass sie sich gegenseitig nicht behindern oder ungewollt verändern. Die Methode dafür nennen wir Mutex (Mutual Exclusion) und meinen damit den gegenseitigen Ausschluss, der nebenläufige Threads daran hindert, in den kritischen Abschnitten der Ablaufsteuerung zeitgleich auf bestimmte Ressourcen zuzugreifen oder diese zu verändern. Mittel zum Zweck sind hier Monitore (wobei ein als Monitor gekennzeichneter Compiler entsprechende Synchronisationsprimitive einfügt) oder Semaphoren (Signalgeber in der Datenstruktur, die die Daten mit den Befehlen Reservieren, Probieren und Freigeben verwalten).
Rendevouz: Alternativ ist es möglich, nebenläufige Threads zeitlich so abzustimmen, dass sie bestimmte Aktionen synchron, durchführen damit keine unnötigen Wartezeiten und Staus verursacht werden. Dazu treffen sie sich zu einer vordefinierten Zeit an einem vordefinierten Kontaktpunkt, um Daten zu übergeben bzw. entgegenzunehmen.
Warteschlangen: Anders als Staus oder zähfließender Verkehr in der Rechenkette sind diese Warteschlangen gewollt, weil sie das Risiko von Chaos und Blockaden durch ein geordnetes Nacheinander von Rechenoperationen (queue und dequeue) verhindern. Dabei arbeiten sie die anfallenden Operationen mit den Mitteln des Zwischenspeicherns nach dem Prinzip First in – First out (FIFO) chronologisch ab.
Parallele Programmierung
Mit Java 8 wurden 2014 gute Voraussetzungen für die parallele Programmierung geschaffen, die auch heute mit Java 10 noch aktuell sind. Rudimentäre Grundlagen für nebenläufige Programmierung gab es bei Java schon immer, aber um verschiedene Threads zur Erledigung einer gemeinsamen Aufgabe zu befähigen, fielen vor Java 8 noch hohe manuelle Aufwände an. Seit 2014 aber stellt die erweiterte Concurrency-Bibliothek java.util.concurrent zahlreiche Features bereit, die das parallele Paradigma effizienter umzusetzen helfen: Synchronisierungskonzepte, Locks oder Semaphoren, Threadpools und vieles mehr. Sie alle verfolgen das Ziel einer schlankeren Implementierung, dennoch bleibt die Anzahl der notwendigen Arbeitsschritte für den Prozessor immer höher als ohne Parallelisierung: Tasks müssen erstellt werden, Daten zwischen den Prozessoren verteilt werden etc. Im schlimmsten Fall frisst dieser Overhead den Vorteil einer parallelen Verarbeitung wieder auf. Vor jedem Projekt sollte man sich also fragen, ob sich dieser Aufwand im laufenden Projekt und auch im laufenden Betrieb der Software amortisiert. Lässt sich diese Frage mit Ja beantworten, ist mit der parallelen Programmierung in Java durchaus einen Effizienzgewinn zu erwirtschaften.
Evolution der parallelen Programmierung mit Java
Seit Java 5.0 gibt es erweiterte Möglichkeiten:
- Threadpools zur Wiederverwendung von Threads und eine sehr rudimentäre Lastverteilung,
- erweiterte Synchronisatoren, wie z. B. Locks oder Semaphoren,
- Datensammlungen mit angepassten Synchronisationskonzepten, die beispielsweise gleichzeitigen Lesezugriff erlauben, aber bei einem Schreibzugriff exklusiven Zugriff anfordern.
Mit Java 6 wurden diese Möglichkeiten verfeinert und geringfügig verbessert. Mit Java 7 gab es das nächste große Feature:
das ForkJoin-Framework. Hiermit wurde es deutlich leichter, Teile-und-Herrsche-Algorithmen parallel umzusetzen: Dabei teilt man eine große Aufgabe in kleinere Teilaufgaben, deren Ergebnisse man dann wieder als Ergebnis der gesamten Aufgabe zusammenfasst. Dabei kann man wiederum auch die Teilaufgaben aufteilen.
Der ForkJoinPool sorgt dabei für eine optimale Verteilung der Aufgaben auf die Prozessoren. Läuft ein Prozessor leer, nimmt er sich einfach die Aufgaben eines anderen Prozessors. Man spricht dabei von „Work stealing“, obwohl es natürlich vollkommen legal ist.
Java 8 führte dann die Streams und damit auch die Parallelen Streams auf Basis des ForkJoin-Frameworks ein.
Weitere Features
Exekutoren: Exekutoren (Executors) sind Schnittstellen, die in Java zur Verwaltung von Threads eingesetzt werden. Sie können einzelne Threads zu so genannten Threadpools bündeln (ThreadPoolExecutor) und diese dazu befähigen, Befehle zu bestimmten Zeiten und mit bestimmten Wiederholungen auszuführen (ScheduledThreadPoolExecutor).
Streams: Streams – in Java über die Stream-API java.util.stream organisiert – sind Datenströme, auf denen verkettete Rechenoperationen entweder nacheinander oder parallel ausgeführt werden können. Dabei führt der jeweilige Stream die Daten nicht selbst im Gepäck, sondern befördert lediglich Verweise auf solche, so dass die ursprünglichen Daten nicht verändert werden. Sinn und Zweck eines Streams ist die Ausführung so genannter Bulk Operations, zu deutsch Massenoperationen, die entweder auf alle oder eine Vielzahl von Sequenzen angewendet werden sollen. Diese Sequenzen können entweder Datensammlungen (Collections), Arrays, unendlich oder auch i/o-basiert sein.
Fazit
Parallele Programmierung in Reinform gibt es nicht. Softwareprogramme sind zumindest anteilig immer auch sequentiell programmiert. Das hat zur Folge, dass Applikationen durch Parallelisierung nicht zwangsweise schneller werden, sondern sogar langsamer werden können, etwa weil Rechenkonflikten vorgebeugt werden muss. Ob sich diese Aufwände lohnen, hängt von Art und Umfang der fertigen IT-Lösung ab und sollte im Vorfeld geklärt werden.
