Markov decision processes for optimizing job scheduling with Reinforcement Learning

Abstract

À medida que nossos sistemas computacionais se tornam maiores e com interações mais complexas, apresenta-se um potencial para o uso de técnicas de aprendizado que se adaptem a variações nas condições de sistemas durante a evolução das cargas de trabalho. O arcabouço de tomada de decisão sequencial fornecido por Aprendizado por Reforço (RL) se adapta bem a problemas de gerenciamento de recursos. Ainda assim, quando consideramos o uso de Aprendizado Profundo para escalonamento de jobs de sistemasde Computação de Alto Desempenho (HPC), vemos que trabalhos existentes ou focam em problemas menores, como a decisão de escolha de heurísticas dentro de um conjunto, ou em instâncias simplificadas do problema. Nesta tese, investigamos modelos de Processos de Tomada de Decisão de Markov (MDP) para resolver o escalonamento de jobs HPC, apresentando uma abordagem para experimentação mais rápida e reprodutível. Sobre essa fundação, investigamos como diferentes agentes se comportam nesse arcabouço, ao mesmo tempo que identificamos deficiências tanto na representação do problema quanto como o aprendizado se dá nesse cenário. Dentre as contribuições deste trabalho, propomos um sistema de software para desenvolvimento e experimentação com agentes deRL, bem como avaliamos algoritmos de estado-da-arte nesse sistema, com desempenho equivalente ao de algoritmos específicos, porém com menos esforço computacional. Nós também mapeamos o problema de escalonamento de jobs HPC para o formalismo de SMDP e apresentamos uma solução online, baseada em aprendizado por reforço profundo que usa uma modificação do algoritmo PPO para minimizar slowdown de jobs com máscara de ações, adicionando suporte a grandes espaços de ações ao sistema. Em nossos experimentos, nós avaliamos os efeitos de ruído nas estimativas de tempo de execução em nosso modelo, observando como ele se comporta tanto em clusters pequenos (64 processadores) quando em clusters grandes (163840 processadores). Nós também mostramos que nosso modelo é robusto a mudanças em carga de trabalho e nos tamanhos de clusters, demonstrando que a transferência de agentes entre clusters funcionam com mudanças de tamanho de cluster de até 10x, além de suportar mudanças de cargade trabalho sintético para seguir a execução de traços de sistemas reais. A abordagem de modelagem proposta possui melhor desempenho que outras da literatura, tornando-a viável para a criação de modelos de escalonamento robustos, transferíveis e capazes de aprender.