論文

査読有り
2015年7月

PERFORMANCE ANALYSIS OF BACKUP-TASK SCHEDULING WITH DEADLINE TIME IN CLOUD COMPUTING

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION
  • Kyosuke Hashimoto
  • ,
  • Hiroyuki Masuyama
  • ,
  • Shoji Kasahara
  • ,
  • Yutaka Takahashi

11
3
開始ページ
867
終了ページ
886
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.3934/jimo.2015.11.867
出版者・発行元
AMER INST MATHEMATICAL SCIENCES-AIMS

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, Map Reduce 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.

リンク情報
DOI
https://doi.org/10.3934/jimo.2015.11.867
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000344081200010&DestApp=WOS_CPL
ID情報
  • DOI : 10.3934/jimo.2015.11.867
  • ISSN : 1547-5816
  • eISSN : 1553-166X
  • Web of Science ID : WOS:000344081200010

エクスポート
BibTeX RIS