Analyse von Lastausgleichsschemata zur Minimierung der Gesamtausführungszeit

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.$X$$n$$m$

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 .$k$$n$

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?$k$$m$$m$$n/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 ?$\mu$$\sigma$$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:$i$$k$$i$$k$

         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? $\mu$ und Standardabweichung $\sigma$ 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.

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. Lassen$F_i$ sei der Zeitsklave $i$ist fertig. Das haben wir dann$M = \max_i(X_i)$. Sei die Anzahl der Jobs, die dem Slave zugewiesen sind . Dann haben wir das .$c_i$$i$$X_i = \sum_{i=1}^{c_i} X = c_i X$

Wenn die kumulative Wahrscheinlichkeitsverteilungsfunktion für , dann ist ist die kumulative Wahrscheinlichkeitsverteilungsfunktion für . Dies bedeutet, dass und wie .$F_i(x)$$X$$P(M < m)$ $= P(\max_i(X_i) < m)$ $= \prod_i P(X_i < m)$ $= \prod_i P(c_i X < m)$ $= \prod_i P(X < \frac{m}{c_i})$ $= \prod_i F(\frac{m}{c_i})$$M$$EM = \int_{-\infty}^{\infty} x (\prod_i F(\frac{x}{c_i}))' dx$$stddev(M) = \sqrt{\int_{-\infty}^{\infty} (x - EM)^2 (\prod_i F(\frac{x}{c_i}))' 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.$EM$$\prod_i F(\frac{x}{c_i})$$c_i$$F$