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

Der Vorschlag bezüglich des Knapsack-Problems ist zwar hilfreich, aber Sie sagten, dass Sie versuchen, die Nettoausführungszeit zu minimieren. Mit dem Knapsack-Ansatz müssten Sie die Größe Ihres Knapsacks so lange erhöhen, bis Sie eine machbare Lösung erhalten - nicht sehr effizient.

Wenn die Nettoausführungszeit durch die längste Fertigstellungszeit aller parallel arbeitenden Threads begrenzt ist, möchte ich die Aufgaben so zuweisen, dass ich die MAXIMALE Arbeitszeit aller Threads MINIMIEREN kann. Dies kann dazu führen, dass ein oder mehrere Threads nicht viel Arbeit leisten, so dass die Arbeit nicht wirklich "ausgeglichen" ist. Wenn Sie die Arbeit ausbalancieren wollen, dann ist das eine andere Zielfunktion. Sie könnten zum Beispiel die Varianz der Arbeit zwischen den Threads minimieren wollen.

Schauen Sie in den Bereich der Arbeitsvorbereitung. Wenn Sie dies nur selten tun, würde ich einen genetischen Algorithmus vorschlagen - wenn Sie dies häufig und in einer stärker automatisierten Weise tun müssen, würde ich vorschlagen, eine kleine Literaturrecherche nach deterministischen Algorithmen durchzuführen. Ich hoffe, das hilft Ihnen.