异构分布式系统中能量感知的并行应用调度算法研究

作     者：叶婷 

作者单位：湖南大学 

学位级别：硕士

导师姓名：全哲

授予年度：2019年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070105[理学-运筹学与控制论] 081201[工学-计算机系统结构] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：异构系统 能耗 并行应用 任务调度 调度长度 可靠性 

摘      要：处理器上能量感知的任务调度一直是计算机系统(例如,异构分布式计算系统)中的热门话题。给定一个包含N个任务n,n,...,n的应用G,以及一个包含处理器集合U=u,u,...,u的计算系统,能耗感知的任务调度通常是指为应用中的每个任务n找到合适的处理器和处理频率,以确保所有任务都能被有效的完成,同时能够优化系统能耗,保证应用执行的整个过程中消耗的能量在控制范围内。围绕绿色计算的主题,本文的主要目标是研究在异构分布式计算系统中,对于考虑任务优先级的并行应用,如何在有能耗约束的前提下最小化应用的调度长度。本文中调度长度是指从启动第一个任务开始到完成最后一个任务之间的时间间隔。对于此问题,现有工作采用的策略是预先为每个未调度的任务分配其最小能耗以满足能耗限制,然后使用启发式算法最小化调度长度。然而,我们通过分析发现,这种预分配策略可能会使调度结果对任务优先级敏感,优先级低的任务在调度时不能得到足够的能量资源,并因此导致最终的调度长度不够乐观。基于此,本文提出了一个新的任务调度算法ISAECC,该算法设计了一种基于权重的分配机制来为任务预分配能耗,最大程度减小因能耗分配不公平对调度结果的影响,并提供了严格的数学证明来验证其可行性。本文基于两个真实的并行应用做了多组实验,和多个传统优秀算法进行对比,结果一致表明,本文提出的算法有更好的性能。除此之外,本文从能耗约束的并行应用调度长度最小化问题出发,基于解决此问题的基本思想进行扩展,又研究了另外两个能量感知的调度问题:(1)在异构分布式系统中,对于有任务优先级约束的并行应用,考虑在有能耗约束的前提下,最大化其可靠性。本文中可靠性是指系统在执行应用的过程中不发生故障的概率。受最小化调度长度问题启发,本文通过将此问题分解为两个子问题来解决,并提出ISAECC*算法;(2)在异构分布式系统中,对于有任务优先级约束的并行应用,同时考虑应用的截止时间约束和能耗约束,最大化可靠性。本文提出MRDECC算法来解决此问题,将其分为两个阶段,先利用ISAECC算法最小化调度长度,在此基础上为最大化可靠性对任务进行重新分配。针对上面两个扩展问题,本文分别给出了充分的实验来证明所提方法的有效性。