Résumé Technique : Ordonnancement DEFT des Workflows Cloud Dynamiques

Définition du Problème

Le papier traite du problème de l'Ordonnancement de Workflows Cloud Dynamiques Sensible au Coût (CADWS) dans les environnements de cloud computing. Dans ce contexte, les workflows arrivent de manière dynamique et sont modélés sous forme de Graphes Orientés Acycliques (DAG) où les nœuds représentent des tâches de calcul et les arêtes représentent des contraintes de précédence. Chaque workflow est associé à une échéance de l'Accord de Niveau de Service (SLA).

Le défi central réside dans la nature dynamique de l'environnement :

1. Arrivées Dynamiques : Les workflows arrivent de manière imprévisible avec des structures et des tailles variables.
2. Échéances Variables : Les échéances présentent un large spectre de sévérité, allant de la tolérance à l'extrême urgence.
3. Fluctuation des Ressources : La disponibilité et les coûts des Machines Virtuelles (VM) changent au fil du temps.

L'objectif est de minimiser le coût total d'exécution, qui est un composite de :

• Frais de Location de VM : Coûts encourus pour la location de VM sur une base de paiement à l'usage (pay-as-you-go).
• Pénalités de SLA : Pénalités financières encourues lorsqu'un workflow ne respecte pas son échéance.

Les approches existantes de Deep Reinforcement Learning (DRL) pour le CADWS emploient généralement des réseaux de politiques monolithiques (voies de propagation directe uniques). Les auteurs soutiennent que ces architectures rigides peinent à s'adapter aux divers scénarios d'ordonnancement imposés par la variation de la sévérité des échéances, car un ensemble unique de règles de décision ne peut pas gérer de manière optimale simultanément des échéances souples et des échéances urgentes.

Méthodologie : DEFT

Les auteurs proposent DEFT (Deadline-pErceptive Mixture-oF-Texperts), une nouvelle architecture de politique DRL conçue pour surmonter les limitations des voies d'inférence rigides.

1. Architecture Mixture-of-Experts (MoE)

Au lieu d'un réseau de politique unique, DEFT utilise un ensemble de sous-réseaux spécialisés (experts).

• Spécialisation : Chaque expert est entraîné pour gérer un niveau spécifique de sévérité d'échéance (contrôlé par un coefficient de relaxation de l'échéance $\gamma$). Par exemple, un expert peut se spécialiser dans un ordonnancement agressif et peu sensible au coût pour les échéances serrées, tandis qu'un autre se concentre sur des stratégies économes en coût et tolérantes aux délais pour les échéances plus souples.
• Entraînement en Deux Phases :
  • Phase 1 (Pré-entraînement des Experts) : Les experts sont pré-entraînés indépendamment sur des workflows avec des valeurs de $\gamma$ fixes et spécifiques pour apprendre des comportements d'ordonnancement distincts.
  • Phase 2 (Affinage Conjoint) : Tous les experts sont chargés dans l'architecture complète et affinés conjointement aux côtés d'un réseau de porte (gating network) et du Module d'Embedding d'État (SEM). Cette phase permet au système de s'adapter à des distributions d'échéances mixtes.

2. Réseau de Porte Adaptatif au Graphe

Une innovation critique de DEFT est son Réseau de Porte Adaptatif au Graphe, qui route dynamiquement les décisions vers l'expert le plus approprié à chaque étape de temps.

• Contexte d'Entrée : Le réseau de porte intègre quatre composantes clés :
  1. Embeddings globaux du workflow (structure du DAG).
  2. Caractéristiques de la tâche prête actuelle et de son contexte topologique.
  3. Caractéristiques au niveau du système (disponibilité et états des VM).
  4. Scores de sévérité d'échéance normalisés.
• Mécanisme de Cross-Attention : Contrairement au gating MoE traditionnel qui utilise de simples couches linéaires, DEFT emploie un mécanisme de cross-attention. L'embedding du DAG du workflow et les états des tâches forment la Requête (Q), tandis que les représentations des experts servent de Clés (K) et de Valeurs (V). Cela permet au portier d'effectuer une sélection d'expert précise et sensible à l'échéance basée sur les dépendances structurelles complexes du workflow.
• Stratégie de Routage : Le système utilise un routage Top-1, sélectionnant l'expert unique le plus approprié pour chaque étape de décision. Les études d'ablation dans le papier suggèrent que le routage Top-1 surpasse le routage Top-k dans cet espace d'action discret, car il évite de "mélanger" des recommandations d'experts conflictuelles qui peuvent conduire à des sélections de VM sous-optimales.

3. Optimisation

La politique est optimisée à l'aide des Stratégies d'Évolution d'OpenAI (ES), une technique d'optimisation basée sur la population choisie pour sa robustesse dans les environnements dynamiques et sa capacité de mise en œuvre parallèle.

Contributions Clés

Le papier revendique trois contributions principales :

1. Première Application de MoE dans l'Ordonnancement de Workflows Dynamiques : DEFT est présenté comme la première approche introduisant des architectures Mixture-of-Experts spécifiquement pour l'ordonnancement de workflows cloud dynamiques, introduisant un nouveau niveau d'adaptabilité dans la conception de politiques sensibles aux échéances.
2. Amélioration de la Diversité et de la Généralisation des Politiques : En employant une stratégie d'entraînement en deux phases (pré-entraînement spécialisé suivi d'un affinage conjoint), DEFT atteint une généralisation supérieure à travers diverses régimes d'échéances et échelles de workflow (Small, Medium, Large) par rapport aux bases de référence DRL monolithiques.
3. Porte Adaptative au Graphe : Les auteurs introduisent un nouveau mécanisme de porte qui combine les représentations de réseaux de neurones sur graphes (GNN) avec le routage MoE. C'est la première conception intéquant des DAG de workflows structurés avec le routage MoE dans un ordonnanceur DRL, permettant une activation d'expert précise et pilotée par l'échéance.

Résultats Expérimentaux

Les auteurs ont évalué DEFT contre cinq bases de référence : deux méthodes heuristiques (ProLis, GRP-HEFT) et trois méthodes DRL de pointe (ES-RL, SPN-CWS, GATES).

• Réduction du Coût Total : DEFT a systématiquement obtenu le coût total le plus bas sur toutes les échelles de workflow (S, M, L).
  • Sur les workflows à grande échelle (Large-scale), DEFT a réduit les coûts de 29,6 % par rapport à la meilleure base de référence DRL (GATES).
  • Les méthodes heuristiques ont été nettement moins performantes, avec des coûts 3 à 10 fois plus élevés que les approches DRL.
• Scalabilité : Alors que d'autres méthodes DRL (comme ES-RL) se dégradaient fortement à mesure que la taille du workflow augmentait, DEFT a démontré une forte scalabilité, l'augmentation des coûts étant beaucoup plus lente à mesure que les échéances se resserraient et que les workflows croissaient.
• Équilibre des Coûts : DEFT a efficacement équilibré le compromis entre les frais de location de VM et les pénalités de SLA. Dans les scénarios avec des échéances serrées, il a priorisé l'évitement des pénalités ; dans les scénarios plus souples, il a minimisé les coûts de VM, adaptant sa stratégie dynamiquement.
• Études d'Ablation :
  • Mécanisme de Porte : Le portage adaptatif au graphe a nettement surpassé les mécanismes de porte linéaires et les mécanismes de porte MLP standards.
  • MoE vs Capacité : Remplacer le PMM fixe par un MoE a donné de meilleurs résultats que le simple approfondissement de l'MLP de la base de référence, confirmant que le gain provient de la sélection de politiques spécialisées plutôt que de l'augmentation de la capacité du modèle.
  • Routage : Le routage Top-1 s'est avéré supérieur au routage Top-k pour ce problème spécifique, évitant la moyenne de décisions d'experts conflictuelles.

Signification et Revendications

Le papier positionne DEFT comme une avancée significative dans le domaine de l'ordonnancement de workflows cloud. Les auteurs affirment que :

• Les architectures rigides sont insuffisantes : Les politiques DRL à voie unique ne peuvent pas gérer efficacement le large spectre de sévérité des échéances trouvé dans les environnements cloud réels.
• L'adaptabilité est la clé : En sélectionnant dynamiquement des experts spécialisés basés sur la structure du workflow en temps réel et l'urgence de l'échéance, DEFT atteint un niveau de flexibilité et de précision que les politiques statiques ne peuvent égaler.
• Impact Pratique : La méthode offre une approche rigoureuse pour un ordonnancement structuré et sensible aux échéances qui réduit considérablement les coûts d'exécution et les violations d'échéances, la rendant adaptée aux environnements cloud complexes et dynamiques.

Les auteurs concluent que DEFT représente un passage des politiques d'ordonnancement statiques et uniformes vers des systèmes adaptatifs et conscients du contexte, capables de raisonner sur des contraintes diverses et évolutives. Des travaux futurs sont suggérés pour étendre cette approche aux environnements multi-locataires (multi-tenant) et explorer l'explicabilité du routage des experts.