BOUNDS ON THE SCALABILITY OF BAG-OF-TASKS APPLICATIONS RUNNING ON MASTER-SLAVE PLATFORMS
Abstract
Bag-of-Tasks applications are parallel applications composed of independent (i.e., embarrassingly parallel) tasks that 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. 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 the scalability. In this paper we studied the scalability of BoT applications running on multi-node systems (e.g. clusters and grids) organized as master-slave platforms, considering two communications paradigms: multiplexed connections and efficient broadcast. We prove that the lowest bound possible on the isoefficiency function for master-slave platforms is achievable by those platforms that have an O(1) efficient broadcast primitive available. We also analyze the impact of output file contention in scalability, under different assumptions. Our study employs a set of simulation experiments that confirms and extends the theoretical results (e.g. by simulating TCP links).
References
H. Casanova , Heuristics for Scheduling Parameter-Sweep Applications in Grid Environments, 9th Heterogeneous Computing workshop (HCW'2000) (IEEE Press, New York, 2000) pp. 349–363. Google Scholar- J. Systems Architecture 52(2), 88 (2006). Crossref, ISI, Google Scholar
- J. Systems and Software 80(5), 778 (2007). Crossref, ISI, Google Scholar
H. Senger , F. A. B. Silva and W. M. Nascimento , Hierarchical Scheduling of Independent Tasks with Shared Files, 6th IEEE International Symposium on Cluster Computing and the Grid Workshops (IEEE CS Press, New York, 2006) pp. 51–56. Google Scholar- Parallel Computing 35(2), 57 (2009). Crossref, ISI, Google Scholar
- Cluster Computing 6(1), 47 (2003). Crossref, Google Scholar
- IEEE Trans. on Aerospace and Electronic Sys. 31(2), 555 (1995). Crossref, ISI, Google Scholar
- IEEE Trans. on Aerospace and Electronic Syst. 26(3), 511 (1990). Crossref, ISI, Google Scholar
- O. Beaumont, L. Carter, J. Ferrante, A. Legrand, L. Marchal and Y. Robert, Scheduling multiple bags of tasks on heterogeneous master-worker platforms: centralized versus distributed solutions. Research Report No 2005-45, cole Normale Suprieure de Lyon, 2005. Available at , http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2005/RR2005-45.pdf . Google Scholar
- IEEE Transactions in Parallel and Distributed Systems 14(4), 369 (2003). Crossref, ISI, Google Scholar
W. Cirne , Running Bag-of-Tasks Applications on Computational Grids: The MyGrid Approach, International Conference on Parallel Processing (ICPP'03) (IEEE Press, New York, 2003) pp. 407–416. Google Scholar- J. Parallel and Distributed Computing 47(2), 185 (1997). Crossref, ISI, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 17(8), 883 (2006). Crossref, ISI, Google Scholar
M. Maheswaran , Dynamic Matching and Scheduling of a Class of Independent Tasks onto Heterogeneous Computing Systems, Heterogeneous Computing Workshop (HCW'99) (IEEE CS Press, New York, 1999) pp. 30–44. Google ScholarE. Santos-Neto , Exploiting Replication and Data Reuse to Efficiently Schedule Data-intensive Applications on Grids, Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP'04)3277,LNCS (Springer, Heidelberg, 2004) pp. 210–232. Google ScholarF. A. B. Silva , Running Data Mining Applications on the Grid: a Bag-of-Tasks Approach, Intl. Conf. Computational Science and its Applications (ICCSA 2004)3044,LNCS (Springer, Heidelberg, 2004) pp. 168–177. Google ScholarF. A. B. Silva , S. Carvalho and E. R. Hruschka , A Scheduling Algorithm for Running Data Mining Applications on the Grid, Euro-Par.3419,LNCS (Springer, Heidelberg, 2004) pp. 254–262. Google Scholar- IEEE Trans. on Computers 56(6), 815 (2007). Crossref, ISI, Google Scholar
-
A. Chaintreau , Sharpness: A tight condition for Throughput Scalability , 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO) ( 2008 ) . Google Scholar - IEEE Parallel and Dist. Tech. 1(3), 12 (1993). Crossref, Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 5(6), 599 (1994). Crossref, ISI, Google Scholar
- International Journal of Parallel Programming 16(6), 501 (1987). Crossref, ISI, Google Scholar
H. Casanova , A. Legrand and M. Quinson , SimGrid: a Generic Framework for Large-Scale Distributed Experiments, 10th IEEE International Conference on Computer Modeling and Simulation (IEEE Press, New York, 2008) pp. 126–131. Google Scholar-
R. Schmidt and F. Pedone , Consistent Main-Memory Database Federations under Deferred Disk Writes , 24th IEEE Symposium on Reliable Distributed Systems ( IEEE Press , New York , 2005 ) . Google Scholar -
J. Liu , A. R. Mamidala and D. K. Panda , Fast and Scalable MPI-Level Broadcast using InfiniBand's Hardware Multicast Support , Proc. of IEEE International Parallel and Distributed Processing Symposium ( 2004 ) . Google Scholar -
A. R. Mamidala , Efficient SMP-Aware MPI-Level Broadcast over InfiniBand's Hardware Multicast , Proc. of IEEE International Parallel and Distributed Processing Symposium ( 2006 ) . Google Scholar T. Hoefler , C. Siebert and W. Rehm , A practically constant-time MPI Broadcast Algorithm for large-scale InfiniBand Clusters with Multicast, Proc. IEEE International Parallel and Distributed Processing Symposium (2007) p. 285. Google Scholar- Journal of Parallel and Distributed Computing 68(7), 887 (2008). Crossref, ISI, Google Scholar
- D. Thain, T. Tannenbaum and M. Livny, Distributed computing in practice: the Condor experience. Concurrency and Computation: Practice and Experience, 17(2-4):323–356, John Wiley & Sons, Ltd. , http://dx.doi.org/10.1002/cpe.938 . Google Scholar
- IEEE Transactions on Parallel and Distributed Systems 19(5), 698 (2008). Crossref, ISI, Google Scholar
-
M. T. Goodrich and R. Tamassia , Algorithm Design: Foundations, Analysis, and Internet Examples ( John Wiley & Sons , 2002 ) . Google Scholar -
T. H. Cormen , Introduction to Algorithms , 2nd edn. ( The MIT Press , 2001 ) . Google Scholar A. Iosup , The Performance of Bags-of-Tasks in Large-Scale Distributed Systems, High Performance Distributed Computing, (HPDC'08) (Boston, USA, 2008) pp. 97–108. Google Scholar- Future Generation Computer Systems 24(7), 672 (2008). Crossref, ISI, Google Scholar
- F. A. B. da Silva, H. Senger, Scalability limits of Bag-of-Tasks applications running on hierarchical platforms, Journal of Parallel and Distributed Computing, In Press, Corrected Proof, Available online, DOI: 10.1016/j.jpdc.2011.01.002 . Google Scholar


