并行分布式系统中的节能调度策略与算法研究

发布时间：2020-05-29 23:01

【摘要】：从计算机诞生之日起,人们便对计算能力开始了无止境的追求,这就一直驱使着计算机系统的发展。过去的解决方案是不断提高CPU的主频来加快处理器的处理速度。然而当物理元器件的性能达到极限时,为了进一步获得更高的处理速度和计算能力,开始出现多CPU计算系统。同多CPU计算系统一起发展的,还有通过通信网络将多个独立的计算资源(包括超级计算机、个人PC、嵌入式系统、数据源、仪器等)连接而组成的逻辑上和物理上分布的高性能协同分布式系统,被称为分布式计算系统。处理器主频快速提高,系统规模急剧增大,使得系统的功耗和能耗也急剧增长。无论是嵌入式系统、并行分布式系统以及集群系统,能耗问题都已成了制约其发展的重大问题。因此如何降低系统能耗,已为亟须解决的重要问题之一。本论文的研究工作主要针对单处理器实时系统、并行分布式系统和云计算系统下存在的能耗问题。针对不同系统下任务的不同特点及调度的不同性能目标,结合低功耗技术,设计不同系统下任务的节能调度策略,实现系统的高效能计算。本文首先针对实时单处理器系统中高功耗问题,提出了基于动态电压/主频调节的伪周期任务节能调度算法CC-DVSST。动态电压/主频调节(DVFS)技术是计算机系统中节能并延长电池使用的一项主要技术。在传统单处理器节能调度中,处理器的主频调节必须基于任务的先验信息,例如任务周期,最坏完成时间(WCET)等等。但是在对伪周期任务进行实际执行时,其相邻任务的到达时间间隔各不相同且总是大于给定的任务周期。同时任务在每个周期的实际执行时间总小于任务的先验最坏执行时间,因此任务的实际总负载要远远小于预测总负载,所需的计算能力小于预测所需的计算能力。CC-DVSST调度算法基于实际负载与预测负载之差对系统的实际负载进行实时计算更新,并动态地对处理器的主频进行调节。文中给定了系统主频调节的时间并给出了目标主频的计算方法。根据实时性证明可知,采用本文的主频调节策略,系统所有任务的实时性都能满足。仿真实验结果也表明,提出的算法能有效降低嵌入式系统的能耗。基于复制的调度算法是并行分布式系统中针对DAG任务的一种有效调度算法。但是,由于复制策略的采用,每个任务被执行多次,导致大量的资源浪费和能耗开销。针对并行分布式计算系统DAG任务调度存在的能耗问题,提出了基于复制的冗余副本删除节能优化调度算法EADS。文中首先分析了基于复制的调度算法中存在副本冗余的问题,然后详细描述了调度冗余副本判定的条件。设计了任务优先级逆序查找方法,按从出结点向入结点的顺序对任务调度中的冗余副本进行查找及删除,在保证基于复制调度算法的高性能的同时降低冗余副本的能耗开销。由于DAG调度算法的贪婪特性,每个任务都被分配到使其最早完成的处理器上,并且尽可能的通过复制关键前驱任务使其完成时间提前。但是,根据分析可知,某些任务的复制只能减小任务的局部完成时间而非整体完成时间。因此延迟某些任务的执行不影响任务的整体性能,但能减少任务的副本数。针对并行分布式计算系统下由于基于复制的DAG任务调度算法的贪婪性而导致的任务调度副本过多的问题,首先提出了基于复制的反馈式任务冗余副本动态删除调度算法(RADS)。然后针对产生的复制调度提出了进一步的优化策略FOS,通过分析任务非关键前驱任务可延迟的特性,介绍了将非冗余副本转化为冗余副本的三个步骤。通过对任务纵向及横向迁移过程中,搜索并删除产生的冗余副本,使得在保证调度性能的同时降低系统的能耗开销。实验结果表明提出的算法相比较已有的复制调度算法具有明显的节能效果。最后针对云计算环境下,传统云平台配置方式使得其计算能力不能适应动态变化任务负载,从而导致服务质量低或者资源冗余和能耗浪费的问题,提出了一种新的资源管理和任务调度策略。在该策略中,云服务商采用资源长期租用和短期租用相结合的方式配置其服务平台,该服务模型被建模为M/M/c+D的排队模型。采用该服务模型,能保证所有任务的服务质量并避免了资源和能耗浪费的问题。基于M/M/c+D排队模型,文中对影响云服务商利润的各项参数,如能耗,固定费用,额外费用等进行分析,并建立了云计算利润最优化模型。文中结合偏导法和二分查找法对该利润最优化问题进行求解,获得在理想连续变量和实际离散变量两种情况下的云平台的最优配置。通过与已有云平台配置方法比较,可知该方案从能耗、利润和服务质量三方面都优于对比算法。
【学位授予单位】：湖南大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP301.6;TP332

【参考文献】