Publicação: Análise comparativa de algoritmos de escalonamento de workflows científicos em processadores heterogêneos
Carregando...
Tipo do documento
Data
Direito de acesso
Programa
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
Em computação de alto desempenho (HPC), algoritmos de escalonamento são decisivos
para transformar hardware em desempenho, custo e eficiência energética — aspecto crítico em cargas modernas que incluem o treinamento de modelos de aprendizado de
máquina, cada vez mais intensivas em recursos. Diferentemente de ambientes homogêneos (nós idênticos), clusters heterogêneos de CPUs/GPUs exibem variação de capacidade
de processamento e de comunicação; assim, a política de mapeamento e ordenação de tarefas torna-se central para minimizar filas, latências e ociosidade, reduzindo o tempo de
execução, o consumo de energia e, consequentemente, a pegada de CO2.
Neste trabalho foi comparado seis heurísticas clássicas de list scheduling — DLS, HEFT,
HEFT-LA, PEFT, IHEFT e IPEFT — em um pipeline reprodutível simulado, padronizando a interface de E/S, o gerador de DAGs e o cálculo de métricas para isolar o
efeito da lógica de decisão. Avaliamos instâncias de grande porte (256–4096 tarefas) derivadas de workflows científicos, em conjuntos de 8, 16 e 32 máquinas, medindo makespan,
balanceamento de carga, waiting time e energia.
Os resultados mostram que heurísticas com look-ahead (PEFT, IPEFT, HEFT-LA)
reduzem consistentemente makespan e waiting time em cenários com comunicação dominante; PEFT e IPEFT preservam a complexidade 𝑂(𝑉
2𝑃), ao passo que o HEFT-LA
apresenta complexidade assintótica superior. Sob baixa comunicação, HEFT permanece
competitivo. IHEFT e IPEFT mitigam lacunas de escalonamento e elevam a utilização.
Observamos um compromisso energia–desempenho: menor ociosidade tende a reduzir a
energia total, mesmo com leve aumento da potência média. Além disso, o DLS apresenta
ganhos de velocidade com o aumento de máquinas ao capturar paralelismo de forma mais
compute-bound, enquanto heurísticas com predição podem tornar-se mais sensíveis às barreiras de comunicação. Como artefatos, disponibilizamos implementações paper-faithful,
um gerador de casos com controle de semente e um pipeline para comparações futuras em
ambientes heterogêneos.
Abstract
In high-performance computing (HPC), scheduling algorithms are decisive to translate
hardware into performance, cost efficiency, and energy efficiency—an especially critical
concern for modern workloads such as machine learning training. Unlike homogeneous settings (identical nodes), heterogeneous CPU/GPU clusters vary in compute and
communication capabilities; thus, task mapping and ordering policies become central to
minimizing queues, latency, and idleness, thereby reducing runtime, energy, and the CO2
footprint.
This work compares six classic list scheduling heuristics—DLS, HEFT, HEFT-LA,
PEFT, IHEFT, and IPEFT—within a fully reproducible simulated pipeline that standardizes I/O interfaces, DAG generation, and metric computation to isolate decision-logic
effects. We evaluate large workflow-derived instances (256–4096 tasks) on sets of 8, 16,
and 32 machines, measuring makespan, load balance, waiting time, and energy.
Results indicate that look-ahead heuristics (PEFT, IPEFT, HEFT-LA) consistently
reduce makespan and waiting time in communication-dominated scenarios; PEFT and
IPEFT preserve 𝑂(𝑉
2𝑃) time complexity, whereas HEFT-LA incurs higher asymptotic cost. Under low communication, HEFT remains competitive. IHEFT and IPEFT
mitigate scheduling gaps and raise utilization. We observe an energy–performance tradeoff: curbing idleness often lowers total energy even with a slight rise in average power.
Additionally, DLS achieves speedups as machine count grows by exploiting computebound parallelism, while predictive heuristics become more sensitive to communication
bottlenecks. We release paper-faithful implementations, a seeded case generator, and a
comparison pipeline to support future studies in heterogeneous environments.
Palavras-chave
Computação de Alto Desempenho, Escalonamento de tarefas, DAG, Modelos de ML, LLM, Workflows científicos
Citação
MONTEIRO, Matheus Costa. Análise comparativa de algoritmos de escalonamento de workflows científicos em processadores heterogêneos. 2025. 140f . Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) – Universidade Federal de Uberlândia, Uberlândia, 2025.
DOI
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso Aberto