Escalabilidade de Aplicações Bag-of-Tasks em Plataformas Heterogêneas

  • Jaime Freire de Souza Universidade Federal de São Carlos
  • Hermes Senger Universidade Federal de São Carlos
  • Fabricio A. B. Silva Universidade Católica de Santos


Bag-of-Tasks (BoT) applications are parallel applications composed of independent (i.e., embarrassingly parallel) tasks, which do not communicate with each other, may depend upon one or more input files, and can be executed in any order. BoT applications are very frequent in several scientific areas, and it is the ideal application class for execution on large distributed computing systems composed of hundreds to many thousands of computational resources. This paper focusses on the scalability of BoT applications running on large heterogeneous distributed computing systems organized as a master-slave platform. The results demonstrate that heterogeneous master-slave platforms can achieve higher scalability than homogeneous platforms for the execution of BoT applications, when the computational power of individual nodes in the homogeneous platform is fixed. However, when individual nodes of the homogeneous platform can scale-up, experiments show that master-slave platforms can achieve near linear speedups.

Palavras-chave: Bag-of-Tasks, Computação Distribuída, Computação Paralela


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.
Como Citar

Selecione um Formato
FREIRE DE SOUZA, Jaime ; SENGER, Hermes ; SILVA, Fabricio A. B.. 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 do XXXVII Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos. Porto Alegre: Sociedade Brasileira de Computação, aug. 2019 . p. 664-677. ISSN 2177-9384. DOI: