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

Sintesi Tecnica: Allocazione Dinamica dei Core per Lavori Malleabili con Parametri di Accelerazione Sconosciuti

Enunciato del Problema
Questo articolo affronta il problema dell'allocazione dinamica delle risorse in sistemi di calcolo multicore che gestiscono un flusso di lavori "malleabili". A differenza dei lavori "moldable", in cui il numero di core allocati è fisico all'arrivo, i lavori malleabili consentono la ridistribuzione dinamica della capacità di elaborazione durante l'esecuzione. Il sistema consiste in un numero fisso di core identici ($c$) e due classi di lavori osservabili. Ogni classe di lavori è caratterizzata da una funzione di accelerazione (speed-up) distinta e sconosciuta $s(z; p)$, dove $z$ è la capacità allocata e $p$ è un parametro sconosciuto che governa il grado di parallelizzabilità.

L'obiettivo è minimizzare il numero medio di lavori nel sistema nel lungo periodo (equivalente al tempo di risposta medio in stato stazionario). Esiste un trade-off fondamentale: allocare più core accelera il completamento del lavoro, ma a causa dei rendimenti decrescenti (ad esempio, la Legge di Amdahl), il guadagno marginale diminuisce man mano che vengono assegnati più core. Sebbene siano note le politiche ottimali per tali sistemi quando i parametri di accelerazione sono fissi e noti (specificamente la politica EQUI per la condivisione equa all'interno delle classi e una frazione ottimale tra le classi derivata dai Processi Decisionali di Markov), questo articolo affronta lo scenario in cui i parametri $p_1$ e $p_2$ sono sconosciuti e devono essere appresi dai dati operativi. Questo vuoto è motivato da applicazioni moderne come l'addestramento di machine learning su larga scala su GPU in cloud, dove le caratteristiche di accelerazione possono variare a causa di carichi di lavoro in evoluzione o aggiornamenti hardware, rendendo irrealistiche le assunzioni statiche.

Metodologia
Gli autori propongono un framework iterativo di apprendimento e controllo che alterna la stima dei parametri all'ottimizzazione della policy.

1. Modello di Sistema:

   • I lavori arrivano tramite un processo di Poisson con tasso $\lambda$. I requisiti di servizio sono distribuiti esponenzialmente con tasso $\mu$.
   • I lavori appartengono alla Classe 1 (probabilità $\alpha$) o alla Classe 2 (probabilità $1-\alpha$).
   • La funzione di accelerazione $s(z; p)$ è lineare per $z \le 1$ ed è concava/non decrescente per $z > 1$. Sono considerati due modelli specifici: la Legge di Amdahl e un modello a legge di potenza ($s(z; p) = \max\{z, 1\}^p$).
   • La policy di allocazione $\pi$ determina la frazione di core assegnata ai lavori della Classe 1 in base allo stato attuale del sistema $(n^{(1)}, n^{(2)})$. All'interno di ogni classe, i core sono condivisi equamente (policy EQUI).

2. Stima dei Parametri (Massima Verosimiglianza):

   • Il cuore del meccanismo di apprendimento è uno stimatore di massima verosimiglianza (MLE) basato sui tempi di inter-partenza dipendenti dallo stato.
   • Il processo di partenza per ogni classe è modellato come un processo di Poisson dipendente dallo stato. Il tasso di partenza istantaneo $\delta^{(i)}$ dipende dal numero di lavori $n^{(i)}$, dai core allocati $c^{(i)}$ e dal parametro sconosciuto $p_i$.
   • La funzione di verosimiglianza è costruita scomponendo gli intervalli di inter-partenza in sotto-intervalli in cui lo stato del sistema (e quindi il tasso di partenza) rimane costante. La log-verosimiglianza è derivata esplicitamente come funzione dei tempi di partenza osservati e della sequenza degli stati del sistema.
   • Gli autori dimostrano che, sotto una policy di allocazione fissa, questi MLE sono fortemente consistenti (convergono quasi certamente ai parametri reali) all'aumentare del numero di partenze osservate. Questa prova si basa sulla struttura rigenerativa del sistema di code e sulla continuità Lipschitz della funzione di accelerazione rispetto a $p$.

3. Ottimizzazione della Policy (MDP):

   • Una volta stimati i parametri, la policy di allocazione ottimale viene calcolata risolvendo l'equazione di ottimalità di Bellman per un Processo Decisionale di Markov (MDP).
   • Lo spazio degli stati è definito dal numero di lavori in ciascuna classe. Lo spazio delle azioni è la frazione di core allocati alla Classe 1.
   • La funzione di costo è il numero totale di lavori nel sistema. L'MDP viene risolto utilizzando l'iterazione del valore dopo aver uniformato il processo a tempo continuo in un equivalente a tempo discreto.

4. Algoritmi di Apprendimento:
   Il documento propone due algoritmi specifici che implementano questo ciclo:

   • Algoritmo 1a: Utilizza solo i dati raccolti durante la finestra di osservazione più recente (definita da un numero fisso di partenze $N_k$) per aggiornare le stime. Ciò consente l'adattabilità a ambienti non stazionari in cui i parametri potrebbero cambiare nel tempo.
   • Algoritmo 1b: Utilizza tutti i dati accumulati dal tempo $t=0$ per aggiornare le stime. Sebbene questo comporti tipicamente una convergenza più rapida e una maggiore accuratezza in scenari stazionari, è meno adattabile ai cambiamenti dei parametri.

Contributi Chiave

• Estensione dei Modelli di Lavori Malleabili: Il documento estende i classici modelli di allocazione dei core per lavori malleabili introducendo un meccanismo di apprendimento per i parametri di accelerazione sconosciuti, andando oltre l'assunzione di conoscenza a priori.
• Inferenza Statistica nei Sistemi di Code: Sviluppa una specifica procedura MLE per stimare le caratteristiche di parallelizzazione utilizzando i tempi di inter-partenza dipendenti dallo stato, provando la forte consistenza sotto policy fisse.
• Framework di Apprendimento Integrato: Propone e analizza due algoritmi iterativi (1a e 1b) che combinano la stima statistica con l'aggiornamento della policy basato sul programmazione dinamica.
• Validazione Numerica: Attraverso estesi esperimenti numerici, il documento dimostra che i metodi proposti raggiungono stime dei parametri accurate e prestazioni di sistema quasi ottimali dopo brevi periodi di osservazione. Evidenzia inoltre un problema di "quasi-identificabilità" in cui stimare i parametri per lavori con bassa parallelizzabilità (basso $p$) è più difficile rispetto a lavori altamente parallelizzabili.

Risultati

• Convergenza: Gli esperimenti numerici confermano che gli stimatori convergono ai parametri reali. L'algoritmo 1b generalmente converge più velocemente di 1a in scenari stazionari grazie all'uso dell'intera cronologia dei dati.
• Adattabilità: In un esperimento non stazionario in cui i parametri di accelerazione cambiano a determinati punti temporali, l'Algoritmo 1a segue con successo l'evoluzione dei parametri e adatta la policy di allocazione di conseguenza, dimostrando la sua utilità in ambienti dinamici.
• Prestazioni: Le policy apprese raggiungono tempi di risposta medi vicini all'ottimo teorico che si otterrebbe se i veri parametri fossero noti sin dall'inizio.
• Asimmetria nella Stima: I risultati indicano che stimare il parametro per la classe con minore parallelizzabilità (minore $p$) è intrinsecamente più complesso e più lento nella convergenza rispetto alla classe con maggiore parallelizzabilità, a causa della debole sensibilità della funzione di accelerazione alle variazioni dell'allocazione dei core in quel regime.

Significatività
Il documento rivendica la propria significatività affrontando una lacuna critica nella letteratura: l'assunzione che le funzioni di accelerazione siano note e statiche. Fornendo un framework per apprendere questi parametri online, il lavoro offre una soluzione pratica per moderni ambienti di calcolo dinamici (come l'addestramento di IA in cloud) dove l'efficienza delle risorse è fondamentale ma le caratteristiche del sistema sono incerte. Gli autori osservano che, sebbene il framework si estenda naturalmente a più di due classi di lavori, la complessità computazionale per risolvere le associate equazioni di Bellman aumenta significativamente, evidenziando un trade-off tra espressività del modello e trattabilità. Il lavoro pone le basi per la ricerca futura su scenari non stazionari, distribuzioni dei tempi di servizio generali e metodi di approssimazione scalabili per sistemi ad alta dimensionalità.