Ich arbeite an einem Multi-Thread-Programm, wo ich eine Anzahl von Worker-Threads habe, die Aufgaben ungleicher Länge ausführen. Ich möchte die Aufgaben so verteilen, dass sie ungefähr die gleiche Menge an Arbeit erledigen. Für jede Aufgabe T i habe ich eine Zahl c i, die eine gute Annäherung an den Arbeitsaufwand liefert, der für diese Aufgabe erforderlich ist.
Ich suche nach einem effizienten (O (N) N = Anzahl der Aufgaben oder besser) Algorithmus, der mir "grob" eine gute Lastverteilung geben wird angesichts der Werte von c i. Es muss nicht optimal sein, aber ich möchte in der Lage sein, einige theoretische Grenzen zu haben, wie schlecht die resultierenden Zuweisungen sind.
Irgendwelche Ideen?
Sie möchten einen Arbeitstealgorithmus implementieren. Jeder Worker-Thread hat eine doppelendige Warteschlange, neue Aufgaben werden am Ende der kleinsten Warteschlange hinzugefügt. Arbeiter entfernen Aufgaben vom Anfang ihrer eigenen Warteschlange (die Trennung von oben und unten reduziert die Konkurrenz). Wenn ein Mitarbeiter keine weiteren Aufgaben zu erledigen hat, stiehlt er einen Job vom unteren Ende der größten Warteschlange. Es ist einfach und funktioniert gut, das ist der Algorithmus, auf dem das Microsoft Parallelsystem mit .net4.0 basiert, glaube ich.
Die resultierende Zuweisung ist ziemlich gut, Worker-Threads bleiben nur übrig, wenn keine Jobs mehr im gesamten System verfügbar sind.
Nb. Wenn du willst, dass ein Beispielcode auseinander reißt, hat mein Freund ein Arbeitsstehlingsystem für C # geschrieben, das du hier finden kannst
Ich möchte nicht im Voraus herausfinden, wie die Aufgaben zugewiesen werden, sondern alle in eine gemeinsame Arbeitswarteschlange werfen. Jeder Worker-Thread, der nichts anderes zu tun hat, ergreift die nächste Aufgabe aus der Warteschlange und überprüft die Warteschlange auf die nächste Aufgabe.
Der einfachste Weg besteht darin, Jobs nach p_i zu sortieren (aber das ist O (n log n)) und dies zu tun:
Dieser Algorithmus sollte die besten Ergebnisse liefern, aber mit O (N M) Zeit, wobei N die Anzahl der Aufgaben und M die Anzahl der Threads ist. Gesamtkosten der Lösung sind 0 (N log N + N M), so dass für M & lt; & lt; N ist O (N log N) und für M nahe N ist O (n ^ 2).
In O (N) scheint das einfach.
Gib jedem Thread einige "Punkte". Lassen Sie p_i die dem Thread T_i zugewiesenen Punkte. Wählen Sie für jede Aufgabe den Thread mit der höchsten p_i und subtrahieren Sie die Aufgabenkosten von p_i . Sie müssen dann nur die nach dem Punktestand geordneten Threads verfolgen, was in O (N) -Zeit trivial ist, und kann leicht in O (log N) mit einem ausgeglichenen Baum durchgeführt werden.
Für den Dauerbetrieb gibt es kein Minimum in p_i . Wenn Sie verhindern möchten, dass Scores in Richtung -inf ablaufen, fügen Sie regelmäßig einen beliebigen Betrag P zu allen Scores hinzu (der gleiche Betrag für alle Scores).
Bearbeiten: Ich habe das falsche N bekommen. Oben, N ist die Anzahl der Threads, entgegen der gestellten Frage. Mit N = Anzahl der Aufgaben und T = Anzahl der Threads führt dies zu O (N * log T) -Kosten. Wenn T "klein" ist, ist dies nahe bei O (N).
Edit 2: Wenn alle Aufgaben im Voraus bekannt sind, sowie die Anzahl der Threads, dann denke ich, dass die Berechnung der optimalen Planung ähnlich wie bei Knacksack Problem und es ist, in aller Allgemeinheit, NP-vollständig (so werden Sie irgendwo exponentials bekommen). Eine einfache, auf Kosten basierende Analyse, wie ich sie oben beschrieben habe, wird Ihnen eine relativ gute Annäherung geben, solange alle einzelnen Aufgaben geringe Kosten in Bezug auf die Gesamtkosten haben, die jedem Thread zugewiesen werden müssen.
Während der Vorschlag bezüglich des Rucksackproblems hilfreich ist, haben Sie gesagt, dass Sie versuchen, die Nettozeit der Ausführung zu minimieren. Wenn Sie den Rucksackansatz verwenden, müssen Sie die Größe Ihres Rucksacks so lange erhöhen, bis Sie eine praktikable Lösung erhalten - nicht sehr effizient.
Wenn die Nettozeit der Ausführung durch die längste Bearbeitungszeit unter allen parallel arbeitenden Threads begrenzt ist, möchte ich Aufgaben zuweisen, so dass ich die MAXIMALE Arbeitszeit über alle Threads MINIMIEREN kann. Dies kann dazu führen, dass ein oder mehrere Threads nicht viel Arbeit leisten, sodass wir die Arbeit nicht wirklich "ausbalancieren". Wenn Sie die Arbeit ausbalancieren wollen, dann ist das eine andere Zielfunktion. Zum Beispiel möchten Sie vielleicht die Varianz in der Arbeit zwischen Threads minimieren.
Schauen Sie in den Bereich der Job-Shop-Planung. Wenn Sie das nur selten tun, würde ich vorschlagen, einen genetischen Algorithmus zu verwenden - wenn Sie es häufiger und auf eine mehr automatisierte Weise tun müssen, würde ich vorschlagen, ein wenig Literatursuche nach deterministischen Algorithmen durchzuführen. Hoffe das hilft.
Tags und Links algorithm load-balancing scheduling heuristics