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

Resumo Técnico: Alocação Dinâmica de Núcleos para Trabalhos Maleáveis com Parâmetros de Aceleração Desconhecidos

Enunciado do Problema
Este artigo aborda o problema da alocação dinâmica de recursos em sistemas de computação multicore que lidam com um fluxo de trabalhos "maleáveis". Diferente dos trabalhos "moldáveis", onde o número de núcleos alocados é fixo na chegada, os trabalhos maleáveis permitem a redistribuição dinâmica da capacidade de processamento durante a execução. O sistema consiste em um número fixo de núcleos idênticos ($c$) e duas classes de trabalhos observáveis. Cada classe de trabalho é caracterizada por uma função de aceleração distinta e desconhecida $s(z; p)$, onde $z$ é a capacidade alocada e $p$ é um parâmetro desconhecido que governa o grau de paralelizabilidade.

O objetivo é minimizar o número médio de longo prazo de trabalhos no sistema (equivalentemente, o tempo de resposta médio em estado estacionário). Existe um compromisso fundamental: alocar mais núcleos acelera a conclusão do trabalho, mas, devido aos retornos decrescentes (por exemplo, a Lei de Amdahl), o ganho marginal diminui à medida que mais núcleos são atribuídos. Embora políticas ótimas para tais sistemas sejam conhecidas quando os parâmetros de aceleração são fixos e conhecidos (especificamente, a política EQUI para compartilhamento igual dentro das classes e uma fração ótima entre as classes derivada de Processos de Decisão de Markov), este artigo aborda o cenário onde os parâmetros $p_1$ e $p_2$ são desconhecidos e devem ser aprendidos a partir de dados operacionais. Esta lacuna é motivada por aplicações modernas como o treinamento de aprendizado de máquina em larga escala em GPUs na nuvem, onde as características de aceleração podem variar devido a cargas de trabalho em evolução ou atualizações de hardware, tornando as suposições estáticas irreais.

Metodologia
Os autores propõem um framework iterativo de aprendizado-e-controle que alterna entre a estimativa de parâmetros e a otimização de políticas.

1. Modelo do Sistema:

   • Os trabalhos chegam via um processo de Poisson com taxa $\lambda$. Os requisitos de serviço são distribuídos exponencialmente com taxa $\mu$.
   • Os trabalhos pertencem à Classe 1 (probabilidade $\alpha$) ou à Classe 2 (probabilidade $1-\alpha$).
   • A função de aceleração $s(z; p)$ é linear para $z \le 1$ e côncava/não decrescente para $z > 1$. Dois modelos específicos são considerados: a Lei de Amdahl e um modelo de lei de potência ($s(z; p) = \max\{z, 1\}^p$).
   • A política de alocação $\pi$ determina a fração de núcleos atribuída aos trabalhos da Classe 1 com base no estado atual do sistema $(n^{(1)}, n^{(2)})$. Dentro de cada classe, os núcleos são compartilhados igualmente (política EQUI).

2. Estimativa de Parâmetros (Máxima Verossimilhança):

   • O núcleo do mecanismo de aprendizado é um Estimador de Máxima Verossimilhança (MLE) baseado em tempos de inter-partida dependentes do estado.
   • O processo de partida para cada classe é modelado como um processo de Poisson dependente do estado. A taxa de partida instantânea $\delta^{(i)}$ depende do número de trabalhos $n^{(i)}$, dos núcleos alocados $c^{(i)}$ e do parâmetro desconhecido $p_i$.
   • A função de verossimilhança é construída através da decomposição dos intervalos de inter-partida em subintervalos onde o estado do sistema (e, portanto, a taxa de partida) permanece constante. A log-verossimilhança é derivada explicitamente como uma função dos tempos de partida observados e da sequência de estados do sistema.
   • Os autores provam que, sob uma política de alocação fixa, esses MLEs são fortemente consistentes (convergem quase certamente para os parâmetros reais) conforme o número de partidas observadas aumenta. Esta prova baseia-se na estrutura regenerativa do sistema de filas e na continuidade Lipschitz da função de aceleração em relação a $p$.

3. Otimização de Política (MDP):

   • Uma vez estimados os parâmetros, a política de alocação ótima é computada resolvendo a equação de optimalidade de Bellman para um Processo de Decisão de Markov (MDP).
   • O espaço de estados é definido pelo número de trabalhos em cada classe. O espaço de ações é a fração de núcleos alocados para a Classe 1.
   • A função de custo é o número total de trabalhos no sistema. O MDP é resolvido usando iteração de valor após a uniformização do processo de tempo contínuo em um equivalente de tempo discreto.

4. Algoritmos de Aprendizado:
   O artigo propõe dois algoritmos específicos que implementam este ciclo:

   • Algoritmo 1a: Utiliza apenas os dados coletados durante a janela de observação mais recente (definida por um número fixo de partidas $N_k$) para atualizar as estimativas. Isso permite a adaptabilidade a ambientes não estacionários onde os parâmetros podem mudar ao longo do tempo.
   • Algoritmo 1b: Utiliza todos os dados acumulados desde o tempo $t=0$ para atualizar as estimativas. Embora isso geralmente resulte em uma convergência mais rápida e maior precisão em configurações estacionárias, é menos adaptável a parâmetros em mudança.

Principais Contribuições

• Extensão dos Modelos de Trabalhos Maleáveis: O artigo estende os modelos clássicos de alocação de núcleos para trabalhos maleáveis ao introduzir um mecanismo de aprendizado para parâmetros de aceleração desconhecidos, indo além da suposição de conhecimento a priori.
• Inferência Estatística em Sistemas de Filas: Desenvolve um procedimento específico de MLE para estimar características de paralelização usando tempos de inter-partida dependentes do estado, provando a consistência forte sob políticas fixas.
• Framework de Aprendizado Integrado: Propõe e analisa dois algoritmos iterativos (1a e 1b) que combinam estimativa estatística com atualizações de política baseadas em programação dinâmica.
• Validação Numérica: Através de extensos experimentos numéricos, o artigo demonstra que os métodos propostos alcançam estimativas de parâmetros precisas e desempenho de sistema próximo ao ótimo após períodos de observação relativamente curtos. Também destaca um problema de "quase-identificabilidade", onde estimar parâmetros para trabalhos com baixa paralelizabilidade (baixo $p$) é mais difícil do que para trabalhos altamente paralelizáveis.

Resultos

• Convergência: Experimentos numéricos confirmam que os estimadores convergem para os parâmetros reais. O Algoritmo 1b geralmente converge mais rápido que o 1a em configurações estacionárias devido ao uso de todo o histórico de dados.
• Adaptabilidade: Em um experimento não estacionário onde os parâmetros de aceleração mudam em pontos de tempo específicos, o Algoritmo 1a rastreia com sucesso os parâmetros em evolução e ajusta a política de alocação de acordo, demonstrando sua utilidade em ambientes dinâmicos.
• Desempenho: As políticas aprendidas alcançam tempos de resposta médios próximos ao ótimo teórico que seria alcançado se os parâmetros reais fossem conhecidos desde o início.
• Assimetria na Estimativa: Os resultados indicam que estimar o parâmetro para a classe com menor paralelizabilidade (menor $p$) é inerentemente mais desafiador e mais lento para convergir do que para a classe com maior paralelizabilidade, devido à sensibilidade mais fraca da função de aceleração às mudanças na alocação de núcleos nesse regime.

Significância
O artigo reivindica significância ao abordar uma lacuna crítica na literatura: a suposição de que as funções de aceleração são conhecidas e estáticas. Ao fornecer um framework para aprender esses parâmetros online, o trabalho oferece uma solução prática para ambientes de computação modernos e dinâmicos (como o treinamento de IA na nuvem) onde a eficiência de recursos é primordial, mas as características do sistema são incertas. Os autores observam que, embora o framework se estenda naturalmente para mais de duas classes de trabalhos, a complexidade computacional para resolver as equações de Bellman associadas aumenta significativamente, destacando um compromisso entre expressividade do modelo e tratabilidade. O trabalho estabelece as bases para pesquisas futuras em configurações não estacionárias, distribuições de tempo de serviço gerais e métodos de aproximação escaláveis para sistemas de alta dimensão.