Checkpointing Workflows for Fail-Stop Errors
Checkpointing Workflows for Fail-Stop Errors
复制标题
DOI：
10.1109/cluster.2017.14
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Li Han;Louis-Claude Canon;H. Casanova;Y. Robert;F. Vivien
中科院分区：
文献类型：
--
作者：
Li Han;Louis-Claude Canon;H. Casanova;Y. Robert;F. Vivien
我们考虑在并行计算平台上安排按定向的无环图（DAG）构造的工作流程应用程序的问题，该平台可能会发生故障停止故障。目的是最大程度地减少预期的整体执行时间或制造pan。解决此问题的解决方案包括在可用处理器上的工作流任务的时间表，并决定了哪些应用程序数据到CheckPoint到CheckPoint到稳定存储的决定，以减轻处理器故障的影响。对于一般dags，这个问题是无可救药的。实际上，鉴于解决方案，计算其预期的制造物仍然是一个困难的问题。为了应对这一挑战，我们考虑了限制的图形类别，最小的串联平行图（M-SPG）。事实证明，许多现实世界的工作流程应用程序自然构成为M-SPG。对于此类的图表，我们提出了一种递归列表安排算法，该算法利用M-SPG结构将子图分配给单个处理器，并使用动态编程来确定应检查这些子指法中的哪些任务。此外，可以使用任务权重的一阶近似和对2态概率概率DAGS的现有评估算法有效计算该算法产生的解决方案的预期MakePAN。我们评估了生产工作流程配置的算法的性能，将其与（i）所有应用程序数据进行检查点的方法进行了比较，该方法与今天执行大多数生产工作流程的标准方式相对应； （ii）一种未检查应用程序数据的方法。我们的结果表明，我们的算法在这两种方法之间取得了良好的折衷，从而使开销比前者更低，并且比后者更好地抵御了失败。
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.