Verteilte topologische Sortieralgorithmus

Question

In meinem aktuellen Projekt habe ich eine große Menge an Daten verarbeitet werden. Die Reihenfolge der Verarbeitung ist wichtig, da in den Daten eine Kind/Eltern-Abhängigkeit besteht. An diesem Punkt baue ich das Abhängigkeitsdiagramm auf einem Rechner und verteile die Arbeit auf mehreren Maschinen, aber ich erreiche Speichergrenze/Verarbeitungslimit auf dem "Master" -Maschine und möchte den gesamten Prozess auf mehreren Maschinen verteilen.

Wie kann ich dieses Abhängigkeitsdiagramm auf mehreren Computern erstellen?

Answer 1

Da die Pfade sehr kurz sind, fügt der klassische Algorithmus, der alle Scheitelpunkte des Out-Grads 0 findet, diese zu der bisherigen Reihenfolge hinzu und löscht sie gut parallel (z. B. MapReduce).

1. Die Jobabhängigkeitsgrafik unter den beteiligten Maschinen partitionieren. Jede Maschine erhält eine disjunkte Untermenge von Jobs und alle Abhängigkeiten, die diese Jobs betreffen.

2. (in Runden wiederholt) Jede Maschine bestimmt, welche ihrer Jobs keine ungeplanten Abhängigkeiten haben. Diese Jobs werden zu einer Zeit geplant, die der aktuellen Rundennummer entspricht. Für jeden Job mit einem der neu geplanten Jobs als Abhängigkeit meldet der Computer, dem der neu geplante Job gehört, diese Tatsache dem Computer, der den abhängigen Job besitzt.

Der gesamte Netzwerkverkehr ist in der Größenordnung von der Größe des Graphen, und die Anzahl der Runden wird durch die Länge des längsten Weges begrenzt, so dass dieser Algorithmus sollte für Ihren Anwendungsfall einigermaßen effizient sein.