Parallele Programmierung

Kernidee und Abgrenzung

Parallele Programmierung ist ein Programmierparadigma, bei dem ein Computerprogramm in Teilstücke zerlegt wird, die nebenläufig ausgeführt werden können. Außerdem umfasst sie Methoden, solche gleichzeitig oder verzahnt laufenden Programmabschnitte zu synchronisieren. Sie steht im Gegensatz zur klassischen sequentiellen oder seriellen Programmierung, bei der Anweisungen streng nacheinander ablaufen.

Ein wichtiger Vorteil ist, dass Programme schneller ausgeführt werden können, zum Beispiel wenn mehrere Prozessorkerne genutzt werden. Außerdem kann parallele Programmierung Nebenläufigkeit, wie sie im Alltag häufig vorkommt, direkt im Programm abbilden. Dadurch kann Quelltext in manchen Fällen einfacher und verständlicher werden. Ein Nachteil ist, dass das Laufzeitverhalten paralleler Algorithmen oft schwerer nachzuvollziehen ist als bei einem entsprechenden sequentiellen Algorithmus.

Umsetzung von Nebenläufigkeit

Für die theoretische Parallelisierung ist es gleichgültig, ob Programmteile wirklich gleichzeitig von unabhängigen Ausführungseinheiten bearbeitet werden oder nur quasi-parallel ablaufen, etwa durch Time-Sharing oder Multitasking. Entscheidend ist der Begriff der Nebenläufigkeit: Programmcode wird nicht streng hintereinander, sondern parallel, verzahnt oder in anderer Reihenfolge ausgeführt.

Zwei Programmteile sind genau dann parallelisierbar, wenn ihre parallele, verzahnte oder verdrehte Ausführung zum selben Resultat führt wie die sequentielle Ausführung. Ist das nicht der Fall, kann es zu einer Race Condition kommen. Eine Race Condition ist eine Situation, in der das Ergebnis davon abhängt, in welcher Reihenfolge nebenläufige Programmteile tatsächlich ausgeführt werden.

Nebenläufigkeit mehrerer unabhängiger Prozesse heißt Multitasking. Nebenläufigkeit innerhalb eines einzelnen Prozesses heißt Multithreading. In den Frühzeiten der Computerentwicklung waren reine Time-Sharing-Systeme verbreitet, die Nebenläufigkeit auf Benutzerebene ermöglichten.

Hardware und automatische Parallelisierung

Parallele Ausführung wird meist durch Hardware unterstützt; die Programmiersprachen sind dann im Allgemeinen darauf angepasst. Parallelisierung kann ausdrücklich durch den Programmierer geschehen, indem Programmteile in separaten Prozessen oder Threads ausgeführt werden. Sie kann aber auch automatisch erfolgen, wenn kausal unabhängige, also parallelisierbare Anweisungsfolgen nebeneinander ausgeführt werden.

Eine automatische Parallelisierung kann durch den Compiler vorgenommen werden, wenn als Zielplattform ein Computer mit Mehrkernprozessor oder ein Parallelrechner zur Verfügung steht. Auch einige moderne CPUs können Unabhängigkeiten im Maschinencode oder Mikrocode eines Programms erkennen und Anweisungen auf verschiedene Teile des Prozessors verteilen, sodass sie gleichzeitig ausgeführt werden. Diese Technik heißt Out-of-order execution.

Konflikte und Synchronisierung

Sobald Prozesse oder Threads miteinander kommunizieren, sind sie streng genommen nicht mehr als Ganze nebenläufig, weil sie sich gegenseitig beeinflussen. Nur einzelne Teilabläufe können dann noch zueinander nebenläufig sein. Wenn die Reihenfolge der Kontaktpunkte oder Kommunikationspunkte nicht festgelegt ist, können Konflikte entstehen.

Ein wichtiger Konflikt ist die Verklemmung, auch Deadlock genannt. Dabei warten zwei Abläufe gegenseitig aufeinander oder blockieren sich gegenseitig. Um solche Probleme zu behandeln, werden verschiedene Synchronisierungstechniken genutzt. Synchronisierung bedeutet, dass der Kontext eines Programmteils vor unerwarteten Veränderungen durch andere Programmteile geschützt wird.

Wenn mehrere Programmteile gemeinsam auf Daten zugreifen und mindestens einer davon schreibend oder verändernd zugreift, muss dieser Zugriff synchronisiert werden. Beispiele sind gegenseitiger Ausschluss durch einen Mutex unter Benutzung von Monitoren oder Semaphoren. Alternativ können bestimmte Aktionen von zwei Prozessen gemeinsam ausgeführt werden; solche Abstimmungen heißen Rendezvous. Eine weitere sichere Art der Kommunikation sind Warteschlangen. Diese Techniken lösen das Problem gleichzeitiger Zugriffe auf Ressourcen, verhindern aber keine Verklemmungen; im Gegenteil können sie solche Probleme begünstigen.

Besonders wichtig sind solche Techniken in verteilten Systemen, vor allem um die Integrität verteilter Transaktionen zu gewährleisten.

Sprachen für paralleles Programmieren

Die meisten Programmiersprachen bieten Möglichkeiten, Abläufe zu parallelisieren. Einige Sprachen wurden jedoch von Grund auf für paralleles Programmieren entworfen oder besitzen diese Fähigkeit inhärent.

Genannt werden unter anderem Newsqueak, eine in den 1980er Jahren veröffentlichte Sprache zur Implementierung grafischer Benutzeroberflächen, und Occam, eine 1985 veröffentlichte imperative Programmiersprache, die auf Communicating Sequential Processes aufbaut. Scratch, eine 2007 veröffentlichte bildungsorientierte visuelle Programmiersprache, führt parallele Programmierung praktisch nebenbei ein: Anfänger nutzen sie dort intuitiv, obwohl traditionelle bildungsorientierte Programmiersprachen zunächst oft sequentiell arbeiten.

Weitere Beispiele sind X10, bei IBM zur Programmierung massiv paralleler Systeme entwickelt, Erlang, bei Ericsson von Joe Armstrong und anderen entwickelt, Chapel von Cray als Konkurrent zu X10, Unified Parallel C als Erweiterung von C99 vom UPC-Konsortium, Rust als 2015 entwickelte Programmiersprache der Mozilla Research Group sowie Go.

Effizienz und Grenzen

Das gleichzeitige Abarbeiten von Berechnungen verkürzt im Allgemeinen die Ausführungszeit eines Programms. Bezogen auf die verbrauchte CPU-Zeit ist ein paralleler Algorithmus jedoch fast immer schlechter als ein serieller, weil die Synchronisierung der Abläufe zusätzlichen Verwaltungsaufwand erzeugt.

Auf einem Einkernsystem ist Parallelisierung deshalb vor allem dann sinnvoll, wenn ein Ausführungsstrang weiterarbeiten kann, während ein anderer warten muss oder warten soll. Ohne Parallelisierung würde dieser Wartezwang das Weiterrechnen im Hintergrund blockieren. Typische Gründe für das Warten sind Aufträge an das Betriebssystem oder Benutzereingaben, während im Hintergrund weitere Abarbeitungen berechnet werden.

Um parallele Programmierung voll auszunutzen, sind mehrere Ausführungseinheiten nötig. Beispiele sind Simultaneous Multithreading (SMT), etwa Hyper-Threading Technology (HTT), sowie Symmetrisches Multiprocessing (SMP), etwa mit Multicore-Prozessoren oder mehreren CPUs. Den Extremfall bildet Massively Parallel Processing (MPP) mit zum Teil mehreren tausend Prozessoren. Ebenfalls verbreitet ist der Einsatz ganzer Verbünde von Einzelrechnern, sogenannter Computercluster, für parallele Berechnungen.

Gleichzeitig sollte möglichst wenig Kontrollcode zur Koordination der Threads nötig sein, wenn dieser nur sequentiell ausgeführt werden kann. Dieser Zusammenhang ergibt sich aus dem Amdahlschen Gesetz über die Parallelisierungseigenschaften von Programmen.