Escalabilidade de Aplicações Bag-of-Tasks em Plataformas Heterogêneas
Resumo
Aplicações Bag-of-Tasks (BoT) são aplicações paralelas compostas de tarefas independentes (ou seja, embaraçosamente paralelas), que não se comunicam entre si, podem depender de um ou mais arquivos de entrada e podem ser executadas em qualquer ordem. As aplicações BoT são muito frequentes em diversas áreas e comumente executadas em grandes sistemas de computação distribuída, como nas grades computacionais ou na nuvem. Este trabalho estuda a escalabilidade de aplicações BoT executando em grandes sistemas de computação distribuída heterogêneos organizados como uma plataforma mestre-escravo. Os resultados mostram que plataformas mestre-escravo heterogêneas podem alcançar limites de escalabilidade mais altos que as plataformas homogêneas para a execução de aplicações BoT, quando o poder computacional dos nós individuais da plataforma homogênea é fixo. No entanto, quando nós individuais da plataforma homogênea podem escalar verticalmente, é mostrado neste trabalho que plataformas homogêneas apresentam escalabilidade próxima do linear.
Palavras-chave:
Bag-of-Tasks, Computação Distribuída, Computação Paralela
Referências
Yahya Al-Dhuraibi, Fawaz Paraiso, Nabil Djarallah, and Philippe Merle. Elasticity in Cloud Computing: State of the Art and Research Challenges. IEEE Transactions on Services Computing (TSC), 11(2):430–447, March 2018.
Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand, Loris Marchal, and Yves Robert. Centralized versus distributed schedulers for bag-of-tasks applications. IEEE Transactions on Parallel and Distributed Systems, 19(5):698–709, 2008.
Olivier Beaumont, Arnaud Legrand, and Yves Robert. Scheduling divisible workloads on heterogeneous platforms. Parallel Computing, 29(9):1121–1152, 2003.
Francine Berman, Richard Wolski, Henri Casanova, Walfredo Cirne, Holly Dail, Marcio Faerman, Silvia Figueira, Jim Hayes, Graziano Obertelli, Jennifer Schopf, et al. Adaptive computing on the grid using apples. IEEE Transactions on Parallel and Distributed Systems, 14(4):369–382, 2003.
Jose L. Bosque, Oscar D. Robles, Pablo Toharia, and Luis Pastor. Evaluating scalability in heterogeneous systems. The Journal of Supercomputing, 58(3):367–375, Dec 2011.
Jose Luis Bosque and Luis Pastor Perez. Theoretical scalability analysis for heterogeneous clusters. In IEEE International Symposium on Cluster Computing and the Grid, 2004. (CCGrid), pages 285–292. IEEE, 2004.
M. Carvalho and F. Brasileiro. A user-based model of grid computing workloads. In 2012 ACM/IEEE 13th Intl. Conf. on Grid Computing, pages 40–48, Sept 2012.
Henri Casanova, Arnaud Giersch, Arnaud Legrand, Martin Quinson, and Frédéric Suter. Versatile, scalable, and accurate simulation of distributed applications and platforms. Journal of Parallel and Distributed Computing, 74(10):2899–2917, June 2014.
Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov, and Francine Berman. Heuristics for scheduling parameter sweep applications in grid environments. In 9th IEEE Heterogeneous Computing Workshop.(HCW 2000), pages 349–363. IEEE, 2000.
Walfredo Cirne, Daniel Paranhos, Lauro Costa, Elizeu Santos-Neto, Francisco Brasileiro, Jacques Sauve, Fabricio AB Silva, Carla O Barros, and Cirano Silveira. Running bag-of-tasks applications on computational grids: The mygrid approach. In International Conference on Parallel Processing (ICPP), pages 407–416. IEEE, 2003.
Fabricio A. B. da Silva and Hermes Senger. Improving scalability of bag-of-tasks applications running on master–slave platforms. Parallel Computing, 35(2):57–71, 2009.
Fabricio A. B. da Silva and Hermes Senger. Scalability analysis of large distributed computing systems. In Grid Computing: techniques and future prospects. Nova Science Publishers, 2015.
Fabricio A.B. da Silva and Hermes Senger. Scalability limits of bag-of-tasks applications running on hierarchical platforms. J. Parallel and Distributed Computing, 71(6):788–801, 2011.
Rafael Ferreira da Silva and Tristan Glatard. A science-gateway workload archive to study pilot jobs, user activity, bag of tasks, task sub-steps, and workflow executions. In European Conference on Parallel Processing, pages 79–88. Springer, 2012.
Marcelo Rodrigo de Castro, Catherine dos Santos Tostes, Alberto MR D´avila, Hermes Senger, and Fabricio AB da Silva. Sparkblast: scalable blast processing using inmemory operations. BMC bioinformatics, 18(1):318, 2017.
Arnaud Giersch, Yves Robert, and Frédéric Vivien. Scheduling tasks sharing files on heterogeneous master–slave platforms. J. Systems Architecture, 52(2):88–104, 2006.
Ananth Y Grama, Anshul Gupta, and Vipin Kumar. Isoefficiency: Measuring the scalability of parallel algorithms and architectures. IEEE concurrency, 1(3):12–21, 1993.
Eduardo Javier Huerta Yero and Marco Aurélio Amaral Henriques. Speedup and scalability analysis of master–slave applications on large heterogeneous clusters. Journal of Parallel and Distributed Computing, 67(11):1155–1167, 2007.
Alexandru Iosup, Ozan Sonmez, Shanny Anoep, and Dick Epema. The performance of bags-of-tasks in large-scale distributed systems. In Proc.17th International Symposium on High Performance Distributed Computing, pages 97–108. ACM, 2008.
Vipin Kumar and V Nageshwara Rao. Parallel depth first search. part ii. analysis. International Journal of Parallel Programming, 16(6):501–519, 1987.
Simon McIntosh-Smith, James Price, Tom Deakin, and Andrei Poenaru. Comparative benchmarking of the first generation of hpc-optimised arm processors on isambard. Concurrency and Computation Practice and Experience - Special Issue on the Cray User Group, pages –, 2018 (to appear).
Luis Pastor and José L Bosque. An efficiency and scalability model for heterogeneous clusters. In Intl. Conf. Cluster Computing (CLUSTER), pages 427–427. IEEE, 2001.
Arnold L Rosenberg and Ron C Chiang. Toward understanding heterogeneity in computing. In Intl. Symp. Parallel & Dist. Processing (IPDPS), pages 1–10. IEEE, 2010.
Arnold L Rosenberg and Ron C Chiang. Heterogeneity in computing: Insights from a worksharing scheduling problem. International Journal of Foundations of Computer Science, 22(06):1471–1493, 2011.
Hermes Senger and Fabricio A. B. da Silva. Bounds on the scalability of bag-of-tasks applications running on master-slave platforms. Paral. Proc. Letters, 22(02), 2012.
Hermes Senger, Eduardo R Hruschka, Fabr´ıcio AB Silva, Liria M Sato, Calebe P Bianchini, and Bruno F Jerosch. Exploiting idle cycles to execute data mining applications on clusters of pcs. Journal of Systems and Software, 80(5):778–790, 2007.
Xian-He Sun and Diane T Rover. Scalability of parallel algorithm-machine combinations. IEEE Transactions on Parallel and Distributed Systems, 5(6):599–613, 1994.
Long Thai, Blesson Varghese, and Adam Barker. A survey and taxonomy of resource optimisation for executing bag-of-task applications on public clouds. Future Generation Computer Systems, 82:1 – 11, 2018.
Olivier Beaumont, Larry Carter, Jeanne Ferrante, Arnaud Legrand, Loris Marchal, and Yves Robert. Centralized versus distributed schedulers for bag-of-tasks applications. IEEE Transactions on Parallel and Distributed Systems, 19(5):698–709, 2008.
Olivier Beaumont, Arnaud Legrand, and Yves Robert. Scheduling divisible workloads on heterogeneous platforms. Parallel Computing, 29(9):1121–1152, 2003.
Francine Berman, Richard Wolski, Henri Casanova, Walfredo Cirne, Holly Dail, Marcio Faerman, Silvia Figueira, Jim Hayes, Graziano Obertelli, Jennifer Schopf, et al. Adaptive computing on the grid using apples. IEEE Transactions on Parallel and Distributed Systems, 14(4):369–382, 2003.
Jose L. Bosque, Oscar D. Robles, Pablo Toharia, and Luis Pastor. Evaluating scalability in heterogeneous systems. The Journal of Supercomputing, 58(3):367–375, Dec 2011.
Jose Luis Bosque and Luis Pastor Perez. Theoretical scalability analysis for heterogeneous clusters. In IEEE International Symposium on Cluster Computing and the Grid, 2004. (CCGrid), pages 285–292. IEEE, 2004.
M. Carvalho and F. Brasileiro. A user-based model of grid computing workloads. In 2012 ACM/IEEE 13th Intl. Conf. on Grid Computing, pages 40–48, Sept 2012.
Henri Casanova, Arnaud Giersch, Arnaud Legrand, Martin Quinson, and Frédéric Suter. Versatile, scalable, and accurate simulation of distributed applications and platforms. Journal of Parallel and Distributed Computing, 74(10):2899–2917, June 2014.
Henri Casanova, Arnaud Legrand, Dmitrii Zagorodnov, and Francine Berman. Heuristics for scheduling parameter sweep applications in grid environments. In 9th IEEE Heterogeneous Computing Workshop.(HCW 2000), pages 349–363. IEEE, 2000.
Walfredo Cirne, Daniel Paranhos, Lauro Costa, Elizeu Santos-Neto, Francisco Brasileiro, Jacques Sauve, Fabricio AB Silva, Carla O Barros, and Cirano Silveira. Running bag-of-tasks applications on computational grids: The mygrid approach. In International Conference on Parallel Processing (ICPP), pages 407–416. IEEE, 2003.
Fabricio A. B. da Silva and Hermes Senger. Improving scalability of bag-of-tasks applications running on master–slave platforms. Parallel Computing, 35(2):57–71, 2009.
Fabricio A. B. da Silva and Hermes Senger. Scalability analysis of large distributed computing systems. In Grid Computing: techniques and future prospects. Nova Science Publishers, 2015.
Fabricio A.B. da Silva and Hermes Senger. Scalability limits of bag-of-tasks applications running on hierarchical platforms. J. Parallel and Distributed Computing, 71(6):788–801, 2011.
Rafael Ferreira da Silva and Tristan Glatard. A science-gateway workload archive to study pilot jobs, user activity, bag of tasks, task sub-steps, and workflow executions. In European Conference on Parallel Processing, pages 79–88. Springer, 2012.
Marcelo Rodrigo de Castro, Catherine dos Santos Tostes, Alberto MR D´avila, Hermes Senger, and Fabricio AB da Silva. Sparkblast: scalable blast processing using inmemory operations. BMC bioinformatics, 18(1):318, 2017.
Arnaud Giersch, Yves Robert, and Frédéric Vivien. Scheduling tasks sharing files on heterogeneous master–slave platforms. J. Systems Architecture, 52(2):88–104, 2006.
Ananth Y Grama, Anshul Gupta, and Vipin Kumar. Isoefficiency: Measuring the scalability of parallel algorithms and architectures. IEEE concurrency, 1(3):12–21, 1993.
Eduardo Javier Huerta Yero and Marco Aurélio Amaral Henriques. Speedup and scalability analysis of master–slave applications on large heterogeneous clusters. Journal of Parallel and Distributed Computing, 67(11):1155–1167, 2007.
Alexandru Iosup, Ozan Sonmez, Shanny Anoep, and Dick Epema. The performance of bags-of-tasks in large-scale distributed systems. In Proc.17th International Symposium on High Performance Distributed Computing, pages 97–108. ACM, 2008.
Vipin Kumar and V Nageshwara Rao. Parallel depth first search. part ii. analysis. International Journal of Parallel Programming, 16(6):501–519, 1987.
Simon McIntosh-Smith, James Price, Tom Deakin, and Andrei Poenaru. Comparative benchmarking of the first generation of hpc-optimised arm processors on isambard. Concurrency and Computation Practice and Experience - Special Issue on the Cray User Group, pages –, 2018 (to appear).
Luis Pastor and José L Bosque. An efficiency and scalability model for heterogeneous clusters. In Intl. Conf. Cluster Computing (CLUSTER), pages 427–427. IEEE, 2001.
Arnold L Rosenberg and Ron C Chiang. Toward understanding heterogeneity in computing. In Intl. Symp. Parallel & Dist. Processing (IPDPS), pages 1–10. IEEE, 2010.
Arnold L Rosenberg and Ron C Chiang. Heterogeneity in computing: Insights from a worksharing scheduling problem. International Journal of Foundations of Computer Science, 22(06):1471–1493, 2011.
Hermes Senger and Fabricio A. B. da Silva. Bounds on the scalability of bag-of-tasks applications running on master-slave platforms. Paral. Proc. Letters, 22(02), 2012.
Hermes Senger, Eduardo R Hruschka, Fabr´ıcio AB Silva, Liria M Sato, Calebe P Bianchini, and Bruno F Jerosch. Exploiting idle cycles to execute data mining applications on clusters of pcs. Journal of Systems and Software, 80(5):778–790, 2007.
Xian-He Sun and Diane T Rover. Scalability of parallel algorithm-machine combinations. IEEE Transactions on Parallel and Distributed Systems, 5(6):599–613, 1994.
Long Thai, Blesson Varghese, and Adam Barker. A survey and taxonomy of resource optimisation for executing bag-of-task applications on public clouds. Future Generation Computer Systems, 82:1 – 11, 2018.
Publicado
06/05/2019
Como Citar
DE SOUZA, Jaime Freire; DA SILVA, Fabrício Alves Barbosa; SENGER, Hermes.
Escalabilidade de Aplicações Bag-of-Tasks em Plataformas Heterogêneas. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 37. , 2019, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2019
.
p. 664-677.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2019.7394.
