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

Résumé Technique : Allocation Dynamique de Cœurs pour des Travaux Malléables avec Paramètres d'Accélération Inconnus

Énoncé du Problème
Cet article traite du problème d'allocation dynamique des ressources dans les systèmes de calcul multicœurs gérant un flux de travaux « malléables ». Contrairement aux travaux « moulables », où le nombre de cœurs alloués est fixé à l'arrivée, les travaux malléables permettent une redistribution dynamique de la capacité de traitement pendant l'exécution. Le système se compose d'un nombre fixe de cœurs identiques ($c$) et de deux classes de travaux observables. Chaque classe de travaux est caractérisée par une fonction d'accélération distincte et inconnue $s(z; p)$, où $z$ est la capacité allouée et $p$ est un paramètre inconnu régissant le degré de parallélisabilité.

L'objectif est de minimiser le nombre moyen de travaux dans le système à long terme (ce qui équivaut au temps de réponse moyen en régime permanent). Un arbitrage fondamental existe : allouer plus de cœurs accélère l'achèvement des travaux, mais en raison des rendements décroissants (par exemple, la loi d'Amdahl), le gain marginal diminue à mesure que davantage de cœurs sont assignés. Bien que les politiques optimales pour de tels systèmes soient connues lorsque les paramètres de vitesse sont fixes et connus (spécifiquement la politique EQUI pour un partage égal au sein des classes et une fraction optimale entre les classes dérivée via des processus de décision markoviens), cet article traite du scénario où les paramètres $p_1$ et $p_2$ sont inconnus et doivent être appris à partir de données opérationnelles. Ce fossé est motivé par des applications modernes comme l'entraînement de modèles d'apprentissage automatique à grande échelle sur des GPU dans le cloud, où les caractéristiques d'accélération peuvent varier en raison de l'évolution des charges de travail ou des mises à niveau matérielles, rendant les hypothèses statiques irréalistes.

Méthodologie
Les auteurs proposent un cadre d'apprentissage et de contrôle itératif qui alterne entre l'estimation des paramètres et l'optimisation de la politique.

1. Modèle de Système :

   • Les travaux arrivent via un processus de Poisson de taux $\lambda$. Les exigences de service sont distribuées exponentiellement de taux $\mu$.
   • Les travaux appartiennent à la Classe 1 (probabilité $\alpha$) ou à la Classe 2 (probabilité $1-\alpha$).
   • La fonction d'accélération $s(z; p)$ est linéaire pour $z \le 1$ et concave/non décroissante pour $z > 1$. Deux modèles spécifiques sont considérés : la loi d'Amdahl et un modèle de puissance ($s(z; p) = \max\{z, 1\}^p$).
   • La politique d'allocation $\pi$ détermine la fraction de cœurs assignés aux travaux de la Classe 1 en fonction de l'état actuel du système $(n^{(1)}, n^{(2)})$. Au sein de chaque classe, les cœurs sont partagés également (politique EQUI).

2. Estimation de Paramètres (Maximum de Vraisemblance) :

   • Le cœur du mécanisme d'apprentissage est un estimateur du maximum de vraisemblance (MLE) basé sur les temps inter-départs dépendants de l'état.
   • Le processus de départ pour chaque classe est modélisé comme un processus de Poisson dépendant de l'état. Le taux de départ instantané $\delta^{(i)}$ dépend du nombre de travaux $n^{(i)}$, des cœurs alloués $c^{(i)}$, et du paramètre inconnu $p_i$.
   • La fonction de vraisemblance est construite en décomposant les intervalles inter-départs en sous-intervalles où l'état du système (et donc le taux de départ) reste constant. La log-vraisemblance est dérivée explicitement en fonction des temps de départ observés et de la séquence des états du système.
   • Les auteurs prouvent que sous une politique d'allocation fixe, ces MLE sont fortement cohérents (convergent presque sûrement vers les vrais paramètres) à mesure que le nombre de départs observés augmente. Cette preuve repose sur la structure régénérative du système de file d'attente et la continuité lipschitzienne de la fonction d'accélération par rapport à $p$.

3. Optimisation de la Politique (MDP) :

   • Une fois les paramètres estimés, la politique d'allocation optimale est calculée en résolvant l'équation de Bellman d'optimalité pour un processus de décision markovien (MDP).
   • L'espace d'état est défini par le nombre de travaux dans chaque classe. L'espace d'action est la fraction de cœurs alloués à la Classe 1.
   • La fonction de coût est le nombre total de travaux dans le système. Le MDP est résolu par itération de la valeur après uniformisation du processus en temps continu en un équivalent en temps discret.

4. Algorithmes d'Apprentissage :
   L'article propose deux algorithmes spécifiques implémentant cette boucle :

   • Algorithme 1a : Utilise uniquement les données collectées durant la fenêtre d'observation la plus récente (définie par un nombre fixe de départs $N_k$) pour mettre à jour les estimations. Cela permet l'adaptabilité à des environnements non stationnaires où les paramètres peuvent changer au fil du temps.
   • Algorithme 1b : Utilise toutes les données accumulées depuis $t=0$ pour mettre à jour les estimations. Bien que cela permette généralement une convergence plus rapide et une plus grande précision dans des contextな stationnaires, cela est moins adaptable aux changements de paramètres.

Contributions Clés

• Extension des Modèles de Travaux Malléables : L'article étend les modèles classiques d'allocation de cœurs pour les travaux malléables en introduisant un mécanisme d'apprentissage pour les paramètres d'accélération inconnus, dépassant l'hypothèse de connaissances a priori.
• Inférence Statistique dans les Systèmes de Files d'Attente : Il développe une procédure MLE spécifique pour estimer les caractéristiques de parallélisation en utilisant les temps inter-départs dépendants de l'état, prouvant la cohérence forte sous des politiques fixes.
• Cadre d'Apprentissage Intégré : Il propose et analyse deux algorithmes itératifs (1a et 1b) qui combinent l'estimation statistique avec la mise à jour de politiques basées sur la programmation dynamique.
• Validation Numérique : À travers des expériences numériques approfondies, l'article démontre que les méthodes proposées atteignent des estimations de paramètres précises et des performances système quasi-optimales après des périodes d'observation relativement courtes. Il souligne également un problème de « quasi-identifiabilité » où l'estimation des paramètres pour les travaux ayant une faible parallélisabilité (faible $p$) est plus difficile que pour les travaux hautement parallélisables.

Résultats

• Convergence : Les expériences numériques confirment que les estimateurs convergent vers les vrais paramètres. L'algorithme 1b converge généralement plus rapidement que le 1a dans les contextes stationnaires grâce à l'utilisation de l'historique complet des données.
• Adaptabilité : Dans une expérience non stationnaire où les paramètres d'accélération changent à des points temporels spécifiques, l'algorithme 1a suit avec succès l'évolution des paramètres et ajuste la politique d'allocation en conséquence, démontrant son utilité dans des environnements dynamiques.
• Performance : Les politiques apprises atteignent des temps de réponse moyens proches de l'optimum théorique qui serait atteint si les vrais paramètres étaient connus dès le début.
• Asymétrie d'Estimation : Les résultats indiquent qu'estimer le paramètre de la classe ayant la plus faible parallélisabilité (plus petit $p$) est intrinsèquement plus complexe et plus lent à converger que pour la classe ayant une parallélisabilité plus élevée, en raison d'une sensibilité plus faible de la fonction d'accélération aux changements d'allocation de cœurs dans ce régime.

Signification
L'article revendique sa pertinence en s'attaquant à une lacune critique dans la littérature : l'hypothèse que les fonctions d'accélération sont connues et statiques. En fournissant un cadre pour apprendre ces paramètres en ligne, ce travail offre une solution pratique pour les environnements de calcul modernes et dynamiques (tels que l'entraînement d'IA dans le cloud) où l'efficacité des ressources est primordiale mais les caractéristiques du système sont incertaines. Les auteurs notent que si le cadre s'étend naturellement à plus de deux classes de travaux, la complexité computationnelle de la résolution des équations de Bellman associées augmente considérablement, soulignant un arbitrage entre l'expressivité du modèle et la tractabilité. Ce travail pose les bases de recherches futures sur les contextes non stationnaires, les distributions de temps de service générales et les méthodes d'approximation extensibles pour les systèmes à haute dimension.