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

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

Abstract
Related Papers

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 and 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-58. doi: 10.1145/1721654.1721672.
[2]	L. A. Barroso and U. Hölzle, "The Datacenter as A Computer: An Introduction to the Design of Warehouse-Scale Machines," Morgan & Claypool, California, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006.
[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-234. doi: 10.1016/j.parco.2007.01.002.
[4]	J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107-113. doi: 10.1145/1327452.1327492.
[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, Lecture Notes in Computer Science, 6275 (2010), 197-207. doi: 10.1007/978-3-642-16132-2_19.
[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-218. doi: 10.1109/TPDS.2008.61.
[7]	D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, "Fundamentals of Queueing Theory," $4^{th}$ edition, John Wiley & Sons, New Jersey, 2008. doi: 10.1002/9781118625651.
[8]	K. Xiong and H. Perros, Service performance and analysis in cloud computing, Proc. 2009 IEEE Congress on Services Services - I, (2009), 693-700. doi: 10.1109/SERVICES-I.2009.121.
[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-477. doi: 10.1109/CCGRID.2009.40.

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-58. doi: 10.1145/1721654.1721672.
[2]	L. A. Barroso and U. Hölzle, "The Datacenter as A Computer: An Introduction to the Design of Warehouse-Scale Machines," Morgan & Claypool, California, 2009. doi: 10.2200/S00193ED1V01Y200905CAC006.
[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-234. doi: 10.1016/j.parco.2007.01.002.
[4]	J. Dean and S. Ghemawat, MapReduce: Simplified data processing on large clusters, Communications of the ACM, 51 (2008), 107-113. doi: 10.1145/1327452.1327492.
[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, Lecture Notes in Computer Science, 6275 (2010), 197-207. doi: 10.1007/978-3-642-16132-2_19.
[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-218. doi: 10.1109/TPDS.2008.61.
[7]	D. Gross, J. F. Shortle, J. M. Thompson and C. M. Harris, "Fundamentals of Queueing Theory," $4^{th}$ edition, John Wiley & Sons, New Jersey, 2008. doi: 10.1002/9781118625651.
[8]	K. Xiong and H. Perros, Service performance and analysis in cloud computing, Proc. 2009 IEEE Congress on Services Services - I, (2009), 693-700. doi: 10.1109/SERVICES-I.2009.121.
[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-477. doi: 10.1109/CCGRID.2009.40.

[1]	Kyosuke Hashimoto, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance analysis of backup-task scheduling with deadline time in cloud computing. Journal of Industrial and Management Optimization, 2015, 11 (3) : 867-886. doi: 10.3934/jimo.2015.11.867
[2]	Tsuguhito Hirai, Hiroyuki Masuyama, Shoji Kasahara, Yutaka Takahashi. Performance optimization of parallel-distributed processing with checkpointing for cloud environment. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1423-1442. doi: 10.3934/jimo.2018014
[3]	Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1515-1526. doi: 10.3934/dcdss.2019104
[4]	Ji-Bo Wang, Bo Zhang, Hongyu He. A unified analysis for scheduling problems with variable processing times. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1063-1077. doi: 10.3934/jimo.2021008
[5]	Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041
[6]	Xuena Yan, Shunfu Jin, Wuyi Yue, Yutaka Takahashi. Performance analysis and system optimization of an energy-saving mechanism in cloud computing with correlated traffic. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3133-3154. doi: 10.3934/jimo.2021106
[7]	Jiping Tao, Zhijun Chao, Yugeng Xi. A semi-online algorithm and its competitive analysis for a single machine scheduling problem with bounded processing times. Journal of Industrial and Management Optimization, 2010, 6 (2) : 269-282. doi: 10.3934/jimo.2010.6.269
[8]	Jinsong Xu. Reversible hidden data access algorithm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1219-1232. doi: 10.3934/dcdss.2019084
[9]	Serap Ergün, Bariş Bülent Kırlar, Sırma Zeynep Alparslan Gök, Gerhard-Wilhelm Weber. An application of crypto cloud computing in social networks by cooperative game theory. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1927-1941. doi: 10.3934/jimo.2019036
[10]	Weidong Bao, Haoran Ji, Xiaomin Zhu, Ji Wang, Wenhua Xiao, Jianhong Wu. ACO-based solution for computation offloading in mobile cloud computing. Big Data & Information Analytics, 2016, 1 (1) : 1-13. doi: 10.3934/bdia.2016.1.1
[11]	Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259
[12]	Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132
[13]	Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174
[14]	Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial and Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767
[15]	Yicheng Liu, Yipeng Chen, Jun Wu, Xiao Wang. Periodic consensus in network systems with general distributed processing delays. Networks and Heterogeneous Media, 2021, 16 (1) : 139-153. doi: 10.3934/nhm.2021002
[16]	Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial and Management Optimization, 2020, 16 (1) : 371-386. doi: 10.3934/jimo.2018157
[17]	Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613
[18]	Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097
[19]	Arminda Moreno-Díaz, Gabriel de Blasio, Moreno-Díaz Jr.. Distributed, layered and reliable computing nets to represent neuronal receptive fields. Mathematical Biosciences & Engineering, 2014, 11 (2) : 343-361. doi: 10.3934/mbe.2014.11.343
[20]	Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2022, 18 (6) : 3807-3830. doi: 10.3934/jimo.2021124

2021 Impact Factor: 1.411

Tools

Metrics

Other articles
by authors

on AIMS
Tsuguhito Hirai Hiroyuki Masuyama Shoji Kasahara Yutaka Takahashi
on Google Scholar
Tsuguhito Hirai Hiroyuki Masuyama Shoji Kasahara Yutaka Takahashi

[Back to Top]