跳到主要导航 跳到搜索 跳到主要内容

Checkpointing Workflows for Fail-Stop Errors

  • Li Han
  • , Louis Claude Canon
  • , Henri Casanova
  • , Yves Robert
  • , Frederic Vivien
  • Laboratoire LIP
  • Universite de Bourgogne Franche-Comte
  • University of Hawai'i at Mānoa
  • The University of Tennessee, Knoxville

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

摘要

We consider the problem of orchestrating the execution of workflow applications structured as Directed Acyclic Graphs (DAGs) on parallel computing platforms that are subject to fail-stop failures. The objective is to minimize expected overall execution time, or makespan. A solution to this problem consists of a schedule of the workflow tasks on the available processors and of a decision of which application data to checkpoint to stable storage, so as to mitigate the impact of processor failures. For general DAGs this problem is hopelessly intractable. In fact, given a solution, computing its expected makespan is still a difficult problem. To address this challenge, we consider a restricted class of graphs, Minimal Series-Parallel Graphs (M-SPGS). It turns out that many real-world workflow applications are naturally structured as M-SPGS. For this class of graphs, we propose a recursive list-scheduling algorithm that exploits the M-SPG structure to assign sub-graphs to individual processors, and uses dynamic programming to decide which tasks in these sub-gaphs should be checkpointed. Furthermore, it is possible to efficiently compute the expected makespan for the solution produced by this algorithm, using a first-order approximation of task weights and existing evaluation algorithms for 2-state probabilistic DAGs. We assess the performance of our algorithm for production workflow configurations, comparing it to (i) an approach in which all application data is checkpointed, which corresponds to the standard way in which most production workflows are executed today; and (ii) an approach in which no application data is checkpointed. Our results demonstrate that our algorithm strikes a good compromise between these two approaches, leading to lower checkpointing overhead than the former and to better resilience to failure than the latter.

源语言英语
主期刊名Proceedings - 2017 IEEE International Conference on Cluster Computing, CLUSTER 2017
出版商Institute of Electrical and Electronics Engineers Inc.
页487-497
页数11
ISBN(电子版)9781538623268
DOI
出版状态已出版 - 22 9月 2017
活动2017 IEEE International Conference on Cluster Computing, CLUSTER 2017 - Honolulu, 美国
期限: 5 9月 2017 → 8 9月 2017

丛书

姓名Proceedings - IEEE International Conference on Cluster Computing, ICCC
卷2017-September
ISSN(印刷版)1552-5244

会议

会议2017 IEEE International Conference on Cluster Computing, CLUSTER 2017
国家/地区美国
市Honolulu
时期5/09/17 → 8/09/17

学术指纹

探究 'Checkpointing Workflows for Fail-Stop Errors' 的科研主题。它们共同构成独一无二的学术指纹。

引用此