Backup-Task Scheduling with Deadline Time in Cloud Computing
Graduate School of Information Science
Nara Institute of Science and Technology
COM1 Level 2
SR8, COM1-02-08
Abstract:
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 research, 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 follows a hyper-exponential, Weibull, and Pareto distribution. We also propose an approximate method to derive performance measures based on extreme value theory. Numerical examples show that the performance improvement by backup tasks significantly depends on workers' processing time distribution.
Biodata:
Shoji Kasahara was born in Hamamatsu City, Shizuoka Pref., Japan, on December 24, 1965. He received the B. Eng. degree from the Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto, Japan, in 1989. He received the M. Eng. and Dr. Eng. degrees from the Division of Applied Systems Science, Faculty of Engineering, Kyoto University in 1991 and 1996, respectively. He was with the Educational Center for Information Processing, Kyoto University from 1993 to 1997, as an Assistant Professor. In 1996, he was a visiting scholar of the University of North Carolina at Chapel Hill, NC, USA. He was also a visiting scholar of the University of Waterloo, Canada in July, 1996. From 1997 to 2005, he was with Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma, Nara, Japan. From 2005 to 2012, he was an Associate Professor of Department of Systems Science, Graduate School of Informatics, Kyoto University, Kyoto Japan. Since 2012, he has been a Professor of Graduate School of Information Science, Nara Institute of Science and Technology, Ikoma, Nara, Japan. His research interests include queueing theory and performance analysis of computer and communication systems.