Scalability limits of Bag-of-Tasks applications running on hierarchical platforms. (English) Zbl 1219.68063
Summary: Bag-of-Tasks 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. Each file may be input for more than one task. Examples of Bag-of-Tasks (BoT) applications include Monte Carlo simulations, massive searches (such as key breaking), image manipulation applications and data mining algorithms. A common framework to execute BoT applications is the master-slave topology, in which the user machine is used to control the execution of tasks. In this scenario, a large number of concurrent tasks competing for resources (e.g., CPU and communication links) severely limits application execution scalability. This paper is devoted to study the scalability of BoT applications running on multi-node systems (such as clusters and multi-clusters) organized as hierarchical platforms, considering several communication paradigms. Our study employs a set of experiments that involves the simulation of various large-scale platforms. The results presented provide important guidelines for improving the scalability of practical applications.
MSC:
| 68M14 | Distributed systems |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Adler, M.; Gong, Y.; Rosenberg, A. L.: On exploiting node-heterogeneous clusters optimally, Theory of computing systems 42, 465-487 (2008) · Zbl 1140.68004 · doi:10.1007/s00224-007-9001-1 |
| [2] | Barroso, L. A.; Hölzle, U.: The datacenter as a computer: an introduction to the design of warehouse-scale machines, Synthesis lectures on computer architecture (2009) |
| [3] | O. Beaumont, L. Carter, J. Ferrante, A. Legrand, L. Marchal, Y. Robert, Scheduling multiple bags of tasks on heterogeneous master–worker platforms: centralized versus distributed solutions, Research Report No 2005-45, École Normale Supérieure de Lyon, 2005. Available at: http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2005/RR2005-45.pdf. |
| [4] | Beaumont, Olivier; Carter, Larry; Ferrante, Jeanne; Legrand, Arnaud; Marchal, Loris; Robert, Yves: Centralized versus distributed schedulers for bag-of-tasks applications, IEEE transactions on parallel and distributed systems, 698-709 (2008) |
| [5] | Beaumont, O.; Legrand, A.; Robert, Y.: Scheduling divisible workloads on heterogeneous platforms, Parallel computing 29, No. 9, 1121-1152 (2003) |
| [6] | Berman, F.; Wolski, R.; Casanova, H.; Cirne, W.; Dail, H.; Faerman, M.; Figueira, S.; Hayes, J.; Obertelli, G.; Schopf, J.; Shao, G.; Smallen, S.; Spring, N.; Su, A.; Zagorodnov, D.: Adaptive computing on the grid using apples, IEEE transactions on parallel and distributed systems 14, No. 4, 369-382 (2003) |
| [7] | J.L. Bosque, L.P. Perez, Theoretical scalability analysis for heterogeneous clusters, in: Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, 2004. |
| [8] | H. Casanova, A. Legrand, M. Quinson, SimGrid: a generic framework for large-scale distributed experimentations, in: 10th IEEE International Conference on Computer Modelling and Simulation, UKSIM/EUROSIM’08. |
| [9] | H. Casanova, A. Legrand, D. Zagorodnov, F. Berman, Heuristics for scheduling parameter-sweep applications in grid environments, in: Proc. 9th Heterogeneous Computing Workshop, HCW’2000, 2000, pp. 349–363. |
| [10] | Cassandras, C.: Discrete event systems: modeling and performance analysis, (1993) |
| [11] | A. Chaintreau, Sharpness: a tight condition for throughput scalability, in: Proceeding of 15th International Colloquium on Structural Information and Communication Complexity, SIROCCO, June 2008. · Zbl 1143.68335 |
| [12] | Cheng, Y. -C.; Robertazzi, T.: Distributed computation for a tree-network with communication delay, IEEE transactions on aerospace and electronic systems 26, No. 3, 511-516 (1990) |
| [13] | Chen, Y.; Sun, X. -H.; Wu, M.: Algorithm-system scalability of heterogeneous computing, Journal of parallel and distributed computing 68, No. 11, 1403-1412 (2008) · Zbl 1243.68051 |
| [14] | W. Cirne, D. Paranhos, L. Costa, E. Santos-Neto, F. Brasileiro, J. Sauve, F.A.B. Silva, C.O. Barros, C. Silveira, Running bag-of-tasks applications on computational grids: the MyGrid approach, in: Proc. International Conference on Parallel Processing, ICPP’03, October 2003, pp. 407–416. |
| [15] | S. Ghemawat, H. Gobioff, S. Leung, The google file system, in: Proceeding of the 2003 ACM Symposium on Operating Systems Principles, 2003. |
| [16] | Giersch, A.; Robert, Y.; Vivien, F.: Scheduling task sharing files on heterogeneous master–slave platforms, Journal of systems architecture 52, No. 2, 88-104 (2006) |
| [17] | Grama, A.; Gupta, A.; Kumar, V.: Isoefficiency: measuring the scalability of parallel algorithms and architectures, IEEE parallel and distributed technology 1, No. 3, 12-21 (1993) |
| [18] | Hagerup, T.: Allocating independent tasks to parallel processors: an experimental study, Journal of parallel and distributed computing 47, No. 2, 185-197 (1997) |
| [19] | E. Heymann, M. Senar, E. Luque, M. Livny, Adaptive scheduling for master–worker applications on the computational grid, in: Proc. IEEE/ACM International Workshop on Grid Computing, GRID 2000, December 2000, pp. 214–227. · Zbl 1005.68678 |
| [20] | Torsten Hoefler, Christian Siebert, Wolfgang Rehm, A practically constant-time mpi broadcast algorithm for large-scale infiniband clusters with multicast, in: 2007 IEEE International Parallel and Distributed Processing Symposium, 2007, p. 285. |
| [21] | Iosup, A.; Jan, M.; Sonmez, O.; Epema, D.: The characteristics and performance of groups of jobs in grids, Lncs 4641, 382-393 (2007) |
| [22] | A. Iosup, O. Sonmez, S. Anoep, D. Epema, The performance of bags-of-tasks in large-scale distributed systems, in: High Performance Distributed Computing, HPDC’08, Boston, USA, 2008, pp. 97–108. |
| [23] | Kaya, K.; Aykanat, C.: Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master–slave environments, IEEE transactions on parallel and distributed systems 17, No. 8, 883-896 (2006) |
| [24] | Korpela, E.; Werthimer, D.; Anderson, D.; Cobb, J.; Lebofsky, M.: SETI@home-massively distributed computing for SETI, Computing in science engineering 3, No. 1, 78-83 (2001) |
| [25] | Kumar, V.; Rao, V. N.: Parallel depth-first search on multiprocessors part II: Analysis, International journal of parallel programming 16, No. 6, 501-519 (1987) · Zbl 0665.68049 |
| [26] | Lee, Y. C.; Zomaya, A. Y.: Practical scheduling of bag-of-tasks applications on grids with dynamic resilience, IEEE transactions on computers 56, No. 6, 815-825 (2007) · Zbl 1390.68135 |
| [27] | Li, K.: Parallel processing of divisible loads on partitionable static interconnection networks, Cluster computing 6, No. 1, 47-55 (2003) |
| [28] | J. Liu, A.R. Mamidala, D.K. Panda, Fast and scalable MPI-level broadcast using infiniband’s hardware multicast support, in: Proceedings of the 2004 IEEE International Parallel and Distributed Processing Symposium, 2004. |
| [29] | J. Mache, R. Broadhurst, J. Ely, Ray tracing on cluster computers, in: Intl. Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2000. |
| [30] | M. Maheswaran, S. Ali, H.J. Siegel, D. Hensgen, R.F. Freund, Dynamic matching and scheduling of a class of independent tasks onto heterogeneous computing systems, in: Proc. Heterogeneous Computing Workshop, HCW’99, 1999, pp. 30–44. |
| [31] | A.R. Mamidala, L. Chai, H.-W. Jin, D.K. Panda, Efficient SMP-aware MPI-level broadcast over infiniband’s hardware multicast, in: Proceedings of the 2006 IEEE International Parallel and Distributed Processing Symposium, 2006. |
| [32] | D. Paranhos, W. Cirne, F.V. Brasileiro, Trading cycles for information: using replication to schedule bag-of-tasks applications on computational grids, in: Proc. International Euro-Par Conference, June 2003. |
| [33] | L.P. Perez, J.L. Bosque, An efficiency and scalalabiltiy model for heterogeneous clusters, in: Proceedings of the 2001 IEEE International Symposium on Cluster Computing, 2001. |
| [34] | G. Romanazzi, P.K. Jimack, Parallel performance prediction for numerical codes in a multi-cluster environment, in: Proc. of the 2008 International MultiConference on Comp. Science and Information Technology, IMCSIT’08, 2008. |
| [35] | A.L. Rosenberg, R.C. Chiang, Toward understanding heterogeneity in computing, in: Proceedings of the 2010 IEEE International Parallel and Distributed Processing Symposium, 2010. |
| [36] | S.M. Sadjadi, S. Shimizu, J. Figueroa, R. Rangaswami, J. Delgado, H. Duran, X.J. Collazo-Mojica, A modeling approach for estimating execution time of long-running scientific applications, in: Proceedings of the 22nd IEEE International Symposium on Parallel and Distributed Processing, IPDPS’08, 2008. |
| [37] | Santos-Neto, E.; Cirne, W.; Brasileiro, F. V.; Lima, A.: Exploiting replication and data reuse to efficiently schedule data-intensive applications on grids, Lecture notes in computer science 3277, 210-232 (2004) |
| [38] | R. Schmidt, F. Pedone, Consistent main-memory database federations under deferred disk writes, in: Proceedings of the 24th IEEE Symposium on Reliable Distributed Systems, SRDS’05, 2005. |
| [39] | Senger, H.; Hruschka, E. R.; Silva, F. A. B.; Sato, L. M.; Bianchini, C. P.; Jerosch, B. F.: Exploiting idle cycles to execute data mining applications on clusters of pcs, Journal of systems and software 80, No. 5, 778-790 (2007) |
| [40] | H. Senger, F.A.B. Silva, W.M. Nascimento, Hierarchical scheduling of independent tasks with shared files, in: Proc. of the Sixth IEEE International Symposium on Cluster Computing and the Grid Workshops, IEEE/CCGRIDW’06, 2006. pp. 51–56. |
| [41] | Silva, F. A. B.; Carvalho, S.; Hruschka, E. R.: A scheduling algorithm for running data mining applications on the grid, Lecture notes in computer science 3419, 254-262 (2004) · Zbl 1096.68579 · doi:10.1007/b99409 |
| [42] | Silva, F. A. B.; Carvalho, S.; Senger, H.; Hruschka, E. R.; Farias, C. R. G.: Running data mining applications on the grid: a bag-of-tasks approach, Lecture notes in computer science 3044, 168-177 (2004) |
| [43] | Silva, F. A. B.; Senger, H.: Improving scalability of bag-of-tasks applications running on master–slave platforms, Parallel computing 35, No. 2, 57-71 (2009) |
| [44] | Sun, X.; Rover, D. T.: Scalability of parallel algorithm–machine combinations, IEEE transactions on parallel and distributed systems 5, No. 6, 599-613 (1994) |
| [45] | Thain, D.; Tannenbaum, T.; Livny, M.: Distributed computing in practice: the condor experience, Concurrency and computation: practice and experience 17, No. 2–4 (2005) |
| [46] | Träff, J. L.; Ripkea, A.: Optimal broadcast for fully connected processor-node networks, Journal of parallel and distributed computing 68, No. 7, 887-901 (2008) · Zbl 1243.68033 |
| [47] | White, S. W.; Torney, D. C.: Use of a workstation cluster for the physical mapping of chromosomes, SIAM news, 14-17 (1993) |
| [48] | Yang, Y.; Raadt, K.; Casanova, H.: Multiround algorithms for scheduling divisible loads, IEEE transactions on parallel and distributed systems 16, No. 11, 1092-1102 (2005) |
| [49] | Yero, E.; Henriques, M.: Speedup and scalabiltity analysis of master–slave applications on large heterogeneous clusters, Journal of parallel and distributed computing 67, 1155-1167 (2007) · Zbl 1124.68326 · doi:10.1016/j.jpdc.2007.04.015 |
| [50] | Zhang, X.; Yan, Y.; He, K.: Latency metric: an experimental metric for measuring and evaluating parallel program and architecture scalability, Journal of parallel and distributed computing 22, No. 3, 392-410 (1994) |
| [51] | Zhou, J.; Lin, X. -Y.; Chung, Y. -C.: Hardware supported multicast in fat-tree-based infiniband networks, Journal of supercomputing 40, 333-352 (2007) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
