💻 computer science

Deft Scheduling of Dynamic Cloud Workflows with Varying Deadlines via Mixture-of-Experts

Questo articolo introduce DEFT, un nuovo scheduler di Deep Reinforcement Learning che impiega un'architettura Mixture-of-Experts adattiva al grafo per allocare dinamicamente workflow cloud con scadenze variabili, riducendo significativamente i costi di esecuzione e le violazioni delle scadenze rispetto ai baseline allo stato dell'arte.

Autori originali: Ya Shen, Gang Chen, Hui Ma, Mengjie Zhang

Pubblicato 2026-06-02

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Ya Shen, Gang Chen, Hui Ma, Mengjie Zhang

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di essere il manager di una cucina enorme e caotica. Ogni pochi minuti arriva un nuovo ordine (un workflow). Ogni ordine è una ricetta complessa con molti passaggi che devono avvenire in un ordine specifico (un DAG o grafo). Alcuni ordini sono urgenti: "Questo piatto deve essere in tavola in 5 minuti!". Altri sono rilassati: "Fallo quando puoi, entro cena".

Il tuo obiettivo è semplice: portare fuori tutto il cibo senza mancare le scadenze, spendendo il meno possibile in stipendi per gli chef.

Questo è il problema dello Scheduling Dinamico dei Workflow nel Cloud.

Il vecchio modo: Lo chef "taglia unica"

In precedenza, i programmi informatici che cercavano di risolvere questo problema agivano come un singolo chef rigido. Avevano un unico set di regole che applicavano a ogni situazione.

Se arrivava un ordine urgente, lo chef poteva andare nel panico e assumere l'aiuto più veloce e costoso.
Se arrivava un ordine lento, lo stesso chef poteva comunque assumere aiuti costosi solo per sicurezza, sprecando denaro.
Oppure, cercava di risparmiare denaro su un ordine urgente, mancando la scadenza e pagando una multa.

Il problema era che un singolo set di regole non riusciva a gestire l'enorme varietà di situazioni. Era come cercare di usare un singolo cacciavite per riparare un orologio, un'auto e una casa.

La nuova soluzione: DEFT (La "Squadra di Esperti")

Gli autori di questo articolo introducono DEFT (Deadline-pErceptive Mixture-oF-Experts). Inve di un singolo chef rigido, DEFT assume una squadra di esperti specializzati, ognuno addestrato per un tipo specifico di urgenza.

Pensa a un ristorante di alto livello con un Capo Chef (la Rete di Gating) e una squadra di Chef Specialisti (gli Esperti):

Gli Chef Specialisti (Gli Esperti):
- Chef "Panico": Addestrato solo su scadenze strettissime. Il suo unico obiettivo è la velocità, anche se costa una fortuna.
- Chef "Budget": Addestrato solo su scadenze rilassate. Il suo unico obiettivo è risparmiare denaro, anche se ci vuole più tempo.
- Chef "Equilibrato": Addestrato su scadenze medie per trovare il perfetto compromesso.
- Nel documento, questi sono reti neurali addestrate specificamente su diversi livelli di pressione della scadenza.
Il Capo Chef (La Rete di Gating Adattiva al Grafo):
- Questo è il manager intelligente. Quando arriva un nuovo ordine, il Capo Chef osserva la situazione:
  - Quanto è urgente la scadenza?
  - Com'è fatta la ricetta (è complessa)?
  - Quanti chef sono attualmente occupati?
- In base a ciò, il Capo Chef sceglie istantaneamente il singolo Chef Specialista migliore per gestire quel particolare ordine.
- Se l'ordine è urgente, chiama lo "Chef Panico". Se è una giornata tranquilla, chiama lo "Chef Budget".

Perché questo è importante

L'articolo afferma che questa è la prima volta che questa idea di "Mixture-of-Experts" (Miscela di Esperti) viene utilizzata per questo specifico tipo di problema di scheduling nel cloud.

Flessibilità: A differenza dei vecchi sistemi a "regola singola", DEFT può cambiare strategia istantaneamente. Non deve essere "veloce" o "economico" tutto il tempo; può essere veloce quando serve e economico quando è sicuro.
Decisioni più intelligenti: Il Capo Chef utilizza uno strumento speciale (chiamato Cross-Attention) per guardare il quadro completo — la struttura della ricetta e la cucina affollata — prima di scegliere l'esperto. Ciò assicura che l'esperto giusto sia scelto per il momento giusto.
Risultati migliori: Nei loro test (simulando migliaia di ordini e chef), DEFT ha risparmiato significativamente più denaro e ha mancato meno scadenze rispetto ai migliori metodi esistenti. Ha gestito molto meglio gli ordini grandi e complessi rispetto ai vecchi sistemi, che tendevano a fallire o a sprecare denaro con l'aumentare del carico di lavoro.

In sintesi

DEFT è come passare da un singolo lavoratore testardo a una squadra dinamica e intelligente. Avere specialisti per diverse situazioni e un manager intelligente per assegnare la persona giusta al lavoro giusto, rende il sistema molto più capace di bilanciare il compromesso tra velocità (rispettare le scadenze) e costo (risparmiare denaro).

L'articolo dimostra che questo approccio funziona meglio dei metodi attuali, specialmente quando il carico di lavoro è imprevedibile e le scadenze variano enormemente.

Sintesi Tecnica: DEFT - Pianificazione di Workflow Cloud Dinamici

Definizione del Problema

Il documento affronta il problema della Pianificazione di Workflow Cloud Dinamici Consapevole dei Costi (CADWS) negli ambienti di cloud computing. In questo contesto, i workflow arrivano dinamicamente e sono modellati come Grafi Aciclici Diretti (DAG), dove i nodi rappresentano task computazionali e gli archi rappresentano vincoli di precedenza. Ogni workflow è associato a una scadenza (deadline) del Service-Level Agreement (SLA).

La sfida principale risiede nella natura dinamica dell'ambiente:

Arrivi Dinamici: I workflow arrivano in modo imprevedibile con strutture e dimensioni variabili.
Scadenze Variabili: Le scadenze presentano un ampio spettro di rigidezza, che vanno da lenienti a estremamente urgenti.
Fluttuazione delle Risorse: La disponibilità e i costi delle Macchine Virtuali (VM) cambiano nel tempo.

L'obiettivo è minimizzare il costo totale di esecuzione, che è un composito di:

Tariffe di Noleggio VM: Costi sostenuti per l'affitto delle VM su base pay-as-you-go.
Penalità SLA: Penali finanziarie sostenute quando un workflow non rispetta la propria scadenza.

Gli approcci esistenti di Deep Reinforcement Learning (DRL) per il CADWS utilizzano tipicamente policy network monolitiche (singoli percorsi feedforward). Gli autori sostengono che queste architetture rigide faticano ad adattarsi ai diversi scenari di pianificazione imposti dalla variazione della rigidità delle scadenze, poiché un singolo insieme di regole decisionali non può gestire in modo ottimale simultaneamente scadenze rilassate e scadenze urgenti.

Metodologia: DEFT

Gli autori propongono DEFT (Deadline-pErceptive Mixture-oF-Texperts), un nuovo design di architettura della policy DRL progettato per superare i limiti dei percorsi di inferenza rigidi.

1. Architettura Mixture-of-Experts (MoE)

Invece di una singola rete di policy, DEFT utilizza un pool di sottoreti specializzate (expert).

Specializzazione: Ogni expert è addestrato per gestire un livello specifico di rigidità della scadenza (controllato da un coefficiente di rilassamento della scadenza $\gamma$ ). Ad esempio, un expert può specializzarsi in una pianificazione aggressiva e insensibile ai costi per scadenze strette, mentre un altro può concentrarsi su strategie efficienti dal punto di vista dei costi e tolleranti ai ritardi per scadenze rilassate.
Addestramento in Due Fasi:
- Fase 1 (Pre-addestramento degli Expert): Gli expert vengono pre-addestrati indipendentamente su workflow con valori di $\gamma$ fissi e specifici per apprendere comportamenti di pianificazione distinti.
- Fase 2 (Fine-tuning Congiunto): Tutti gli expert vengono caricati nella piena architettura e sottoposti a fine-tuning congiunto insieme a una rete di gating e al modulo di embedding dello stato (SEM). Questa fase permette al sistema di adattarsi a distribuzioni di scadenze miste.

2. Rete di Gating Adattiva al Grafo

Un'innovazione critica in DEFT è la Rete di Gating Adattiva al Grafo, che instrada dinamicamente le decisioni verso l'expert più appropriato ad ogni passo temporale.

Contesto di Input: La rete di gating integra quattro componenti chiave:
1. Embedding globali del workflow (struttura DAG).
2. Caratteristiche del task corrente pronto e del suo contesto topologico.
3. Caratteristiche a livello di sistema (disponibilità e stati delle VM).
4. Punteggi normalizzati di rigidità della scadenza.
Meccanismo di Cross-Attention: A differenza del gating MoE tradizionale che utilizza semplici strati lineari, DEFT impiega un meccanismo di cross-attention. L'embedding del DAG del workflow e gli stati dei task formano la Query (Q), mentre le rappresentazioni degli expert fungono da Key (K) e Value (V). Ciò consente alla porta (gate) di eseguire una selezione degli expert fine granulare e sensibile alla scadenza basata sulle complesse dipendenze strutturali del workflow.
Strategia di Routing: Il sistema utilizza il routing Top-1, selezionando il singolo expert più adatto per ogni passo decisionale. Gli studi di ablazione nel documento suggeriscono che il routing Top-1 supera il routing Top-k in questo spazio di azione discreto, poiché evita di "mescolare" raccomandazioni di expert conflittuali che possono portare a selezioni di VM subottimali.

3. Ottimizzazione

La policy è ottimizzata utilizzando le OpenAI Evolution Strategies (ES), una tecnica di ottimizzazione basata sulla popolazione scelta per la sua robustezza in ambienti dinamici e la sua idoneità all'implementazione parallela.

Contributi Chiave

Il documento rivendica tre contributi primari:

Prima Applicazione di MoE nella Pianificazione di Workflow Dinamici: DEFT è presentato come il primo approccio a introdurre architetture Mixture-of-Experts specificamente per la pianificazione di workflow cloud dinamici, introducendo un nuovo livello di adattabilità nel design della policy consapevole delle scadenze.
Miglioramento della Diversità e Generalizzazione della Policy: Utilizzando una strategia di addestramento in due fasi (pre-addestramento specializzato seguito da fine-tuning congiunto), DEFT raggiunge una generalizzazione superiore attraverso diversi regimi di scadenza e scale di workflow (Piccolo, Medio, Grande) rispetto alle baseline DRL monolitiche.
Gating Adattivo al Grafo: Gli autori introducono un nuovo meccanismo di gating che combina le rappresentazioni delle reti neurali a grafi (GNN) con il routing MoE. Questa è la prima progettazione che integra i DAG strutturati dei workflow con il routing MoE in uno scheduler DRL, consentendo un'attivazione degli expert precisa e guidata dalla scadenza.

Risultati Sperimentali

Gli autori hanno valutato DEFT contro cinque baseline: due metodi euristici (ProLis, GRP-HEFT) e tre metodi DRL allo stato dell'arte (ES-RL, SPN-CWS, GATES).

Riduzione del Costo Totale: DEFT ha costantemente ottenuto il costo totale più basso in tutte le scale di workflow (S, M, L).
- Sui workflow su larga scala, DEFT ha ridotto i costi del 29,6% rispetto alla migliore baseline DRL (GATES).
- I metodi euristici sono stati significativamente peggiori, con costi da 3 a 10 volte superiori rispetto agli approcci DRL.
Scalabilità: Mentre altri metodi DRL (come ES-RL) degradavano bruscamente all'aumentare della dimensione del workflow, DEFT ha dimostrato una forte scalabilità, con un aumento dei costi molto più lento man mano che le scadenze si stringevano e i workflow crescevano.
Bilanciamento dei Costi: DEFT ha bilanciato efficacemente il compromesso tra le tariffe di noleggio VM e le penalità SLA. In scenari con scadenze strette, ha dato priorità all'evitare le penalità; in scenari rilassati, ha minimizzato i costi delle VM, adattando la sua strategia dinamicamente.
Studi di Ablazione:
- Meccanismo di Gating: Il gating adattivo al grafo ha superato significativamente i meccanismi di gating lineari e standard MLP.
- MoE vs Capacità: Sostituire il PMM fisso con MoE ha prodotto risultati migliori rispetto al semplice approfondimento dell'MLP nella baseline, confermando che il guadagno deriva dalla selezione di una policy specializzata piuttosto che solo da un aumento della capacità del modello.
- Routing: Il routing Top-1 è risultato superiore al routing Top-k per questo problema specifico, evitando la media di decisioni di expert conflittuali.

Significato e Rivendicazioni

Il documento posiziona DEFT come un avanzamento significativo nel campo della pianificazione dei workflow cloud. Gli autori affermano che:

Le architetture rigide sono insufficienti: Le policy DRL a percorso singolo non possono gestire efficacemente l'ampio spettro di rigidità delle scadenze presenti nei veri ambienti cloud.
L'adattabilità è la chiave: Selezionando dinamicamente expert specializzati in base alla struttura del workflow in tempo reale e all'urgenza della scadenza, DEFT raggiunge un livello di flessibilità e precisione che le policy statiche non possono eguagliare.
Impatto Pratico: Il metodo offre un approccio rigoroso alla pianificazione strutturata e guidata dalle scadenze che riduce significativamente i costi di esecuzione e le violazioni delle scadenze, rendendolo adatto a complessi e dinamici ambienti cloud.

Gli autori concludono che DEFT rappresenta un passaggio dalle politiche di pianificazione statiche "one-size-fits-all" a sistemi adattivi e consapevoli del contesto, capaci di ragionare su vincoli diversificati ed evolutivi. Il lavoro futuro suggerisce di estendere questo approccio ad ambienti multi-tenant ed esplorare l'esplicabilità nel routing degli expert.