异构分布式系统中基于DVS的节能调度算法研究与实现

摘要

随着信息技术的发展，异构分布式计算机系统以其低成本、高效率的特点得到人们的广泛关注。在异构分布式计算机系统的研究过程中，任务调度算法决定了并行程序是否能够充分利用系统中的计算资源在最短时间内完成任务的执行。同时，随着硬件技术的进步处理器能耗问题日益凸显。除了进一步改进硬件外，好的任务调度算法应当在保证调度时效性的同时兼顾对系统能耗的优化。
　　 针对任务调度问题，目前研究者已经提出了各种有效算法，如基于表的调度算法、基于复制的调度算法以及基于随机搜索的遗传算法等。这些算法特点各异，分别在特定情况下均可以得到近似最小化的程序调度时间。同时，动态电源管理技术(Dynamic Power Management，DPM)、动态电压/频率调节技术等低功耗技术(Dynamic Voltage/Frequency Scaling，DVS/DVFS)的广泛使用也使得任务调度算法在系统能耗优化上的表现越来越好。
　　 本文在相对复杂的能耗模型下，专注于动态电压/频率调节技术在调度算法中的使用细节，通过优化目的电压等级的选取策略和电压调节过后可用空闲时间的再利用，进一步提高算法的能耗优化性能。
　　 通过研究处理器电压转换的转换能耗和转换后任务处理中的能耗节省量二者之间的关系，本文在已有调度算法的基础上提出了一种基于动态电压/频率调节技术的单一任务单元能耗优化算法(Single Task Unit-Dynamic Voltage Scaling，STU-DVS)，该算法既保证了调度时效性，又通过优化目的电压等级的选取策略来降低系统能耗。实验结果表明在不同系统及并行程序的情况下，STU-DVS算法较其它对比算法的能耗优化性能获得了一定程度的提高。
　　 通过研究调度过程中可用空闲时间的利用，本文在STU-DVS算法的基础之上提出了时隙再利用能耗优化算法(Time Slot Reuse-Dynamic Voltage Scaling，TSR-DVS)，该算法通过可用空闲时间的收集和利用，扩大了动态电压/频率调节技术的使用空间，进一步降低系统能耗。实验结果表明，空闲时间利用率的提升使得TSR-DVS算法能耗优化性能进一步提高。

目录

声明

摘要

插图索引

附表索引

第1章 绪论

1．1 研究背景

1．1．1 分布式计算机系统

1．1．2 任务调度

1．1．3 能耗问题

1．2 研究现状

1．2．1 任务调度算法研究现状

1．2．2 低功耗技术的研究现状

1．3 主要研究内容

1．4 本文内容结构

第2章 相关理论知识概述

2．1 异构分布式计算机系统模型

2．2 并行程序的DAG模型

2．3 调度过程基本属性

2．4 典型调度算法

2．5 典型低功耗技术

2．6 常见调度方案

2．7 小结

第3章 基于DVS的单一任务单元能耗优化调度算法

3．1 引言

3．2 问题具体分析

3．3 改进算法的实现

3．4 实验分析

3．4．1 示例DAG图

3．4．2 随机产生的DAG图

3．5 小结

第4章 基于DVS的时隙再利用能耗优化调度算法

4．1 引言

4．2 问题具体分析

4．3 TSR-DVS算法的原理和实现

4．4 实验分析

4．4．1 示例DAG图

4．4．2 随机产生的DAG图

4．5 小结

结论

参考文献

致谢

附录A 攻读学位期间所发表的学术论文和参加的项目