Dynamic Core Allocation for Malleable Jobs with Unknown Speed-up Parameters

Technische Zusammenfassung: Dynamische Kern-Allokation für malleable Jobs mit unbekannten Speed-up-Parametern

Problemstellung
Diese Arbeit befasst sich mit dem Problem der dynamischen Ressourcenallokation in Multicore-Computing-Systemen, die einen Strom von „malleablen“ (verformbaren) Jobs verarbeiten. Im Gegensatz zu „moldablen“ (formbaren) Jobs, bei denen die Anzahl der allokierten Kerne bei Ankunft feststeht, erlauben malleable Jobs eine dynamische Umverteilung der Verarbeitungskapazität während der Ausführung. Das System besteht aus einer festen Anzahl identischer Kerne ($c$) und zwei beobachtbaren Jobklassen. Jede Jobklasse ist durch eine distinkte, unbekannte Speed-up-Funktion $s(z; p)$ charakterisiert, wobei $z$ die allokierte Kapazität und $p$ ein unbekannter Parameter ist, der den Grad der Parallelisierbarkeit bestimmt.

Das Ziel ist die Minimierung der langfristigen mittleren Anzahl an Jobs im System (entspricht der mittleren Antwortzeit im stationären Zustand). Es besteht ein grundlegender Trade-off: Die Allokation von mehr Kernen beschleunigt den Abschluss des Jobs, aber aufgrund abnehmender Erträge (z. B. Amdahls Gesetz) sinkt der Grenznutzen, wenn mehr Kerne zugewiesen werden. Während optimale Policies für solche Systeme bekannt sind, wenn die Speed-up-Parameter fest und bekannt sind (speziell die EQUI-Policy für die gleichmäßige Teilung innerhalb der Klassen und ein optimaler Anteil zwischen den Klassen mittels Markov-Entscheidungsprozessen), behandelt diese Arbeit das Szenario, in dem die Parameter $p_1$ und $p_2$ unbekannt sind und aus operativen Daten gelernt werden müssen. Diese Lücke wird durch moderne Anwendungen wie das großskalige Training von maschinellem Lernen auf Cloud-GPUs motiviert, bei denen sich die Speed-up-Charakteristika aufgrund sich entwickelnder Workloads oder Hardware-Upgrades ändern können, was statische Annahmen unrealistisch macht.

Methodik
Die Autoren schlagen ein iteratives Lern-und-Steuerungs-Framework vor, das zwischen der Parameterschätzung und der Policy-Optimierung alterniert.

1. Systemmodell:

   • Jobs treffen über einen Poisson-Prozess mit Rate $\lambda$ ein. Die Service-Anforderungen sind exponentiell verteilt mit Rate $\mu$.
   • Jobs gehören zu Klasse 1 (Wahrscheinlichkeit $\alpha$) oder Klasse 2 (Wahrscheinlichkeit $1-\alpha$).
   • Die Speed-up-Funktion $s(z; p)$ ist linear für $z \le 1$ und konkav/nicht-abnehmend für $z > 1$. Zwei spezifische Modelle werden betrachtet: Amdahls Gesetz und ein Potenzgesetz-Modell ($s(z; p) = \max\{z, 1\}^p$).
   • Die Allokations-Policy $\pi$ bestimmt den Anteil der Kerne, der den Jobs der Klasse 1 zugewiesen wird, basierend auf dem aktuellen Systemzustand $(n^{(1)}, n^{(2)})$. Innerhalb jeder Klasse werden die Kerne gleichmäßig geteilt (EQUI-Policy).

2. Parameterschätzung (Maximum Likelihood):

   • Der Kern des Lernmechanismus ist ein Maximum-Likelihood-Schätzer (MLE), der auf zustandsabhängigen Inter-Departure-Zeiten basiert.
   • Der Departure-Prozess für jede Klasse wird als zustandsabhängiger Poisson-Prozess modelliert. Die instantane Departure-Rate $\delta^{(i)}$ hängt von der Anzahl der Jobs $n^{(i)}$, den allokierten Kernen $c^{(i)}$ und dem unbekannten Parameter $p_i$ ab.
   • Die Likelihood-Funktion wird konstruiert, indem die Inter-Departure-Intervalle in Sub-Intervalle zerlegt werden, in denen der Systemzustand (und damit die Departure-Rate) konstant bleibt. Die Log-Likelihood wird explizit als Funktion der beobachteten Departure-Zeiten und der Sequenz der Systemzustände hergeleitet.
   • Die Autoren beweisen, dass unter einer festen Allokations-Policy diese MLEs stark konsistent sind (konvergieren fast sicher gegen die wahren Parameter), wenn die Anzahl der beobachteten Departures steigt. Dieser Beweis stützt sich auf die regenerative Struktur des Warteschlangensystems und die Lipschitz-Stetigkeit der Speed-up-Funktion bezüglich $p$.

3. Policy-Optimierung (MDP):

   • Sobald die Parameter geschätzt wurden, wird die optimale Allokations-Policy durch Lösen der Bellman-Optimalitätsgleichung für einen Markov-Entscheidungsprozess (MDP) berechnet.
   • Der Zustandsraum wird durch die Anzahl der Jobs in jeder Klasse definiert. Der Aktionsraum ist der Anteil der Kerne, die der Klasse 1 zugewiesen werden.
   • Die Kostenfunktion ist die Gesamtzahl der Jobs im System. Der MDP wird mittels Value Iteration gelöst, nachdem der kontinuierliche Prozess in ein diskretes Äquivalent uniformiert wurde.

4. Lernalgorithmen:
   Die Arbeit schlägt zwei spezifische Algorithmen vor, die diese Schleife implementieren:

   • Algorithmus 1a: Verwendet nur die Daten, die während des jüngsten Beobachtungsfensters (definiert durch eine feste Anzahl von Departures $N_k$) gesammelt wurden, um die Schätzungen zu aktualisieren. Dies ermöglicht die Anpassungsfähigkeit an nicht-stationäre Umgebungen, in denen sich Parameter ändern können.
   • Algorithmus 1b: Verwendet alle seit $t=0$ gesammelten Daten, um die Schätzungen zu aktualisieren. Während dies in stationären Settings typischerweise eine schnellere Konvergenz und höhere Genauigkeit liefert, ist es weniger anpassungsfähig an sich ändernde Parameter.

Wesentliche Beiträge

• Erweiterung der Modelle für malleable Jobs: Die Arbeit erweitert klassische Modelle der Kern-Allokation für malleable Jobs, indem sie einen Lernmechanismus für unbekannte Speed-up-Parameter einführt und damit über die Annahme von A-priori-Wissen hinausgeht.
• Statistische Inferenz in Warteschlangensystemen: Sie entwickelt ein spezifisches MLE-Verfahren zur Schätzung von Parallelisierungseigenschaften unter Verwendung von zustandsabhängigen Inter-Departure-Zeiten und beweist die starke Konsistenz unter festen Policies.
• Integriertes Lern-Framework: Sie schlägt und analysiert zwei iterative Algorithmen (1a und 1b) vor, die statistische Schätzung mit dynamischer Programmierung kombinieren.
• Numerische Validierung: Durch umfangreiche numerische Experimente demonstriert die Arbeit, dass die vorgeschlagenen Methoden genaue Parameterschätzungen und eine nahezu optimale Systemleistung nach relativ kurzen Beobachtungszeiträumen erreichen. Sie hebt zudem ein Problem der „Quasi-Identifizierbarkeit“ hervor, bei dem die Schätzung von Parametern für Jobs mit geringer Parallelisierbarkeit (niedriges $p$) schwieriger ist als für hochgradig parallelisierbare Jobs.

Ergebnisse

• Konvergenz: Numerische Experimente bestätigen, dass die Schätzer gegen die wahren Parameter konvergieren. Algorithmus 1b konvergiert in stationären Settings im Allgemeinen schneller als 1a, da er die gesamte Datenhistorie nutzt.
• Anpassungsfähigkeit: In einem nicht-stationären Experiment, bei dem sich die Speed-up-Parameter zu bestimmten Zeitpunkten ändern, verfolgt Algorithmus 1a die sich entwickelnden Parameter erfolgreich und passt die Allokations-Policy entsprechend an, was seine Nützlichkeit in dynamischen Umgebungen unterstreicht.
• Leistung: Die gelernten Policies erreichen mittlere Antwortzeiten, die nahe am theoretischen Optimum liegen, welches erreicht würde, wenn die wahren Parameter von Beginn an bekannt wären.
• Asymmetrie in der Schätzung: Die Ergebnisse zeigen, dass die Schätzung des Parameters für die Klasse mit geringerer Parallelisierbarkeit (kleineres $p$) inhärent schwieriger und langsamer konvergiert als für die Klasse mit höherer Parallelisierbarkeit, was auf die schwächere Sensitivität der Speed-up-Funktion gegenüber Änderungen der Kern-Allokation in diesem Bereich zurückzuführen ist.

Bedeutung
Die Arbeit beansprucht ihre Bedeutung durch die Adressierung einer kritischen Lücke in der Literatur: der Annahme, dass Speed-up-Funktionen bekannt und statisch sind. Indem sie ein Framework bereitstellt, um diese Parameter online zu lernen, bietet die Arbeit eine praktische Lösung für moderne, dynamische Computing-Umgebungen (wie das Cloud-basierte KI-Training), in denen Ressourceneffizienz entscheidend, aber Systemcharakteristika unsicher sind. Die Autoren merken an, dass sich das Framework natürlich auf mehr als zwei Jobklassen erweitern lässt, die rechnerische Komplexität beim Lösen der zugehörigen Bellman-Gleichungen jedoch signifikant steigt, was einen Trade-off zwischen Modell-Expressivität und Handhabbarkeit verdeutlicht. Die Arbeit legt den Grundstein für zukünftige Forschung zu nicht-stationären Settings, allgemeinen Service-Zeit-Verteilungen und skalierbaren Approximationsmethoden für hochdimensionale Systeme.