Wann sollte DAG (Directed Acyclic Graph) für die Programmierung verwendet werden?

37

Ich habe kürzlich ein Framework namens ecto gefunden .

In diesem Framework gibt es eine Basiskomponente namens "plasm" , die ecto Directed Acyclic Graph ist. In ecto kann das Plasma von ecto scheduler bedient werden.

Ich frage mich, was der Vorteil dieses Mechanismus ist und in welchen anderen Situationen können wir das Konzept der DAG nutzen?

Po-Jen Lai
quelle
6
Die meisten Versionsverwaltungssysteme implementieren die Überarbeitungen als DAG.
Oded
1
Planung ist ein ganzer Zweig von Problemen, die sich viel mit der DAG befassen .
TC1
1
Viele Dinge, die als Bäume dargestellt werden, sollten wirklich als DAGs dargestellt werden, wenn man die seltsamen, aber immer noch etwas häufigen Randfälle berücksichtigt.
Joachim Sauer
@JoachimSauer zB Dateisysteme mit Hardlinks
jk.

Antworten:

29

Gute Frage.

  • Code kann durch eine DAG dargestellt werden, die die Eingaben und Ausgaben jeder der im Code ausgeführten arithmetischen Operationen beschreibt; Diese Darstellung ermöglicht es dem Compiler, die Eliminierung gemeinsamer Unterausdrücke effizient durchzuführen.
  • Die meisten Versionsverwaltungssysteme implementieren die Überarbeitungen als DAG.
  • Mehrere Programmiersprachen beschreiben Wertesysteme, die durch einen gerichteten azyklischen Graphen miteinander verbunden sind. Wenn sich ein Wert ändert, werden seine Nachfolger neu berechnet. Jeder Wert wird in Abhängigkeit von seinen Vorgängern in der DAG ausgewertet.
  • DAG ist hilfreich beim Erkennen von Deadlocks, da sie die Abhängigkeiten zwischen einer Reihe von Prozessen und Ressourcen veranschaulichen.
  • In vielen randomisierten Algorithmen in der Berechnungsgeometrie verwaltet der Algorithmus eine Verlaufs-DAG, die Merkmale einer geometrischen Konstruktion darstellt, die durch spätere Merkmale mit feinerem Maßstab ersetzt wurden. Punktlokalisierungsabfragen können wie für die obigen zwei Datenstrukturen durch Verfolgen von Pfaden in dieser DAG beantwortet werden.
  • Sobald wir die DAG im Speicher haben, können wir Algorithmen schreiben, um die maximale Ausführungszeit des gesamten Satzes zu berechnen.
  • Beim Programmieren von Tabellenkalkulationssystemen muss der Abhängigkeitsgraph, der eine Zelle mit einer anderen verbindet, wenn in der ersten Zelle eine Formel gespeichert ist, die den Wert in der zweiten Zelle verwendet, ein gerichteter azyklischer Graph sein. Zyklen von Abhängigkeiten sind nicht zulässig, da sie dazu führen, dass die am Zyklus beteiligten Zellen keinen genau definierten Wert haben. Wenn die Abhängigkeiten azyklisch sein müssen, kann außerdem eine topologische Reihenfolge verwendet werden, um die Neuberechnungen von Zellenwerten zu planen, wenn das Arbeitsblatt geändert wird.
  • Mit DAG können wir Algorithmen schreiben, um die Berechnungen in der richtigen Reihenfolge auszuwerten.

EDIT:

  • Die Reihenfolge der Formelzellenauswertung bei der Neuberechnung von Formelwerten in Tabellenkalkulationen kann mithilfe von DAGs erfolgen
  • Git verwendet DAGs für die Inhaltsspeicherung, Referenzzeiger für Köpfe, Objektmodelldarstellung und Remote-Protokoll.
  • DAGs werden beim Trace-Scheduling verwendet: Der erste praktische Ansatz für das globale Scheduling, das Trace-Scheduling, versucht, den am häufigsten ausgeführten Kontrollflusspfad zu optimieren.
  • Ecto ist ein Verarbeitungsframework und verwendet DAG, um Verarbeitungsdiagramme so zu modellieren, dass die Diagramme eine geordnete synchrone Ausführung ausführen. Plasm in Ecto ist die DAG und Scheduler arbeitet darauf.
  • DAGs werden beim Software-Pipelining verwendet, bei dem es sich um eine Technik handelt, mit der Schleifen auf eine Weise optimiert werden, die mit dem Hardware-Pipelining vergleichbar ist.

Gute Ressourcen:

Md Mahbubur Rahman
quelle
1
Keine Schleifen? Ich würde denken, dass es sich qualifizieren sollte, solange eine Schleife endet. Anstatt A -> B -> C zu sein, könnte es A -> B -> A1 -> B1 -> A2 -> B2 -> C sein. Zyklisch in einem Sinne, aber nicht in einem anderen. Eher eine Spirale als ein Kreis.
GlenPeterson
@ GlenPeterson, ja du hast recht. Ich habe meine Antwort bearbeitet. Danke für den Kommentar. :)
Md Mahbubur Rahman
Denken Sie immer noch nicht, dass "Straight Line" notwendig ist. Das 'G' in DAG steht für Graph. Schau dir meine Antwort unten an. Es tut mir leid, dass ich Ihre nicht sorgfältig genug gelesen habe, bevor ich geantwortet habe, aber ich habe Ihre Antwort für Ihre Vollständigkeit und Ihr gesamtes Erleuchtungsniveau +1 gegeben.
GlenPeterson
@ GlenPeterson, Entschuldigung für den Fehler. Ich habe meine Antwort aktualisiert. Ich mag auch Ihre Antwort. Also mache +1 auf deine Antwort.
Md Mahbubur Rahman
3
Danke für deine +1. Ich denke immer noch, dass der gesamte Code DAG ist, nicht auf arithmetische Ausdrücke beschränkt. E / A, Ausnahmen, Interaktionen mit mehreren Prozessen und Hardware-Interrupts sind nur andere Start- oder Endknoten in einem gerichteten (weil sie Start- oder Endknoten sind), azyklischen (keine Endlosschleifen) Diagramm (endliche Menge geordneter Knotenpaare). . Eine interessante Antwort auf Rickys Frage könnte sein: "Gibt es einen korrekten und funktionierenden Code, der keine DAG ist?". Ich denke, die Antwort ist "Nein", aber ich würde mich freuen, wenn jemand mir das Gegenteil beweist.
GlenPeterson
12

Die Antwort ist, dass es nicht viel mit Programmierung zu tun hat. Es hat mit Problemlösung zu tun.

Genauso wie verknüpfte Listen Datenstrukturen sind, die für bestimmte Problemklassen verwendet werden, sind Diagramme nützlich, um bestimmte Beziehungen darzustellen. Verknüpfte Listen, Bäume, Diagramme und andere abstrakte Strukturen haben nur insofern eine Verbindung zur Programmierung, als Sie sie in Code implementieren können. Sie existieren auf einer höheren Abstraktionsebene. Es geht nicht um Programmierung, sondern um die Anwendung von Datenstrukturen bei der Lösung von Problemen.

Wenn Sie dennoch eine Beziehung zur Programmierung haben möchten, beachten Sie bitte folgende Punkte:

  • Die DAG (bekannt als Wait-For-Graphs - weitere technische Details ) ist hilfreich beim Erkennen von Deadlocks, da sie die Abhängigkeiten zwischen einer Reihe von Prozessen und Ressourcen veranschaulicht (beide sind Knoten in der DAG). Ein Deadlock würde auftreten, wenn ein Zyklus erkannt wird.
  • Sobald Sie die DAG im Speicher haben, können Sie Algorithmen schreiben, um:
    • Stellen Sie sicher, dass die Berechnungen in der richtigen Reihenfolge ausgewertet werden ( topologische Sortierung )
    • Wenn Berechnungen parallel durchgeführt werden können, aber jede Berechnung eine maximale Ausführungszeit hat, können Sie die maximale Ausführungszeit des gesamten Satzes berechnen
Vaibhav Agarwal
quelle
1
Um noch einmal zu zeigen, dass dies den Rahmen der Programmierung sprengt, müssen Sie überlegen, wie Sie die Tabellen in einer relationalen Datenbank ankreuzen, um die Länge des Pfads von einer Tabelle zur nächsten mental zu analysieren. Dies entspricht der mentalen Verwendung einer DAG zur Bestimmung der Leistung von Ihr Datenmodell
Jimmy Hoffa
6

Andere Leute haben DAG auf Daten angewendet, aber ich denke, es ist mindestens genauso anwendbar (wenn nicht mehr) auf Code. Mahbubur R Aaman erwähnt dies, daher ist dies in Wirklichkeit eher ein Nachtrag zu seiner Antwort als eine vollständige Antwort für sich.

Mir fällt ein, dass jedes zwingende Computerprogramm, das frei von Endlosschleifen ist (danke @AndresF.), Ein gerichteter azyklischer Graph (DAG) ist. Dies bedeutet, dass die möglichen Wege zur Ausführung des Codes gerichtet sind (zuerst dies, dann das) und azyklisch (keine Endlosschleifen bilden). Sie sind ein Diagramm, weil der Pfad durch einen signifikanten Code selten so einfach ist wie eine Liste oder ein Baum.

Ich habe vielleicht 4 Jahre in XSLT gearbeitet. Ich hatte eine schreckliche Zeit, um zu erklären, warum es keine gute Allzweck-Programmiersprache war, aber DAG ist der Grund. Insbesondere ist XSLT eine datengetriebene Sprache. Sie definieren Funktionen (ja im Sinne der funktionalen Programmierung), rufen diese Funktionen jedoch nicht unbedingt aus Ihrem Code auf. Vielmehr richtet XSLT eine Kombination aus Auswahl und Iteration der Knoten eines XML-Eingabedokuments ein. Dadurch kann die Struktur der Eingabedaten bestimmen, welche Funktionen in welcher Reihenfolge aufgerufen werden.

Dies war sehr interessant und sehr cool, bis Ihr Programm auf eine Datenbedingung stieß, auf die Sie nicht um 02:30 Uhr testeten und die Sie aufwachen und beheben mussten. Wenn Sie die Daten die DAG definieren lassen, werden aus der Definition der DAG alle möglichen Eingabebedingungen - die für jede nicht triviale Geschäftsanwendung unkalkulierbar sind. sie sind unvorstellbar.

Zuerst dachte ich, dass funktionale Programmierung möglicherweise keine DAG ist, da die Ausführungsreihenfolge manchmal für den Programmierer nicht klar ist oder sogar nicht klar ist. Ein Funktionsprogramm definiert jedoch Abhängigkeiten. Tatsächlich könnte die deklarative Natur der funktionalen Programmierung so verstanden werden, dass sie nur Abhängigkeiten definiert (a ^ 2 = b ^ 2 + c ^ 2), ohne die Ausführungsreihenfolge anzugeben (es spielt keine Rolle, ob 'b' oder 'c' zuerst quadriert wird , solange beide quadratisch sind, bevor sie addiert werden).

Obwohl die Funktionsprogrammierung die Reihenfolge der Operationen auf einer detaillierten Ebene möglicherweise absichtlich vage beschreibt, sind Abhängigkeiten äußerst klar. Dies sind genau die Funktionen, die es so zugänglich machen, dass es gleichzeitig verwendet werden kann. In jedem Fall gibt es immer noch ein Diagramm mit Pfaden durch den Code, und dieses Diagramm ist weiterhin gerichtet (Abhängigkeiten müssen vor abhängigen Tasks ausgewertet werden), sodass ich denke, dass die DAG auch dort gilt.

Schöne Frage - danke fürs posten!

GlenPeterson
quelle
1
Ist dieses zwingende Programm Ihrer Meinung nach eine DAG while (true) { print("hi"); }? Vielleicht möchten Sie nicht terminierende Programme ausschließen?
Andres F.
5

Derzeit wird die DAG in der Programmierung unterschätzt. Historisch gesehen wurden viele Dinge im Zusammenhang mit der Entwicklung mit Bäumen und Hierarchien gemacht, da es für unser Gehirn praktisch ist, etwas in einer Kiste zu bewegen, um komplexe Dinge einfacher zu verwalten. Aber wenn Sie Ereignisse betrachten und wie sie von anderen Ereignissen und Zuständen abhängen, erhalten Sie DAG, weil alles in unserem Leben und im Programm von irgendetwas in der Vergangenheit abhängen kann, aber nicht in der Zukunft, so dass Sie perfekt "azyklisch" werden. Beziehungen, die für das DAG-Konzept gelten sollen. Obwohl dies in der Entwicklung nur selten explizit verwendet wird, würde es helfen, die Dinge besser zu verstehen, wenn dies berücksichtigt wird

Maksee
quelle
2

Ich frage mich, was der Vorteil von Plasm in Ecto ist ...

Mit der DAG können Sie eine Auflistung von Aufgaben in einer Sequenz mit der Einschränkung modellieren, dass bestimmte Aufgaben vor den anderen erledigt werden müssen. Ecto ist ein Verarbeitungsframework und verwendet DAG, um Verarbeitungsdiagramme so zu modellieren, dass die Diagramme eine geordnete synchrone Ausführung ausführen. Plasm in Ecto ist die DAG und Scheduler arbeitet darauf.

In welchen anderen Situationen können wir das Konzept der DAG nutzen?

  • DAWG ist eine Datenstruktur, die eine Reihe von Zeichenfolgen darstellt und eine Abfrageoperation ermöglicht, mit der geprüft wird, ob eine bestimmte Zeichenfolge proportional zu ihrer Länge zur Zeitmenge gehört.
  • Git verwendet DAGs für die Inhaltsspeicherung, Referenzzeiger für Köpfe, Objektmodelldarstellung und Remote-Protokoll.
theD
quelle
Es ist zwar lange her ... aber ich denke, diese Antwort hilft mir wirklich, den Geist von ECTO zu verstehen. Ich muss darauf hinweisen. Vielen Dank!
Po-Jen Lai
0

In der Praxis ähnelt unsere Software einer IDE, in der der Endbenutzer eine Reihe von Vorgängen definieren kann, die an einem Bild ausgeführt werden sollen (Machine Vision Inspection). Diese Inspektionen können von anderen Inspektionen abhängig oder von diesen abhängig sein. Da dies alles vom Endbenutzer konfigurierbar ist, können wir zur Entwurfszeit keine Optimierungen für die Parallelverarbeitung vornehmen. Durch die Darstellung dieser Inspektionen und Abhängigkeiten als DAG können wir die Parallelität der Gesamtinspektion optimieren, um eine maximale Leistung zur Laufzeit zu erzielen.

Dave Nay
quelle
-1

Nur ein weiteres Beispiel: Die Speicherverwaltungsregeln in Cocoa-Apps sind so festgelegt, dass alle starken Referenzen einen gerichteten azyklischen Graphen bilden, um die Abwesenheit von Lecks zu gewährleisten.

millenomi
quelle
-2

Hinzufügen einer weiteren Antwort, da noch kein Verweis auf Build-Systeme vorhanden ist, makedie DAG verwenden, um Abhängigkeiten für das Erstellen herauszufinden.

Weitere Details hier

dlmeetei
quelle
Habe ich etwas falsches gesagt, warum es abgelehnt wurde
dlmeetei
Sie haben eine ziemlich alte Frage mit einer ziemlich schlechten Antwort beantwortet. Wenn Sie versucht sind, eine Antwort zu schreiben, die lautet "Hinzufügen, weil es niemand anders erwähnt hat ..." und nur einen einzigen Satz enthält, ist dies keine so gute Antwort. Bitte versuchen Sie, die Frage vollständig zu beantworten und zu erklären, wie die Anwendung eine DAG verwendet, wie dieses Design funktioniert und warum dies gegenüber anderen Optionen ausgewählt wurde. Idealerweise sind mehrere Absätze inhaltlich wert.
Ok, lassen Sie es mich später
erläutern
Ok, anstatt zu wiederholen, Nur mit einem Link aktualisiert, der beschreibt, wie es in Tools wiemake
dlmeetei
Links haben die böse Angewohnheit, abgestanden zu werden oder zu versagen. In diesem Fall sind Sie wieder da, wo Sie angefangen haben - eine kurze, einzeilige Antwort, die nicht viel hilft. Können Sie den Inhalt des Links zusammenfassen, damit diese Antwort für sich allein steht? (Behalte den Link, stelle nur sicher, dass die Antwort auch ohne den Link gut ist).
Dan Pichelman