Heuristischer Algorithmus für den Lastausgleich zwischen Threads

Question

Ich arbeite an einem Multi-Thread-Programm, bei dem ich eine Reihe von Worker-Threads habe, die Aufgaben von ungleicher Länge ausführen. Ich möchte einen Lastausgleich zwischen den Aufgaben herstellen, um sicherzustellen, dass sie ungefähr die gleiche Menge an Arbeit verrichten. Für jede Aufgabe T _i Ich habe eine Anzahl c _i was einen guten Näherungswert für den Arbeitsaufwand darstellt, der für diese Aufgabe erforderlich ist.

Ich bin auf der Suche nach einem effizienten (O(N) N = Anzahl der Aufgaben oder besser) Algorithmus, der mir "ungefähr" einen guten Lastausgleich liefert, wenn die Werte von c _i . Es muss nicht optimal sein, aber ich würde gerne einige theoretische Grenzen dafür haben, wie schlecht die resultierenden Zuweisungen sind.

Irgendwelche Ideen?

Answer 1

Sie möchten eine Algorithmus zum Stehlen von Arbeit . Jeder Worker-Thread hat eine doppelendige Warteschlange, neue Aufgaben werden am Ende der kleinsten Warteschlange hinzugefügt. Die Arbeiter entfernen Aufgaben vom oberen Ende ihrer eigenen Warteschlange (die Trennung von oben und unten verringert die Konkurrenzsituation), und wenn ein Arbeiter keine Aufgaben mehr zu erledigen hat, stiehlt er eine Aufgabe vom unteren Ende der größten Warteschlange. Dies ist der Algorithmus, auf dem das parallele System von Microsoft, das mit .net4.0 kommt, basiert, glaube ich.

Die daraus resultierende Zuteilung ist ziemlich gut, da die Worker-Threads nur dann keine Arbeit mehr haben, wenn im gesamten System keine Aufträge mehr verfügbar sind.

Nb. Wenn Sie einen Beispielcode zum Zerlegen suchen, hat mein Freund ein System zum Stehlen von Arbeit für C# geschrieben, das Sie hier finden können aquí

Answer 2

Ich neige dazu, nicht zu versuchen, im Voraus herauszufinden, wie die Aufgaben zuzuordnen sind, sondern sie alle in einen gemeinsamen Arbeitsvorrat zu werfen. Jeder Worker-Thread, der nichts anderes zu tun hat, holt sich die nächste Aufgabe aus der Warteschlange, erledigt die Arbeit und überprüft die Warteschlange auf die nächste Aufgabe.

Answer 3

Am einfachsten ist es, die Aufträge absteigend nach p_i zu sortieren (aber das ist O(n log n)) und dies zu tun:

1. Für jeden Thread haben wir die geschätzte Laufzeit e_n = 0.
2. Für jede Aufgabe i wird der Thread gefunden, der minimal e_n Aufgaben hat, und e_n = e_n + p_i.

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. Die Gesamtkosten der Lösung sind O(N log N + N M), also für M << N ist O(N log N) und für M nahe N ist O(n^2).

Answer 4

In O(N) scheint dies einfach zu sein.

Geben Sie jedem Thema einige "Punkte". Lassen Sie p_i die dem Thread zugewiesenen Punkte T_i . 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 noch die Threads nach Punkten geordnet verfolgen, was in O(N)-Zeit trivial ist und mit einem ausgeglichenen Baum leicht in O(log N) erledigt werden kann.

Für den Dauerbetrieb gibt es kein Minimum an p_i . Wenn Sie vermeiden wollen, dass die Punktzahl in Richtung -inf abweicht, fügen Sie einfach regelmäßig einen beliebigen Betrag P auf alle Punkte (der gleiche Betrag für alle Punkte).

編集する： Ich habe das falsche N. Oben steht N für die Anzahl der Threads, im Gegensatz zur 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 an O(N).

Bearbeiten 2: Wenn alle Aufgaben im Voraus bekannt sind, ebenso wie die Anzahl der Threads, dann denke ich, dass die Berechnung der optimalen Zeitplanung mit der Knapsack-Problem und es ist in aller Allgemeinheit NP-komplett (man wird also irgendwo Exponentiale bekommen). Eine einfache kostenbasierte Analyse, wie ich sie oben beschrieben habe, liefert eine relativ gute Annäherung, solange alle einzelnen Aufgaben im Verhältnis zu den Gesamtkosten, die jedem Thread zugewiesen werden müssen, geringe Kosten verursachen.

Answer 5

Ich würde mir Algorithmen für den Lastausgleich ansehen, z. B.

http://www.ieee802.org/3/trunk_study/february98/congdon.pdf

http://publib.boulder.ibm.com/infocenter/cicstg/v6r0m0/index.jsp?topic=/com.ibm.cicstg600.doc/ccllal0292.htm