论文部分内容阅读
从嵌入式设备到大型数据中心都已经广泛采用异构分布式系统架构。随着系统集成度和性能的提高,能耗逐渐增大并已成为系统设计的主要瓶颈。因此,需要通过有效的能量管理(包括能量约束与高能效两个方面)技术来协调能量的使用。动态电压与频率调节(DVFS)技术通过同时缩小处理器的电源电压和频率来调节能量消耗,已成为一项重要的能量管理技术。本文对异构分布式系统中面向能量管理的并行应用调度算法展开研究:从通用的异构分布式系统入手,研究在能量约束条件下,并行应用的性能和可靠性优化问题;并以此为基础,拓展到异构分布式嵌入式系统,研究满足不同约束条件的高能效调度与优化问题。本文的主要工作和创新点概括为以下几个方面:1、研究能量约束并行应用的高性能调度,解决异构分布式系统上能量约束并行应用的调度长度最小化的问题。这个问题在本文中被分解为两个子问题,即满足能量约束和调度长度最小化。本文提出了具有能量约束的最小调度长度(MSLECC)算法,首先,通过将未分配任务预先分配给具有最小能耗的处理器,将应用的能量约束转移到每个任务的能量约束,解决了满足能量约束的问题;然后,通过以低时间复杂度来启发式地调度每个任务,并选择EFT最小的处理器和频率组合来解决第二个子问题;最后采用真实的并行应用实例进行实验,结果表明,与经典的HEFT和ECS算法相比,本文所提出的MSLECC算法不仅使得应用的实际能量值满足给定的能量约束,而且其调度长度更短。2、研究能量约束并行应用的可靠性增强调度,解决最大限度地提高异构分布式系统中能量约束并行应用的可靠性的问题。该问题在本文中分解为两个子问题:满足能量约束和最大化可靠性。本文提出了具有能量约束的最大化可靠性(MREC)算法,首先,通过将应用的能量约束转移到每个任务的能量约束来解决第一个子问题;然后,通过考虑在任务分配之前确定每个任务的能量,并选择具有最大可靠性值的处理器和频率组合来解决可靠性最大化问题,同时满足其能量约束;最后,采用真实的并行应用实例进行实验,结果表明,与优秀的RMEC算法相比,本文所提出的MREC算法不仅实际能量值满足给定的能量约束,而且具有更高的可靠性值。3、研究实时并行应用的高能效调度,解决异构分布式系统中实时并行应用的能耗最小化问题。首先,提出截止期限松弛算法,该算法引入截止期限松弛的概念,从而实现在不使用DVFS情况下的具有最小动态能耗的高效任务分配,同时尽可能满足任务的截止期限约束。其次,提出非DVFS高能效调度(NDES)算法,该算法引入可变截止期限松弛的概念,通过反复调用截止期限松弛算法以保证满足应用的截止期限,从而实现降低能耗。再次,进一步提出全局DVFS高能效调度(GDES)算法,该算法在满足任务之间的优先级约束和应用截止期限约束的条件下,将任务迁移到产生最小动态能耗的处理器松弛中。最后,通过模拟实验和真实平台进行验证,结果表明本文所提出的NDES和GDES组合算法(NDES&GDES算法),能够比当前最优的高能效调度算法节省更多的能量。4、研究可靠并行应用的高能效容错调度,解决异构分布式嵌入式系统中可靠并行应用的高能效调度和高能效容错调度问题。首先,提出了一种非容错的满足可靠性目标的高能效调度(ESRG)算法,以降低能耗,同时满足基于DAG的异构嵌入式系统并行应用的可靠性目标。其次,考虑到使用ESRG如果可靠性目标超过一定的阈值,应用的可靠性目标是不可达的,因此进一步提出了一种满足可靠性目标的高能容错调度(EFSRG)算法,使用容错的机制保证应用的可靠性目标可达。最后,在不同应用规模上对实际并行应用进行了实验,包括快速傅立叶变换和高斯消元。实验结果表明,本文所提出的EFSRG算法降低的能耗高于其他方法在同等规模条件下降低的能耗。