异构并行分布式系统可信调度理论与方法研究

发布时间：2018-04-03 17:28

本文选题：并行分布式系统　切入点：任务调度　出处：《湖南大学》2013年博士论文

【摘要】：随着社会经济与信息技术的飞速发展,以网络计算和并行计算为基础的分布式计算已成为IT技术的重要发展方向,特别是异构并行分布式系统因其低成本高性能而受到企业界和学术界的广泛关注。但系统规模持续扩大的同时,系统平均无故障时间却越来越低,任务执行行为可靠性已成为保证并行应用成功的关键。其次,分布式系统为实现信息保密性、数据完整性和边界安全保护而面临大量安全威胁,这些威胁主要源于网络环境下资源与用户行为的不可控性和不确定性。另一方面,并行应用实践表明任务实际执行时间往往受输入数据、系统环境和任务本身If分支的影响而具有随机性。面对由可靠性、安全性、任务计算量随机性等导致的分布式系统可信性,提出了考虑可信性的任务调度理论与方法,以期对对提高分布式系统应用性能具有重要意义的资源管理展开深入研究与探索,力图解决其中的部分关键理论与技术问题。本文首先建立由任务DAG模型构建器、任务计算量评估、任务调度器、任务分配、信任管理、信任值计算、可靠性分析、安全开销计算、任务可信评估等模块构成的可信调度体系结构。针对异构计算系统任务在不同处理机上执行时其计算成本不同的特点,克服以任务执行平均值、中间值、最好值或最坏值等方法给任务调度带来的困惑,提出异构计算系统计算能力异构因子α,并依此实现任务优先级计算和处理机选择。在此基础上,提出基于任务复制的表调度算法(HEFD)。模拟实验结果表明任务调度算法HEFD优于HEFT、HLD和HCPFD算法。其次,针对大规模分布式计算系统的异构性、动态性和广域性等特点,提出可靠性驱动的层次调度体系。分析任务在处理机上执行的可靠性、数据在通信网络上通信的可靠性及相互关系,建立应用程序任务执行行为可靠性模型。在此基础上提出可靠性驱动的分层任务调度算法(HRDS)。其中,全局任务调度器负责把应用程序分配给虚拟节点,局部调度器则在虚拟节点内实现基于DAG模型的任务调度与分配。实验结果表明相对于经典调度算法MCMS和HEFT,HRDS具有较好的性能。针对分布式计算系统面临的安全威胁,受经济学品牌形象实践与心理学理论启发,在研究分布式信任表现形式与特点基础上提出基于博弈论微分对策技术的信任值动态量化计算方法。依据用户任务安全需求和分布式系统提供的安全信任保障,提出任务执行行为安全性开销计算方法和安全性风险评估技术。最后,提出考虑任务执行行为安全开销的调度模型和调度算法SDS。实验结果表明SDS算法不仅能有效提高系统安全性,还具有较好的调度性能。经典任务调度算法一般假定任务计算量通过软件工程配置技术或预测技术获得,且是确定不变值。而并行应用计算实践却表明任务计算量具有随机性,这种不精确性将明显影响调度算法性能。因而针对此问题,本文首先证明基于DAG模型随机任务调度长度的下限是以任务期望构成的确定型任务调度长度。然后,研究任务计算量服从正态分布的应用程序,利用Clark方程实现并行任务完成时间期望与方差的计算,在此基础上提出随机sb_level近似计算算法。受确定型表调度算法DLS启发,提出针对随机任务调度问题的随机动态级调度算法(SDLS)。实验结果表明随机动态级调度算法具有较好的调度性能。
[Abstract]:With the rapid development of social economy and information technology , distributed computing based on network computing and parallel computing has become the important development direction of IT technology , especially heterogeneous parallel distributed system , which is the key to guarantee the success of concurrent application .

This paper first establishes a trusted scheduling architecture consisting of task DAG model builder , task computation quantity evaluation , task scheduler , task assignment , trust management , trust value calculation , reliability analysis , security cost calculation , task confidence assessment , etc .

Secondly , based on the characteristics of heterogeneous , dynamic and wide - domain characteristics of large - scale distributed computing systems , a hierarchical scheduling system of reliability driven is proposed . The reliability and mutual relation of communication between tasks on the communication network are analyzed , and the reliability model of the application task execution behavior is established . The task scheduling and allocation based on DAG model are realized in the virtual nodes . The results show that the performance of the distributed computing system is better than the classical scheduling algorithm MCMS and HEFT .

In view of the security threats faced by distributed computing systems , inspired by economics brand image practice and psychology theory , a dynamic quantitative method based on game theory differential game technique is proposed based on the research of distributed trust expression and characteristics . Finally , a scheduling model and a scheduling algorithm SDS are presented . The results show that the SDS algorithm not only can effectively improve the system security , but also has better scheduling performance .

The classical task scheduling algorithm generally assumes that the task computation amount is obtained by software engineering configuration technology or prediction technology , and is a fixed value .

【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP338.8

【参考文献】