论文部分内容阅读
随着大规模科学计算应用的普及以及并行数据处理规模的不断增大,以网格和并行计算为基础的分布计算系统已成为信息技术和通信技术的重要发展方向,尤其是通过互联网络将大量廉价、处理能力和可靠性等都相互异构的计算单元进行连接所构成的数据存储和计算平台受到学术界和工业界的广泛关注。异构分布计算平台也成为中国战略性新兴产业的重要组成部分,其中系统性能和可靠性优化问题已成为国内外研究的热点。但是系统和应用规模逐渐增大的同时,并行应用对系统长期可靠运行的时间需求也越来越高。此外,由于异构系统下计算资源的动态加入和退出,并行应用程序输入参数的变化以及异构系统环境等因素将引起并行应用程序的执行出现不确定性和不可控性等安全威胁。因此,各并行任务能否可靠地运行是评价分布计算系统优劣的关键指标之一。尤其当异构分布计算系统在时间和空间维度存在关联失效背景下,如何分析系统可靠性以及通过任务调度对并行应用程序执行过程的可靠性进行优化等问题。本文首先从系统可靠性分析理论入手,重点解决关联失效模式下异构分布计算系统可靠性度量和优化方法,并在分布计算系统资源管理和任务分配等方面展开深入研究和探索,提出考虑性能和可靠性开销、具有截止时间约束以及计算资源存在关联失效等条件下的任务调度理论和可靠性优化方法,旨在解决异构分布计算系统可靠性领域的部分关键技术问题。本文的主要研究工作和贡献包括:(1)扩展现有分布计算系统可靠性分析方法,提出关联失效模式下异构分布计算系统可靠性评估方法。目前的异构分布计算系统存在大规模资源共享、广域通信以及多资源合作,而很多传统可靠性分析方法都建立在计算资源间的失效是相互独立的假设基础之上,没有考虑计算资源在时间和空间维度上可能存在的关联失效,尤其随着纳米级大规模集成电路的快速发展,高能电磁辐射引起计算节点关联失效的概率越来越大。根据分布计算系统资源的失效特征建立系统失效模型,提出关联失效模式下基于泰勒展开式的计算系统可靠性度量方法,并从系统结构角度分析共因失效对系统可靠性的影响程度,通过仿真实验验证影响系统可靠度和平均无故障时间的主要因素。在此基础上,进一步提出冗余系统和静态失效系统可靠性分析方法,并通过仿真实验验证算法的性能和有效性。(2)针对资源存在异构性、动态性和广域分布性等特点的大规模分布计算系统,提出基于任务期望执行时间和可靠性开销的表调度算法。分析任意架构网络模型(APN)下关联任务之间最可靠通信链路的选择问题,并提出考虑可靠性开销的最优路径选择算法(OCPR)。在此基础上通过添加具有预测功能的分布计算节点选择策略,以及考虑系统异构性和可靠性开销的任务优先级计算方法,设计分布计算系统环境下可靠性驱动的任务调度算法(RDLS)。仿真实验结果表明所提算法在相同时间复杂度条件下,相对于经典的HEFT和RASD算法具有更优的调度性能和可靠性指标。(3)针对实际分布计算系统运行过程中所收集的开源失效数据集FTA,从时间和空间角度对计算资源的关联失效进行建模,其中空间角度又分为物理空间关联失效和逻辑空间关联失效两种失效模型,并利用马尔科夫随机场和Gibbs分布之间存在的等价理论对所提出的关联失效模型进行理论分析和形式化建模。对关联失效进行建模的目的是将分布计算系统内的节点进行关联组划分,每个组内的计算节点具有强关联性,从而为选择冗余节点来提高任务执行可靠性提供依据,避免选择同-关联失效组内的多个计算节点作为同一任务的副本计算节点。通过理论分析和实验验证了所提关联失效模型的有效性和可行性。(4)针对计算资源存在关联失效的分布计算系统和具有截止时间约束的并行DAG应用程序,提出基于任务截止时间划分的关键路径模型和子任务截止时间分配算法(SDA)。在此基础上,进一步提出基于可靠性驱动的贪心任务复制算法(RDGD)和基于费用驱动的任务复制算法(CDD),在选择复本资源进行任务分配以提高应用程序执行可靠性时,避免同一个子任务分配给具有关联失效特性的计算节点集合内的多个节点,以最大化子任务执行结果的可靠性。实验结果显示基于截止时间划分的关键路径和基于不同目标的可靠性优化调度算法不仅能够提高并行应用程序执行的可靠性,同时又能满足并行应用程序调度性能的需求。