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]

Vieri Benci, Marco Cococcioni. The algorithmic numbers in non-archimedean numerical computing environments. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1673-1692. doi: 10.3934/dcdss.2020449

[2]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[3]

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, 2021, 14 (5) : 1717-1746. doi: 10.3934/dcdss.2020451

[4]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Recent progresses in the theory of nonlinear nonlocal problems. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[5]

M. Mahalingam, Parag Ravindran, U. Saravanan, K. R. Rajagopal. Two boundary value problems involving an inhomogeneous viscoelastic solid. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1351-1373. doi: 10.3934/dcdss.2017072

[6]

Fritz Gesztesy, Helge Holden, Johanna Michor, Gerald Teschl. The algebro-geometric initial value problem for the Ablowitz-Ladik hierarchy. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 151-196. doi: 10.3934/dcds.2010.26.151

[7]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[8]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023

[9]

Jianping Gao, Shangjiang Guo, Wenxian Shen. Persistence and time periodic positive solutions of doubly nonlocal Fisher-KPP equations in time periodic and space heterogeneous media. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2645-2676. doi: 10.3934/dcdsb.2020199

[10]

John Leventides, Costas Poulios, Georgios Alkis Tsiatsios, Maria Livada, Stavros Tsipras, Konstantinos Lefcaditis, Panagiota Sargenti, Aleka Sargenti. Systems theory and analysis of the implementation of non pharmaceutical policies for the mitigation of the COVID-19 pandemic. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021004

[11]

Cécile Carrère, Grégoire Nadin. Influence of mutations in phenotypically-structured populations in time periodic environment. Discrete & Continuous Dynamical Systems - B, 2020, 25 (9) : 3609-3630. doi: 10.3934/dcdsb.2020075

[12]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[13]

Guillermo Reyes, Juan-Luis Vázquez. Long time behavior for the inhomogeneous PME in a medium with slowly decaying density. Communications on Pure & Applied Analysis, 2009, 8 (2) : 493-508. doi: 10.3934/cpaa.2009.8.493

[14]

Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems - A, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189

[15]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258

[16]

Linlin Li, Bedreddine Ainseba. Large-time behavior of matured population in an age-structured model. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2561-2580. doi: 10.3934/dcdsb.2020195

[17]

Tomáš Roubíček. An energy-conserving time-discretisation scheme for poroelastic media with phase-field fracture emitting waves and heat. Discrete & Continuous Dynamical Systems - S, 2017, 10 (4) : 867-893. doi: 10.3934/dcdss.2017044

[18]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[19]

Zengyun Wang, Jinde Cao, Zuowei Cai, Lihong Huang. Finite-time stability of impulsive differential inclusion: Applications to discontinuous impulsive neural networks. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2677-2692. doi: 10.3934/dcdsb.2020200

2019 Impact Factor: 1.366

Metrics

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

[Back to Top]