容错并行程序设计模型的研究与实现

The research is proposed under the backgrounds that computer architecture enters the parallelism age and the system reliability becomes an increasing concern. The proposal aims to develop a parallel programming model supporting fault tolerance. The task is the basic unit of scheduling, execution, fault detection and recovery in the proposed model which exploits task-level parallelism to achieve high performance and low overhead of fault tolerance. The proposed research focuses on: 1) Task grain fault detection and recovery. A buffer-commit computation model will be used for transient fault tolerance and application-level diskless checkpointing technique will be used for permanent fault tolerance. A discarding algorithm will be studied, which determines whether a processing element on which faults frequently occur should continue to be used or not. 2) A hierarchical and scalable task scheduling framework. For multi-core clusters, a fault-tolerant work-stealing scheduling scheme will be designed to exploit intra-node parallelism and support fault tolerance. An adaptive scheduling scheme which combines work-stealing and work-sharing will be used to exploit inter-node parallelism. 3) Task partitioning. The proposed model uses different initial partitioning approaches adaptively for three patterns of task parallelism, flat parallelism, recursive parallelism and irregular parallelism. Dynamic task splitting will be studied for parallel loops and divide-and-conquer applications. In addition, a runtime chunk splitting method will be used to achieve load balancing. To sum up, the proposed research incorporate fault-tolerance mechanisms into parallel programming model to deal with performance and reliability issues in application level.

本课题在计算机体系结构并行化的发展趋势和日益突出的容错需求两方面背景下提出，研究支持容错的并行程序设计模型。该模型以任务为基本单元进行调度、执行、错误检测和恢复，通过充分发掘并行性提高系统性能和降低容错开销。主要研究内容包括：1）任务粒度的错误检测和恢复机制，拟采用一种Buffer-Commit的计算模型支持瞬时错误的容忍，采用应用级无盘检查点实现永久错误的容忍，并研究对错误频发的计算单元的弃用算法；2）分层可扩展的任务调度框架，对多核集群系统，节点内采用容错的工作窃取调度策略，节点间采用工作窃取和工作共享相结合的自适应调度策略；3）任务划分，针对不同并行模式研究不同的初始划分方法，研究并行循环和分治应用在运行时的动态划分策略，以获得最佳的负载均衡，另外，对出错任务研究一种动态分割算法。总之，本课题在并行程序设计中融入对错误容忍的支持，兼顾系统性能和可靠性两个方面。

随着并行计算机系统规模的扩大，可靠性问题越来越突出，容错已成为软硬件系统设计中的一个重要问题。本课题以提高并行计算机系统性能和可靠性为目标，在基于任务的并行程序设计模型中融入错误检测和恢复机制，系统的研究支持容错的任务并行编程模型。课题组成员在为期三年的研究中取得了如下重要研究成果：1）提出了一个轻量级的Buffer-Commit计算模型来保证程序遇到错误时重新执行的正确性，在共享存储多核平台上，我们用一组并行循环测试程序检验了我们的技术；2）结合工作窃取和工作共享这两种动态任务调度策略，针对多核集群平台提出了一种自适应的层次化任务调度策略，该策略采用层次化的调度框架，在完成初始的静态任务分配后，任务首先在节点内动态调度以达到节点内各处理核之间的负载均衡，其次在节点间以工作共享或工作窃取的方式适时迁移，以平衡各计算节点的任务量；3）提出了容错工作窃取任务调度算法，采用双任务队列保存待执行任务和出错任务，充分发掘任务并行性来降低容错带来的任务冗余执行的开销；4）局域性是影响并行程序性能的一个重要因素，对此我们提出了访存敏感的任务映射策略，根据任务的访存特征选择不同映射算法，尽量将数据访问量大的任务映射到共享存储器周围，从而降低系统整体通信开销；5）整合上述技术，我们提出了支持容错的任务并行程序设计模型FT-TPP，实现了其运行时系统，实验表明FT-TPP相比其它容错技术有较低的性能开销。本课题的研究成果对并行编程模型的设计有重要的理论意义，对大规模系统可靠性的提高有一定的参考价值，在航空、航天等对系统可靠性要求较高的领域有潜在的应用价值。