Escalonador online de workflows sensível ao estado da rede
Resumo
A execução de workflows distribuídos depende tanto dos recursos computacionais quanto da eficiência da comunicação entre tarefas. Políticas tradicionais de escalonamento priorizam precedência e custo computacional, desconsiderando o impacto do posicionamento das tarefas sobre a rede. Este artigo apresenta um escalonador online consciente da rede, agnóstico à política base, que ajusta a alocação considerando métricas topológicas e informações históricas. Um parâmetro controla o peso da intervenção da camada de rede. Avaliada sobre as heurísticas EASY, HEFT, CPOP e PEFT em uma topologia Dragonfly, a proposta reduziu em até 32% os saltos, 38% os fluxos entre racks, 51% os fluxos entre grupos e 33% o custo de comunicação, com significância estatística (p < 0, 05).Referências
Arabnejad, H. and Barbosa, J. G. (2014). List scheduling algorithm for heterogeneous systems by an optimistic cost table. IEEE Transactions on Parallel and Distributed Systems, 25(3):682–694.
Canel, C., Madhavan, B., Sundaresan, S., Spring, N., Kannan, P., Zhang, Y., Lin, K., and Seshan, S. (2024). Understanding incast bursts in modern datacenters. In Proceedings of the 2024 ACM Internet Measurement Conference, pages 674–680. ACM.
Deelman, E., Vahi, K., Rynge, M., Mayani, R., da Silva, R. F., Papadimitriou, G., and Livny, M. (2019). The evolution of the pegasus workflow management software. Computing in Science & Engineering, 21(4):22–36.
Ghabashneh, E., Zhao, Y., Lumezanu, C., Spring, N., Sundaresan, S., and Rao, S. (2022). A microscopic view of bursts, buffer contention, and loss in data centers. In Proceedings of the 22nd ACM Internet Measurement Conference, pages 567–580. ACM.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287–326.
Jalaparti, V., Bodik, P., Menache, I., Rao, S., Makarychev, K., and Caesar, M. (2015). Network-aware scheduling for data-parallel jobs: Plan when you can. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, pages 407–420. ACM.
Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., and Vahi, K. (2013). Characterizing and profiling scientific workflows. Future Generation Computer Systems, 29(3):682–692.
Kim, J., Dally, W. J., Scott, S., and Abts, D. (2008). Technology-driven, highly-scalable dragonfly topology. In Proceedings of the 35th Annual International Symposium on Computer Architecture, pages 77–88. IEEE Computer Society.
Koslovski, G. P., Pereira, K., and Albuquerque, P. R. (2024). Dag-based workflows scheduling using actor–critic deep reinforcement learning. Future Generation Computer Systems, 150:354–363.
Kwok, Y.-K. and Ahmad, I. (1999). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406–471.
Li, W., Liu, J., Wang, S., Zhang, T., Zou, S., Hu, J., Jiang, W., and Huang, J. (2021). Survey on traffic management in data center network: From link layer to application layer. IEEE Access, 9:38427–38456.
Lifka, D. A. (1995). The anl/ibm sp scheduling system. In Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, pages 295–303, Santa Barbara, CA, USA. Springer.
Liu, F., Tong, J., Mao, J., Bohn, R., Messina, J., Badger, L., and Leaf, D. (2011). Nist cloud computing reference architecture. Special Publication 500-292, National Institute of Standards and Technology, Gaithersburg, MD, USA.
Liu, X. and Buyya, R. (2020). Resource management and scheduling in distributed stream processing systems: A taxonomy, review, and future directions. ACM Computing Surveys, 53(3):1–40.
Lu, P.-J., Lai, M.-C., and Chang, J.-S. (2022). A survey of high-performance interconnection networks in high-performance computer systems. Electronics, 11(9):1369.
Noormohammadpour, M. and Raghavendra, C. S. (2018). Datacenter traffic control: Understanding techniques and tradeoffs. IEEE Communications Surveys & Tutorials, 20(2):1492–1525.
Saeedizade, E. and Ashtiani, M. (2025). Scientific workflow scheduling algorithms in cloud environments: A comprehensive taxonomy, survey, and future directions. Journal of Scheduling, 28(1):1–63.
Shin, J., Arroyo, D., Tantawi, A. N., Wang, C., Youssef, A., and Nagi, R. (2024). Cloudnative workflow scheduling using a hybrid priority rule, dynamic resource allocation, and dynamic task partition. In Proceedings of the 2024 ACM Symposium on Cloud Computing, pages 830–846. ACM.
TOP500.org (2025). El capitan retains 1 as jupiter becomes europe’s first exascale system in the 66th top500 list. [link]. Accessed: 2026-06-14.
Topcuoglu, H., Hariri, S., and Wu, M.-Y. (2002). Performance-effective and lowcomplexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):260–274.
Vijayakumar, S., Madhavapeddy, A., and Kalyvianaki, E. (2024). Scheduling for reduced tail task latencies in highly utilized datacenters. In Proceedings of the 2024 ACM Symposium on Cloud Computing, pages 302–321. ACM.
Canel, C., Madhavan, B., Sundaresan, S., Spring, N., Kannan, P., Zhang, Y., Lin, K., and Seshan, S. (2024). Understanding incast bursts in modern datacenters. In Proceedings of the 2024 ACM Internet Measurement Conference, pages 674–680. ACM.
Deelman, E., Vahi, K., Rynge, M., Mayani, R., da Silva, R. F., Papadimitriou, G., and Livny, M. (2019). The evolution of the pegasus workflow management software. Computing in Science & Engineering, 21(4):22–36.
Ghabashneh, E., Zhao, Y., Lumezanu, C., Spring, N., Sundaresan, S., and Rao, S. (2022). A microscopic view of bursts, buffer contention, and loss in data centers. In Proceedings of the 22nd ACM Internet Measurement Conference, pages 567–580. ACM.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5:287–326.
Jalaparti, V., Bodik, P., Menache, I., Rao, S., Makarychev, K., and Caesar, M. (2015). Network-aware scheduling for data-parallel jobs: Plan when you can. In Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication, pages 407–420. ACM.
Juve, G., Chervenak, A., Deelman, E., Bharathi, S., Mehta, G., and Vahi, K. (2013). Characterizing and profiling scientific workflows. Future Generation Computer Systems, 29(3):682–692.
Kim, J., Dally, W. J., Scott, S., and Abts, D. (2008). Technology-driven, highly-scalable dragonfly topology. In Proceedings of the 35th Annual International Symposium on Computer Architecture, pages 77–88. IEEE Computer Society.
Koslovski, G. P., Pereira, K., and Albuquerque, P. R. (2024). Dag-based workflows scheduling using actor–critic deep reinforcement learning. Future Generation Computer Systems, 150:354–363.
Kwok, Y.-K. and Ahmad, I. (1999). Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computing Surveys, 31(4):406–471.
Li, W., Liu, J., Wang, S., Zhang, T., Zou, S., Hu, J., Jiang, W., and Huang, J. (2021). Survey on traffic management in data center network: From link layer to application layer. IEEE Access, 9:38427–38456.
Lifka, D. A. (1995). The anl/ibm sp scheduling system. In Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, pages 295–303, Santa Barbara, CA, USA. Springer.
Liu, F., Tong, J., Mao, J., Bohn, R., Messina, J., Badger, L., and Leaf, D. (2011). Nist cloud computing reference architecture. Special Publication 500-292, National Institute of Standards and Technology, Gaithersburg, MD, USA.
Liu, X. and Buyya, R. (2020). Resource management and scheduling in distributed stream processing systems: A taxonomy, review, and future directions. ACM Computing Surveys, 53(3):1–40.
Lu, P.-J., Lai, M.-C., and Chang, J.-S. (2022). A survey of high-performance interconnection networks in high-performance computer systems. Electronics, 11(9):1369.
Noormohammadpour, M. and Raghavendra, C. S. (2018). Datacenter traffic control: Understanding techniques and tradeoffs. IEEE Communications Surveys & Tutorials, 20(2):1492–1525.
Saeedizade, E. and Ashtiani, M. (2025). Scientific workflow scheduling algorithms in cloud environments: A comprehensive taxonomy, survey, and future directions. Journal of Scheduling, 28(1):1–63.
Shin, J., Arroyo, D., Tantawi, A. N., Wang, C., Youssef, A., and Nagi, R. (2024). Cloudnative workflow scheduling using a hybrid priority rule, dynamic resource allocation, and dynamic task partition. In Proceedings of the 2024 ACM Symposium on Cloud Computing, pages 830–846. ACM.
TOP500.org (2025). El capitan retains 1 as jupiter becomes europe’s first exascale system in the 66th top500 list. [link]. Accessed: 2026-06-14.
Topcuoglu, H., Hariri, S., and Wu, M.-Y. (2002). Performance-effective and lowcomplexity task scheduling for heterogeneous computing. IEEE Transactions on Parallel and Distributed Systems, 13(3):260–274.
Vijayakumar, S., Madhavapeddy, A., and Kalyvianaki, E. (2024). Scheduling for reduced tail task latencies in highly utilized datacenters. In Proceedings of the 2024 ACM Symposium on Cloud Computing, pages 302–321. ACM.
Publicado
03/11/2026
Como Citar
ALVARENGA, Victor Tavares; KOSLOVSKI, Guilherme Piêgas; PILLON, Maurício Aronne.
Escalonador online de workflows sensível ao estado da rede. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 27. , 2026, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 1-14.
DOI: https://doi.org/10.5753/sscad.2026.31659.
