7Nebenläufige und Parallele Programmierung

Die Leistungsfähigkeit von Prozessoren und Computern wächst praktisch seit dem Beginn des Computerzeitalters in den 50er Jahren des vorigen Jahrhunderts exponenziell an. Schon Gordon Moore, einer der Gründer von Intel, sagte in den 60er Jahren ein anhaltend exponenzielles Wachstum der Integrationsdichte voraus – das ist die Dichte der Transistoren auf einem Computerchip; diese Vorhersage ist seither als das Mooresches Gesetz bekannt. Erstaunlicherweise ist es bis heute gültig und wird auch aller Voraussicht nach noch einige Jahre bestand haben.

In den letzten Jahrzehnten zog eine steigende Integrationsdichte immer auch eine steigende Rechenleistung der Rechner nach sich. In den letzten Jahren ist dies jedoch in zunehmendem Maße nicht mehr der Fall. Die Integrationsdichte steigt zwar weiter gemäß des Mooreschen Gesetzes, jedoch schlägt sich diese immer weniger in einer reinen Geschwindigkeitssteigerung (im Allgemeinen gemessen an der Taktfrequenz) nieder, sondern die steigende Integrationsdichte wird zunehmend dafür genutzt, Möglichkeiten für Parallelität zu schaffen. Dies geschieht aus der Not heraus, dass die momentan erreichten Taktfrequenzen von mehreren Gigaherz aus technischen Gründen nicht mehr ohne weiteres erhöht werden können. Andernfalls würde die entstehende Wärmeenergie zu groß werden und könnte nicht mehr sinnvoll abgeführt werden. Das Mooresche Gesetz wird sich in Zukunft dadurch manifestieren, dass sich die Anzahl der Cores (also der parallel arbeitenden Prozessorkerne in einem Rechner) alle 2 – 3 Jahre verdoppeln wird. Um diese Prozessorkerne auch tatsächlich nutzen zu können, wird es immer wichtiger werden, parallel arbeitende Software zu entwickeln, die die Rechenleistung mehrerer Prozessor-Kerne bzw. mehrerer Prozessoren gleichzeitig, d. h. parallel, ausschöpfen kann.

7.1Grundlegendes

Wir stellen einige grundlegende Begriffe vor und gehen der Frage nach, was man eigentlich unter Parallelität versteht, und wie sich die Begriffe Nebenläufigkeit und Parallelität zueinander verhalten.

7.1.1Prozesse, Tasks und Threads

Ein Prozess ist ein durch das jeweilige Betriebssystem gekapseltes separat abgearbeitetes Programm. Üblicherweise reserviert das Betriebssystem für einen bestimmten Prozess einen Teil des Hauptspeichers und schützt diesen vor Zugriff durch andere Prozesse. Insbesondere der Programmcode verschiedener Prozesse befindet sich in logisch getrennten und vor gegenseitigem Zugriff geschützten Speicherbereichen. Ver schiedene Prozesse laufen nebenläufig ; das bedeutet, sie stehen in keiner oder in geringer zeitlicher Abhängigkeit. Es ist im Allgemeinen relativ einfach möglich, Prozesse zu parallelisieren, falls entsprechende Hardware vorhanden ist. Die Kommunikation zwischen zwei Prozessen ist – unter anderem aufgrund der logisch voneinander getrennten Speicherbereiche – gewöhnlich recht aufwändig. Prozesse werden gelegentlich abhängig vom Kontext als Tasks bezeichnet.

Ein einzelner Prozess wiederum kann mehrere Threads beinhalten. Als Threads werden nebenläufige Ausführungsstränge bezeichnet. Ein Thread ähnelt zwar einem Prozess, besitzt aber wenigerOverhead . 43 Insbesondere besitzt ein Thread keinen durch das Betriebssystem eigens für ihn geschützten Speicherbereich. Obwohl Threads nebenläufige Programmteile implementieren, sind diese im Allgemeinen nicht ohneweiteres parallelisierbar. Als Threads werden oft Code-Teile realisiert, die zwar serielle Aufgaben darstellen aber nicht unbedingt in einer linearen Art und Weise ablaufen müssen. Ein typisches Beispiel stellt eine sogenannte Event-Loop dar. Das ist eine Art Endlosschleife, die nichts anderes tut, als auf ein bestimmtes oder eine Menge bestimmter Ereignisse zu warten, um in Folge bestimmte Aktionen anzustoßen. Event-Loops sollten nicht die gesamten Rechenkapazitäten des Rechners aufbrauchen, sondern eher „stückchenweise“ abgearbeitet werden; hier würde es sich anbieten die Event-Loop in einem Thread abzuarbeiten. Die Kommunikation zwischen Threads ist – unter anderem aufgrund des geringeren Organisations-Overheads – im Vergleich zur Kommunikation zwischen Prozessen weniger aufwändig.

7.1.2Nebenläufigkeit vs. Parallelität

Häufig werden die Begriffe „Nebenläufigkeit“ und „Parallelität“ durcheinander geworfen. Für diese Einführung in die parallele Programmierung ist eine klare Unterscheidung dieser Begriffe jedoch wichtig.

Nebenläufigkeit

Als nebenläufig werden Prozesse (bzw. Tasks oder Threads) bezeichnet, deren Ausführungen in keiner zeitlichen Abhängigkeit zueinander stehen. Sind zwei Prozesse A und B nebenläufig, dann spielt es also keine Rolle, ob entweder zuerst A und dann B , oder zuerst B und dann A , oder A und B verzahnt (etwa mittels Time-Sharing) oder gar tatsächlich parallel ausgeführt werden.

Parallelität

Zwei Prozesse werden parallel ausgeführt, wenn Sie auf zwei gleichzeitig arbeitenden Ausführungseinheiten (etwa zwei Rechnern, zwei CPUs oder zwei Cores) wirklich gleichzeitig ausgeführt werden.

7.1.3Multithreading, Time-Sharing und Threadzustände

Threads müssen nicht notwendigerweise auf paralleler Hardware ausgeführt werden. Üblicherweise ist das Betriebssystem dafür zuständig, die Ausführung mehrerer Threads zumindest für den Benutzer bzw. Programmierer parallel erscheinen zu lassen. Dies geschieht mittels Time-Sharing : Das Betriebssystem weist hierbei den einzelnen Threads Zeitscheiben zu, und ein Thread erhält die Rechenzeit der CPU für eine bestimmte begrenzte Zeitspanne, die sich oft nur im Millisekunden-Bereich bewegt, bevor er die Rechenzeit an den nächsten Thread abgeben muss. Üblicherweise erfolgt diese Zuteilung der Rechenzeit reihum. Abbildung 7.1 veranschaulicht die Funktionsweise von Time-Sharing.

Abb. 7.1. Funktionsweise des (Software-seitigen) Multithreading.

Viele Betriebssysteme erlauben zum einen eine Priorisierung der Threads: Diejenigen Threads mit einer höheren Priorität erhalten in der Regel längere Zeitscheiben. Zum anderen können sich in vielen Betriebssystemen die Threads und auch, Prozesse in unterschiedlichen Zuständen befinden. Wichtig ist insbesondere der Zustand Idle , der anzeigt, dass der jeweilige Thread oder Prozess auf ein Ereignis wartet; dies kann etwa eine Benutzereingabe sein, die Freigabe einer Ressource, wie etwa des Hauptspeichers oder des Systemsbusses, oder auch ein durch einen anderen Thread auszulösendes Ereignis, wie etwa die Freigabe eines Locks. Befindet sich ein Thread im Zustand Idle , so erhält er entweder keine oder nur eine sehr kurze Zeitscheibe, die lediglich dazu dient zu prüfen, ob das Ereignis eingetreten ist. Durch die geschickte Verwendung mehrerer Threads kann man es so schaffen, die Leerlaufzeiten des Prozessors möglichst kurz zu halten.

7.1.4Programmierung mit Threads vs. Multi-Core-Programmierung

Threads wurden Anfang der 90er Jahre eingeführt, um die Asynchronität bei der Programmierung von Ein-Ausgabeeinheiten und beim Progammieren von Benutzeroberflächen modellieren zu können. Die wirkliche Parallelisierung dieser Aufgaben stand dabei nie zur Debatte. Es ist daher keine gute Idee zu versuchen, einen bestimmten parallelisierbaren Algorithmus durch Threads auf mehrere Cores oder mehrere Prozessoren zu parallelisieren. Es kann nicht garantiert werden, dass zwei Threads auch tatsächlich parallel auf zwei unterschiedlichen Prozessoren laufen; in Python ist dies aus technischen Gründen sogar unmöglich 44 .

Pythons thread -Modul bietet eine einfache technische Schnittstelle für die Programmierung mit Threads. Das threading -Modul greift auf das thread -Modul zurück und bietet eine abstraktere Schnittstelle zur Programmierung mit Threads. Für die Programmierung komplexer Anwendungen ist es ratsam, high-level-Module wie etwa das Python-Modul twisted zu verwenden.

7.2Parallele Rechnerarchitekturen

Diese Einführung in die Informatik lässt eigentlich die Rechnertechnik und die Technische Informatik außen vor und beschreibt fast ausschließlich die Sicht eines Programmierers. Will man jedoch parallele Software erstellen, dann ist es entscheidend wichtig zu wissen, wie die Hardware, auf der die parallelen Programme ablaufen sollen, grob strukturiert ist, und ob und wie sie überhaupt Software parallelisieren kann. Es zeigt sich, dass es sehr unterschiedliche „Grade“ von Parallelität gibt, die eine bestimmte Hardware unterstützt – angefangen von einer Cloud, bis hin zu einer GPU oder einem Prozessor, der hardware-seitiges Multithreading unterstützt. Im Folgenden skizzieren wir grob parallele Hardwarearchitekturen – insbesondere um zu klären, von welcher dieser Architekturen wir im Weiteren bei der Programmierung paralleler Programme ausgehen.

7.2.1NOWs

Als NOW (engl. für Network of Workstations ) wird eine Menge durch ein Netzwerk verbundener Computer bezeichnet, wie in Abbildung 7.2 veranschaulicht. Die Rechner eines NOW arbeiten so eng zusammen, dass sie für den Benutzer wie ein einzelner schneller Computer wirken. Entscheidend für die Rechenleistung ist ein schnelles LAN (= Local Area Network), das die Computer verbindet. NOWs sind im Allgemeinen kostengünstiger als vergleichbar schnelle Einzelrechner. Viele der weltweit schnellsten Rechner sind NOWs. Abbildung 7.2 veranschaulicht solch einen Zusammenschluss von Rechnern zu einem NOW; in der Abbildung hat dieser Zusammenschluss die Form eines sogenannten Grids – einer matrixartigen Verbindung von Rechnern. Es sind jedoch auch andere Verbindungsmöglichkeiten denkbar.

Abb. 7.2. Aufbau eines sogenannten NOW: Viele eigenständige Rechner werden über ein schnelles Netzwerk miteinander verbunden und können dadurch nach außen den Eindruck eines einzigen leistungsstarken Rechners vermitteln. Häufig formen diese Rechner ein sogenanntes Grid, d. h. sie sind matrixartig miteinander verbunden. Grundsätzlich sind jedoch auch andere Verbindungsarten möglich, beispielsweise die Verbindung über einen Bus.

7.2.2SMPs und Mehrkern-Prozessoren

In einem sogenannten symmetrischen Multiprozessorsystem , oft kurz einfach SMP genannt, befinden sich in einem Rechner mehrere gleichartige Prozessoren, die sich einen gemeinsamen Speicher teilen. Abbildung 7.3 veranschaulicht den Aufbau eines symmetrischen Multiprozessorsystems. Man bezeichnet ein solches Multiprozessorsystem übrigens deshalb als symmetrisch , weil jeder Prozessor prinzipiell jeden Prozess ausführen können muss; bei asymmetrischen Multiprozessorsystemen dagegen, ist jedem Prozessor eine Aufgabe bzw. ein Aufgabenbereich fest zugewiesen.

Mehrkern-Rechner bzw. Mehrkern-Prozessoren sind SMPs, bei denen sich mehrere Prozessoren auf einem einzigen Chip befinden.

Abb. 7.3. Grundsätzlicher Aufbau eines Multi-Core-Rechners. Dieser besteht aus mehreren parallel arbeitenden, sich auf einem Chip befindenden Prozessoren – auch Cores genannt. Ein Multicore-Rechner hat einen Speicher, auf den die Cores gemeinsam Zugreifen. Dieser Speicher zusammen mit dem Systembus, bildet oft den Flaschenhals eines solchen Systems.

7.2.3GPUs

Das Kürzel „GPU“ steht für „Graphics Processing Unit “. Eine GPU ist ein Hilfsprozessor 45 , der auf die Berechnung graphischer Darstellungen, unter anderem auf das sogenannte Rendering 46 spezialisiert ist.

Eine GPU ist für eine bestimmte Art paralleler Berechnungen ausgelegt, sog. SIMD-Berechnungen. Das Kürzel „SIMD“ steht für Single Instruction, Multiple Data ; eine GPU bietet also Maschinenbefehle an, die bestimmte Berechnungen über viele Daten gleichzeitig ausführen können. Dies sind etwa Kommandos zur Vektor-Matrix-Multiplikation oder zur Berechnung eines Skalarprodukts, bei denen dieselbe Operation (nämlich in diesem Fall die Multiplikation) über eine ganze Reihe von Daten (nämlich in diesem Fall über alle Komponenten eines Vektors bzw. über alle Zeilen bzw. Spalten einer Matrix) ausgeführt werden müssen.

Abbildung 7.4 zeigt grob die Architektur einer typischen GPU – angelehnt an die ATI-Evergreen-GPU-Architektur. Im Gegensatz zu Mehrkern-Rechnern ist die Parallelität in der Architektur einer GPU feingranularer: Diese Architektur besteht aus 20

Abb. 7.4. Architektur einer typischen GPU – angelehnt an die ATI-Evergreen-GPU-Architektur.

parallel arbeitenden SIMD-Prozessoren; neben den über den Systembus erreichbaren globalen Cache-Speichern 47 , hat auch jeder dieser Prozessoren seinen eigenen lokalen Speicher. Jeder dieser SIMD-Prozessoren besteht wiederum intern aus 16 sogenannten Thread-Prozessoren, und jeder dieser Thread-Prozessoren hat ebenfalls einen lokalen Speicher. Diese Vielzahl an lokalen Speichern verhindert unnötige Kommunikation über den verhältnismäßig langsamen Systembus und stellt sicher, dass möglichst viele Operationen nur mit lokalen Speichermodulen arbeiten. Insgesamt hat diese GPU 20 · 16 · 5 = 1600 parallel arbeitender SIMD-Prozessoren. Diese Architektur ist also auf eine große Anzahl parallel arbeitender Kleinst-Operationen ausgelegt – insofern kann man die durch eine GPU ermöglichte Parallelität als feingranular bezeichnen.

Außerdem ist die Architektur der gängigen Hauptprozessoren unserer Desktop-Rechner darauf spezialisiert, die Latenzzeiten, d. h. die Antwortzeiten, möglichst gering zu halten. Dagegen ist die Architektur einer GPU darauf spezialisiert, den Durchsatz , d. h. die Größe des verarbeitbaren Datenstroms, möglichst hoch zu halten. Das liegt daran, dass für die eigentlichen Anwendungen einer GPU die Latenzzeit unkritisch ist: ein Bild muss nur ca. alle 20 Millisekunden (geht man von ca. 50 Bildern pro Sekunde aus, um eine ruckelfreie Darstellung zu garantieren) fertig berechnet zur Ausgabe auf dem Bildschirm vorliegen, und 20 Milisekunden sind für Prozessoren eine verhältnismäßig lange Zeit.

Aufgabe 7.1

Lesen Sie [7] und diskutieren Sie, welche algorithmischen Aufgaben (abgesehen von den graphischen Berechnungen, für die GPUs ursprünglich ausgelegt sind) von der Unterstützung einer GPU bzw. einer GPGPU (= General Purpose GPU) profitieren könnten.

7.2.4Hardware-seitiges Multithreading

Hardware-seitiges Multithreading, oft auch als Simultaneous Multithreading bezeichnet, unterstützt durch zusätzliche Hardware (wie mehrere getrennte Registersätze, mehrere ALUs, mehrere Pipelines) die tatsächlich parallele Ausführung mehrerer Threads. Jeder Thread besitzt hierzu einen eigenen lokalen Speicher (in Form eines eigenen Registersatzes, Stackpointers, Programmzählers und teilweise sogar durch eine eigene Befehlspipeline). Anstatt das Betriebssystem die zeitlich verschränkte Ausführung der Threads mittels Time-Sharing organisieren zu lassen, übernimmt die Prozessorhardware diese Aufgabe. Dies macht sich in der Praxis zum einen dadurch bemerkbar, dass Thread-Wechsel viel schneller erfolgen können als durch Software-seitiges Multithreading und zum anderen können Threads zumindest teilweise wirklich parallel ablaufen.

7.3Techniken Paralleler Programmierung

Es gibt einige grundsätzlich unterschiedliche parellele Programmiertechniken. Allen gemeinsam ist, dass sie eine Aufgabe intern in Threads oder Prozesse aufteilen, und Möglichkeiten bereitstellen, diese Threads oder Prozesse von Zeit zu Zeit miteinander kommunizieren zu lassen. Entweder, um Daten, etwa Ergebnisse von Teilberechnungen, auszutauschen oder um sich zeitlich zu synchronisieren, d. h. Prozess x muss etwa warten, bis Prozess y fertig ist, oder bis Prozess y ein bestimmtes Zwischenergebnis liefert. Verschiedene Techniken paralleler Programmierung unterscheiden sich im Wesentlichen dadurch, wie eine solche Inter-Prozesskommunikation und - synchronisation erfolgen kann.

7.3.1Locks

Der Datenaustausch paralleler (oder nebenläufiger) Prozesse erfolgt oft durch globale Variablen, auf die alle Prozesse gemeinsam Zugriff haben, in die also alle Prozesse schreiben und von denen alle Prozesse lesen können. Dadurch kann aber die proble matische Situation entstehen, dass mehrere Prozesse (praktisch) gleichzeitig in eine Variable schreiben wollen. Trifft man diesbezüglich keine Vorsichtsmaßnahmen, so ensteht durch diese Situation eine sog. race condition – wörtlich übersetzt „Wettlaufbedingung“; liegt solch eine Wettlaufbedingung vor, so bedeutet dies, dass das Ergebnis einer Operation oder eines Algorithmus ungewollt stark vom zeitlichen Verhalten der Prozesse abhängt. Aber nicht nur das: durch Wettlaufbedingungen können auch die Art von Inkonsistenzen oder gar Datenverluste entstehen, vor denen sich auch Datenbankmanagementsysteme schützen müssen (siehe Kapitel 5.2 ).

In Abbildung 7.5 ist eine Situation dargestellt, in der zwei nebenläufige Threads (es könnten genauso gut Prozesse sein) auf eine globale Variable x zugreifen. Es sind keine Vorkehrungen gegen gleichzeitigen oder verschränkten Zugriff getroffen. Man sieht, dass dadurch die von Thread2 durchgeführten Änderungen durch die von Thread1 ausgeführte Änderungsoperation überschrieben werden. Um solche race conditions zu verhindern, muss ein Thread vor Zugriff auf eine globale Variable diese durch einen sog. Lock schützen – dies ist in Abbildung 7.6 veranschaulicht. Sobald Thread1 auf die globale Variable x zugreift, setzt er xLock mittels der acquire -Methode in den Zustand locked . Jeder andere Thread, der – während sich xLock im Zustand locked befindet – xLock.acquire ausführen will, muss warten, bis xLock mittels der release -Methode wieder freigegeben ist. Solch ein wartender Thread befindet sich typischerweise im Idle -Zustand und verbraucht entsprechend wenig Rechenressourcen. Während xLock sich im Zustand locked befindet, kann Thread1 ungestört die Änderungen an der globalen Variablen x vornehmen, und die Gefahr inkonsistenter Zustände ist gebannt.

7.3.2Message-Passing

Message Passing geht einen anderen Weg der Interprozess-Kommunikation: Prozesse (bzw. Prozessoren oder eigenständige Rechner in einem NOW) senden sich gegenseitig Nachrichten, um Daten auszutauschen oder um sich zeitlich zu synchronisieren. Es gibt eine standardisierte Schnittstelle, das MPI (ein Kürzel für Message Passing Interface ), die Funktionen für das Message Passing bereitstellt. Im Kern besteht diese Schnittstelle aus einer send -Funktion und einer receive -Funktion.

7.3.3Bulk Synchronous Parallel Model (BSP)

Sowohl durch Message-Passing als auch durch Kommunikation und Synchronisation mittels Locks und globaler Variablen kann es zu Deadlocks kommen. Als Deadlock bezeichnet man folgende Situation: Nehmen wir an, Prozess A hat Lock l1 gesperrt und Prozess B hat Lock l2 gesperrt. Ein Deadlock entsteht, wenn Prozess A solange mit dem Freigeben von l1 wartet, bis l2 freigegeben ist, und gleichzeitig Prozess B solange mit dem Freigeben von l2 wartet, bis l1 freigegeben wurde. Keiner der Prozesse kann fortfahren.

Abb. 7.5. Zwei nebenläufige Threads in einer Beispielsituation, die Inkonsistenzen und Datenverlust verursacht. Während Thread1 gerade dabei ist, die globale Variable x zu ändern, liest Thread2 die Variable x und überschreibt den alten Wert mit x + 1. Thread1 „weiß“ davon jedoch nichts und überschreibt x mit dem verdoppelten ursprünglichen Wert von x ; die von Thread2 durchgeführten Änderungen werden so ignoriert.

Abb. 7.6. Hier werden Inkonsistenzen und Datenverlust dadurch vermieden, dass ein sog. Lock gesetzt wird, sobald Thread1 mit dem Prozess beginnt, die Variable x zu verändern. Während der Lock gesetzt ist, kann kein anderer Thread auf x zugreifen und muss solange warten, bis Thread1 den Lock wieder freigibt.

Das Bulk Synchronous Parallel Model schränkt die Möglichkeiten der Interprozess-Kommunikation ein, verhindert jedoch im Gegenzug Deadlocks und erleichtert zudem Laufzeit-Abschätzungen. Die Grundidee ist die folgende: Die Interprozess-Kommuni-kation erfolgt nur zu bestimmten Zeitpunkten im „bulk“, also in größeren Message-Paketen. Nach diesem Kommunikationsschritt erfolgt eine sogenannte Barrier Synchronisation , d. h. zu diesem Zeitpunkt wird auf alle beteiligte Prozesse gewartet und es darf erst fortgefahren werden, wenn alle Prozesse synchronisiert sind.

7.4Multithread-Programmierung in Python

Es gibt prinzipiell nur eine Situation, in der eine Verwendung von Threads sinnvoll ist: Ein Programm muss auf eine Reihe von Ereignissen warten bzw. auf diese reagieren, und es ist nicht von vornherein klar, in welcher Reihenfolge die Ereignisse eintreten. Diese Reihenfolge könnte etwa von Benutzereingaben, Signalen von externen Geräten, wie etwa einem Scanner oder Drucker, oder sonstigen nicht-deterministisch eintreffenden Situationen abhängen.

Abb. 7.7. Ein Deadlock: Thread1 wartet auf Thread2 und Thread2 wartet auf Thread1 .

Insbesondere graphische Benutzeroberflächen, die sogenannten GUIs, arbeiten gerne mit Threads, um bestimmte, für die Oberfläche relevante Ereignisse (wie Mausklicks oder Tastatureingaben) effizient abzufragen. Auch für die Implementierung vieler Kommunikationsprotokolle (hier muss auch auf Ereignisse bestimmter Geräte gewartet werden) ist eine Verwendung von Threads sinnvoll – hierfür bietet etwa das Pythonmodul twisted eine Schnittstelle an.

7.4.1Das threading-Modul

Erstes Beispiel: Nebenläufige Summation

Wir beginnen mit einem zwar nicht praktisch sinnvollen jedoch instruktiven Beispiel, das veranschaulicht, wie sich nebenläufige Threads verhalten. Das in Listing 7.1 gezeigte Skript startet mehrere Threads, die jeweils die Summe mit einem zufällig gewählten n berechnen:

Listing 7.1. Mehrere Threads berechnen nebenläufig die Summe der ersten n natürlichen Zahlen.

In Zeile 11 werden in einer Listenkomprehension drei Threads mittels des Thread -Konstruktors des Moduls threading angelegt. Der target -Parameter spezifiziert, welche Funktion der jeweilige Thread ausführen soll. In diesem Fall führen alle drei Threads dieselbe Funktion aus – nämlich die ab Zeile 4 definierte Funktion sumThread. Das args-Argument spezifiziert (als Tupel) die Argumente, die dem jeweiligen Thread übergeben werden, in diesem Fall ist das lediglich eine Zahl.

7.4.2Verwendung von Locks

Jeder Thread gibt zunächst den Text 'Beginne Thread ...: Summiere bis ...' aus, summiert dann die Zahlen auf und gibt schließlich den Text Ende Thread ...: Summe ist ... aus. Sehen wir uns einmal eine tatsächliche Ausgabe des obigen Skripts an:

An den unteren drei Zeilen kann man zunächst erkennen, dass die Reihenfolge, in der die Threads enden, eine andere ist als die Reihenfolge, in der sie gestartet wurden.

Aufgabe 7.2

Erklären Sie die Reihenfolge, in der die Threads enden.Warum endet hier Thread 2 noch vor Thread 1?

Führt man den Programmcode aus Listeing 7.1 unter Linux aus, so kann sogar vorkommen, dass die Bildschirmausgabe eines Threads mittendrin unterbrochen wird und der Ausführungsstrang einem anderen Thread übergeben wird. Ob und wann dies geschieht, lässt sich, zumindest aus der Perspektive des reinen Anwenders des Betriebssystems, nicht vorhersagen und muss gedanklich der „Willkür“ des Betriebssystems zugeschrieben werden.

Als Programmierer hat man aber eine Möglichkeit, solch „unschöne“ Unterbrechungen zu verhindern. Listing 7.2 zeigt, wie ein Teil solcher Unterbrechnungen durch Verwendung eines Locks verhindert werden kann.

Listing 7.2. Erweiterung von Listing 7.1 : Die Bildschirmausgabe in Zeile 7 wird unter Verwendung eines Locks vor Unterbrechungen durch die anderen Threads geschützt.

In Zeile 13 wird eine einfache Lock-Variable definiert, die zwei Zustände locked und unlocked besitzt. Der Methodenaufruf l.acquire () wartet – falls erforderlich – so lange, bis l im Zustand unlocked ist und wandelt den Zustand in locked um. Der Methodenaufruf l.release () überführt l wieder in den Zustand unlocked . Eine Unterbrechung der print -Ausgabe,wäre nun nicht mehr möglich. Betrachten wir nochmals die Beispielausgabe von oben: Ist Thread 1 gerade dabei, Zeile 7 abzuarbeiten und eine entsprechende Bildschirmausgabe zu produzieren, so ist es zwar möglich, dass er während dieser Bildschirmausgabe von einem anderen Thread (etwa Thread 2) unterbrochen wird. Thread 1 hat jedoch zuvor l.acquire () ausgeführt, d. h. der Lock ist gesperrt. Thread 2 muss mit der Ausführung von Zeile 6 (also l.acquire ) warten, bis der Lock wieder freigegeben ist, d. h. bis Thread 1 die Kommandos in den Zeilen 7 und 8 fertig ausgeführt hat.

Aufgabe 7.3

Zwar ist durch das in Listing 7.2 gezeigte Skript die Gefahr, dass die Bildschirmausgabe eines Threads durch die Bildschirmausgabe eines anderen Threads unterbrochen wird, weitgehend gebannt. Es sind jedoch nach wie vor Situationen denkbar, in denen es zu einer solchen unerwünschten Unterbrechung kommen kann.

(a)Beschreiben Sie eine Situation während der Ausführung des in Listing 7.2 gezeigten Skripts, in der die Bildschirmausgabe eines Threads durch die Bildschirmausgabe eines anderen Threads unterbrochen werden kann.

(b)Passen Sie das in Listing 7.2 gezeigte Skript so an, dass alle Unterbrechungen von Bildschirmausgaben ausgeschlossen werden.

Daten aus einer Liste von URLs

Wir fahren mit folgendem einfachen und auch praktisch nützlichen Anwendungsbeispiel fort, das mit Verwendung von Threads sehr viel schneller ablaufen kann als eine entsprechende rein serielle Implementierung. Wir wollen Daten (sagen wir: die ersten 1024 Bytes) aus einer Reihe verschiedener URLs abrufen. Eine serielle Implementierung ohne die Verwendung von Threads zeigt Listing 7.3 :

Listing 7.3. Serielle Implementierung der Aufgabe, Daten aus einer Liste von URLs zu lesen.

Hier können wir die Ausführungszeit durch Verwendung von Threads in der Regel deutlich verbessern. Warum ist das so? Welcher Teil der Implementierung wirkt sich negativ auf die Laufzeit aus? Das Kommando urlopen öffnet ein Socket zu einer URL; je nach Bandbreite der jeweiligen Verbindung und Leistungsfähigkeit des jeweiligen Servers dauert es eine gewisse Zeit, bis die angeforderten Daten von der URL eintreffen. In dieser Zeit befindet sich das Pythonskript gewissermaßen im Leerlauf und verschwendet seine Rechenzeit damit, auf eintreffende Daten zu warten. Dieses aktive Warten kann man durch Verwendung von Threads vermeiden.

Die in folgendem Listing 7.4 gezeigte Implementierung verwendet Threads um Daten aus einer Liste von URLs zu lesen.

Listing 7.4. Nebenläufige Implementierung der Aufgabe, Daten aus einer Liste von URLs zu lesen.

In Zeile 10 wird pro URL ein Thread erzeugt; dies geschieht unter Verwendung des Konstruktors Thread , dessen target -Argument die Funktion spezifiziert, die der jeweilige Thread „gleichzeitig“ 48 zu den übrigen Threads ausführt, und dessen args-Argument die Argumente spezifiziert, mit der die Thread-Funktion aufgerufen wird. Die Schleife in Zeile 11 startet jeden dieser Threads jeweils mit der start ()-Methode.

Aufgabe 7.4

Wie oben schon erwähnt, kann man die Aufgabenstellung, Daten aus einer Reihe von URLs zu lesen, mittels Threads viel effizienter implementieren. Verwenden Sie Pythons timeit -Modul, oder das entsprechende „Magic-Command“ %timeit in einem Python-Notebook, um die Laufzeit desjenigen in Listing 7.3 gezeigten seriellen Skripts mit der Laufzeit des in Listing 7.4 zu vergleichen.

7.4.3Das queue-Modul

Bisher ließen wir die Threads lediglich Daten auf dem Bildschirm ausgeben. Häufig ist es jedoch notwendig, die von den einzelnen Threads produzierten Daten aufzusammeln und in einer (globalen) Variablen zu speichern.

Locks und globale Variablen

Listing 7.5 zeigt, wie man die Ausgaben der URLs – statt sie einfach auf dem Bildschirm auszugeben – in der globalen Variable erg speichert.

Listing 7.5. Nebenläufiges Lesen der Daten aus verschiedenen URLs; die Daten werden in der für die einzelnen Threads globalen Variablen erg aufgesammelt.

Die Threads tragen nun die aus den URLs gelesenen Daten in die globale Listenva-riable erg ein. Dies geschieht – durch Locks geschützt – in Zeile 8. Jeder der in Zeile 14 erzeugten Threads greift auf dieselbe globale Variable zu. Hier unterscheiden sich die Threads fundamental von den in Abschnitt 7.5.1 behandelten Prozessen: Prozesse besitzen keine gemeinsame Umgebung; jeder Prozess arbeitet auf getrennten Kopien globaler Variablen. Nachdem in Zeile 15 alle Threads gestartet wurden, wartet man in Zeile 16, bis alle Threads beendet wurden. Dies erledigt der Aufruf t.join () : er lässt das Hauptprogramm solange warten, bis Thread t beendet wurde. Erst danach enthält die Liste erg alle durch die Threads produzierten Daten, und die Ergebnisse können ausgegeben werden.

Aufgabe 7.5

(a)Was würde das Skript aus Listing 7.5 ausgeben, wenn man Zeile 16 auskommentieren würde?

(b)An welcher Listenposition der Variable erg stehen die Ausgaben desjenigen Threads, der als erstes endete? An welcher Listenposition der Variable erg stehen die Ausgaben desjendigen Threads, der als letztes endete?

Aufgabe 7.6

(a)Erweitern Sie das in Listing 7.5 gezeigte Skript so, dass jeder Thread auch zusätzlich die von ihm benötigte Laufzeit in der Liste erg speichert.

(b)Bestimmen Sie zusätzlich die Laufzeit des gesamten Skripts und vergleichen Sie die Summe der Laufzeiten der einzelnen Threads mit der Gesamtlaufzeit des Skripts. Erklären Sie ihre Beobachtungen.

Tipp: Verwenden Sie die Funktion time aus dem Pythonmodul time , zur Laufzeitberechnung.

Queues

Pythons threading -Modul bietet alle nötigen Möglichkeiten der Synchronisation von Threads und der Datenkommunikation zwischen Threads an, wie beispielsweise Locks, Semaphoren oder Events. Eine Semaphore ist eine Verallgemeinerung eines Locks. Während ein Lock nur zwei Zustände (nämlich locked und unlocked ) kennt, kennt eine Semaphore viele Zustände. Eine Semaphore ist eine globale Variable, die die Anzahl der acquire -Aktionen minus die Anzahl der release -Aktionen speichert. So kann man etwa kontrollieren, wie viele Threads gleichzeitig auf eine bestimmte Ressource zugreifen dürfen.

Trotz der schon vorhandenen Möglichkeiten des threading-Moduls ist es dennoch in vielen Fällen ratsam, die auf das Zusammenspiel mit Threads abgestimmten Warteschlangen (auch in der deutschsprachigen Literatur oft als Queues bezeichnet) des Pythonmoduls Queue zu verwenden. Eine Queue ist eine sogenannte First-in-First-out-Datenstruktur (kurz auch als Fifo-Datenstruktur bezeichnet): Dasjenige Element, das als erstes in die Queue eingefügt wurde, kommt auch als erstes „zum Zuge“. Abbildung 7.8 veranschaulicht die Funktionsweise einer Queue: Ein neues Element wird „hinten“ in die Queue eingereiht; dies geschieht mittels der put-Methode. Das am weitesten „vorne“ befindliche Element, das also als erstes eingefügt wurde, wird bei einem Aufruf der get -Methode als nächstes zur weiteren Verarbeitung entfernt.

Verwendet man Queues um die von Threads produzierten Ergebnisse aufzusammeln bzw. um Ergebnisse zwischen Threads auszutauschen, so braucht man sich als Programmierer um Locks und eventuelle Race-Conditions nicht zu kümmern; die get und put -Methoden einer Queue kapseln das Setzen und Lösen der Locks an den richtigen Stellen.

Abb. 7.8. Funktionsweise einer Queue-Datenstruktur. Mittels der put -Methode reiht man ein neues Element „hinten“ in der Warteschlange ein. Das am weitesten „vorne“ befindliche Element kann mittels der get -Methode aus der Queue zur weiteren Bearbeitung entfernt werden. Beide Operationen sind thread-safe , d. h. sie verwenden Locks so zur richtigen Zeit, dass es zu keinen Race-Conditions kommen kann.

Listing 7.6. Nebenläufiges Lesen der Daten aus verschiedenen URLs; die durch die einzelnen Threads produzierten Daten werden globalen synchronisierten Queue q aufgesammelt.

Jeder Thread führt die Funktion getUrl mit einer anderen URL aus und fügt – sobald sie die Daten von der URL erhalten hat – diese mittels put in die Queue ein (Zeile 6). Diese Einfügeoperationen ist sicher: das Queue -Objekt „kümmert“ sich um das Setzen der dafür notwendigen Locks und das Freistellen dieser Locks nach der put -Operation; der Progammierer braucht sich darum nicht zu kümmern. Die Schleife in Zeile 14 liest Daten der Queue mittels der get-Methode aus. Man beachte, dass unmittelbar nach Ausführung der Schleife in Zeile 13 die Queue leer ist. Ein Aufruf der get-Methode blockiert die Ausführung des Hauptprogramms so lange, bis sich ein Datum in der Queue befindet, dass dann zurückgeliefert wird.

Aufgabe 7.7

Wie würde sich das in Listing 7.6 gezeigte Pythonskript verhalten, falls Sie nach Zeile 14 die Codezeile

einfügen würden?

7.5Multicore-Programmierung in Python

Wie schon weiter oben erwähnt, ist es nicht möglich, Threads in einer tatsächlich parallelen Weise auf unterschiedliche Prozessoren zu verteilen. Wollen wir Codeteile auf unterschiedlichen Prozessorkernen ausführen lassen, müssen wir daher auf andere Python-Module zurückgreifen.

7.5.1Das multiprocessing -Modul

Das multiprocessing -Modul stellt eine ähnliche Schnittstelle bereit, wie das threading -Modul. Der wichtige Unterschied besteht darin, dass das multiprocessing -Modul mit mehreren Prozessen arbeitet, die – im Unterschied zu Threads – auch auf mehreren Kernen eines Prozessors tatsächlich parallel laufen können. Sowohl das multiprocessing -Modul als auch das später vorgestellte mpi4py -Modul können je nach Einstellungen auch auf mehreren getrennten Rechner – etwa einem NOW – parallel laufen. Wir gehen dieser Möglichkeit jedoch hier nicht näher nach, sondern beschränken uns auf die Vorzüge der parallelen Ausführung auf mehreren Kernen eines einzelnen Rechners.

Beispiel 1: Durchführung eines Zufallsexperimentes

Wir wollen durch die wiederholte Ausführung eines Zufallsexperimentes Näherungswerte für Wahrscheinlicheiten bestimmen. In diesem Beispiel interessieren wir uns für die Frage, wie groß die Wahrscheinlichkeit ist, bei n -maligem Würfeln eine Gesamtaugensumme von k zu erhalten – Abbildung ?? veranschaulicht diese Fragestellung. Listing 7.7 zeigt eine rein serielle Implementierung eines solchen Zufallsexperimentes. Die Parameter n, k und die Anzahl der Wiederholungen werden über die Kommandozeile eingelesen. Die Listenkomprehension in Zeile 7 summiert die Augenzahlen eines Wurfs auf und prüft ob diese Summe der Zahl k entspricht.

Listing 7.7. Serielle Implementierung des Zufallsexperiments

Dieses Problem ist embarrassingly parallel . Als embarrassingly parallel bezeichnet man Probleme bzw. Algorithmen, die sich einfach und effektiv in parallelisierbare Teilprobleme zerlegen lassen. Bei Verwendung von M parallelen Prozessoren kann man bei solchen Problemen eine Laufzeitsteigerung um (fast) den Faktor M erwarten. Das in Listing 7.7 implementierte Zufallsexperiment kann man sehr einfach in parallelisierbare Teile zerlegen: Will man das Zufallsexperiment M -mal wiederholen, so könnte man etwa M parallele Prozesse verwenden – jeder führt ein einziges Zufallsexperiment durch. Will man dagegen nur beispielsweise P (mit P < M ) Prozesse verwenden, führt jeder Prozess M /P Zufallsexperimente aus. Die in Listing 7.8 gezeigte Implementierung verwendet Pythons multiprocessing-Modul, um eine solche Aufteilung des Zufallsexperients in (eine frei wählbare Anzahl) P parallel arbeitende Prozesse zu realisieren.

Listing 7.8. Parallele Implementierung des Zufallsexperimentes unter Verwendung von P Prozessen.

In den Zeilen 5 bis 9 werden die globalen Variablen n, k, M, P und myM definiert; wichtig zu wissen ist, dass jeder der gestarteten P Prozesse auf getrennten Kopien dieser globalen Variablen arbeitet. Die Funktion proc zwischen Zeile 12 und Zeile 19 wird von jedem der P Prozesse parallel abgearbeitet. Jeder dieser Prozesse führt myMP Wiederholungen des Zufallsexperimentes durch. Dies geschieht in der for -Schleife in Zeile 15. Die Variable zaehler enthält danach die Anzahl der myM Experimente, die eine Gesamtaugensumme von k ergaben. Der Wert von zaehler wird schließlich auf die allen Prozessen gemeinsame Variable gesamt aufaddiert. Hierbei wird mit einem Lock gearbeitet, um Race-Conditions zu vermeiden.

Diese gemeinsame Variable gesamt wird in Zeile 22 durch den Konstruktor Value definiert, den das multiprocessing -Modul anbietet. Im Gegensatz zu den üblichen Python-Variablen muss der Typ der gemeinsamen Variablen vorab festgelegt werden (hier: ' i' für Integer ). In Zeile 23 werden die P Prozesse über eine Listenkomprehension mittels des Konstruktors Process erzeugt. Dieser Konstruktor erwartet zwei Argumente: Das target -Argument legt die Funktion fest, die der jeweilige Prozess parallel mit allen anderen Prozessen ausführt. Das args -Argument spezifiziert die Argumente des jeweiligen Prozesses, in diesem Fall sind das die Prozessnummer, die gemeinsame Variable und der Lock. In Zeile 26 werden alle Prozesse gestartet. Ein Aufruf der Methode join lässt das aufrufende Programm (hier: das Hauptprogramm) solange warten, bis der jeweilige Prozess beendet ist. Die print -Anweisung in Zeile 28 wird also erst dann ausgeführt, wenn alle P Prozesse beendet sind.

Die Abfrage if __name__ == '__main__' in Zeile 21 stellt sicher, dass dieses Skript nicht wieder rekursiv von allen gestarteten Prozessen ausgeführt wird (was zur Folge hätte, dass jeder der P gestarteten Prozesse wiederum P Prozesse startet, usw.). Lediglich im Hauptprogramm gilt, dass __name__ den Wert '__main__' ) hat, und lediglich im Hauptprogramm werden daher neue Prozesse gestartet.

Aufgabe 7.8

Vergleichen Sie die Laufzeiten der Implementierung aus Listing 7.7 mit der Laufzeit der Implementierung aus Listing 7.8 auf einem Mehrkern-Rechner.

Aufgabe 7.9

Wir betrachten folgende Fragestellung aus der Stochastik: „Gegeben seien n Kinder an die zufällig k Gummibärchen verteilt werden. Wie groß ist die Wahrscheinlicheit, dass dabei (mindestens) ein Kind leer ausgeht?“

(a)Implementieren Sie einen seriellen Algorithmus, der dieses Zufallsexperiment M -mal durchführt.

(b)Geben Sie mit Hilfe von Pythons multiprocessing -Modul eine parallele Implementierung an, die P parallel arbeitende Prozesse verwendet, um das Zufallsexperiment M -mal durchzuführen.

Die Parameter n , k , M und P sollen dabei jeweils als Kommandozeilenparameter übergeben werden.

7.5.2Das mpi4py-Modul

Das Python-Modul mpi4py stellt eine Schnittstelle zu der frei verfügbaren Open-Source-Implementierung MPICH[2] des Message-Passing-Standards MPI-2 dar. Zur Installation des mpi4py -Moduls, das nicht in der Standard-Installation von Python enthalten ist, verfahren Sie wie folgt:

Zusätzlich müssen sie die MPI-Laufzeitumgebung installieren. Unter Windows bietet sich hierfür die MSMPI-Implementierung an, die sich auf den Download-Seiten von Microsoft befindet. Unter Linux gibt es mehrere Alternativen, beispielsweise OpenMPI. Der Pythoncode muss dann innerhalb der Laufzeitumgebung mittels des installierten mpiexe -Kommandos von der Shell aus gestartet werden.

Beispiel 1: Paralleles Summieren

Betrachten wir als erstes Beispiel einen Algorithmus, der sich offensichtlich in parallel arbeitende Teilaufgaben zerlegen lässt, das Aufsummierung der ersten n natürlichen Zahlen 49 :

Aufgrund der Assoziativität der Summation, kann diese Berechnung auf zwei parallel arbeitende Prozesse verteilt werden:

Das in Listing 7.9 gezeigte Python-Skript parSum implementiert diese Parallelität mit Hilfe von Message-Passing. Dieses Skript sollte deshalb auch von einer Shell aus mittels

gestartet werden. Das Kommando mpiexec bewirkt, dass das Kommando python parSum.py in der durch MPICH bereitgestellten Message-Passing-Umgebung ausgeführt wird. Die Option -n 3 bewirkt, dass drei Prozesse gestartet werden. Jeder dieser drei Prozesse führt das Skript parSum.py gleichzeitig aus. Anders als beim Multithreading besitzen diese drei Prozesse keine gemeinsamen Variablen. Die in den Zeilen 8 und 11 gesetzte Variable s beispielsweise ist keine gemeinsame Variable von Prozess 0 und Prozess 1 , sondern beide Prozesse arbeiten auf jeweils unterschiedlichen Kopien.

Listing 7.9. Das Skript parSum.py : Paralleles Aufsummieren implementiert mittels Message-Passing.

Die in Zeile 3 verwendete Variable MPI.COMM_WORLD stellt einen Kommunikations-Handler bereit (ein Objekt der Klasse Intracomm ), über den Nachrichten unter anderem mittels der Methoden send und recv zwischen den einzelnen Prozessen ausgetauscht werden können. Mittels der Methode Get_rank () in Zeile 4 erkundigt sich der jeweilige Prozess nach der Nummer, die er von dem Message-Passing-System zugewiesen bekam. Die Fallunterscheidungen ab Zeile 7 stellen sicher, dass Prozess0 die Anweisungen in den Zeilen 8 und 9, Prozess1 die Anweisungen in den Zeilen 11 und 12 und Prozess2 die Anweisungen in den Zeilen 14 und 15 ausführt.Wohlgemerkt laufen diese drei Anweisungsblöcke in verschiedenen Prozessen nebenläufig zueinander und – vorausgesetzt, der Rechner unterstützt Parallelität, wie dies etwa bei Mehrkernprozessoren der Fall ist – größtenteils tatsächlich parallel. Die recv -Anweisungen in Zeile 14 im Code für Prozess 2 lässt Prozess 2 solange warten, bis eine Nachricht von Prozess 1 eingetroffen ist. Diese wird dann in Variable s1 gespeichert. Anschließend wartet die recv -Anweisung in Zeile 15 bis eine Nachricht von Prozess 0 eingetroffen ist und, speichert dessen Nachricht in s0 . Schließlich werden in Zeile 16 die beiden Teilsummen von Prozess 2 addiert und ausgegeben.

Abbildung 7.10 veranschaulicht den Ablauf des Skripts parSum.py in drei parellelen Prozessen. Die send-receive- Aktionen des Message-Passing-Interfaces sind hierbei durch waagerechte Pfeile dargestellt.

Aufgabe 7.10

Implementieren Sie die gleiche Aufgabe, nämlich die Summation der Zahlen bis n, nur dass sie jetzt statt zwei Prozessorkernen vier Prozessorkerne verwenden.

Aufgabe 7.11

Implementieren Sie die gleiche, wie durch das Skript in Listing 7.9 realisierte Funktionalität ...

(a)...unter Verwendung des multiprocessing -Moduls.

(b)...unter Verwendung von Threads mittels des threading -Moduls.

Abb. 7.10. Funktionsweise der in Listing 7.9 gezeigten Implementierung des parallelen Aufsummierens mittels Message-Passing.

Vergleichen Sie jeweils die Laufzeiten dieser Implementierungen mit der Laufzeit des Skripts aus Listing 7.9 und erklären Sie ihre Beobachtungen.

Beispiel 2: Eine Pipeline zur Berechnung von Primzahlen.

Eine bewährte Technik, einen bestimmten Fertigungs- oder Berechnungs-Prozess zu beschleunigen, besteht in der Organisation einer Fließbandverarbeitung, in der Informatik auch oft mit dem englischen Begriff Pipelining bezeichnet. Bei der Fließbandverarbeitung unterteilt man einen Fertigungs- oder Berechnungsprozess in einige möglichst gleich lange bzw. gleich aufwändige Schritte, die in diesem Zusammenhang oft als Pipelinestufen bezeichnet werden. Ein in der Literatur [6, 8] häufig verwendetes Beispiel aus dem Alltagsleben, zur Veranschaulichung der Funktionsweise des Pipelining, ist das Wäschewaschen. Man kann den Prozess des Wäschewaschens unterteilen in die Pipelinestufen „Waschen“, „Trocknen“, „Bügeln“ und „Einräumen“. Abbildung 7.11 zeigt das Wäschewaschen einmal ohne Pipelining und einmal mit Pipelining, bei dem die Pipelinestufen verzahnt ausgeführt werden. Es gibt einige Situationen, in denen eine Berechnung über Pipelining nicht möglich ist bzw. sich nicht lohnt: 1. Wenn verschiedene Pipelinestufen auf die gleiche Ressource (etwa den Hauptspeicher) zugreifen wollen. 2. Wenn eine nachfolgende Berechnung vom Ergebnis der vorherigen Berechnung abhängt. 3. Wenn die Reihenfolge der Berechnungen statisch nicht klar ist (etwa bei dynamischen Sprüngen).

Abb. 7.11. Wäschewaschen ohne Pipelining (oben) und Wäschewaschen mit Pipelining (unten).

Aufgabe 7.12

Angenommen, wir haben einen Berechnung, die in fünf Pipelinestufen unterteilt werden kann. Die Berechnung soll zehn Mal hintereinander ausgeführt werden. Wie groß ist der Zeitgewinn der Ausführung mit Pipelining gegenüber der Ausführung ohne Pipelining, wenn ...

(a)...alle Pipelinestufen gleich lang sind.

(b)...eine Pipelinestufe nur halb so lange ist wie alle anderen.

(c)...eine Pipelinestufe doppelt so lange ist wie alle anderen.

(d)...eine Pipelinestufe viermal so lange ist wie alle anderen.

Als Beispiel für die Realisierung einer Pipeline mittels Message-Passing implementieren wir einen Algorithmus zur Berechnung der Anzahl von Primzahlen kleiner als N. Zur Bestimmung der Primzahlen gehen wir ähnlich vor wir das berühmte Sieb des Erathostenes: Man erhält die Liste aller Primzahlen, indem zunächst alle Vielfachen von 2 aussortiert werden, danach alle Vielfachen der nächsten Zahl, die übrigbleibt (nämlich 3), usw. Die Implementierung in Listing 7.10 unterteilt diese Berechung in drei Pipelinestufen, aufgeteilt auf die drei Prozesse P 0 , P 1 und P 2 . Prozess P 0 sortiert alle Vielfachen von 3 (und 2) aus, Prozess P 1 sortiert alle Vielfachen von 5 aus und Prozess P 2 kümmert sich um die restlichen Vielfachen.

Listing 7.10. Implementierung einer Pipeline zum Berechnung von Primzahlen. Die einzelnen Pipelinestufen, realisiert durch die drei Prozesse P 0 , P 1 und P 2 , filtern sukzessive Zahlen aus, die durch 3, 5, 7 usw. teilbar sind.

Betrachten wir den Code für die jeweiligen Prozesse getrennt:

–Prozess P 0 : Der Code für P 0 befindet sich in den Zeilen 7 bis 9. Die for -Schleife durchläuft alle ungeraden Zahlen von 3 bis N . Jede Zahl i, die nicht durch 3 teilbar ist, wird mittels comm. send ( i,dest=1 ) an P 1 gesendet. Nach Beendigung der for -Schleife sendet P 0 das END_MSG-Signal an P 1 und signalisiert so, das Ende der Übertragungen.

–Prozess P 1 : Der Code für P 1 befindet sich in den Zeilen 11 bis 16. In jedem while -Schleifendurchlauf wird eine von P 0 kommende Zahl empfangen und genau dann an P 2 weitergeschickt, wenn diese Zahl nicht durch 5 teilbar ist (Zeile 16). Empfängt P 1 das END_MSG -Signal von P 0 , leitet er dieses Signal an P 2 weiter, beendet die Schleife und stoppt.

–Prozess P 2 : Der Code für P 2 befindet sich in den Zeilen 18 bis 27. In jedem äußeren while -Schleifendurchlauf empfängt P 2 eine Zahl von P 1 und testet diese im inneren while -Schleifendurchlauf darauf, ob diese weitere Teiler (größer als 7) besitzt. Falls nein, handelt es sich um eine Primzahl, und die Zahl wird ausgegeben.

Abbildung 7.12 veranschaulicht das Zusammenspiel der drei Prozesse in einer Pipeline. Optimalerweise könnte solch eine Pipeline einen Geschwindigkeitszuwachs um (nahezu) den Faktor drei ergeben, wenn 1. die drei Prozesse keine gemeinsamen Ressourcen wie etwa den Hauptspeicher ansprechen würden, und 2. die Laufzeiten der Sende- und Empfangsoperationen vernachlässigbar wären (was jedoch i. A. nicht realistisch ist) und 3. die (Rechen-)Arbeit über die drei Pipelinestufen gleichmäßig verteilt wäre (was in diesem Beispiel jedoch nicht der Fall ist). Man spricht in diesem Zusammenhang auch von der sogenannten Load Balance , und meint damit eben die möglichst gleichmäßige Verteilung der Rechenarbeit.

Abb. 7.12. Funktionsweise der in Listing 7.9 gezeigten Implementierung von Pipelining.

Aufgabe 7.13

Welche der Pipelinestufen der Pipeline zur Berechnung von Primzahlen hat i. A. mehr Rechenarbeit zu leisten, welche weniger Rechenarbeit?

Aufgabe 7.14

Implementieren Sie den obigen Algorithmus mit Hilfe von Pythons multiprocessing-Modul.

Sowohl die Werkzeuge des multiprocessing -Moduls als auch die Werkzeuge des mpi4py- Moduls lassen dem Programmierer die Verantwortung, sich um die Synchronisation der Prozesse zu kümmern.