Analyse von Lastausgleichsschemata zur Minimierung der Gesamtausführungszeit

7

Angenommen, eine bestimmte parallele Anwendung verwendet ein Master-Slave-Design, um eine große Anzahl von Workloads zu verarbeiten. Jeder Workload dauert einige Zyklen. Die Anzahl der Zyklen, die eine bestimmte Arbeitslast benötigt, wird durch eine bekannte Zufallsvariable . Angenommen, es gibt solche Workloads und äquivalente Slaves (Verarbeitungsknoten). Natürlich befasst sich eine allgemeinere Version dieser Frage mit dem Fall von Slaves mit unterschiedlichen Fähigkeiten, aber wir ignorieren dies vorerst.Xnm

Der Master kann keine Workloads verarbeiten, aber Workloads auf Slave-Knoten verteilen und den Fortschritt der Slave-Knoten überwachen. Insbesondere kann der Master die folgenden Aktionen ausführen:

  1. Beginnen Sie sofort mit der Verarbeitung von Workloads auf einem beliebigen freien Knoten.k
  2. Erhalten Sie sofort eine Bestätigung über den Abschluss eines zuvor initiierten Stapels von Workloads durch einen Knoten .k
  3. Bestimmen Sie zu jedem Zeitpunkt und sofort den Status aller Knoten (frei oder ausgelastet) sowie die Anzahl der abgeschlossenen Workloads und die Anzahl der verbleibenden Workloads.

Nehmen wir der Einfachheit halber an, dass teilt .kn

Es gibt mindestens zwei Kategorien von Lastausgleichsstrategien zur Minimierung der Gesamtausführungszeit aller Workloads unter Verwendung aller Slaves (zur Verdeutlichung spreche ich von der Makespan- oder Wanduhrzeit, nicht von der Gesamtprozesszeit, die unabhängig von der ist Lastausgleichsstrategie unter Verwendung der in dieser Frage getroffenen vereinfachenden Annahmen): statisch und dynamisch. In einem statischen Schema werden alle Platzierungsentscheidungen zum Zeitpunkt . In einem dynamischen Schema kann der Master Platzierungsentscheidungen anhand von Informationen über den Fortschritt einiger Slaves treffen und so eine bessere Auslastung erzielen (in der Praxis sind mit der dynamischen Planung im Vergleich zur statischen Planung Gemeinkosten verbunden, aber wir ignoriere diese). Nun zu einigen Fragen:t=0

  1. Gibt es eine bessere Möglichkeit, Workloads statisch zu planen, als Stapel von Workloads so gleichmäßig wie möglich auf die Slaves aufzuteilen (der Einfachheit halber können wir auch annehmen, dass teilt , sodass Stapel statisch vollständig gleichmäßig geplant werden können). ? Wenn das so ist, wie?kmmn/.k
  2. Wie sollten unter Verwendung der besten statischen Planungsrichtlinie der Mittelwert und die Standardabweichung für die Gesamtausführungszeit in Bezug auf den Mittelwert und die Standardabweichung von ?μσX.

Ein einfacher dynamischer Load - Balancer kann planen Chargen von - Workloads zunächst auf jeden Slave, und dann, wenn Knoten das erste vervollständigen Chargen, eine zusätzliche Charge plant Workloads auf einem first-come, first-served Prinzip zu jedem Slave. Wenn also zunächst zwei Slave-Knoten geplant sind, werden 2 Stapel mit jeweils 2 Workloads geplant, und der erste Slave beendet seine zwei Stapel. Für den ersten Slave wird ein zusätzlicher Stapel geplant, während der zweite Slave weiterarbeitet. Wenn der erste Slave den neuen Stapel beendet, bevor der zweite Stapel seine anfängliche Arbeit beendet, setzt der Master die Planung für den ersten Slave fort. Erst wenn der zweite Slave seine Arbeit abgeschlossen hat, wird ihm ein neuer Stapel von Workloads ausgegeben. Beispiel:ichkichk

         DYNAMIC           STATIC
         POLICY            POLICY

     slave1  slave2    slave1  slave2
     ------  ------    ------  ------

t<0    --      --        --      --

t<1  batch1  batch3    batch1  batch3
     batch2  batch4    batch2  batch4
                       batch5  batch7
                       batch6  batch8

t=1    --    batch3    batch5  batch3
             batch4    batch6  batch4
                               batch7
                               batch8

t<2  batch5  batch3    batch5  batch3
             batch4    batch6  batch4
                               batch7
                               batch8

t=2    --    batch4    batch6  batch4
                               batch7
                               batch8

t<3  batch6  batch4    batch6  batch4
                               batch7
                               batch8

t=3    --      --        --    batch7
                               batch8

t<4  batch7  batch8      --    batch7
                               batch8

t=4    --      --        --    batch8

t<5      -DONE-          --    batch8

t=5                      --      --

t < 6                      -DONE-

Zur Verdeutlichung benötigen die Chargen 1 und 2 jeweils 1/2 Sekunde für die Verarbeitung, Charge 3 2 Sekunden für die Verarbeitung und die Chargen 4 bis 8 jeweils 1 Sekunde für die Verarbeitung. Diese Informationen sind a priori nicht bekannt. Im statischen Schema werden alle Jobs zu t = 0 verteilt, während im dynamischen Schema die Verteilung berücksichtigen kann, wie die tatsächlichen Laufzeiten der Jobs "ausgefallen" sind. Wir stellen fest, dass das statische Schema eine Sekunde länger dauert als das dynamische Schema, wobei Slave1 3 Sekunden und Slave2 5 Sekunden arbeitet. Im dynamischen Schema arbeiten beide Slaves die vollen 4 Sekunden.

Nun zu der Frage, die das Schreiben motiviert hat:

  1. Wie hoch sollten unter Verwendung der oben beschriebenen dynamischen Lastausgleichsrichtlinie der Mittelwert und die Standardabweichung für die Gesamtausführungszeit in Bezug auf den Mittelwert sein? μ und Standardabweichung σ von X.?

Interessierte Leser versichern mir, dass dies keine Hausaufgaben sind, obwohl es wahrscheinlich nicht viel schwieriger ist, als man es in bestimmten Kursen als Hausaufgaben erwarten würde. Wenn jemand Einwände dagegen erhebt und verlangt, dass ich etwas Arbeit zeige, bin ich gerne bereit (obwohl ich nicht weiß, wann ich in naher Zukunft Zeit habe). Diese Frage basiert tatsächlich auf einer Arbeit, die ich vor ein oder zwei Semestern noch nie gemacht habe, und empirische Ergebnisse waren dort, wo wir sie verlassen haben. Vielen Dank für Ihre Hilfe und / oder Mühe. Ich bin gespannt, was Sie zusammengestellt haben.

Patrick87
quelle
1
Was ist die Rolle von k? Wenn Sie nur genau planen könnenk Workloads (und nicht weniger), ist es nicht gleichbedeutend, von einzelnen Workloads zu sprechen, die benötigt werden? kmal so lange? Erreichen alle Workloads t = 0?
Alex Ten Brink
Wäre es nicht natürlicher anzunehmen, dass Ausführungszeiten sind f(ich)/.s mit ich eine Instanz ("Workload"), f eine bekannte Funktion und sdie Geschwindigkeit der aktuellen Maschine? In diesem Fall können Sie die Maschinengeschwindigkeiten verwenden, um Ihre Entscheidungen zu informieren und Geschwindigkeiten zu lernen, wenn Sie diese nicht kennen (oder sich ändern). Zufällige Ausführungszeiten geben Ihnen keine Informationen darüber, wie Sie Ihre Arbeit verteilen können.
Raphael
@AlextenBrink Ja, alle Workloads kommen zum Zeitpunkt t = 0 an. In gewissem Sinne können Sie in dieser Frage davon ausgehen, dass k = 1 ist ... aber X gilt für eine einzelne Workload, nicht für einen Stapel von k Workloads und in In jedem Fall könnte k etwas sein, das ich in der Praxis optimieren möchte (um möglicherweise den Overhead für die Kommunikationslatenz zu überwinden). Wenn Sie den Rest für k = 1 lösen können, sollte der Sprung zu anderem k einfach sein (finden Sie einfach die Verteilung Y = X + X + ... + X (k-mal) heraus).
Patrick87
@Raphael Ich stimme zu, dass zufällige Workload-Größen keine nützlichen Informationen darüber geben, wie die Arbeit verteilt werden soll ... das ist jedoch die Absicht des Problems. Hier werden einige Vereinfachungen vorgenommen, aber ich interessiere mich hauptsächlich dafür, diese einfachen Methoden (statisch und dynamisch) mit diesen vereinfachten Annahmen zu analysieren, bevor (möglicherweise) der Umfang der Frage erweitert wird (zum Beispiel indem wir sagen, dass wir mehr Informationen haben darüber, wie viel Arbeit eine bestimmte Arbeitslast erfordert und indem die Annahme von Knoten mit einheitlicher oder konstanter Leistung fallengelassen wird).
Patrick87
@Raphael Tatsächlich ist die Motivation für diese Frage genau die folgende: Wenn Sie nicht wissen, wie lange eine bestimmte Arbeitslast dauern wird, können Sie viel besser als die oben beschriebenen statischen und dynamischen Methoden? Wie viel besser ist die dynamische Methode im Vergleich zur statischen Methode (sie kann nicht schlechter sein, und ich gebe ein Beispiel, in dem die Dynamik tatsächlich besser ist).
Patrick87

Antworten:

5

Aktualisieren:

Für die neue Version, in der Sie versuchen, die Makespan zu minimieren, hat Ihr statischer Zeitplan immer noch den optimalen erwarteten Wert.

Lassen M.sei die Zufallsvariable für die Makespan. LassenF.ich sei der Zeitsklave ichist fertig. Das haben wir dannM.=maxich(X.ich). Sei die Anzahl der Jobs, die dem Slave zugewiesen sind . Dann haben wir das .cichichX.ich=ich=1cichX.=cichX.

Wenn die kumulative Wahrscheinlichkeitsverteilungsfunktion für , dann ist ist die kumulative Wahrscheinlichkeitsverteilungsfunktion für . Dies bedeutet, dass und wie .F.ich(x)X.P.(M.<m) =P.(maxich(X.ich)<m) =ichP.(X.ich<m) =ichP.(cichX.<m) =ichP.(X.<mcich) =ichF.(mcich)M.E.M.=- -x(ichF.(xcich))'dxstddev(M.)=- -(x- -E.M.)2(ichF.(xcich))'dx

Das Minimieren von das Minimieren von , was bedeutet, dass wir alle s gleich niedrig halten (da monoton ansteigt und zwischen 0 und 1 liegt). Dies bedeutet, dass wir alle Aufgaben gleichmäßig auf die Slaves verteilen sollten. Genau das erreicht Ihr statischer Zeitplan.E.M.ichF.(xcich)cichF.

Alex ten Brink
quelle
Ich glaube, ich war mir wahrscheinlich nicht sicher, was ich wollte. Wenn ich "Gesamtzeit" sage, meine ich "Wanduhrzeit", nicht "Prozesszeit". Natürlich macht die Planung keinen Unterschied, wenn ich nur die Laufzeiten aller Programme addieren möchte. Was ich minimieren möchte, ist die Gesamtzeit, die alle Slaves benötigen, um die gesamte Arbeit zu erledigen. In dem Beispiel, das ich zur Verfügung stelle, ist die Zeit, an der ich interessiert bin, 4s; Ich glaube, die Zeit, über die Sie sprechen, beträgt 8 Sekunden, da die Sklaven so viel Zeit mit dem Rechnen verbringen. Ein Sklave könnte zum Beispiel vor dem anderen fertig werden, was bedeutet, dass meine Metrik von "Nachzüglern" verletzt würde.
Patrick87
Anders ausgedrückt, so wie ich die Frage beabsichtige, haben meine statischen und dynamischen Schemata für das von mir bereitgestellte Beispiel eine unterschiedliche Leistung, und Dynamik ist besser. Wenn das aus meiner Frage nicht klar hervorgeht, muss ich die Frage bearbeiten.
Patrick87
@ Patric87: Das Wort, nach dem du dann suchst, ist 'Makespan', was als das letzte Mal definiert wird, wenn ein Sklave fertig ist. Ich kann Ihnen auch die Analyse für diesen Fall geben (vielleicht nicht heute), aber es wird ein bisschen länger dauern :)
Alex ten Brink
Ja, Makespan ist ein Begriff dafür. Ich nehme an, es wäre am besten, diesen Begriff explizit in der Frage zu verwenden, um Verwirrung durch andere Personen zu vermeiden, die möglicherweise nicht den Hintergrund haben, den Kontext der Frage zu verstehen.
Patrick87
Vielleicht irre ich mich, aber X + X! = 2X im Allgemeinen richtig? Was ist, wenn X wie Würfelwürfe gleichmäßig verteilt ist? Es gibt einen Unterschied zwischen zweimaligem Würfeln und Addieren der Zahlen und einmaligem Würfeln und Multiplizieren mit zwei (der Mittelwert ist der gleiche, aber Form und Ausbreitung unterscheiden sich). Der Rest der Analyse sieht gut aus, aber ich bin mir nicht ganz sicher, welche Auswirkungen mein Punkt haben könnte, wenn der Punkt gültig ist. Ich denke, es könnte, da der Mittelwert nicht beeinflusst wird, der stdev und das erwartete Maximum der erwarteten Werte durch stdev beeinflusst werden ... das scheint intuitiv plausibel.
Patrick87