American Institute of Mathematical Sciences

Advanced
  • Previous Article
    The impact of the $NT$-policy on the behaviour of a discrete-time queue with general service times
  • JIMO Home
  • This Issue
  • Next Article
    Analysis of an M/M/1 queueing system with impatient customers and a variant of multiple vacation policy
January  2014, 10(1): 113-129. doi: 10.3934/jimo.2014.10.113

Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing

Tsuguhito Hirai 1, , Hiroyuki Masuyama 2, , Shoji Kasahara 3, and  Yutaka Takahashi 2,

1. 

Graduate School of Informatics, Kyoto University, Yoshida-Hommachi, Sakyo-ku, Kyoto 606-8501, Japan
2. 

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

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

Received  September 2012 Revised  June 2013 Published  October 2013

In cloud computing, a large-scale parallel-distributed processing service is provided where a huge task is split into a number of subtasks and those subtasks are processed on a cluster of machines called workers. In such a processing service, a worker which takes a long time for processing a subtask makes the response time long (the issue of stragglers). One of efficient methods to alleviate this issue is to execute the same subtask by another worker in preparation for the slow worker (backup tasks). In this paper, we consider the efficiency of backup tasks. We model the task-scheduling server as a single-server queue, in which the server consists of a number of workers. When a task enters the server, the task is split into subtasks, and each subtask is served by its own worker and an alternative distinct worker. In this processing, we explicitly derive task processing time distributions for the two cases that the subtask processing time of a worker obeys Weibull or Pareto distribution. We compare the mean response time and the total processing time under backup-task scheduling with those under normal scheduling. Numerical examples show that the efficiency of backup-task scheduling significantly depends on workers' processing time distribution.
Keywords: task scheduling, queueing analysis., Cloud computing, parallel-distributed processing, backup tasks.
Mathematics Subject Classification: Primary: 60K25, 60J10; Secondary: 68M2.
Citation: Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of large-scale parallel-distributed processing with backup tasks for cloud computing. Journal of Industrial & Management Optimization, 2014, 10 (1) : 113-129. doi: 10.3934/jimo.2014.10.113
References:
[1]

M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica and M. Zaharia, A view of cloud computing,, Communications of the ACM, 53 (2010), 50.  doi: 10.1145/1721654.1721672.  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]

J. Dejun, G. Pierre and C.-H. Chi, EC2 performance analysis for resource provisioning of service-oriented applications,, Proc. Service-Oriented Computing: ICSOC/ServiceWave 2009 Workshops, 6275 (2010), 197.  doi: 10.1007/978-3-642-16132-2_19.  Google Scholar

[6]

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

[7]

D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, "Fundamentals of Queueing Theory,", $4^{th}$ edition, (2008).  doi: 10.1002/9781118625651.  Google Scholar

[8]

K. Xiong and H. Perros, Service performance and analysis in cloud computing,, Proc. 2009 IEEE Congress on Services Services - I, (2009), 693.  doi: 10.1109/SERVICES-I.2009.121.  Google Scholar

[9]

N. Yigitbasi, A. Iosup, D. Epema and S. Ostermann, C-Meter: A framework for performance analysis of computing clouds,, Proc. 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, (2009), 472.  doi: 10.1109/CCGRID.2009.40.  Google Scholar

show all references

References:
[1]

M. Armbrust, A. Fox, R. Griffith, A. D. Joseph, R. Katz, A. Konwinski, G. Lee, D. Patterson, A. Rabkin, I. Stoica and M. Zaharia, A view of cloud computing,, Communications of the ACM, 53 (2010), 50.  doi: 10.1145/1721654.1721672.  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]

J. Dejun, G. Pierre and C.-H. Chi, EC2 performance analysis for resource provisioning of service-oriented applications,, Proc. Service-Oriented Computing: ICSOC/ServiceWave 2009 Workshops, 6275 (2010), 197.  doi: 10.1007/978-3-642-16132-2_19.  Google Scholar

[6]

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

[7]

D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, "Fundamentals of Queueing Theory,", $4^{th}$ edition, (2008).  doi: 10.1002/9781118625651.  Google Scholar

[8]

K. Xiong and H. Perros, Service performance and analysis in cloud computing,, Proc. 2009 IEEE Congress on Services Services - I, (2009), 693.  doi: 10.1109/SERVICES-I.2009.121.  Google Scholar

[9]

N. Yigitbasi, A. Iosup, D. Epema and S. Ostermann, C-Meter: A framework for performance analysis of computing clouds,, Proc. 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, (2009), 472.  doi: 10.1109/CCGRID.2009.40.  Google Scholar

[1]

Karl-Peter Hadeler, Frithjof Lutscher. Quiescent phases with distributed exit times. Discrete & Continuous Dynamical Systems - B, 2012, 17 (3) : 849-869. doi: 10.3934/dcdsb.2012.17.849
[2]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017
[3]

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
[4]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361
[5]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225
[6]

Longxiang Fang, Narayanaswamy Balakrishnan, Wenyu Huang. Stochastic comparisons of parallel systems with scale proportional hazards components equipped with starting devices. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021004
[7]

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
[8]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024
[9]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[10]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1
[11]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367
[12]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[13]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056
[14]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[15]

Dan Wei, Shangjiang Guo. Qualitative analysis of a Lotka-Volterra competition-diffusion-advection system. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2599-2623. doi: 10.3934/dcdsb.2020197
[16]

Hailing Xuan, Xiaoliang Cheng. Numerical analysis and simulation of an adhesive contact problem with damage and long memory. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2781-2804. doi: 10.3934/dcdsb.2020205
[17]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137
[18]

Xiaoyi Zhou, Tong Ye, Tony T. Lee. Designing and analysis of a Wi-Fi data offloading strategy catering for the preference of mobile users. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021038
[19]

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

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (47)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences