面向容错需求的可延展并行任务调度研究

Reliability and efficiency are two key criteria of computer systems. Nowadays taking into full account both the reliability and efficiency is an important research topic. This project studies scheduling malleable parallel jobs with fault-tolerance requirement. We first leverage the checking point scheme to achieve fault tolerance. Based on such fault-tolerance scheme, we then utilize the malleable parallel job’s property that supports reallocating computing resources during the running time to study the scheduling problem under different job models (e.g., Non-clairvoyant, Clairvoyant): 1) without any failure, we concatenate the price of using checking point fault-tolerance scheme to design scheduling algorithms and analyze their competitive ratios; 2) to deal with failure, we first design backups’ placement and enabling algorithms and then propose and analyze scheduling algorithms; 3) aiming at failure recovery, we first propose scheduling algorithms from the global and local view and then compare and analyze them respectively. From this research project, we can not only obtain new algorithms for scheduling malleable parallel jobs with fault-tolerance requirement but also achieve new theoretical knowledge on approximate scheduling algorithms. Hence，this work is fundamental for us to design high efficiency and robust computer systems.

可靠性与高效性是计算机系统的两个关键维度。统筹考虑系统可靠性与高效性是当前重要研究方向。本项目面向容错需求研究可延展并行任务调度。我们拟采用检查点备份机制实现容错，然后结合该容错机制并利用可延展并行任务在运行过程中支持动态调整计算资源的特性，分别在不同任务模型下（Non-clairvoyant, Clairvoyant）研究优化调度性能：1）针对无失效，结合设立检查点计算代价设计近似调度算法并分析竞争比；2）针对失效场景，设计备份放置和启用方案，然后以此为基础提出计算资源调整方案并分析竞争比；3）针对失效恢复，分别从全局和局部视角设计资源调整方案并对比分析优劣。通过本项目的研究，不仅能面向容错需求得出优化可延展并行任务调度性能的方法，也能在理论层面上获得对近似调度算法的新认知，从而为我们构建高效、鲁棒的计算机系统奠定基础。

本项目研究形成了面向容错需求调度可延展并行任务的关键模型与算法。考虑到实际的云计算系统，研究涉及到了多种不同的任务模型和多个任务调度目标，在不同场景设定下均提出了有效的调度算法。本研究工作在增强可靠性的基础上可提高系统资源利用率或改善任务执行之间的公平性。研究成果未来可应用于规模化云计算平台。.在不考虑失效的前提下，首先针对一组任务研究最小化系统开销问题。当任务同构时，我们分别设计了最优的离线任务调度算法和近似比为2的在线任务调度算法；当任务异构时，设计了一个5倍近似比的离线调度算法。其次，本项目针对并行任务的调度公平性从资源划分的角度进行了定义，分别在两个不同的设定下，即任务可无限延展和不可无限延展，分析了构造的公平模型可满足帕累托最优，Envy-freeness，Strategy-proofness, 和Sharing incentive。同时，我们设计了以公平为调度目标的多个调度算法并通过理论分析和实验获得了算法性能评价。.针对失效场景，本项目设计了备份放置方案和资源调整方案并分析近似比。本项目首先利用复本技术实现容错，然后针对调度在线并行任务，以减少系统资源浪费为目标，提出了三个在线调度算法，mirroring, shifting和mixing，并进行了近似比分析。其中mirroring算法会导致系统资源严重浪费，shifting算法对在线任务不友好，而mixing可以平缓的增加对系统资源的需求，对在线任务最友好。.针对失效恢复，分别从全局和局部视角设计资源调整方案并对比分析优劣。项目在容错设计的基础之上，首先用参数f设定系统的容错能力，当系统发生失效且失效数量没有超出系统容错能力时，启动容错恢复。项目分别从mirroring, shifting和mixing，三种调度算法出发，设计了将系统恢复至正常状态的算法，保持系统的容错能力，从而有效的应对未来可能发生的失效。