Localized Fault Recovery for Nested Fork-Join Programs
Localized Fault Recovery for Nested Fork-Join Programs
复制标题
嵌套 Fork-Join 程序的局部故障恢复
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Wenjing Ma
中科院分区：
文献类型：
--
作者：
Gokcen Kestor;S. Krishnamoorthy;Wenjing Ma
使用工作窃取计划的嵌套叉-Join程序可以自动平衡负载并适应执行环境中的更改。在本文中，我们设计了一种方法，可以从这些程序遇到的故障中有效恢复。具体而言，我们专注于在存在故障失败的情况下对任务空间的局部恢复。我们提出了一种方法，可以有效地跟踪，在窃取工作下，通过各种线程执行的工作之间的关系。此信息用于识别和安排要重新执行的任务，而不会干扰正常的任务执行。该算法精确地计算了丢失的工作，造成最小的重新定义开销，并可以从任意数量的失败中恢复。实验评估表明，在没有故障，与丢失工作相同的顺序的恢复开销的情况下，间接费用低，而恢复成本比替代策略要低得多。
Nested fork-join programs scheduled using work stealing can automatically balance load and adapt to changes in the execution environment. In this paper, we design an approach to efficiently recover from faults encountered by these programs. Specifically, we focus on localized recovery of the task space in the presence of fail-stop failures. We present an approach to efficiently track, under work stealing, the relationships between the work executed by various threads. This information is used to identify and schedule the tasks to be re-executed without interfering with normal task execution. The algorithm precisely computes the work lost, incurs minimal re-execution overhead, and can recover from an arbitrary number of failures. Experimental evaluation demonstrates low overheads in the absence of failures, recovery overheads on the same order as the lost work, and much lower recovery costs than alternative strategies.