检索结果-内蒙古大学图书馆

Task-Level Checkpointing and Localized Recovery to Tolerate Permanent Node Failures for Nested Fork–Join Programs in Clusters

引用

SN Computer Science 2024年第3期5卷 320页

作者： Reitz, Lukas Fohry, Claudia Research Group Programming Languages/Methodologies University of Kassel Wilhelmshöher Allee 71-73 Kassel 34121 Germany

Exascale supercomputers consist of millions of processing units, and this number is still growing. Therefore, hardware failures, such as permanent node failures, become increasingly frequent. They can be tolerated with system-level Checkpoint/Restart, which saves the whole application state transparently and, if needed, restarts the application from the saved state;or with application-level checkpointing, which saves only relevant data via explicit calls in the program. The former approach requires no additional programming expense, whereas the latter is more efficient and allows to continue program execution after failures on the intact resources (localized shrinking recovery). An increasingly popular programming paradigm is asynchronous many-task (AMT) programming. Here, programmers identify parallel tasks, and a runtime system assigns the tasks to worker threads. Since tasks have clearly defined interfaces, the runtime system can automatically extract and save their interface data. This approach, called task-level checkpointing (TC), combines the respective strengths of system-level and application-level checkpointing. AMTs come in many variants, and so far, TC has only been applied to a few, rather simple variants. This paper considers TC for a different AMT variant: nested fork–join (NFJ) programs that run on clusters of multicore nodes under work stealing. We present the first TC scheme for this setting. It performs a localized shrinking recovery and can handle multiple node failures. In experiments with four benchmarks, we observed execution time overheads of around 44 % at 1536 workers, and negligible recovery costs. Additionally, we developed and experimentally validated a prediction model for the running times of the scheme. © The Author(s) 2024.

关键词： Asynchronous many-task programming Fault tolerance Task-level checkpointing Work stealing

来源：评论

学校读者我要写书评

暂无评论

Comparison of Load Balancing Schemes for Asynchronous Many-Task Runtimes 1

引用

14th International Conference on Parallel Processing and Applied Mathematics, PPAM 2022

作者： Reitz, Lukas Hardenbicker, Kai Fohry, Claudia Research Group Programming Languages/Methodologies University of Kassel Kassel Germany

ISBN: (数字)9783031304453

ISBN: (纸本)9783031304446

A popular approach to program scalable irregular applications is Asynchronous Many-Task (AMT) programming. Here, programs define tasks according to task models such as dynamic independent tasks (DIT) or nested fork-join (NFJ). We consider cluster AMTs, in which a runtime system maps the tasks to worker threads in multiple processes. Thereby, dynamic load balancing can be achieved via work-stealing or work-sharing. A well-performing work-stealing variant is the lifeline scheme. While previous implementations are restricted to single-worker processes, a recent hybrid extension combines the scheme with intra-process work-sharing between multiple workers. The hybrid scheme comes at the price of a higher complexity. This paper investigates whether this complexity is indispensable by contrasting the scheme with a pure work-stealing extension of the lifeline scheme introduced in the paper. In an experimental comparison based on independent DIT and NFJ implementations and three benchmarks, the pure work-stealing scheme is on a par or even outperforms the hybrid one by up to 3.8 %. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

关键词： Parallel programming

来源：评论

学校读者我要写书评

暂无评论

Checkpointing and localized recovery for nested fork-join programs

arXiv

引用

arXiv 2021年

作者： Fohry, Claudia Research Group Programming Languages / Methodologies University of Kassel Germany

While checkpointing is typically combined with a restart of the whole application, localized recovery permits all but the affected processes to continue. In task-based cluster programming, for instance, the application can then be finished on the intact nodes, and the lost tasks be reassigned. This extended abstract suggests to adapt a checkpointing and localized recovery technique that has originally been developed for independent tasks to nested fork-join programs. We consider a Cilk-like work stealing scheme with work-first policy in a distributed memory setting, and describe the required algorithmic changes. The original technique has checkpointing overheads below 1% and neglectable costs for recovery, we expect the new algorithm to achieve a similar performance. © 2021, CC BY.

关键词： Recovery

来源：评论

学校读者我要写书评

暂无评论

A Selective and Incremental Backup Scheme for Task Pools

A Selective and Incremental Backup Scheme for Task Pools

引用

International Conference on High Performance Computing and Simulation

作者： Claudia Fohry Jonas Posner Lukas Reitz Research Group Programming Languages/Methodologies University of Kassel

ISBN: (纸本)9781538678800

Checkpointing is a common approach to prevent loss of a program's state after permanent node failures. When it is performed on application-level, less data need to be saved. This paper suggests an uncoordinated application-level check-pointing technique for task pools. It selectively and incrementally saves only those tasks that have stayed in the pool during some period of time and that have not been saved before. The checkpoints are held in a resilient in-memory data store. Our technique applies to any task pool variant in which workers operate at the top of local pools, and work stealing operates at the bottom. Furthermore, the tasks must be free of side effects, and the final result must be calculated by reduction from individual task results. We implemented the technique for the lifeline-based global load balancing variant of task pools. This variant couples random victim selection with an overlay graph for termination detection. A fault-tolerant realization already exists in the form of a Java library, called JFT_GLB. It uses the APGAS and Hazelcast libraries underneath. Our implementation modifies JFT_GLB by replacing its nonselective checkpointing scheme with our new one. In experiments, we compared the overhead of the new scheme to that of JFT_GLB, with UTS, BC and two synthetic benchmarks. The new scheme required slightly more running time when local pools were small, and paid off otherwise.

关键词： Algorithms - Reliable Parallel Distributed Algorithms Algorithms - Fault Tolerance and Resilience in HPC Systems Algorithms - Load Balancing and Sharing Software and Middleware in HPC Systems - Libraries and programming Environments

来源：评论

学校读者我要写书评

暂无评论

Fault Tolerance for Lifeline-Based Global Load Balancing

引用

Journal of Software Engineering and Applications 2017年第13期10卷 925-958页

作者： Claudia Fohry Marco Bungart Paul Plock Research Group Programming Languages/Methodologies University of Kassel Kassel Germany

Fault tolerance has become an important issue in parallel computing. It is often addressed at system level, but application-level approaches receive increasing attention. We consider a parallel programming pattern, the task pool, and provide a fault-tolerant implementation in a library. Specifically, our work refers to lifeline-based global load balancing, which is an advanced task pool variant that is implemented in the GLB framework of the parallel programming language X10. The variant considers side effect-free tasks whose results are combined into a final result by reduction. Our algorithm is able to recover from multiple fail-stop failures. If recovery is not possible, it halts with an error message. In the algorithm, each worker regularly saves its local task pool contents in the main memory of a backup partner. Backups are updated for steals. After failures, the backup partner takes over saved copies and collects others. In case of multiple failures, invocations of the restore protocol are nested. We have implemented the algorithm by extending the source code of the GLB library. In performance measurements on up to 256 places, we observed an overhead between 0.5% and 30%. The particular value depends on the application’s steal rate and task pool size. Sources of performance overhead have been further analyzed with a logging component.

关键词： Fault Tolerance Task Pool Load Balancing GLB Resilient X10

来源：评论

学校读者我要写书评

暂无评论

Cooperation vs. coordination for lifeline-based global load balancing in APGAS 6

Cooperation vs. coordination for lifeline-based global load ...

引用

6th ACM SIGPLAN Workshop on X10, X10 2016

作者： Posner, Jonas Fohry, Claudia Research Group Programming Languages Methodologies University of Kassel Germany

ISBN: (纸本)9781450343862

Work stealing can be implemented in either a cooperative or a coordinated way. We compared the two approaches for lifelinebased global load balancing, which is the algorithm used by X10's Global Load Balancing framework GLB. We conducted our study with the APGAS library for Java, to which we ported GLB in a first step. Our cooperative variant resembles the original GLB framework, except that strict sequentialization is replaced by Java synchronization constructs such as critical sections. Our coordinated variant enables concurrent access to local task pools by using a split queue data structure. In experiments with modified versions of the UTS and BC benchmarks, the cooperative and coordinated APGAS variants had similar executions times, without a clear winner. Both variants outperformed the original GLB when compiled with Managed X10. Experiments were run on up to 128 nodes, to which we assigned up to 512 places. © 2016 ACM.

关键词： Java programming language

来源：评论

学校读者我要写书评

暂无评论

A Robust Fault Tolerance Scheme for Lifeline-Based Taskpools

A Robust Fault Tolerance Scheme for Lifeline-Based Taskpools

引用

International Conference on Parallel Processing Workshops (ICPPW)

作者： Claudia Fohry Marco Bungart Research Group Programming Languages / Methodologies University of Kassel Germany

ISBN: (纸本)9781509028269

Fault tolerance is of increasing importance for parallel computing. While often addressed at system level, application-level resilience techniques may be more efficient. In particular, it seems worthwhile to provide fault tolerant libraries for reusable patterns such as the task pool. We consider a task pool variant that uses cooperative work stealing, called the lifeline scheme. It is implemented in the GLB library of the PGAS programming language X10. Extending our own previous work, we present a fault-tolerance scheme for this setting, which is both communication-efficient and robust. Here, robustness denotes the ability to tolerate multiple coincident failures of interrelated workers. Our algorithm keeps two copies of important data, and tolerates almost all permanent place failures that leave one of the copies intact. For that, we nest execution of restore protocols. We implemented our algorithm within the GLB library. Performance measurements show a steal count dependent overhead of 5 to 40% during failure-free operation and a negligible overhead for restore.

关键词： Fault tolerance Fault tolerant systems Libraries Robustness Protocols Resilience Computer languages

来源：评论

学校读者我要写书评

暂无评论

Towards an efficient fault-tolerance scheme for GLB 5

Towards an efficient fault-tolerance scheme for GLB

引用

5th ACM SIGPLAN Workshop on X10, X10 2015

作者： Fohry, Claudia Bungart, Marco Posner, Jonas Research Group Programming Languages / Methodologies University of Kassel Germany

ISBN: (纸本)9781450335867

X10's Global Load Balancing framework GLB implements a userlevel task pool for inter-place load balancing. It is based on work stealing and deploys the lifeline algorithm. A single worker per place alternates between processing tasks and answering steal requests. We have devised an efficient fault-tolerance scheme for this algorithm, improving on a simpler resilience scheme from our own previous work. Among the base ideas of the new scheme are incremental backups of "stable" tasks and an actor-like communication structure. The paper reports on our ongoing work to extend the GLB framework accordingly. While details of the scheme are left out, we discuss implementation issues and preliminary experimental results.

关键词： Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Fault tolerance schemes for global load balancing in X10

引用

Scalable Computing 2015年第2期16卷 169-185页

作者： Fohry, Claudia Bungart, Marco Posner, Jonas Research Group Programming Languages / Methodologies University of Kassel Kassel Germany

Scalability postulates fault tolerance to be efficient. One approach handles permanent node failures at user level. It is supported by Resilient X10, a Partitioned Global Address Space language that throws an exception when a place fails. We consider task pools, which are a widely used pattern for load balancing of irregular applications, and refer to the variant that is implemented in the Global Load Balancing framework GLB of X10. Here, each worker maintains a private pool and supports cooperative work stealing. Victim selection and termination detection follow the lifeline scheme. Tasks may generate new tasks dynamically, are free of side-effects, and their results are combined by reduction. We consider a single worker per node, and assume that failures are rare and uncorrelated. The paper introduces two fault tolerance schemes. Both are based on regular backups of the local task pool contents, which are written to the main memory of another worker and updated in the event of stealing. The first scheme mainly relies on synchronous communication. The second scheme deploys asynchronous communication, and significantly improves on the first scheme's efficiency and robustness. Both schemes have been implemented by extending the GLB source code. Experiments were run with the Unbalanced Tree Search (UTS) and Betweenness Centrality benchmarks. For UTS on 128 nodes, for instance, we observed an overhead of about 81% with the synchronous scheme and about 7% with the asynchronous scheme. The protocol overhead for a place failure was negligible. © 2015 SCPE.

关键词： Fault tolerance

来源：评论

学校读者我要写书评

暂无评论

Fault-Tolerant Global Load Balancing in X10

Fault-Tolerant Global Load Balancing in X10

引用

International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC)

作者： Marco Bungart Claudia Fohry Jonas Posner Research Group Programming Languages/Methodologies University of Kassel Germany

Scalability postulates fault tolerance to be effective. We consider a user-level fault tolerance technique to cope with permanent node failures. It is supported by X10, one of the major Partitioned Global Address Space (PGAS) languages. In Resilient X10, an exception is thrown when a place (node) fails. This paper investigates task pools, which are often used by irregular applications to balance their load. We consider global load balancing with one worker per place. Each worker maintains a private task pool and supports cooperative work stealing. Tasks may generate new tasks dynamically, are free of side-effects, and their results are combined by reduction. Our first contribution is a task pool algorithm that can handle permanent place failures. It is based on snapshots that are regularly written to other workers and are updated in the event of stealing. Second, we implemented the algorithm in the Global Load Balancing framework GLB, which is part of the standard library of X10. We ran experiments with the Unbalanced Tree Search (UTS) and Between ness Centrality (BC) benchmarks. With 64 places on 4 nodes, for instance, we observed an overhead of about 4% for using fault-tolerant GLB instead of GLB. The protocol overhead for a place failure was neglectable.

关键词： Protocols Fault tolerance Fault tolerant systems Registers Load management Electronics packaging Data structures

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：