Abhängigkeitsgraph

Ein Abhängigkeitsgraph beschreibt, welche Tasks, Prozesse oder Berechnungsschritte vor anderen abgeschlossen sein müssen.

Bestandteile

• Knoten: Tasks, Prozesse oder Funktionen
• gerichtete Kanten: Abhängigkeiten

Eine Kante

A -> B

bedeutet:
B darf erst starten, wenn A beendet ist.

Verwendung

Abhängigkeitsgraphen helfen dabei, Programme zu parallelisieren.

Tasks ohne direkte oder indirekte Abhängigkeit voneinander können parallel ausgeführt werden.

Beispiel

A -> B
A -> C
B -> D
C -> D

Dann gilt:

• A muss zuerst laufen.
• B und C können danach parallel laufen.
• D darf erst laufen, wenn B und C fertig sind.

Zusammenhang mit Parallelisierung

• Mit fork/join können Abhängigkeiten flexibel umgesetzt werden.
• Mit parbegin/parend können zusätzliche künstliche Abhängigkeiten entstehen, weil parend auf alle Zweige wartet.

Links

• Parallelität
• Nebenläufigkeit
• Fork, Join, Wait
• parbegin und parend
• blatt1.pdf