异构系统中处理器可靠性和能耗感知的调度算法研究

摘要

随着芯片技术的不断进步，计算系统的发展呈现异构、大规模、高性能等特点。异构的高性能计算系统为科学计算、工程应用等众多领域提供了一个很好的大规模计算解决方案，同时也在不断地为人们的日常生活带来便利。然而高性能计算伴随着更多的能源消耗，其中的低功耗问题和可靠性问题一直研究中的重点和难点。本文将围绕绿色计算这一主题，重点展开异构系统计算过程中的能耗管理、可靠性管理、成本预算下性能最大化等问题的研究。具体来说，本文的主要工作和贡献概括为以下四个方面：
　　1.在有能量预算前提下，开展基于异构系统中有优先约束关系的任务集(记为DAG)的可靠性感知的任务调度算法研究。传统的COMS功耗模型的不足在于其不能准确反映处理器的功率消耗与处理器执行频率之间的关系。为此，本文中采用更具说服力的能耗模型及可靠性模型，以量化采用动态电压频率调节(DVFS)技术后对处理器在执行任务过程中瞬态故障的影响。在有能量预算的前提下，使得有优先约束关系的任务在异构计算系统中执行的过程中系统运行的可靠性最大化。本文提出了三个低时间复杂度、有可靠性意识的启发式算法(分别记为RHEFT、RCPOP和RMEC)。并通过组合11种不同的通信计算比值(记为CCR)，不同的异构处理器数量，分别对不同的节点数量的随机的和真实世界的DAG任务图进行测试。与另外两个优秀的有可靠性意识的算法的对比实验表明，RHEFT、RCPOP和RMEC在有能量预算的约束下，DAG任务图在异构计算系统中的调度在系统的可靠性加强方面有着明显的加强。
　　2.在 DAG任务图存在共享时限约束的前提下，采用共享恢复技术，开展基于异构计算系统中系统可靠性加强的研究。鉴于处理器的瞬态故障的发生率远大于永久故障这一事实，针对DAG任务图在共享的时限约束的前提下，本文采用DVFS技术解决能量节约问题和使用共享恢复技术来解决任务调度中出现的瞬态故障，并提出了三个使用共享恢复技术的可靠性加强和能量节约联合优化的启发式算法(分别记为SHRHEF、SHRCPOP、SHRMEC)。通过组合不同的通信计算比值、不同的处理器数量等进行配置，并对多组随机的和特定的任务图进行多次测试。实验结果表明，在满足条件约束的情况下，即使发生瞬时故障，提出的三个算法依然能保证系统仍然以较高的可靠性和较低的能耗完成任务集的执行。
　　3.开展基于异构计算系统中 DAG任务集运行过程中高系统可靠性和低能量消耗的双目标优化研究。按需收费的模式要求数据中心能提供给用户多种选择。针对有优先约束关系的任务集，在其存在共享截止时间的前提下，本文研究其在执行的过程中获得较高的可靠性和消耗较低的能量的双目标优化问题。为此，提出的BOGA算法，在初始化种群时采用经典的算法生成优先任务队列，使用单点交叉保证任务集在满足优先约束的前提下产生新的优先任务队列，使用帕累托占优评价两个解质量的好坏，采用快速非支配排序对搜索的解集合进行等级划分，为算法进入下一次迭代中，从种群中挑选出更好的优质的解创造条件。最后在jMetal框架中实现BOGA算法，并使用三种真实的并行任务图进行测试，对比实验表明，BOGA可以获得更好的帕累托前沿。
　　4.在考虑处理器电压切换开销的前提下，基于高性能嵌入式系统，开展执行时间服从统计分布的低功耗任务调度研究。针对很多能量敏感的高性能设备，当采用DVFS技术进行能耗管理时，处理器在进行电压切换时产生的开销将不可以简单地忽略。为此，本文针对执行时间服从统计分布的独立任务集，分别基于高性能的单核处理器和多核处理器，提出能量感知的OUET、UDPSM节能调度算法。对算法的评价中，分别使用执行时间服从均匀分布、高斯分布、指数分布等benchmark进行测试，OUET、UPDSM与没有考虑切换开销的算法相比，无论在能量节约方面还是在任务截止时间的错失率方面，都展示了更好的性能。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪 论

1.1 并行分布式系统概述

1.2 课题研究背景及意义

1.3 本文的主要工作

1.4 论文组织框架

第2章 异构计算系统任务调度研究

2.1 引言

2.2 经典的研究方法

2.3 算法评估

2.4 本章小结

第3章 基于能量约束的可靠性加强研究

3.1 引言

3.2 相关工作

3.3 准备工作

3.4 实例分析

3.5 算法设计

3.6 实验和算法评价

3.7 本章小结

第4章 基于Recovery技术的可靠性加强研究

4.1 引言

4.2 相关工作

4.3 系统模型

4.4 实例分析

4.5 算法设计

4.6 实验和算法评价

4.7 本章小结

第5章 考虑可靠性与能耗的双目标调度算法

5.1 引言

5.2 相关研究

5.3 准备工作

5.4 问题描述

5.5 算法设计

5.6 实验和算法评价

5.7 本章小结

第6章 考虑切换开销的节能调度

6.1 引言

6.2 相关研究

6.3 系统模型

6.4 实例分析

6.5 算法设计

6.6 实验分析

6.7 本章小结

结论

1. 本文工作总结

2. 研究展望

参考文献

附录A 攻读博士学位期间已发表与待发表的论文

附录B 攻读博士学位期间参与的科研项目

致谢