Parallelisierbarkeit

Nebenläufigkeit liegt vor, wenn mehrere Ereignisse in keiner kausalen Beziehung zueinander stehen, sich also nicht beeinflussen. Ereignisse sind nebenläufig, wenn keines eine Ursache des anderen ist. Oder anders ausgedrückt: Aktionen können nebenläufig ausgeführt werden (sie sind parallelisierbar), wenn keine das Resultat der anderen benötigt. Eine Modellierungssprache, die diese Abhängigkeiten sehr gut wiedergibt, sind Petri-Netze.

Kausalordnung

Beispiel von nebenläufigen Aktionen

Die Nebenläufigkeit beschreibt einen relativistischen Begriff der Gleichzeitigkeit, der im Kausalitätsprinzip begründet ist (siehe Relativität der Gleichzeitigkeit und Happened-Before). Man kann sich das anhand eines Minkowski-Diagramms verdeutlichen: Ein Ereignis ist nebenläufig zu einem anderen, wenn es im Anderswo des anderen Ereignisses liegt. Das heißt, das eine Ereignis befindet sich weder in der Zukunft, noch in der Vergangenheit des anderen bzw. keines der Ereignisse ist Ursache oder Wirkung des anderen. Die drei Relationen "ist Ursache von", "ist Wirkung von" und "ist nebenläufig zu" definiert die Kausalordnung, eine Halbordnung, die zu einer Sequenzialisierung der Ereignisse benutzt werden kann.

Dies macht man sich zum Beispiel in der Netzwerktechnik zu Nutze, da hier die Kausalordnung nur durch die Übermittlung von Nachrichten definiert ist: zur Sequenzialisierung von verteilten Prozessen werden hier Logische Uhren eingesetzt, die den relativistischen Zeitbegriff spiegeln.

Planung

Beispiel zur kausalen Abhängigkeit

Man kann das Konzept der Nebenläufigkeit nicht nur auf die Betrachtung von Ereignissen anwenden, sondern auch zur Planung von Aktionen. Dabei wird festgelegt, welche Aktion eine Voraussetzung einer anderen ist. Die Nebenläufigkeit ist dann so definiert, dass zwei Aktionen nebenläufig sind, wenn keine von ihnen Voraussetzung der anderen ist. Auf Grund der sich daraus ergebenden Halbordnung lassen sich dann Abläufe planen, optimieren und gegebenenfalls parallelisieren. Als Beispiel (nicht das gleiche wie in der Abbildung!) hier ein kleines Programm in Pseudocode (mit Zeilennummern):

Z1 a= 2; Z2 b= 3; Z3 p= a + b; Z4 q= a * b; Z5 r= q - p;

Die (kausalen) Abhängigkeiten ergeben sich dadurch, welches Kommando das Ergebnis eines anderen benötigt. Insbesondere sind die folgenden Zeilenpaare (potenziell) nebenläufig, weil nicht eine von dem Ergebnis der anderen abhängt: Z1 || Z2 und Z3 || Z4. Auf einem Massiv-Parallelen Computer könnten diese Befehle jeweils parallel ausgeführt werden. Einige moderne CPUs sind sogar in der Lage, solche Situationen zu erkennen und einzelne Befehle gleichzeitig in verschiedenen Teilen desselben Prozessors auszuführen (siehe Pipeline).

Siehe auch

• Asynchrone Kommunikation
• Multithreading
• Parallele Programmierung
• Paralleler Algorithmus
• Petri-Netz
• Philosophenproblem
• Race Condition
• Specification and Description Language
• Synchrone Kommunikation

Literatur

• Peter Ziesche: Nebenläufige & verteilte Programmierung. W3L, 2004, ISBN 3937137041
• Douglas Schmidt, Michael Stal, Hans Rohnert, Frank Buschmann: Pattern-orientierte Softwarearchitektur, Muster für nebenläufige und vernetzte Objekte. dpunkt 2002, ISBN 3-89864-142-2