Análise comparativa de algoritmos de escalonamento de workflows científicos em processadores 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.