July  2015, 11(3): 867-886. doi: 10.3934/jimo.2015.11.867

Performance analysis of backup-task scheduling with deadline time in cloud computing

1. 

Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto 606-8501, Japan

2. 

Graduate School of Information Science, Nara Institute of Science and Technology, 8916-5 Takayama, Ikoma, Nara 630-0192

Received  October 2013 Revised  May 2014 Published  October 2014

In large-scale parallel job processing for cloud computing, a huge task is divided into subtasks, which are processed independently on a cluster of machines called workers. Since the task processing lasts until all the subtasks are completed, a slow worker machine makes the overall task-processing time long, degrading the task-level throughput. In order to alleviate the performance degradation, MapReduce conducts backup execution, in which the master node schedules the remaining in-progress subtasks when the whole task operation is close to completion. In this paper, we investigate the effect of backup tasks on the task-level throughput. We consider the backup-task scheduling in which a backup subtask for a worker starts when the subtask-processing time of the worker reaches the deadline time. We analyze the task-level processing-time distribution by considering the maximum subtask-processing time among workers. The task throughput and the amount of all the workers' processing times are derived when the worker-processing-time (WPT) follows a hyper-exponential, Weibull, and Pareto distribution. We also propose an approximate method to derive performance measures based on extreme value theory. The approximations are validated by Monte Carlo simulation. Numerical examples show that the performance improvement by backup tasks significantly depends on workers' processing time distribution.
Citation: Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial & Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867
References:
[1]

S. Ali, B. Eslamnour and Z. Shah, A case for on-machine load balancing,, Journal of Parallel and Distributed Computing, 71 (2011), 556.  doi: 10.1016/j.jpdc.2010.11.003.  Google Scholar

[2]

L. A. Barroso and U. Hölzle, The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines,, Morgan & Claypool, (2009).  doi: 10.2200/S00193ED1V01Y200905CAC006.  Google Scholar

[3]

W. Cirne, D. Paranhos, F. Brasileiro and L. F. W. Góes, On the efficacy, efficiency and emergent behavior of task replication in large distributed systems,, Parallel Computing, 33 (2007), 213.  doi: 10.1016/j.parco.2007.01.002.  Google Scholar

[4]

J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters,, Communications of the ACM, 51 (2008), 107.  doi: 10.1145/1327452.1327492.  Google Scholar

[5]

M. Dobber, R. V. D. Mei and G. Koole, Dynamic load balancing and job replication in a global-scale grid environment: A comparison,, IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207.  doi: 10.1109/TPDS.2008.61.  Google Scholar

[6]

P. Embrechets, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance,, Springer, (1997).  doi: 10.1007/978-3-642-33483-2.  Google Scholar

[7]

T. Hirai, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing,, Journal of Industrial and Management Optimization, 10 (2014), 113.  doi: 10.3934/jimo.2014.10.113.  Google Scholar

[8]

W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes in C,, 2nd edition, (1992).   Google Scholar

[9]

S. Resnick, Extreme Values, Regular Variation and Point Processes,, Springer Series in Operations Research and Financial Engineering. Springer, (2008).   Google Scholar

[10]

T. White, Hadoop: The Definitive Guide,, 2nd edition, (2008).   Google Scholar

[11]

K. Wolter, Stochastic Models for Fault Tolerance: Restart, Rejuvenation, and Checkpointing,, With a foreword by Aad van Moorsel. Springer, (2010).  doi: 10.1007/978-3-642-11257-7.  Google Scholar

show all references

References:
[1]

S. Ali, B. Eslamnour and Z. Shah, A case for on-machine load balancing,, Journal of Parallel and Distributed Computing, 71 (2011), 556.  doi: 10.1016/j.jpdc.2010.11.003.  Google Scholar

[2]

L. A. Barroso and U. Hölzle, The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines,, Morgan & Claypool, (2009).  doi: 10.2200/S00193ED1V01Y200905CAC006.  Google Scholar

[3]

W. Cirne, D. Paranhos, F. Brasileiro and L. F. W. Góes, On the efficacy, efficiency and emergent behavior of task replication in large distributed systems,, Parallel Computing, 33 (2007), 213.  doi: 10.1016/j.parco.2007.01.002.  Google Scholar

[4]

J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters,, Communications of the ACM, 51 (2008), 107.  doi: 10.1145/1327452.1327492.  Google Scholar

[5]

M. Dobber, R. V. D. Mei and G. Koole, Dynamic load balancing and job replication in a global-scale grid environment: A comparison,, IEEE Transactions on Parallel and Distributed Systems, 20 (2009), 207.  doi: 10.1109/TPDS.2008.61.  Google Scholar

[6]

P. Embrechets, C. Klüppelberg and T. Mikosch, Modelling Extremal Events for Insurance and Finance,, Springer, (1997).  doi: 10.1007/978-3-642-33483-2.  Google Scholar

[7]

T. Hirai, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing,, Journal of Industrial and Management Optimization, 10 (2014), 113.  doi: 10.3934/jimo.2014.10.113.  Google Scholar

[8]

W. H. Press, S. A. Teukolsky, W. T. Vetterling and B. P. Flannery, Numerical Recipes in C,, 2nd edition, (1992).   Google Scholar

[9]

S. Resnick, Extreme Values, Regular Variation and Point Processes,, Springer Series in Operations Research and Financial Engineering. Springer, (2008).   Google Scholar

[10]

T. White, Hadoop: The Definitive Guide,, 2nd edition, (2008).   Google Scholar

[11]

K. Wolter, Stochastic Models for Fault Tolerance: Restart, Rejuvenation, and Checkpointing,, With a foreword by Aad van Moorsel. Springer, (2010).  doi: 10.1007/978-3-642-11257-7.  Google Scholar

[1]

Shuyang Dai, Fengru Wang, Jerry Zhijian Yang, Cheng Yuan. A comparative study of atomistic-based stress evaluation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020322

[2]

Yining Cao, Chuck Jia, Roger Temam, Joseph Tribbia. Mathematical analysis of a cloud resolving model including the ice microphysics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 131-167. doi: 10.3934/dcds.2020219

[3]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020449

[4]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451

[5]

Pierre-Etienne Druet. A theory of generalised solutions for ideal gas mixtures with Maxwell-Stefan diffusion. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020458

[6]

Juan Pablo Pinasco, Mauro Rodriguez Cartabia, Nicolas Saintier. Evolutionary game theory in mixed strategies: From microscopic interactions to kinetic equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020051

[7]

Antoine Benoit. Weak well-posedness of hyperbolic boundary value problems in a strip: when instabilities do not reflect the geometry. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5475-5486. doi: 10.3934/cpaa.2020248

[8]

Mehdi Badsi. Collisional sheath solutions of a bi-species Vlasov-Poisson-Boltzmann boundary value problem. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2020052

[9]

Mokhtar Bouloudene, Manar A. Alqudah, Fahd Jarad, Yassine Adjabi, Thabet Abdeljawad. Nonlinear singular $ p $ -Laplacian boundary value problems in the frame of conformable derivative. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020442

[10]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

[11]

Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046

[12]

Serena Dipierro, Benedetta Pellacci, Enrico Valdinoci, Gianmaria Verzini. Time-fractional equations with reaction terms: Fundamental solutions and asymptotics. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 257-275. doi: 10.3934/dcds.2020137

[13]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336

[14]

Cuicui Li, Lin Zhou, Zhidong Teng, Buyu Wen. The threshold dynamics of a discrete-time echinococcosis transmission model. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020339

[15]

Awais Younus, Zoubia Dastgeer, Nudrat Ishaq, Abdul Ghaffar, Kottakkaran Sooppy Nisar, Devendra Kumar. On the observability of conformable linear time-invariant control systems. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020444

[16]

Hoang The Tuan. On the asymptotic behavior of solutions to time-fractional elliptic equations driven by a multiplicative white noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020318

[17]

Haixiang Yao, Ping Chen, Miao Zhang, Xun Li. Dynamic discrete-time portfolio selection for defined contribution pension funds with inflation risk. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020166

[18]

Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216

[19]

Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341

[20]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (58)
  • HTML views (0)
  • Cited by (2)

[Back to Top]